Play tic-tac-toe and never lose

Question

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

Answer 1

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.

Answer 2

Python 3, 18 bytes

lambda a:a+a%2*2-1

Try it online!

This brilliant AI will always force a tie, and sometimes win if you let it. The grid is numbered in a spiral, like so:

1 2 3
8 9 4
7 6 5

and the computer always goes first. For the first move, input "10". This is a little redundant because it always goes in the same place, but it's already built into the algorithm so ¯\_(ツ)_/¯

By going in the middle first, the game is essentially converted into 1 dimension, with the only way to win being 3 in a row along the sides. The divides all of these remaining 8 squares into pairs, and always goes in the other square in the pair. For example, if you go in square 1, it goes in square 2. If you go in square 2, it goes in square 1. The nice thing about this system is that it will never make an illegal move, as well as never losing.

This was actually from a magic trick invented by Martin Gardner, where you can predict the outcome of a game of tic-tac-toe. Every game ends the exact same, including rotation, or the computer wins. It "never loses".

This is definitely my favorite solution to a code golf that I ever have found, and probably ever will find.

Answer 3

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 

Answer 4

Python 3: 341 bytes

So, my first attempt of code golfing, nice challenge! I thought of something similar myself with a complete game in mind though. Here is the AI code:

def e(b,t):return any([b[i]==b[i+d]==b[i+2*d]==t for i,d in((0,1),(3,1),(6,1),(0,3),(1,3),(2,3),(0,4),(2,2))])
def n(b,t,d=8):
    if e(b,t):return 0,1
    if e(b,-t):return 0,-1
    if all(b):return 0,0
    x=-2
    for m in range(9):
        if b[m]==0:
            b[m]=t;s,b[m]=-n(b,-t,d-1)[1],0
            if s>x:x,y=s,m
    return y,x

Try online
Try the code here.

Input/output

Function n takes a 1D array as input where X and O are represented by 1 and -1, and empty squares by 0. Example board:

b = [0, 1, 0, -1, 0, -1, 0, 0, 1]

equals

[' ', 'X', ' ']
['O', ' ', 'O']
[' ', ' ', 'X']

It then outputs the best move (board index 0 to 8) for the given player along with its evaluation:

• Score = 1: Current player wins
• Score = -1: Other player wins
• Score = 0: Draw if both players play perfectly \

Explanation
Function 'n' is a Negamax framework where it goes through the entire tree of possible solutions from the given board state until the game is finished (a player wins or board is full). For each possible move it goes depth first and checks all possible outcomes of that move until the end.

If the score from a move is larger than the current best (set to -2 as default to always get a better move to play) the best score and best move is updated. At the end the best move and score is returned. \

Commented code

# Checks if the given player has 3 in a row and returns 1 if so
def evaluate(board,turn):
    for i, d in (0,1),(3,1),(6,1),(0,3),(1,3),(2,3),(0,4),(2,2):
        if board[i]==b[i+d]==b[i+2*d]==turn: return 1

# Negamax recursive function
def negamax(board, turn, depth=8):

    # Checks if player or opponent has won
    if evaluate(board,turn): return 0,1
    if evaluate(board,-turn): return 0,-1

    # Checks if board is full
    if all(board): return 0,0

    # Goes through all possible moves in the board (available spots)
    best_score = -2
    for index in range(9):
        if board[index]==0:

            # Make the move, evaluate position, and unmake the move
            board[index] = turn
            score = -negamax(board, -turn, depth-1)[1]
            board[index] = 0

            # If score was better than previous best score, update best score and move
            if score > best_score:
                best_score, best_move = score, index

    # Return best move and score after it has gone through all possibilities
    return best_move, best_score