## Implementing Minimax and Alpha-Beta Pruning Using Python

### Teleology (a.k.a – what is the purpose of this post?)

Recently, I finished an artificial intelligence project that involved implementing the Minimax and Alpha-Beta pruning algorithms in Python.

These algorithms are standard and useful ways to optimize decision making for an AI-agent, and they are fairly straightforward to implement.

I haven’t seen any actual working implementations of these using Python yet, however. So I’m posting my code as an example for future programmers to improve & expand upon.

It’s also useful to see a working implementation of abstract algorithms sometimes, when you’re seeking greater intuition about how they work in practice.

My hope is that this post provides you with some of that intuition, should you need it–and that it does so at an accelerated pace.

### Ontology (a.k.a – how does this abstract idea __actually work__, in reality?)

Assumptions:  This code assumes you have already built a game tree relevant to your problem, and now your task is to parse it. If you haven’t yet built a game tree, that will be the first step in this process. I have a previous post about how I did it for my own problem, and you can use that as a starting point. But keep in mind that YMMV.

My implementation looks like this:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 ########################## ###### MINI-MAX ###### ########################## class MiniMax: # print utility value of root node (assuming it is max) # print names of all nodes visited during search def __init__(self, game_tree): self.game_tree = game_tree # GameTree self.root = game_tree.root # GameNode self.currentNode = None # GameNode self.successors = [] # List of GameNodes return def minimax(self, node): # first, find the max value best_val = self.max_value(node) # should be root node of tree # second, find the node which HAS that max value # –> means we need to propagate the values back up the # tree as part of our minimax algorithm successors = self.getSuccessors(node) print "MiniMax: Utility Value of Root Node: = " + str(best_val) # find the node with our best move best_move = None for elem in successors: # —> Need to propagate values up tree for this to work if elem.value == best_val: best_move = elem break # return that best value that we've found return best_move def max_value(self, node): print "MiniMax–>MAX: Visited Node :: " + node.Name if self.isTerminal(node): return self.getUtility(node) infinity = float('inf') max_value = –infinity successors_states = self.getSuccessors(node) for state in successors_states: max_value = max(max_value, self.min_value(state)) return max_value def min_value(self, node): print "MiniMax–>MIN: Visited Node :: " + node.Name if self.isTerminal(node): return self.getUtility(node) infinity = float('inf') min_value = infinity successor_states = self.getSuccessors(node) for state in successor_states: min_value = min(min_value, self.max_value(state)) return min_value # # # UTILITY METHODS # # # # successor states in a game tree are the child nodes… def getSuccessors(self, node): assert node is not None return node.children # return true if the node has NO children (successor states) # return false if the node has children (successor states) def isTerminal(self, node): assert node is not None return len(node.children) == 0 def getUtility(self, node): assert node is not None return node.value

view raw

minimax.py

hosted with ❤ by GitHub

How-to:  To use this code, create a new instance of the Minimax object, and pass in your GameTree object. This code should work on any GameTree object that has fields for: 1) child nodes; 2) value. (That is, unless I made an error, which of course, is very possible)

After the Minimax object is instantiated, run the minimax() function, and you will see a trace of the program’s output, as the algorithm evaluates each node in turn, before choosing the best possible option.

What you’ll notice:  Minimax needs to evaluate **every single node** in your tree. For a small tree, that’s okay. But for a huge AI problem with millions of possible states to evaluate (think: Chess, Go, etc.), this isn’t practical.

How we solve:  To solve the problem of looking at every single node, we can implement a pruning improvement to Minimax, called Alpha-Beta.

Alpha-Beta Pruning Improvement

Essentially, Alpha-Beta pruning works keeping track of the best/worst values seen as the algorithm traverses the tree.

Then, if ever we get to a node with a child who has a higher/lower value which would disqualify it as an option–we just skip ahead.

