13
\$\begingroup\$

(There exists some challenges that require to use the best strategy, but here we don't. Even if you are able to win, you are allowed to make a tie)

Challenge

Write a program which plays the game tic-tac-toe. It must not lose (therefore, it should end the game either with a tie or by winning).

Allowed I/O methods

  1. Input may be the current board. You can assume that all previous moves of the 2nd player were played by your engine.
  2. Input may be the first player's moves, and your function stores which moves happened in the past. In this case the function is called multiple times, once for each move; or the function/program prompt input for multiple times.
  3. You are allowed to take an extra input saying if you are the first player, or write two (possibly related) functions to solve the first-player problem and the second-player one. If your program need use the input method 2 (multiple call), you can decide what is passed in the first call.
  4. Output may be the board after your turn.
  5. Output may be your move.
  6. A move may be represented as a pair of numbers (can be 0-indexing or 1-indexing), a number in range 0~8, or a number in range 1~9.
  7. The board may be represented as a 3×3 array, or an array of length 9. Even if the language have 0-indexing array, you can use 1-indexing.
  8. The cells on the grid may use any 3 different values to indicate X, O and empty.

Winning criteria

Shortest code in each language win.

\$\endgroup\$
  • \$\begingroup\$ If a losing is given to you then your solution is invalid. You are playing with other, so the chessboard won't instantly change, so we can assume that all previous moves of the 2nd player were also played by our engine \$\endgroup\$ – l4m2 Dec 29 '17 at 13:17
  • 3
    \$\begingroup\$ xkcd.com/832 \$\endgroup\$ – totallyhuman Dec 29 '17 at 14:14
  • 1
    \$\begingroup\$ @l4m2 Just restart the interpreter. Done. Why bother with it? It just unnecessarily increase the byte count for nothing. \$\endgroup\$ – user202729 Dec 29 '17 at 14:15
  • 1
    \$\begingroup\$ As a reminder, you should not change the challenge in the comment. \$\endgroup\$ – user202729 Dec 29 '17 at 14:17
  • 4
    \$\begingroup\$ Don't do the bonus. Either require it or remove it, don't make it optional. The bonus ruins the challenge.. \$\endgroup\$ – Rɪᴋᴇʀ Dec 29 '17 at 21:06
5
\$\begingroup\$

Befunge, 181 168 bytes

>>4&5pp20555>>03>16p\::5g8%6p5v
 ^p5.:g605$_ #!<^_|#:-1g61+%8g<
543217539511|:_^#->#g0<>8+00p3+5%09638527419876
v<304p$_v#:->#$$:2`#3_:^
>#\3#13#<111v124236478689189378

Positions on the board are numbered 1 to 9. By default you get the first move, but if you want to allow the computer to go first, you can just enter 0 for your first move. When you've made a move, the computer will respond with a number indicating their move.

There are no checks to make sure you don't enter a valid move, and there also no checks to see if anyone has won or lost. Once their are no more moves to be made, the program just goes into an infinite loop.

It's a bit difficult to test this online, since there are no online interpreters with interactive input. However, if you know what moves you're going to make in advance (which assumes you know how the computer is going to respond), you can kind of test on TIO with those moves preprogrammed.

User plays first: Try it online!
Computer plays first: Try it online!

To makes it easier to see what's going on, I've also got a version that outputs the board between moves.

User plays first: Try it online!
Computer plays first: Try it online!

Note that you'll have to wait for TIO to timeout before you can see the results.

Explanation

The board is stored in the Befunge memory area as a flat array of 9 values, indexed from 1 to 9. This lets us use the zero offset as a special case "no move" when we want to let the computer play first. Player moves are stored as 4, and computer moves as 5. To start with all positions are initialised to 32 (the Befunge memory default), so whenever we access the board we mod with 8, so we'll get back either 0, 4 or 5.

Given that arrangement, if we sum the values of any three positions on the board, we know that the computer is one move away from winning if the total is 10, the player is one move away from winning if the total is 8, and the positions are shared between computer and player (but still one position is free) if the total is 9.

Our entire strategy is based around this concept. We have a routine that takes a list of triples indicating sets of three positions on the board, we calculate the sum of those positions, and if the sum equals a certain total, the computer moves to whichever of the positions in the set is free.

The main list of triples that we test are the winning combinations (1/2/3, 1/5/9, 1/4/7, etc.). We first look for a total of 10 (the computer is about to win), and then a total of 8 (the player is about to win and we need to block that move). Less obviously, we also check for a total of 9 (if the player and computer each have one of the positions, it's a good strategy for the computer to take the third).

Prior to that last scenario, the other strategic move we make is to check all the corner sets (1/2/4, 2/3/6, etc.) as well as two opposing corner combinations (1/8/9 and 3/7/8). If any of these combinations sum to 8, i.e. the player has taken two of the positions, it's a good strategy for the computer to take the remaining free position.

Finally, there are a two special case moves. First, we always try and take the center position before any other move. This is achieved with the same routine as all our other moves, just passing in a single triple, 5/5/5, and a target sum of 0. Additionally, if all other test have failed to find a move, we try to take one of the top corners as a last resort. Again this is simply achieved by testing the triples 1/1/1 and 3/3/3, with a target sum of 0.

I don't think this is necessarily a perfect strategy - there may be games that the computer draws which could potentially have been won - but it's good enough to never lose a match. I've run a test script that tried to play every possible move against the computer, and for every valid sequence of moves, the computer either won or drew the game.

\$\endgroup\$
  • \$\begingroup\$ I don't quite know Befunge, but maybe you can go test all possible input (Sample) \$\endgroup\$ – l4m2 Jan 5 '18 at 3:45
  • \$\begingroup\$ @l4m2 FYI, I have now run a test script that tried every possible move against the computer and can confirm that it never loses. \$\endgroup\$ – James Holderness Jan 10 '18 at 1:38
2
\$\begingroup\$

Python 2: 399 401 349 333 317 370 bytes

2x Bug Fix: credit to l4m2

-52 chars: credit to undergroundmonorail

-16 chars: credit to Jonathan Frech

-26 chars: credit to user202729

def f(b):
 t=4,9,2,3,5,7,8,1,6;n=lambda k:[t[i]for i,j in enumerate(b)if j==k];p,o,a,I=n(2),n(1),n(0),t.index
 for i in p:
    for j in p:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in o:
    for j in o:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in 9,3,7,1:
    if i in a and 5 in p:return I(i)
 for i in 5,4,2,8,6:
    if i in a:return I(i)
 return I(a[0])

Try it Online!

On the first day of a linear algebra course I took last semester, my astute graduate student instructor proposed that if you represent the tic-tac-toe board as the the matrix:

4 | 9 | 2
--+---+--
3 | 5 | 7
--+---+--
8 | 1 | 6

then getting three in a row is equivalent to picking three numbers in the range [1,9] that add up to 15. This answer exploits this idea. The function takes a list containing nine numbers representing the board. 0 indicates an empty space, 1 is occupied by the opponent, and 2 represents a previous play made by the program. The first 3 lines figure out what numbers the program has picked (p), the opposition has picked (o), and are still available (a). It then looks through the available numbers and sees if any of them, combined with two numbers it has already picked add to fifteen. If it does, it will pick that square and win. If there are no immediate winning moves, it will check to see if the opponent can win using the same method. If they can, it will take their winning square. If there is neither a winning nor blocking move available, it will move in a corner. This prevents a fools mate:

- - - 
- X -
- - -

- O -             # Bad Move
- X -
- - -

- O X
- X -
- - -

- O X
- X -
O - -

- O X
- X -
O - X

If none of these situations occur, it will choose a square arbitrarily. The function outputs a number [0,8] representing the 0 indexed square chosen by the algorithm.

Edit: The algorithm now prioritizes the center over the diagonal, which will prevent another fools mate possibility pointed out by l4m2 and related strategies.

Edit: To clarify, the function takes in a board in the form of an array and outputs a move as an integer on [0,8]. Because this I/O strategy is so clunky , here's a wrapper script that makes it more interactive. It takes a single command line argument, which should be 1 if the player goes first, and 0 if the program goes first.

import sys

def f(b):
 t=4,9,2,3,5,7,8,1,6;n=lambda k:[t[i]for i,j in enumerate(b)if j==k];p,o,a,I=n(2),n(1),n(0),t.index
 for i in p:
    for j in p:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in o:
    for j in o:
     for k in a:
        if i+j+k==15and-j+i:return I(k)
 for i in 9,3,7,1:
    if i in a and 5 in p:return I(i)
     for i in 5,4,2,8,6:
        if i in a:return I(i)
 return I(a[0])

board = [0,0,0,0,0,0,0,0,0]
rep = {0:"-",1:"X",2:"O"}

turn = int(sys.argv[1])
while True:
    for i in range(3):
        print rep[board[i*3]]+" "+rep[board[i*3+1]]+" "+rep[board[i*3+2]]
        print
    if turn:
        move = int(raw_input("Enter Move [0-8]: "))
    else:
        move = f(board)
    board[move] = turn+1
    turn = (turn+1)%2 
\$\endgroup\$
  • 1
    \$\begingroup\$ Hacked \$\endgroup\$ – l4m2 Dec 31 '17 at 6:49
  • 1
    \$\begingroup\$ All your return lines except the last one can be put on the line before them, saving whitespace \$\endgroup\$ – undergroundmonorail Dec 31 '17 at 7:05
  • 1
    \$\begingroup\$ Also I can't help but wonder if it would save bytes to, instead of doing e=enumerate, do f=lambda n:[t[i]for i,j in enumerate(b)if j==n] and assign p, o and a using the function. Haven't counted it though \$\endgroup\$ – undergroundmonorail Dec 31 '17 at 7:07
  • 3
    \$\begingroup\$ Still hacked. xkcd.com/832 really helps \$\endgroup\$ – l4m2 Dec 31 '17 at 10:00
  • 2
    \$\begingroup\$ Hacked 3 \$\endgroup\$ – l4m2 Jan 1 '18 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.