In this lecture, we'll implement the Minimax search for the example from the previous lecture. As a reminder, here's the search tree, with Minimax scores attached to those nodes. Let's go look at how we actually implement this. For our tree, we're using a modified version of the TreeNode and tree classes that we've seen before. The difference is that I've added a Minimax score field to the TreeNode, and I've added a property that lets us retrieve that Minimax score and to also set that Minimax score. So this way, the TreeNodes can hold their Minimax score as we do the Minimax search. I've also added a configuration class that is essentially a configuration of the game "board". I put board in quotes there. It's the bins, and how many things are in each bin. So it's just a list of bins, each of which is an int. The count of how many things are in that bin. We have a constructor, we pass in the bin contents, and then we just add those contents to our bin's list. We can get a read-only list of the bins. And this is a useful property to tell if the bins are empty, because that means that the game has just been lost. So all we do, is we go through each of the bins and if the bin value is greater than zero, there's something in it so we return False out of the property. If we get all the way past the loop, we never found a bin and that had something in it. So we return true, because the configuration is now empty. Over here in our main class, I have a couple of Static fields that I'm saving for efficiency. And this is just so I don't need to keep creating new lists of ints and configurations. I can just clear these lists instead of creating new lists and we'll see where I use both of those fields soon. In our min method, we build the game tree and then we run our Minimax method to attach scores to each of the nodes in the tree. After we're done doing that, we retrieve the children of the root. We say the MaxChildNode is the first child. So what we're doing, is we're assuming that the leftmost child is in fact the best choice. But we might find out we were wrong, so we go through the rest of the children. Notice, we start this for loop at one, and we check to see if that child's Minimax score is greater than the MaxChildNode we've saved so far. And if it is, we just found a new MaxChildNode, So we set MaxChildNode equal to the one we're currently looking at. When we're all done, all we have to do is, say, the best move is to configuration MaxChildNode value. So this piece, just finding the best child node, is pretty straightforward, as is this. These are the pieces that are Minimax search. To build the tree, we start by building the root node. So we have that in content's list, I clear the list, I add two and I add one. So that's the left bin and the right bin. And then I create a new configuration, which I've called the root configuration, and I pass in that list. So now, root configuration is a configuration object that has two bins whose contents are two and one. Now I need to go through and build the complete tree. So, here's my tree and the constructor for the tree requires that I pass in a configuration, so I do. I also have a node list and I am sort of using this like the search lists we've seen before. So I'm going to add a node to the list, and I'll pull a node from the front, and I'll expand its children, and I'll add them to the back, because I'm just going to do a breadth-first build of the tree. And once the node list is empty, I'm done expanding nodes and I've built my entire tree. So, I add the route to the node list, and while there's something to expand in the node list, I pull off the first node and I remove it from the node list. I now generate it's children by calling the get next configurations method that we'll look at soon. This is the method that says, given this current board configuration, what are all the next possible board configurations? And it returns that to us as a list of those configurations. And then for each one of them, I create a node from that configuration and I add that node to the tree and I add that node at the back of the node list, because I'm going to want to expand this configuration to all its next possible configurations until I run out of configurations. When I'm all done, I return the tree. The game tree has been built but there are no Minimax scores attached yet. Here's that method that generates all the next configurations. So, here's what I do. I get the bins from the current configuration and I'm going to go through each bin. So I'll start with the left-most bin and I set current bin count to be whatever is in that left-most bin. And while current bin count is greater than zero, I'll take one Teddy out of the bin and then I'll clear the contents and add the range of current bins. So I'm copying the existing configuration right here and then I change the one I just changed, and then I add that new configuration to the list. So basically, this inner while loop for a particular bin, it takes out one at a time, creating new configurations, and this for loop does that for each of the bins we have. In this particular case, we only have two. But in your programming assignment, you'll have more than two. So now, the Minimax search stuff. We pass in a tree which is really a node, but it's a root of a sub-tree that we're going to search, and we tell whether or not we're maximizing, because that will determine whether we're trying to pick the highest score of our children or the lowest score of our children. Now, I get all the children from this node that I passed in. If I have one or more children, then I'm going to loop over those children, and for each one, I'm going to make a recursive call to Minimax with that child and I toggle maximizing. Because as I move down one ply, if I'm currently maximizing, I should be minimizing, and if I'm currently minimizing, I should be maximizing. So that's an important piece of doing this. As we move down, we have to change whether or maximizing or minimizing. Once I've done all that, I set my beginning Minimax score. So if I'm maximizing, I say the best score I've found so far is the minimum possible integer. So the first time through this loop we're going to get to, I should replace this with something better. Now, I go through all the children of this node and if I'm maximizing, I check to see if the child I'm examining has a better score than the best score I've found so far. And if it does, then I'm going to change the best score I've found so far to the one I just found. If I'm minimizing, I use less than because I'm looking for a worse score. Finally, if I'm at a leaf node, leaf nodes are the base case for our recursion for this example, then I assign an actual score. So up to this point, All we're doing is comparing scores and picking the best one but we haven't actually assigned those zeroes and ones to the leaf nodes yet. So assigned Minimax score does that. We pass in a node and we pass on whether or not we're maximizing. If, in fact, the configuration is empty, then if we're maximizing, if we are at a maximizing ply when we got to empty bins, that means that the minimizing player, player two, took the last Teddy. So we set our score to one because we just won the game. If we're minimizing, then player one took the last Teddy on the previous ply and we set the Minimax Score to zero, because player one just lost the game. And that's it. That is the code to implement a Minimax search on the example we've been looking at. To recap, in this lecture, we learned how to implement a Minimax search and you'll actually extend this for the programming assignment for this module.
