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

User · Answer

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.

_x000D_

function checkSuccession (line){_x000D_
    if (line === SYMBOLS.X.repeat(3)) return SYMBOLS.X_x000D_
    if (line === SYMBOLS.O.repeat(3)) return SYMBOLS.O_x000D_
    return false _x000D_
}_x000D_
_x000D_
function getResult(board){_x000D_
_x000D_
    let result = RESULT.incomplete_x000D_
    if (moveCount(board)<5){_x000D_
        return result_x000D_
    }_x000D_
_x000D_
    let lines_x000D_
_x000D_
    //first we check row, then column, then diagonal_x000D_
    for (var i = 0 ; i<3 ; i++){_x000D_
        lines.push(board[i].join(''))_x000D_
    }_x000D_
_x000D_
    for (var j=0 ; j<3; j++){_x000D_
        const column = [board[0][j],board[1][j],board[2][j]]_x000D_
        lines.push(column.join(''))_x000D_
    }_x000D_
_x000D_
    const diag1 = [board[0][0],board[1][1],board[2][2]]_x000D_
    lines.push(diag1.join(''))_x000D_
    const diag2 = [board[0][2],board[1][1],board[2][0]]_x000D_
    lines.push(diag2.join(''))_x000D_
    _x000D_
    for (i=0 ; i<lines.length ; i++){_x000D_
        const succession = checkSuccesion(lines[i])_x000D_
        if(succession){_x000D_
            return succession_x000D_
        }_x000D_
    }_x000D_
_x000D_
    //Check for tie_x000D_
    if (moveCount(board)==9){_x000D_
        return RESULT.tie_x000D_
    }_x000D_
_x000D_
    return result_x000D_
}

_x000D_

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.

_x000D_

const copyBoard = (board) => board.map( _x000D_
    row => row.map( square => square  ) _x000D_
)_x000D_
_x000D_
function getAvailableMoves (board) {_x000D_
  let availableMoves = []_x000D_
  for (let row = 0 ; row<3 ; row++){_x000D_
    for (let column = 0 ; column<3 ; column++){_x000D_
      if (board[row][column]===null){_x000D_
        availableMoves.push({row, column})_x000D_
      }_x000D_
    }_x000D_
  }_x000D_
  return availableMoves_x000D_
}_x000D_
_x000D_
function applyMove(board,move, symbol) {_x000D_
  board[move.row][move.column]= symbol_x000D_
  return board_x000D_
}_x000D_
 _x000D_
function getBestMove (board, symbol){_x000D_
_x000D_
    let availableMoves = getAvailableMoves(board)_x000D_
_x000D_
    let availableMovesAndScores = []_x000D_
_x000D_
    for (var i=0 ; i<availableMoves.length ; i++){_x000D_
      let move = availableMoves[i]_x000D_
      let newBoard = copyBoard(board)_x000D_
      newBoard = applyMove(newBoard,move, symbol)_x000D_
      result = getResult(newBoard,symbol).result_x000D_
      let score_x000D_
      if (result == RESULT.tie) {score = 0}_x000D_
      else if (result == symbol) {_x000D_
        score = 1_x000D_
      }_x000D_
      else {_x000D_
        let otherSymbol = (symbol==SYMBOLS.x)? SYMBOLS.o : SYMBOLS.x_x000D_
        nextMove = getBestMove(newBoard, otherSymbol)_x000D_
        score = - (nextMove.score)_x000D_
      }_x000D_
      if(score === 1)  // Performance optimization_x000D_
        return {move, score}_x000D_
      availableMovesAndScores.push({move, score})_x000D_
    }_x000D_
_x000D_
    availableMovesAndScores.sort((moveA, moveB )=>{_x000D_
        return moveB.score - moveA.score_x000D_
      })_x000D_
    return availableMovesAndScores[0]_x000D_
  }

_x000D_

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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          Win  If you have two in a row  play the third to get three in a row    Block  If the opponent has two in a row  play the third to block them    Fork  Create an opportunity where you can win in two ways    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    Center  Play the center    Opposite Corner  If the opponent is in the corner  play the opposite   corner    Empty Corner  Play an empty corner    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

User · Answer

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

User · Answer

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

User · Answer

An attempt without using a play field    to win your double         if not  not to lose opponent s double       if not  do you already have a fork have a double double       if not  if opponent has a fork  search in blocking points for possible double and fork ultimate win     if not search forks in blocking points which gives the opponent the most losing possibilities      if not only blocking points not to lose       if not search for double and fork ultimate win      if not search only for forks which gives opponent the most losing possibilities     if not search only for a double    if not dead end  tie  random      if not it means your first move   if it s the first move of the game   give the opponent the most losing possibility the algorithm results in only corners which gives 7 losing point possibility to opponent     or for breaking boredom just random      if it s second move of the game   find only the not losing points gives a little more options     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

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

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

Examples related to algorithm

Examples related to artificial-intelligence

Examples related to tic-tac-toe