Rather than going into a theoretical discussion of WHY Alpha-Beta works, this post is focused on the HOW. For me, it’s easier to see the how and work backwards to why. So here’s the quick and dirty implementation.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 ########################## ###### MINI-MAX A-B ###### ########################## class AlphaBeta: # print utility value of root node (assuming it is max) # print names of all nodes visited during search def __init__(self, game_tree): self.game_tree = game_tree # GameTree self.root = game_tree.root # GameNode return def alpha_beta_search(self, node): infinity = float('inf') best_val = –infinity beta = infinity successors = self.getSuccessors(node) best_state = None for state in successors: value = self.min_value(state, best_val, beta) if value > best_val: best_val = value best_state = state print "AlphaBeta: Utility Value of Root Node: = " + str(best_val) print "AlphaBeta: Best State is: " + best_state.Name return best_state def max_value(self, node, alpha, beta): print "AlphaBeta–>MAX: Visited Node :: " + node.Name if self.isTerminal(node): return self.getUtility(node) infinity = float('inf') value = –infinity successors = self.getSuccessors(node) for state in successors: value = max(value, self.min_value(state, alpha, beta)) if value >= beta: return value alpha = max(alpha, value) return value def min_value(self, node, alpha, beta): print "AlphaBeta–>MIN: Visited Node :: " + node.Name if self.isTerminal(node): return self.getUtility(node) infinity = float('inf') value = infinity successors = self.getSuccessors(node) for state in successors: value = min(value, self.max_value(state, alpha, beta)) if value <= alpha: return value beta = min(beta, value) return value # # # UTILITY METHODS # # # # successor states in a game tree are the child nodes… def getSuccessors(self, node): assert node is not None return node.children # return true if the node has NO children (successor states) # return false if the node has children (successor states) def isTerminal(self, node): assert node is not None return len(node.children) == 0 def getUtility(self, node): assert node is not None return node.value

view raw

alpha-beta.py

hosted with ❤ by GitHub

How-to:  This algorithm works the same as Minimax. Instantiate a new object with your GameTree as an argument, and then call alpha_beta_search().

What you’ll notice:  Alpha-Beta pruning will always give us the same result as Minimax (if called on the same input), but it will require evaluating far fewer nodes. Tracing through the code will illustrate why.

### Phenomenology (a.k.a – how will I perceive this, myself?)

This isn’t the most robust implementation of either algorithm (in fact it’s deficient in many ways), so I wouldn’t recommend it for industrial use.

However, this code should simply illustrate how each algorithm works, and it will provide output you can trace through and compare against–as long as you are able to construct the GameTree for your problem.

From there, it’s only a matter of time until you’ll understand it intuitively. This is one of those things that took a little while for me to grasp–so hopefully having a clear example will help others get there more quickly. Good luck.

## Recursively Parsing a List of Lists into a Game Tree Using Python

### Background

I’ve been working on a AI project today and came across this problem.

Given input data structured like so:

[‘A’, [‘B’, (‘D’, 3), (‘E’, 5)], [‘C’, [‘F’, [‘I’,(‘K’,0), (‘L’, 7)],(‘J’,5)], [‘G’, (‘M’,7), (‘N’,8)], (‘H’,4)]]

I need to parse and build tree which has an arbitrary branching factor, and values only at the leaves.

(As for why:  Later, I’ll be running Minimax and some other algorithms on this tree, in order to algorithmically determine the best possible game move. More on that in another post.)

This seemed like a good problem to solve recursively. And to avoid a soul-sucking debug session, I decided my goal was to solve it as succinctly as possible.

Here’s what I came up with. Why I’m posting: This seems like it would be a very common AI/Data-Structures problem, but my first few searches on the subject came up with nada. Nothing even closely related to the problem I’m solving. So doing my part to fix that now.

