What algorithm for a tic-tac-toe game can I use to determine the "best move" for the AI?

Question

In a tic-tac-toe implementation I guess that the challenging part is to determine the best move to be played by the machine.

What are the algorithms that can pursued? I'm looking into implementations from simple to complex. How would I go about tackling this part of the problem?

Answer 1

The strategy from Wikipedia for playing a perfect game (win or tie every time) seems like straightforward pseudo-code:

Quote from Wikipedia (Tic Tac Toe#Strategy)

A player can play a perfect game of Tic-tac-toe (to win or, at least, draw) if they choose the first available move from the following list, each turn, as used in Newell and Simon's 1972 tic-tac-toe program.[6]

1. Win: If you have two in a row, play the third to get three in a row.

2. Block: If the opponent has two in a row, play the third to block them.

3. Fork: Create an opportunity where you can win in two ways.

4. Block Opponent's Fork:

   Option 1: Create two in a row to force the opponent into defending, as long as it doesn't result in them creating a fork or winning. For example, if "X" has a corner, "O" has the center, and "X" has the opposite corner as well, "O" must not play a corner in order to win. (Playing a corner in this scenario creates a fork for "X" to win.)

   Option 2: If there is a configuration where the opponent can fork, block that fork.

5. Center: Play the center.

6. Opposite Corner: If the opponent is in the corner, play the opposite corner.

7. Empty Corner: Play an empty corner.

8. Empty Side: Play an empty side.

Recognizing what a "fork" situation looks like could be done in a brute-force manner as suggested.

Note: A "perfect" opponent is a nice exercise but ultimately not worth 'playing' against. You could, however, alter the priorities above to give characteristic weaknesses to opponent personalities.

Answer 2

What you need (for tic-tac-toe or a far more difficult game like Chess) is the minimax algorithm, or its slightly more complicated variant, alpha-beta pruning. Ordinary naive minimax will do fine for a game with as small a search space as tic-tac-toe, though.

In a nutshell, what you want to do is not to search for the move that has the best possible outcome for you, but rather for the move where the worst possible outcome is as good as possible. If you assume your opponent is playing optimally, you have to assume they will take the move that is worst for you, and therefore you have to take the move that MINimises their MAXimum gain.

Answer 3

The brute force method of generating every single possible board and scoring it based on the boards it later produces further down the tree doesn't require much memory, especially once you recognize that 90 degree board rotations are redundant, as are flips about the vertical, horizontal, and diagonal axis.

Once you get to that point, there's something like less than 1k of data in a tree graph to describe the outcome, and thus the best move for the computer.

-Adam

Answer 4

A typical algo for tic-tac-toe should look like this:

Board : A nine-element vector representing the board. We store 2 (indicating Blank), 3 (indicating X), or 5 (indicating O). Turn: An integer indicating which move of the game about to be played. The 1st move will be indicated by 1, last by 9.

The Algorithm

The main algorithm uses three functions.

Make2: returns 5 if the center square of the board is blank i.e. if board[5]=2. Otherwise, this function returns any non-corner square (2, 4, 6 or 8).

Posswin(p): Returns 0 if player p can’t win on his next move; otherwise, it returns the number of the square that constitutes a winning move. This function will enable the program both to win and to block opponents win. This function operates by checking each of the rows, columns, and diagonals. By multiplying the values of each square together for an entire row (or column or diagonal), the possibility of a win can be checked. If the product is 18 (3 x 3 x 2), then X can win. If the product is 50 (5 x 5 x 2), then O can win. If a winning row (column or diagonal) is found, the blank square in it can be determined and the number of that square is returned by this function.

Go (n): makes a move in square n. this procedure sets board [n] to 3 if Turn is odd, or 5 if Turn is even. It also increments turn by one.

The algorithm has a built-in strategy for each move. It makes the odd numbered move if it plays X, the even-numbered move if it plays O.

Turn = 1    Go(1)   (upper left corner).
Turn = 2    If Board[5] is blank, Go(5), else Go(1).
Turn = 3    If Board[9] is blank, Go(9), else Go(3).
Turn = 4    If Posswin(X) is not 0, then Go(Posswin(X)) i.e. [ block opponent’s win], else Go(Make2).
Turn = 5    if Posswin(X) is not 0 then Go(Posswin(X)) [i.e. win], else if Posswin(O) is not 0, then Go(Posswin(O)) [i.e. block win], else if Board[7] is blank, then Go(7), else Go(3). [to explore other possibility if there be any ].
Turn = 6    If Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else Go(Make2).
Turn = 7    If Posswin(X) is not 0 then Go(Posswin(X)), else if Posswin(X) is not 0, then Go(Posswin(O)) else go anywhere that is blank.
Turn = 8    if Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else go anywhere that is blank.
Turn = 9    Same as Turn=7.

I have used it. Let me know how you guys feel.

Answer 5

Since you're only dealing with a 3x3 matrix of possible locations, it'd be pretty easy to just write a search through all possibilities without taxing you computing power. For each open space, compute through all the possible outcomes after that marking that space (recursively, I'd say), then use the move with the most possibilities of winning.

Optimizing this would be a waste of effort, really. Though some easy ones might be:

• Check first for possible wins for the other team, block the first one you find (if there are 2 the games over anyway).
• Always take the center if it's open (and the previous rule has no candidates).
• Take corners ahead of sides (again, if the previous rules are empty)

Answer 6

An attempt without using a play field.

1. to win(your double)
2. if not, not to lose(opponent's double)
3. if not, do you already have a fork(have a double double)
4. if not, if opponent has a fork
   
   1. search in blocking points for possible double and fork(ultimate win)
   2. if not search forks in blocking points(which gives the opponent the most losing possibilities )
   3. if not only blocking points(not to lose)
5. if not search for double and fork(ultimate win)
6. if not search only for forks which gives opponent the most losing possibilities
7. if not search only for a double
8. if not dead end, tie, random.
9. if not(it means your first move)
   
   1. if it's the first move of the game;
      
      1. give the opponent the most losing possibility(the algorithm results in only corners which gives 7 losing point possibility to opponent)
      2. or for breaking boredom just random.
   2. if it's second move of the game;
      
      1. find only the not losing points(gives a little more options)
      2. or find the points in this list which has the best winning chance(it can be boring,cause it results in only all corners or adjacent corners or center)

Note: When you have double and forks, check if your double gives the opponent a double.if it gives, check if that your new mandatory point is included in your fork list.

Answer 7

You can have the AI play itself in some sample games to learn from. Use a supervised learning algorithm, to help it along.

Answer 8

Rank each of the squares with numeric scores. If a square is taken, move on to the next choice (sorted in descending order by rank). You're going to need to choose a strategy (there are two main ones for going first and three (I think) for second). Technically, you could just program all of the strategies and then choose one at random. That would make for a less predictable opponent.

Answer 9

This answer assumes you understand implementing the perfect algorithm for P1 and discusses how to achieve a win in conditions against ordinary human players, who will make some mistakes more commonly than others.

The game of course should end in a draw if both players play optimally. At a human level, P1 playing in a corner produces wins far more often. For whatever psychological reason, P2 is baited into thinking that playing in the center is not that important, which is unfortunate for them, since it's the only response that does not create a winning game for P1.

If P2 does correctly block in the center, P1 should play the opposite corner, because again, for whatever psychological reason, P2 will prefer the symmetry of playing a corner, which again produces a losing board for them.

For any move P1 may make for the starting move, there is a move P2 may make that will create a win for P1 if both players play optimally thereafter. In that sense P1 may play wherever. The edge moves are weakest in the sense that the largest fraction of possible responses to this move produce a draw, but there are still responses that will create a win for P1.

Empirically (more precisely, anecdotally) the best P1 starting moves seem to be first corner, second center, and last edge.

The next challenge you can add, in person or via a GUI, is not to display the board. A human can definitely remember all the state but the added challenge leads to a preference for symmetric boards, which take less effort to remember, leading to the mistake I outlined in the first branch.

I'm a lot of fun at parties, I know.

Answer 10

A Tic-tac-toe adaptation to the min max algorithem

let gameBoard: [
    [null, null, null],
    [null, null, null],
    [null, null, null]
]

const SYMBOLS = {
    X:'X',
    O:'O'
}

const RESULT = {
    INCOMPLETE: "incomplete",
    PLAYER_X_WON: SYMBOLS.x,
    PLAYER_O_WON: SYMBOLS.o,
    tie: "tie"
}

We'll need a function that can check for the result. The function will check for a succession of chars. What ever the state of the board is, the result is one of 4 options: either Incomplete, player X won, Player O won or a tie.

function checkSuccession (line){
    if (line === SYMBOLS.X.repeat(3)) return SYMBOLS.X
    if (line === SYMBOLS.O.repeat(3)) return SYMBOLS.O
    return false 
}

function getResult(board){

    let result = RESULT.incomplete
    if (moveCount(board)<5){
        return result
    }

    let lines

    //first we check row, then column, then diagonal
    for (var i = 0 ; i<3 ; i++){
        lines.push(board[i].join(''))
    }

    for (var j=0 ; j<3; j++){
        const column = [board[0][j],board[1][j],board[2][j]]
        lines.push(column.join(''))
    }

    const diag1 = [board[0][0],board[1][1],board[2][2]]
    lines.push(diag1.join(''))
    const diag2 = [board[0][2],board[1][1],board[2][0]]
    lines.push(diag2.join(''))
    
    for (i=0 ; i<lines.length ; i++){
        const succession = checkSuccesion(lines[i])
        if(succession){
            return succession
        }
    }

    //Check for tie
    if (moveCount(board)==9){
        return RESULT.tie
    }

    return result
}

Our getBestMove function will receive the state of the board, and the symbol of the player for which we want to determine the best possible move. Our function will check all possible moves with the getResult function. If it is a win it will give it a score of 1. if it's a loose it will get a score of -1, a tie will get a score of 0. If it is undetermined we will call the getBestMove function with the new state of the board and the opposite symbol. Since the next move is of the oponent, his victory is the lose of the current player, and the score will be negated. At the end possible move receives a score of either 1,0 or -1, we can sort the moves, and return the move with the highest score.

const copyBoard = (board) => board.map( 
    row => row.map( square => square  ) 
)

function getAvailableMoves (board) {
  let availableMoves = []
  for (let row = 0 ; row<3 ; row++){
    for (let column = 0 ; column<3 ; column++){
      if (board[row][column]===null){
        availableMoves.push({row, column})
      }
    }
  }
  return availableMoves
}

function applyMove(board,move, symbol) {
  board[move.row][move.column]= symbol
  return board
}
 
function getBestMove (board, symbol){

    let availableMoves = getAvailableMoves(board)

    let availableMovesAndScores = []

    for (var i=0 ; i<availableMoves.length ; i++){
      let move = availableMoves[i]
      let newBoard = copyBoard(board)
      newBoard = applyMove(newBoard,move, symbol)
      result = getResult(newBoard,symbol).result
      let score
      if (result == RESULT.tie) {score = 0}
      else if (result == symbol) {
        score = 1
      }
      else {
        let otherSymbol = (symbol==SYMBOLS.x)? SYMBOLS.o : SYMBOLS.x
        nextMove = getBestMove(newBoard, otherSymbol)
        score = - (nextMove.score)
      }
      if(score === 1)  // Performance optimization
        return {move, score}
      availableMovesAndScores.push({move, score})
    }

    availableMovesAndScores.sort((moveA, moveB )=>{
        return moveB.score - moveA.score
      })
    return availableMovesAndScores[0]
  }

Algorithm in action, Github, Explaining the process in more details