In order to make the traditional Tic Tac Toe Game unbeatable, it is necessary to create an algorithm that can calculate all the possible moves available for the Computer and can use that to determine the best possible move.
Introduction
To solve games using AI, we will introduce the concept of a Game Tree followed by Minimax algorithm. This algorithm sees a few steps ahead and puts itself in the shoes of its opponent. It keeps playing ahead until it reaches a terminal arrangement of the board (terminal state) resulting in a tie, a win, or a loss. Once in a terminal state, the AI will assign an arbitrary positive score (+10) for a win, a negative score (-10) for a loss, or a neutral score (0) for a tie.
At the same time, the algorithm evaluates the moves that lead to a terminal state based on the players’ turn. It will choose the move with maximum score when it is the AI’s turn and choose the move with the minimum score when it is the human player’s turn. Using this strategy, Minimax avoids losing to the human player.
What is Minimax?
Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario. When dealing with gains, it is referred to as "maximin" - to maximize the minimum gain. Originally formulated for n-player zero-sum game theory (one player wins (+10) and other player loses (-10) or both of anyone not to win (0)), covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision-making in the presence of uncertainty.
How does it work?
To check whether or not the current move is better than the best move we take the help of minimax function which will consider all the possible ways the game can go and returns the best value for that move, assuming the opponent also plays optimally until it finds a terminal state (win, draw or lose).
Game Tree
Image:
Explanation:
This image depicts all the possible paths that the game can take from the root board state. It is often called the Game Tree.
The 3 possible scenarios in the above example are :
- Left Move : If X plays [2,0]. Then O will play [2,1] and win the game. The value of this move is -10
- Middle Move : If X plays [2,1]. Then O will play [2,2] which draws the game. The value of this move is 0
- Right Move : If X plays [2,2]. Then he will win the game. The value of this move is +10;
Remember, even though X has a possibility of winning if he plays the middle move, O will never let that happen and will choose to draw instead.
Therefore the best choice for X, is to play [2,2], which will guarantee a victory for him.
Discussion (15)
Nice work 👍
Thanks...
youtu.be/ZHd5swo8X6c
Cool implementation.
Thanks
I could beat or draw it though. 😜tic tac toe is human solvable.
Can you send a Screenshot where you've beaten the Computer ??😏
Yup. like I said, it is human-solvable.
dev-to-uploads.s3.amazonaws.com/up...
youtu.be/ZHd5swo8X6c
Woah, that's great. Might wanna look into it. Can you suggest what could I change in the script to overcome this ??
Thanks for the video.😀
If you have two people, Alice and Bob, who both know the solution, every game will be a draw. If a third player, Charlie, doesn't know the solution, as long as Alice goes first against Charlie she will always win.
Yeah, that makes sense. But, I thought in the same example maybe the computer can think like Bob and know what's next so...
Your code is very neatly done, but you really should try to get in the habit of commenting on what functions do in a clear way, and when you introduce a new variable say what it is.
For example, at line 51 by looking at the function "def bconv(TTT):" i can immediately tell this thing is converting from B to T. I have no idea what B and T is, or why you're converting them in the first place.
Bacons to tomatoes? :D
You should also clear the mouse input buffer and reinit it after laucnhing and between games. :D
youtu.be/48OqfWgv9ak
Yeah, actually cleaning of the code and comments is still in progress so I'll add comments to make them clear and look into flushing the mouse input. Thanks for the help.😁