Hello people! In this post we will look at one of the most basic Artificial Intelligence algorithm, the MiniMax algorithm. MiniMax algorithm is used to implement basic AI or game logic in 2 player games. The most common scenario is implementing a perfect Tic-Tac-Toe player. So, in this article we will look at how to implement it.
Given that two players are playing a game optimally (playing to win), MiniMax algorithm tells you what is the best move that a player should pick at any state of the game. So, the input to MiniMax algorithm would be –
- State of the game.
- Whose turn it is.
And the output would be the best move that can be played by the player given in the input.
Idea of MiniMax Algorithm –
In the game of Tic-Tac-Toe, there are two players, player X and player O. Now imagine there’s a scoreboard which displays a huge number called “score”, and –
- If X wins, the score increases by 10.
- If O wins, the score is decreased by 10.
- If it is a draw, then the score remains unchanged.
So now, the bigger the number score has, the better it is for X, which means X will try to maximize score as much as possible. Similarly, the lesser the score, the better it is for O, so O will try to minimize the score as much as possible.
To understand this better, imagine you are player X and this is the current state of your game –
- +10 if you choose state 2.
- 0 if you choose state 3 because it will be a draw if Player O is playing optimally.
- -10 if you choose state 3.
So conceptually we know that player X must choose the winning move. This is done programmatically bu choosing the move which will return the maximum score. So, X will always try to maximize the score and will always choose that move which will fetch X the maximum score. Thus, in the above scenario X chooses the move which goes to state 2.
Now, to make sure you understand both sides of this algorithm. Let us take the same state as above and let us say it is O’s turn now and not X’s. Can you draw a state diagram which will depict all the possible moves and the scores which will be returned by playing them? You can! Just pause here for a moment and try to draw the state diagram for the above game, assuming it is player O’s move.
You should get a diagram like this –
- -10 if you choose to go to state 2.
- -10 if you choose to go to state 3.
- +10 if you choose to go to state 4.
Player O will always try to minimize the score, so player O must select a move which will either lead to state 2 or 3 to win.
Writing code for MiniMax algorithm –
Writing code for MiniMax algorithm is not very difficult, but you may not get it in the first try so I’ll help you out. Firstly, have a clarity on the smaller pieces of logic and write methods for them first. You will need these 3 helper methods for your code –
- printGame(game) – which prints the state of Tic-Tac-Toe game.
- hasPlayerWon(game, player) – which tells if the given player has won the given Tic-Tac-Toe game.
- score(game) – which returns +10 if player X has won, -10 if player Y has won, 0 otherwise.
So now you have a little clarity over the smaller pieces, code them first. Now, you are ready to write the MiniMax algorithm method. It is a recursive method which takes in 2 inputs –
- the state of the game
- information on which player’s turn it is.
It will need to return –
- max/min score which can be achieved for the given player for the given game state.
- best move which can be played by given player.
We can make a new class to return all the information we need. So, our MiniMax algorithm will look like –
(score, bestMove) minimaxAlgorithm(game, isXTurn): if player X has won: // score is 10, no best move in this case return (score = 10, move = none) if player O has won: // score is -10, no best move in this case return (score = -10, move = none) bestMove = (none, none) foreach emptySpace in game: game[emptySpace] = isXTurn ? X : O currentMove = ( score = minimax(game, !isXTurn).score, move = emptySpace ) if currentMove is better than bestMove: bestMove = currentMove game[emptySpace] = emptySpace if no bestMove was found: // score is 0, no best move in this case return (score = 0, move = none) return bestMove
With your new clarity over the helper methods and the pseudocode, try to write the code for MiniMax algorithm. When in doubt come back and read the MiniMax algorithm theory and the implementation tips. Remember, you are trying to write the code for an ideal Tic-Tac-Toe player here, so you need to write the starter code for simulating a 2-player Tic-Tac-Toe game.
Try it on your own, it will be fun to create a game. If you get stuck, you can refer to my code –
The above implementation is a pretty raw. It doesn’t have checks like checking if user has input an empty cell or not. I trust you can fix all those loopholes. If you do, in the end you have an unbeatable Tic-Tac-Toe player! Congrats on taking your first step to build your dream AI! 😀
Some awesome resources –
Keep practicing! Happy Coding! 😀