Board Game Artificial Intelligence: the Minimax Algorithm

Ever wondered how the computers you play against in chess or checkers are made? Well look no further than this Instructable for it will show you how to make a simple but effective artificial intelligence (AI) using the Minimax Algorithm! By using the Minimax Algorithm, the AI makes well planned and thought out moves (or at least mimics a thought process). Now, I could just give you the code for the AI that I made, but that wouldn't be fun. I'll explain the logic behind the computer's choices.

In this Instructable, I'll be walking you through the steps on how to make an AI for Othello (AKA Reversi) in python. You should have an intermediate understanding of how to code in python before tackling this project. Here are a few good websites to look at to prepare you for this Instructable: w3schools or learnpython. At the end of this Instructable, you should have a AI that will make calculated moves and should be able to defeat most humans.

Since this Instructable will be primarily dealing with how to make an AI, I will not be explaining how to design a game in python. Instead, I will be giving the code for the game where a human can play against another human and modify it so that you can play a game where a human plays against the AI.

I learned how to create this AI through a summer program at Columbia SHAPE. I had a good time there so take a look at their website to see if you would be interested.

Now that we got the logistics out of the way, let's start coding!

(I put a couple of notes in the images so make sure to look at them)

This is easy:

1) Computer with a python environment such as Spyder or IDLE

2) Download the files for the Othello game from my GitHub

3) Your brain with patience installed

When you go into my GitHub, you should see 5 files. Download all 5 and place them all in the same folder. Before we run the game, open all the files in the spyder environment.

Here is what the files do:

1) othello_gui.py --> this file creates the game board for the players to play on (whether human or computer)

2) othello_game.py --> this file plays two computers against each other without the gameboard and only shows the score and move positions

3) ai_template.py --> this is where you will be putting all your code to make your AI

4) randy_ai.py --> this is a premade AI that chooses its moves randomly

5) othello_shared.py --> a bunch of pre-made functions that you can use to make your AI such as to check for available moves, the score, or board state

6) The three other files: Puma.py, erika_5.py, and nathan.py, made by me, Erika, and Nathan respectively from the SHAPE program, these are three different AIs with unique codes

Once you have all the files open, in the bottom right-hand corner of the screen, type "run othello_gui.py" and hit enter in the IPython Console. Or in Mac terminal, type "python othello_gui.py" (after you are in the right folder of course). Then a board should pop up on your screen. This mode is the human vs human mode. Light goes second and dark first. Look at my video if you are confused. iAt the top, there is the score of each color tile. To play, click a valid move space to place a tile there and then give the computer to your opponent who will do the same and repeat.

If you do not know how to play Othello, read these rules from the ultra boards website:

Black always moves first. A move is made by placing a disc of the player's color on the board in a position that "out-flanks" one or more of the opponent's discs. A disc or row of discs is outflanked when it is surrounded at the ends by discs of the opposite color. A disc may outflank any number of discs in one or more rows in any direction (horizontal, vertical, diagonal).... (finish reading at their website)

The difference between the original game and this python game is that when there are no valid moves left for one player the game ends.

Now that you can play the game with a friend, let's make an AI that you can play with.

Before talking about how to write this in code, let's go over the logic behind it. The minimax algorithm is a decision-making, back-tracking algorithm and is typically used in two-player, turn-based games. The goal of this AI is to find the next best move and the following best moves until it wins the game.

Now how would the algorithm determine which move is the best move? Stop and think how you would choose the next move. Most people would choose the move that would give them the most points, right? Or if they were thinking ahead, they would choose the move which would set up a situation where they could gain even more points. The latter way of thinking is the way how the Minimax Algorithm thinks. It looks ahead to all the future board setups and makes the move that would lead to the most points.

I called this a backtracking algorithm, because it starts by first creating and evaluating all the future board states with their associated values. This means that the algorithm will play the game as many as it needs to (making the moves for itself and the opponent) until every scenario of the game has played. To keep track of all the board states (scenarios), we can draw a tree (look in the pictures). The tree in the picture above is a simple example of a game of Connect 4. Every board configuration is called a board state and its place on the tree is called a node. All the nodes at the bottom of the tree are the final board states after making all the moves. Obviously some board states are better for one player than the other. So, now we have to make the AI choose which board state it wants to get to.

To give values to the board states, we have to learn the strategies of the game that we are playing: in this case, the strategies of Othello. Because this game is a battle of flipping the opponent's and your discs, the best disc positions are the ones that are stable and cannot be flipped over. The corner, for example, is the place where when a disc is placed it cannot be changed to the other color. Thus, that spot would be extremely valuable. Other good positions include the sides of the board which would allow for you to take a lot of stones. There are more strategies on this website.

