DEV Community

loading...

Tic-Tac-Toe you can't beat...

dhhruv profile image Dhruv Panchal ・3 min read

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.

Tic Tac Toe GUI

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:

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.

GitHub Link for Source Code:

GitHub logo dhhruv / Tic-Tac-Toe

πŸŽƒ Unbeatable Tic Tac Toe Game using Minimax Algorithm.

References:

Discussion (15)

pic
Editor guide
Collapse
cmuralisree profile image
Chittoji Murali Sree Krishna

Nice work πŸ‘

Collapse
dhhruv profile image
Collapse
james_palermo_bc208e463e4 profile image
Collapse
james_palermo_bc208e463e4 profile image
James Palermo

Cool implementation.

Collapse
dhhruv profile image
Collapse
james_palermo_bc208e463e4 profile image
James Palermo

I could beat or draw it though. 😜tic tac toe is human solvable.

Thread Thread
dhhruv profile image
Dhruv Panchal Author

Can you send a Screenshot where you've beaten the Computer ??😏

Thread Thread
james_palermo_bc208e463e4 profile image
Thread Thread
james_palermo_bc208e463e4 profile image
Thread Thread
dhhruv profile image
Dhruv Panchal Author

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.πŸ˜€

Thread Thread
james_palermo_bc208e463e4 profile image
James Palermo

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.

Thread Thread
dhhruv profile image
Dhruv Panchal Author

Yeah, that makes sense. But, I thought in the same example maybe the computer can think like Bob and know what's next so...

Thread Thread
james_palermo_bc208e463e4 profile image
James Palermo

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

Thread Thread
james_palermo_bc208e463e4 profile image
James Palermo • Edited

You should also clear the mouse input buffer and reinit it after laucnhing and between games. :D

youtu.be/48OqfWgv9ak

Thread Thread
dhhruv profile image
Dhruv Panchal Author

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.😁