If we were to make (X1), it leaves square 2 open for O, leading to the win.Īnd that’s basically all there is to Min Max! You take a scoring algorithm, make a tree of all the possible states, and work backward from the leaves to find the best move possible. Let’s look at the two options we didn’t take. We then think our opponent will choose 0(3), forcing us to choose X(1) last, leading to a draw. In this case, we got the (0) from X(2), which should be our next move. To determine what move to make, we simply look at which node we took that score from. The score being 0 means that we think the best we can do is tie this game.

It’s our turn so we take the largest score from our children. We can now do the last unscored node and score the board as it stands now. For the middle node we bring up the 0 and the right node we bring up the -1 For the left most node that means we bring up the -1. We take the smallest value from the possible children. After this node, it will be O’s turn, so we are in a minimizing turn. Now things get a bit more interesting! The next unscored node is (X1). We can do the same for the other single-choice nodes as well. We just take the 0 from the bottom layer and assign it to our node. But since there is only one choice left, there isn’t much to maximize. After this node, it is my turn, so we are maximizing the possible score. Let’s look at the first un-scored node (X1, 03).

Minimax works by choosing the move with the best score when it’s your turn and assuming your opponent will choose whatever has the lowest score (as this is what’s best for them). With all of our end states scored, we can score the rest of the nodes following the minimax algorithm. Ok, so now we have a complete tree of all the possible outcomes for our game! We can use the scoring algorithm we defined at the beginning to score these end states. We still have some leaf nodes that aren’t end-states so we can continue exploring the tree. I did say Minimax was a tree search, so let us draw a tree to represent the moves we could makeĪnd we can complete this tree by showing all the potential moves my opponent would have next.Īfter some of these moves, the game would be over, and I would have lost let’s mark them as losses. Now an experienced Tic Tac Toe player might be able to figure out where to go next on their own, but we will explore this example a bit. I have 3 options let’s number them on our game board. Ok, so I’m playing as X’s in this game of Tic Tac Toe, and I need to decide what to do next. With our scoring algorithm sorted out, let us dive into the middle of a game. In Battlesnake, we’ll use a more complicated scoring function, but this will work great for Tic Tac Toe We can do a simple mapping of Loss to -1, Draw to 0 and Win to 1. In Tic Tac Toe, there are three possible end states, so let’s use that to define a ‘scoring algorithm’ to use. To go into more detail, let’s look at a pretty simple game, Tic Tac Toe. It’s a tree search algorithm designed to choose the “best” move by looking at several future moves and using a scoring function to determine which end states are desirable. Minimax is an algorithm designed originally for two-player, zero-sum games. Minimax is a popular algorithm in Battlesnake and one I’ve used for most of my competitive snakes. Today let’s look at the minimax algorithms and two multiplayer variations.

You play by making a ‘snake’ web server that receives the game state on each turn, and you have to decide which direction your snake should go! If you don’t know about Battlesnake, make sure to go check it out at. I’ve been playing Battlesnake for just over a year now, and I’m having so much fun! The community is incredible, and I’m having a ton of fun trying out different strategies and algorithms trying to take those top spots! Minimax in Battlesnake 3.5.22 Minimax in Battlesnake

Battle snake springs