Now we can assign values to the positions for each board state board. When a position is occupied by the AI's piece, then you give a certain number of points depending on the position. For example, a board state where the AI's piece is in the corner, you can give a bonus of 50 points, but if it were in an unfavorable spot, the piece may have a value of 0. After taking into account all the values of the positions, you assign the board state a value. For example, if the AI has a piece in the corner the board state can have a score of 50 while another board state with the AI's piece in the middle has a score of 10.

There are many ways to do this, and I have three different heuristics to evaluate the board pieces. I encourage you to make your own type of heuristic. I uploaded three different AIs to my github by three different makers, with three different heuristics: Puma.py, erika5.py, nathanh.py.

Now it would be nice if the AI could just choose all the moves to get to the board state with the highest score. But remember that the AI was also choosing the moves for the opponent when it was generating all the board states and if the opponent is smart, it won't allow the AI to get to the highest board score. Instead, a smart opponent would make the move to make the AI go to the lowest board state. In the algorithm, we call the two players a maximizing player and a minimizing player. The AI would be the maximizing player since it wants to get the most points for itself. The opponent would be the minimizing player since the opponent is trying to make the move where the AI gets the fewest points.

Once all the board states are generated and values have been assigned to the boards, the algorithm starts to compare the board states. In the pictures, I created a tree to represent how the algorithm would choose its moves. Each split in the branches is a different move the AI or the opponent can play. To the left of the rows of nodes, I wrote whether the maximizing or minimizing player is going. The bottom row is all the board states with their values. Inside of each of those nodes is a number and those are the scores we assign to each of the boards: the higher they are, the better it is for the AI to have.

Definitions: parent node - a node that results or creates nodes below it; the origin of the children nodes - the nodes that come from the same parent node

The empty nodes represent which move the AI will make to get to the best board state. It starts with comparing the children of the leftmost node: 10, -3, 5. Since the maximizing player would make the move, it would choose the move that would give it the most points: 10. So, we then select and store that move with the board score and write it in the parent node. Now that 10 is in the parent node, it is now the minimizing players turn. However, the node that we would compare 10 to is empty, so we have to evaluate that node first before the minimizing player can choose. So we go back to the maximizing player's turn and compare the children of the adjacent node: 8, -2. Maximizing will choose 8 and we write that in the empty parent node. Now that the algorithm has finished filling in the empty spaces for the children of a node above it, the minimizing player can compare those children - 10 and 8 and choose 8. The algorithm then repeats this process until the entire tree is filled out. At the end of this example, we have the score 8. That's the highest board state the AI can play to assuming the opponent is playing optimally. So the AI will choose the first move that leads to the 8 board state, and if the opponent plays optimally, the AI should play all the moves to get to board state 8. (Follow the notes on my pictures)

I know that was a lot. If you are one of those types that need to have someone talk to you to understand something, here are a couple of videos that I watched to help me grasp the idea behind this: 1, 2, 3.

After you understand the logic behind the minimax algorithm, take a look at this pseudocode (the functions that are universal to all codes) from wikipedia:

function minimax(node, depth, maximizingPlayer) is

if depth = 0 or node is a terminal node then

return the heuristic value of node

if maximizingPlayer then

value := −∞

for each child of node do

value := max(value, minimax(child, depth − 1, FALSE))

return value

else (* minimizing player *)

value := +∞

for each child of node do

value := min(value, minimax(child, depth − 1, TRUE))

return value

This is a recursive function, meaning that it calls itself over and over until it reaches a stopping point. First, the function takes in three values, the node, depth, and whose turn it is. The node value is the place where you want the program to start searching. The depth is how far you want the program to search. For example, in my tree example it has a depth of 3, because it searched all the board states after 3 moves. Of course, we would like the AI to check every board state and choose a winning win, but in most games where there are thousands if not millions of board configurations, your laptop at home won't be able to process all those configurations. So, we limit the AI's search depth and have it go to the best board state.

This pseudocode is reproducing the process that I explained in the previous two steps. Now let's take this a step further and right this in python code.

Before taking a look at my Minimax AI code, take a crack at trying to make your own AI with the ai_template.py file and the pseudo-code we talked about in the last step. There are two functions in the ai template called: def minimax_min_node(board, color) and def minimax_max_node(board, color). Instead of having the minimax function call itself recursively, we have two different functions, which call each other. To create the heuristic to evaluate board states, you will have to create your own function. There a premade functions in the othello_shared.py file that you can use to build your AI.

Once you have your AI, try running it against, randy_ai.py. To run two ais against each other, type in "python othello_gui.py (insert ai file name).py (insert file name).py" in the mac terminal or type "run othello_gui.py (insert ai file name).py (insert file name).py" and make sure you are in the right directory. Also, look at my video for the exact steps.

Now get a bunch of your computer friends and make them design their own AI! Then you can make a competition and have your AI duke it out. Hopefully, even if you could not build your own AI, you were able to understand how the minimax algorithm works. If you have any questions, feel free to post any questions in the comments below.