### Working Code

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 """ @author Tony Poerio @email tony@tonypoer.io tree_parser.py –> parse a nested data string into a tree. Only leaf nodes have values. I'm intending to running minimax algorithms on these trees for a competitive game AI Data should be in the following format: ['A', ['B', ('D', 3), ('E', 5)], ['C', ['F', ['I',('K',0), ('L', 7)],('J',5)], ['G', ('M',7), ('N',8)], ('H',4)]] Note that Leaves must be **tuples** Usage: python tree_parser.py [filename] File should have data in the format shown above. """ from ast import literal_eval import sys ########################## ###### PARSE DATA ######## ########################## def parse_data_as_list(fname): with open(fname, "r") as f: data_as_string = f.read() print data_as_string data_list = literal_eval(data_as_string) return data_list class GameNode: def __init__(self, name, value=0, parent=None): self.Name = name # a char self.value = value # an int self.parent = parent # a node reference self.children = [] # a list of nodes def addChild(self, childNode): self.children.append(childNode) class GameTree: def __init__(self): self.root = None def build_tree(self, data_list): """ :param data_list: Take data in list format :return: Parse a tree from it """ self.root = GameNode(data_list.pop(0)) for elem in data_list: self.parse_subtree(elem, self.root) def parse_subtree(self, data_list, parent): # base case if type(data_list) is tuple: # make connections leaf_node = GameNode(data_list) leaf_node.parent = parent parent.addChild(leaf_node) # if we're at a leaf, set the value if len(data_list) == 2: leaf_node.value = data_list return # recursive case tree_node = GameNode(data_list.pop(0)) # make connections tree_node.parent = parent parent.addChild(tree_node) for elem in data_list: self.parse_subtree(elem, tree_node) # return from entire method if base case and recursive case both done running return ########################## #### MAIN ENTRY POINT #### ########################## def main(): filename = sys.argv print "hello world! " + filename data_list = parse_data_as_list(filename) data_tree = GameTree() data_tree.build_tree(data_list) if __name__ == "__main__": main()

view raw

tree_parser.py

hosted with ❤ by GitHub

### Signing Out

Side note. I’m actually not sure what this tree (with weights only at the leaves) would be called technically. It reminds me of the tree made during Huffman Encoding, but it’s not quite a match for that since we aren’t summing the values in all parent nodes. If you know the technical name, let me know, so I can update.

## Experimenting with the Harris Corner Detector Algorithm in Matlab

### tl;dr

Example code to start experimenting with the Harris Corner Detection Algorithm on your own, in Matlab. And some of the results I obtained in my own testing.

### Corner Cases

Among the classic algorithms in Computer Vision is Harris Corner Detection. (For the original paper, from 1988, see here.) The problem it solves:  Given any image file, can you find which areas correspond to a corner with a high degree of certainty?

The answer is yes. And the algorithm is elegant. Essentially the steps are:

1. Convert your image to a Matrix, storing the pixel values by intensity (converting to B/W makes this easier)
2. Find the horizontal and vertical gradients of the image (essentially the derivative of pixel intensities). This will let us know where there are horizontal and vertical edges.
3. Scan the image getting groups of pixels for however wide an area you are concerned with, and perform a calculation to determine where the horizontal and vertical edges intersect. (This requires some relatively complex linear algebra, but I’m not focusing on the theory here, just the implementation.)

Recently, I was trying to implement my own version of the Harris Detector in Matlab, and ended up banging my head against the wall for a few hours while figuring out some of the subtler details the hard way.

Here’s the code I came up with, and some examples of the outputs. Grab the code from both gists below, and you can start experimenting on your own.

