0:41

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.

Â