Ruby Tic Tac Toe — Negamax with Alpha Beta Pruning
One of my challenges this week was to redo Tic Tac Toe in Ruby, this time implementing Alpha Beta Pruning to speed it up.
When discussing it with one of my mentors, I mentioned that I’d recently read that Alpha Beta Pruning was easier to implement using a derivative of minimax called Negamax. Negamax is a bit simpler than Minimax because it only focuses on the point of view of the player using it. If you are interested here’s my post on implementing Minimax in Java.
These algorithms work by analysing every single possible move that could occur on a given board, and minimising the chances of losing the game.
As you can probably imagine, analysing every single possible move in a game of tic tac toe is quite time consuming. Here’s where Alpha Beta Pruning comes in. Alpha Beta Pruning speeds things up by choosing to stop analysing a node if it finds that there is a worse possible outcome than one it has already calculated. If you’ve got 50 minutes I would strongly encourage you watch this video.
I’ve implemented Minimax twice now, and Negamax is a simplified version of Minimax, so I figured it would be quick and easy. I was wrong.
There are countless blogs that explain Minimax and how people have implemented them that I found to be extremely helpful :
- Recursion 201: Minimax, Tic Tac Toe, & An Unbeatable AI
- Unbeatable Tic Tac Toe with Minimax
- Minimax Algorithm Tic Tac Toe
- Unbeatable Tic Tac Toe — Minimax in Java (I had to!)
I found extremely few resources on Negamax. The vast majority of my implementation came from the pseudocode in the wikipedia entry, as well as one the pseudocode in this helpful resource.
The blogs that I had used to come to understand Minimax provide real world code explanations. The Negamax resources used pseudocode in an abstract situation. It was significantly more difficult, but the victory of getting it to work is so much sweeter.
Here is my implementation in Ruby:
class PerfectComputer
attr_reader :marker
def initialize(marker)
@marker = marker
end
def choose_space(game)
@best_score = {}
negamax(game)
@best_score.max_by {|key, value| value}[0]
end
private
def negamax(game, depth = 0, alpha = -1000, beta = 1000, color = 1)
return color * score_scenarios(game, depth) if game.game_over?
max = -1000
game.board.check_available_spaces.each do |space|
game.board.place_marker(space, game.current_player.marker)
game.change_turns
negamax_value = -negamax(game, depth+1, -beta, -alpha, -color)
game.board.place_marker(space, space)
game.change_turns
max = [max, negamax_value].max
@best_score[space] = max if depth == 0
alpha = [alpha, negamax_value].max
return alpha if alpha >= beta
end
max
end
def score_scenarios(game, depth)
return 0 if game.game_tied?
return 1000 / depth if game.game_won_by?(self)
return -1000 / depth
end
end
1.1 initialize
attr_reader :marker
def initialize(marker)
@marker = marker
end
We instantiate the class with a marker — generally “X” or “O”, and store it as an instance variable to access later with an attribute reader.
2 choose_space
def choose_space(game)
@best_score = {}
negamax(game)
@best_score.max_by {|key, value| value}[0]
end
This is the polymorphic call that comes from the game class.
- We create an empty hash and save it to an instance variable called
best_score
. - We call negamax passing in the current game object. This will check every possible outcome of the game.
- When our recursive calls has finished, we look into the
best_score
hash for the highest value, and return the key, choosing the best possible move to not let our opponent win.
3.1 negamax — Initial Method Call
def negamax(game, depth = 0, alpha = -1000, beta = 1000, color = 1)
When we call negamax, we pass in:
- the current game object
- a depth of how far we are into our recursive algorithm (starting at 0)
- an integer called alpha, starting at -1000
- an integer called beta, starting at 1000
- an integer called color, starting at 1
Alpha and beta represent lower and upper bounds for child node values at a given tree depth. The color indicates the current player, and will either be 1 for us, or -1 for our oponent.
3.2 negamax — Return a score when the game is over
return color * score_scenarios(game, depth) if game.game_over?
At the very start of our recursive function, we have our base case, which is to return the result of score_scenarios
if the game is over. If the game is not over we will move on.
NOTE: This is multiplied by the current value of color, so it is us making the move, it will be multiplied by one (making no change), and if it is our opponent we multiply it by -1, making a positive value negative, or a negative value positive.
4 score_scenarios — Calculate the outcome of our game
def score_scenarios(game, depth)
return 0 if game.game_tied?
return 1000 / depth if game.game_won_by?(self)
return -1000 / depth
end
Here’s where it gets fun.
- If our game is tied, we return 0. We haven’t won or we haven’t lost.
- If we have won, we return 1000 divided by the current depth. Remember, the depth is the number of times the recursive algorithm has been called, meaning the number of turns since we called it. If we can win on the next move we will have 1000, if it is in 3 moves it will be 333.
- Our else statement is the exact same, just negative. The only time this else statement would be called is if our opponent wins (as we only enter this function if the game is over, and we’ve checked if the game is tied or if we have won)
Still following? Let’s jump back into our negamax method
3.3 negamax — Set Max
max = -1000
max is a variable we will use going forward. In the pseudocode I’d looked, it was negative infinity, but that wasn’t logical to me. I decided to make it -1000 to be easier to work with. This value will change very soon.
3.4 negamax — Try out every space on the board
game.board.check_available_spaces.each do |space|
game.board.place_marker(space, game.current_player.marker)
game.change_turns
negamax_value = -negamax(game, depth+1, -beta, -alpha, -color)
game.board.place_marker(space, space)
game.change_turns
max = [max, negamax_value].max
@best_score[space] = max if depth == 0
alpha = [alpha, negamax_value].max
return alpha if alpha >= beta
end
I’ll break this down, but I want to show it all in one place at the start so you don’t need to keep scrolling up.
For every single available space on our board we do the subsequent steps.
3.4.1 negamax — Emulate a move
game.board.place_marker(space, game.current_player.marker)
game.change_turns
We place a marker in one of the available spaces, and then change the turns. Exactly like a real player taking a turn.
3.4.2 negamax — Recursive call
negamax_value = -negamax(game, depth+1, -beta, -alpha, -color)
The state of the board has now changed, so we call negamax again. This time; however, we do it a bit differently. Notice the following:
- - sign in front of negamax, meaning we change the sign of the result
- depth + 1 — we are adding one to our depth value, as we are going a layer deeper
- - sign in front of both alpha and beta — we are changing the signs
- alpha and beta have switched places; in our next call, our old alpha number will act as beta and vice vera
- - sign in front of color — meaning this is a negative number, which makes sense as it is our opponents move
3.4.3 negamax — Put our board back to it’s original state
game.board.place_marker(space, space)
game.change_turns
This will only happen once we’ve reached our base case; we haven’t actually made any moves, so we need to put the board back to it’s original state, space by space. We also make sure that it is still the correct player’s turn.
3.4.4 negamax — Compare max and negamax_value
max = [max, negamax_value].max
We set our max variable to whichever is higher between our max value (previously set to -1000) or our negamax_value.
3.4.5 negamax — Save our score outcome to our best_score hash
@best_score[space] = max if depth == 0
This is where the magic happens. When we are at our base case, add a key value pair of the space we were testing and our score outcome to our best_score
hash. We draw on this in all the way in step one, when we want to choose our best score. This is where we set these scores.
3.4.6 negamax — Alpha beta pruning
alpha = [alpha, negamax_value].max
return alpha if alpha >= beta
Here is where we get our huge speed gains. We save the higher value of alpha and our negamax_value to the alpha variable. If it is higher than beta, we return alpha and exit the function.
This is where we check if we so far have a worse outcome in our node — if we do, we stop calculating that node and move on.
3.5 negamax — Return max at the end of our method
max
What a sad way to finish an exciting algorithm, though this is where our negamax_value
that we’ve been referring to inside the loop comes from. This is the value that gets added to our key value pairs inside the best_score
hash.
Breaking it down into these tiny steps it wasn’t that difficult, and everything was relatively obvious. I find recursive algorithms extremely difficult to troubleshoot. At one stage I drew out by hand exactly what was happening for one of my tests while it was failing.
I’m really happy that I didn’t give up and go back to Minimax which was very tempting, and am extremely grateful that one of the crafters here at 8th Light, Jarkyn, spent two hours of her valuable time pairing with me and helping me troubleshoot my code.
I genuinely hope this blog post helps someone. Please reach out if you want to discuss.