Make computer never lose in tic-tac-toe

Question

I'm working on a simple Tic Tac Toe code game for C. I have most of the code finished, but I want the AI ​​to never play.

I read about the minimax algorithm, but I do not understand this. How to use this algorithm so that the computer can either Win or Draw, but never lose?

Answer 1

A way to approach this problem is to study possible futures. Usually (for chess or AI drafts) you consider futures a certain number of moves forward, but because games with tic tac toe are so short, you can research until the end of the game.

Conceptual implementation

So you create a branch structure:

• AI imagines taking every legal step
• The AIs imagine the user making every legal move that they can make after each of his legal moves.
• AI then presents each of its next legal steps.
• and etc.

Then, moving from the most branched end (farthest forward), the player whose turn (AI or user) chooses which future is best for him (to win, lose or draw) at each branch point. Then he passes the player above the tree (closer to the present); each time choosing a better future for the player whose imaginary turn is until, finally, you find yourself at the first branch point, where the AI ​​can see futures that lose to it, losing, drawing and winning. He chooses a future in which he wins (or if no draws are available).

Actual implementation

Note that conceptually this is what happens, but you don’t need to create the whole tree, and then judge like that. You can work just as easily, although the tree gets to the most distant points of time and then chooses.

Here, this approach works well with a recursive function. Each level of a function checks all its branches; passing them a possible future and returns -1.0, + 1; choosing the best score for the current player at each point. The highest level chooses a move, without actually knowing how each future rolls out, how well they come out.

Pseudo code

I assume in this pseudocode that +1 is AI gain, 0 is drawing, -1 is user loss

determineNextMove(currentStateOfBoard) currentBestMove= null currentBestScore= - veryLargeNumber for each legalMove score=getFutureScoreOfMove(stateOfBoardAfterLegalMove , AI'sMove) if score>currentBestScore currentBestMove=legalMove currentBestScore=score end end make currentBestMove end getFutureScoreOfMove(stateOfBoard, playersTurn) if no LegalMoves return 1 if AI wins, 0 if draw, -1 if user wins end if playersTurn=AI'sTurn currentBestScore= - veryLargeNumber //this is the worst case for AI else currentBestScore= + veryLargeNumber //this is the worst case for Player end for each legalMove score=getFutureScoreOfMove(stateOfBoardAfterLegalMove , INVERT playersTurn) if playersTurn ==AI'sTurn AND score>currentBestScore //AI wants positive score currentBestScore=score end if playersTurn ==Users'sTurn AND score<currentBestScore //user wants negative score currentBestScore=score end end return currentBestScore end 

This pseudo-code does not care what the initial board is (you call this function each time the AI ​​moves with the current board) and does not return which path it will take in the future (we cannot know if the user will play optimally, therefore this information is useless), but she will always choose the step that goes towards an optimal future for AI.

Considerations for big tasks

In this case, when you research until the end of the game, it is obvious that the best future is possible (win, lose or attract), but if you are only going to (for example) five movements in the future, you will have to find a way to determine this; in a checkerboard or rough piece is the easiest way to do this when a piecewise position is a useful addition.

Answer 2

I did such a thing about 5 years ago. I did a study. In tic tac toe it will not take much time, you just need to prepare templates for the first two or three moves.

You need to check how to play:

• The computer starts up first.
• The player plays first.

There are 9 different starting positions:

But in fact, only 3 of them are different (others rotate). Therefore, after this you will see what should be done after some specific steps, I think that you do not need any algorithms in this case, because the end of tic tac toe is determined by the first moves. Therefore, in this case, you will need several if-else or switch and a random generator.

Answer 3

Make a helper program for predicting cases with which the user can win. Then you can say that your ai does what the user must do in order to win.

Answer 4

tic tac toe belong to a group of games that will not be lost if you know how to play, so for such games you do not need to use trees and modified sorting algorithms. To write such an algorithm, you need only a few functions:

• CanIWin() to check if the computer has 2 lines and it is possible to win.
• ShouldIBlock() to check if the player has 2 lines and needs to block it.

These two functions should be called in this order, if it returns true , you need to either win or not give the winner to the player.

After that, you need to do other calculations to move.

One exclusive situation is when the computer launches the game. You need to select a cell that belongs to the largest number of different directions (of which 8 of them are 3 horizontal, vertical and 2 diagonal). In such an algorithm, the computer will always choose the center, because it has 4 directions, you should add a little opportunity to choose the second best option to make the game a little more attractive.

Therefore, when you reach a situation where some selected parts of the board and computer must move, you need to evaluate each free cell. ( If the first or second function returns true , you must take action before you get to this place !!! ). Therefore, in order to evaluate a cell, you need to calculate how many open directions remain on each cell, and you also need to block at least one enemy direction.

After that, you will have several possible cells to put your mark on. Therefore, you need to check the sequence of necessary actions, because you will have several options, and it may happen that one of them leads to your loss. Therefore, after that, you will be tuned, and you can arbitrarily choose to move or choose the one with the highest rating.

I have to say this, as said at the beginning of the post. Big games do not have an ideal strategy and, say, chess is based on templates, but also on a strategy of perspective thinking ( patricia trie is used for such a thing). So, to summarize, you do not need complex algorithms, just a few functions to calculate how much you win, and the opponent loses with the move.