Play tic-tac-toe and never lose

14

(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.

l4m2

Posted 2017-12-29T07:59:04.153

Reputation: 5 985

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 – l4m2 – 2017-12-29T13:17:04.913

Why the In this case you can have a reset function or reset when the game is over part is removed? Function need to be called for multiple times, don't it? – l4m2 – 2017-12-29T13:20:02.347

3https://xkcd.com/832/ – totallyhuman – 2017-12-29T14:14:04.587

1@l4m2 Just restart the interpreter. Done. Why bother with it? It just unnecessarily increase the byte count for nothing. – user202729 – 2017-12-29T14:15:07.457

1

As a reminder, you should not change the challenge in the comment.

– user202729 – 2017-12-29T14:17:15.917

'll change the problem when change is decided. Pure explanation that also exist in the problem doesn't lead to editing prob, either – l4m2 – 2017-12-29T15:11:20.373

Is it acceptable to provide an interactive program that repeatedly prompts the player for their move, each time outputting the program's counter move in response? I think that is the intent of option 2 of the allowed I/O, but it isn't entirely clear to me. – James Holderness – 2017-12-29T16:38:44.480

@James Holderness Yes you can. The original contain doesn't say "call for multiple times", and someone changed it. – l4m2 – 2017-12-29T18:20:01.687

4Don't do the bonus. Either require it or remove it, don't make it optional. The bonus ruins the challenge.. – Rɪᴋᴇʀ – 2017-12-29T21:06:34.803

@Bruce Forte The program uses best stragety, but the other player may not – l4m2 – 2017-12-30T03:20:24.223

I guess that's what bonus do. I change it into "need to handle both, but can be two function " – l4m2 – 2017-12-31T03:06:19.320

Answers

4

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.

James Holderness

Posted 2017-12-29T07:59:04.153

Reputation: 8 298

I don't quite know Befunge, but maybe you can go test all possible input (Sample)

– l4m2 – 2018-01-05T03:45:47.230

@l4m2 FYI, I have now run a test script that tried every possible move against the computer and can confirm that it never loses. – James Holderness – 2018-01-10T01:38:43.883

2

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 

Zachary Cotton

Posted 2017-12-29T07:59:04.153

Reputation: 679

1Hacked – l4m2 – 2017-12-31T06:49:53.337

1All your return lines except the last one can be put on the line before them, saving whitespace – undergroundmonorail – 2017-12-31T07:05:56.760

1Also 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 – undergroundmonorail – 2017-12-31T07:07:43.330

1333 bytes. – Jonathan Frech – 2017-12-31T07:21:08.147

3

Still hacked. https://xkcd.com/832/ really helps

– l4m2 – 2017-12-31T10:00:21.637

2Hacked 3 – l4m2 – 2018-01-01T11:18:05.243