### Harris Algorithm

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 function [ x, y, scores, Ix, Iy ] = harris_corners( image ) %HARRIS_CORNERS Extracts points with a high degree of 'cornerness' from %RGB image matrix of type uint8 % Input – image = NxMx3 RGB image matrix % Output – x = nx1 vector denoting the x location of each of n % detected keypoints % y = nx1 vector denoting the y location of each of n % detected keypoints % scores = an nx1 vector that contains the value (R) to which a % a threshold was applied, for each keypoint % Ix = A matrix with the same number of rows and columns as the % input image, storing the gradients in the x-direction at each % pixel % Iy = A matrix with the same nuimber of rwos and columns as the % input image, storing the gradients in the y-direction at each % pixel % compute the gradients, re-use code from HW2P, use window size of 5px % convert image to grayscale first G = rgb2gray(image); % convert to double G2 = im2double(G); % create X and Y Sobel filters horizontal_filter = [1 0 –1; 2 0 –2; 1 0 –1]; vertical_filter = [1 2 1; 0 0 0 ; –1 –2 –1]; % using imfilter to get our gradient in each direction filtered_x = imfilter(G2, horizontal_filter); filtered_y = imfilter(G2, vertical_filter); % store the values in our output variables, for clarity Ix = filtered_x; Iy = filtered_y; % Compute the values we need for the matrix… % Using a gaussian blur, because I get more positive values after applying % it, my values all skew negative for some reason… f = fspecial('gaussian'); Ix2 = imfilter(Ix.^2, f); Iy2 = imfilter(Iy.^2, f); Ixy = imfilter(Ix.*Iy, f); % set empirical constant between 0.04-0.06 k = 0.04; num_rows = size(image,1); num_cols = size(image,2); % create a matrix to hold the Harris values H = zeros(num_rows, num_cols); % % get our matrix M for each pixel for y = 6:size(image,1)-6 % avoid edges for x = 6:size(image,2)-6 % avoid edges % calculate means (because mean is sum/num pixels) % generally, this algorithm calls for just finding a sum, % but using the mean makes visualization easier, in my code, % and it doesn't change which points are computed to be corners. % Ix2 mean Ix2_matrix = Ix2(y–2:y+2,x–2:x+2); Ix2_mean = sum(Ix2_matrix(:)); % Iy2 mean Iy2_matrix = Iy2(y–2:y+2,x–2:x+2); Iy2_mean = sum(Iy2_matrix(:)); % Ixy mean Ixy_matrix = Ixy(y–2:y+2,x–2:x+2); Ixy_mean = sum(Ixy_matrix(:)); % compute R, using te matrix we just created Matrix = [Ix2_mean, Ixy_mean; Ixy_mean, Iy2_mean]; R1 = det(Matrix) – (k * trace(Matrix)^2); % store the R values in our Harris Matrix H(y,x) = R1; end end % set threshold of 'cornerness' to 5 times average R score avg_r = mean(mean(H)); threshold = abs(5 * avg_r); [row, col] = find(H > threshold); scores = []; %get all the values for index = 1:size(row,1) %see what the values are r = row(index); c = col(index); scores = cat(2, scores,H(r,c)); end y = row; x = col; end

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 image = imread('your_image.png'); image = imresize(image, 0.75); # or however much you want to resize if your image is large [ x, y, scores, Ix, Iy ] = harris_corners( image ); figure; imshow(image) hold on for i = 1:size(scores,2) plot(x(i), y(i), 'ro', 'MarkerSize', scores(i) * 2); # you may need to play with this multiplier or divisor based on your image # I've used –> (/1000) to (* 10) end saveas(gcf,'your_image_with_corners.png'); hold off

### My Outputs

Here’s what you can expect to see. I’m coloring the corners RED, using circles that grow larger the more likely the area is to hold a corner. So, larger circles –> more obvious corners. (Also note that I’m downsizing my output images slightly, just to make computation faster. )

### Closing

That’s it. With this code, you can start experimenting with Harris Detectors in about 30 seconds. And hopefully the way I’ve written it is transparent enough to make it obvious what’s going on behind the scenes. Most of the implementations out there are somewhat opaque and hard to understand at a conceptual level. But I’m hoping that my contribution will make this all a little more straightforward to those just gettings started. Enjoy. -t