What algorithm for tic-tac-toe can be used to determine the "best move" for AI?

Question

In the tic-tac-toe implementation, I assume that the challenge is to determine the best movement the machine will play.

What algorithms can I do? I study implementations from simple to complex. How do I solve this part of the problem?

Answer 1

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

Quote from Wikipedia (Tic Tac Toe # strategy )

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

• Win: If you have two lines, play the third to get three lines.

• Block: if the adversary has two lines, play the third to block them.

• Fork: create an opportunity in which you can win in two ways.

• Opponents lock widget:

  Option 1: Create two rows to force the opponent in defense, for how long since this does not lead to their creation with a fork or victory. For example, if “X” has an angle, “O” has a center, and “X” also has an opposite angle, “O” does not have to play in the corner to win. (A corner game in this scenario creates a fork for “X” to win.)

  Option 2: if there is a configuration where the adversary can develop, block this fork.

• Center: Center playback.

• Opposite angle: if the opponent is in a corner, play the opposite corner.

• Empty corner: play the empty corner.

• Empty side: play on the empty side.

Recognizing what the “plug” situation looks like can be done in a crude way, as suggested.

Note: an “ideal” opponent is a great exercise, but ultimately you should not “play” against. However, you could change your priorities to give characteristic flaws to your opponent’s personalities.

Answer 2

What you need (for tic-tac-toe or a much more complex game such as Chess) is the minimax algorithm or a slightly more complex version of it, alpha-beta trimming . Ordinary naive minimax will do a great job with a small search space like tic-tac-toe.

In short, what you want to do is not look for the move that has the best possible result for you, but rather the transition where the worst possible result is most effective. If you assume that your opponent is playing optimally, you should assume that they will make the worst move for you, and therefore you need to make a move that minimizes their maximum win.

Answer 3

The brute force method for creating every single possible board and counting it on the basis of the boards that it later produces further on the tree does not require a lot of memory, especially if you learn that 90 degrees rotation is redundant, vertical, horizontal and diagonal axis.

Once you get to this point, there is something like less than 1k of data in the tree description to describe the result, and therefore the best way for a computer.

-Adam

Answer 4

A typical tic-tac-toe algorithm should look like this:

Blackboard: A vector of nine elements representing a blackboard. We store 2 (indicating empty), 3 (indicating X) or 5 (indicating O). Turn: an integer indicating which course the game is going to play. The 1st move will be marked 1, the last - 9.

Algorithm

The main algorithm uses three functions.

Make2: returns 5 if the central square of the board is empty, 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 wins the next turn; otherwise, the square number is returned, which is the winning move. This feature will allow the program to both win and block the victory of opponents. This function works by checking each row, column and diagonal. Multiplying the values ​​of each square together for the entire row (or column or diagonal), you can check the possibility of winning. 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, you can define an empty square in it and return the number of this square of this function.

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

The algorithm has a built-in strategy for each move. He makes an odd move if he plays X , an even move if he 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)) ie [ block opponents win], else Go(Make2). Turn = 5 if Posswin(X) is not 0 then Go(Posswin(X)) [ie win], else if Posswin(O) is not 0, then Go(Posswin(O)) [ie 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 used this. Let me know how you guys feel.

Answer 5

Since you are dealing with a 3x3 matrix of possible locations, it would be easy to simply write a search for all the possibilities without burdening you with computational power. For each open space, calculate all the possible results after they mark this space (recursively, I would say), and then use the move with the greatest possible winnings.

Optimizing this would be a waste of effort. Although some simple ones may be:

• First, check the possible winnings for the other team, you will find the first one to block (if there are 2 games in any case).
• Always keep the center if it is open (and there are no candidates in the previous rule).
• Take the corners in front of the sides (again, if the previous rules are empty)

Answer 6

You may have an AI game in some examples of games to learn. Use a supervised learning algorithm to help him.

Answer 7

Trying without using the playing field.

• to win (your double)
• if not, do not lose (opponent twice)
• If not, you already have a plug (there is a double double)
• if not, if the opponent has a fork
  • search in blocking points for possible doubles and fork (final victory)
  • if not search forks in blocking points (which gives the enemy the most losing opportunities)
  • if not only block points (do not lose)
• if not search for doubles and fork (final victory)
• if not search only for forks, which give the enemy the most losing opportunities.
• if you do not look only double
• if not a dead end, tie, random.
• if not (this means your first move)
  
  • if this is the first move of the game;
    
    • gives the opponent the most losing opportunity (the algorithm only leads to corners, which gives 7 points of loss of opportunity to the enemy)
    • or for hacking boredom just by accident.
  • if this is the second turn of the game;
    
    • find only those losses (gives a little more options)
    • or find the points on this list that have the best winning chance (this can be boring because it only results in all corners or adjacent corners or center).

Note. If you have doubles and forks, check to see if your double gives a double. If it does, check to see if your new required item is on the markup list.

Answer 8

The rank of each square with numerical points. If you take a square, go to the next selection (sorted in descending order by rank). You will need to choose a strategy (there are two main ones for the first and three (I think) for the second). Technically, you can simply program all strategies, and then choose one at random. That would do for a less predictable adversary.

Answer 9

This answer assumes that you understand the implementation of the perfect algorithm for P1 and discusses how to achieve victory in conditions against ordinary human players, who will make some mistakes more often than others.

The game, of course, should end in a draw if both players play optimally. On a human level, the P1 game, playing in the corner, wins much more often. For some psychological reason, P2 is led to the idea that playing in the center is not so important, which is unsuccessful for them, since this is the only answer that does not create a winning game for P1.

If P2 is correctly locked in the center, P1 must play in the opposite corner, because, for any psychological reason, P2 will prefer the symmetry of the game in the corner, which again creates a losing card for them.

For any move P1 that can do for the initial move, there is a step P2 that can create a win for P1 if both players play optimally after that. In this sense, P1 can play everywhere. Edge movements are weaker in the sense that most of the possible answers to this move cause a draw, but there are still answers that will create a win for P1.

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

The next challenge you can add in person or through the graphical interface is not displaying the board. A person can definitely remember the entire state, but the added problem leads to the preference for symmetrical boards, which require less effort to remember, which led to the error that I described in the first branch.

I really like parties, I know.

Answer 10

Tic-tac-toe adaptation to the minimum maximum algorithm

 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 need a function that can check the result. The function will check the sequence of characters. Whatever the condition of the board, the result is one of 4 options: either unfinished, or player X wins, or player O wins, or a draw.

 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 get the state of the board and the player’s symbol for which we want to determine the best possible move. Our function will check all possible moves using the getResult function. If this is a win, he will give him 1 point. In case of loss, he will get -1, and a draw - 0. If he is not defined, we will call the getBestMove function with the new state of the board and the opposite symbol. Since the opponent’s next move, his victory is the loss of the current player, and the score will be nullified. At the end, a possible move gets a score of 1.0 or -1, we can sort the moves and return the move with the most points.

 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 detail