9 – Propagating Values Up the Tree

In order to propagate wins and losses up the game tree, to the point where a computer player can make a decision, we need to start at the bottom of the tree. Let’s start with the left side of the tree. In the left-most branch, O wins. In the next branch over, O never gets … Read more

8 – MIN and MAX Levels

With terminal node in our game tree. With a +1 if our computer player wins and a -1 if it loses. We’ve used squares to indicate the terminal nodes and put their scores inside them. We are going to assume that our opponent x is really smart and will always play to win. In other … Read more

7 – How Do We Tell the Computer Not to Lose_

In most situations in this game tree our computer player O wins. But in a few situations,the game ends with our opponent X winning at level five. If our computer player makes a poor choice for its first move, X can win no matter what O does. Clearly we never want our computer player to … Read more

6 – Building a Game Tree (Contd.)

Let’s keep expanding the nodes in order until we have fully expanded level three of our tree. As we see, some nodes have two children, others have three. Even so, we see that the exponential growth of the children makes it increasingly difficult to display the full tree on the screen at once. In level … Read more

5 – Which of These Are Valid Moves_ Solution

Okay, so remember that the pieces can move like a queen in chess, but can not pass through positions that have been previously played. Also, when a piece is moved it doesn’t leave a trail like the game snake, but just the last position is marked as impassable. So here are those resulting child nodes. … Read more

3 – Building a Game Tree

Now let’s use a simple two by three version of isolation to illustrate how to make a game tree that shows all the moves possible during a game. We will use this game tree to select moves which give the best guarantee of winning. Consider any field spot on the game board as unavailable. We … Read more

20 – Max Number of Nodes

Okay, after playing with five by five isolation for a bit. The average branching factor seems to be about 8. So we now get an estimate of 8 to the 25th nodes. >> That’s about 10 to the 22nd nodes. >> Great, that means we only have to wait for around 1.2 million years to … Read more

19 – The Branching Factor (Contd.)

What if we do average branching factor instead? >> That sounds like a good idea but, how do we do that? >> Just try it out. >> Sure, why not? I always say do the simple thing first and only add intelligence when necessary. Let’s write a quick computer game player that moves randomly and … Read more

17 – Number of Nodes in a Game Tree

How many nodes do you think the Minimax algorithm will need to visit in the game tree? Here’s some choices where b is the average branching factor, and d is the average depth. So we have bd, d to the power of b, d squared, and b to the power of d. Pick what you … Read more

16 – The Branching Factor

While the center position has 16 spaces in which it can move, most other positions have 12 or less. As the game plays, we will have less and less spaces our player can move. >> That means we can make a better estimate on how many nodes we have right? >> Yep, okay, we know … Read more

15 – Max Moves Solution

Assuming that the opponent is not in the way, the center position has a maximum potential moves with 16. Two vertically up. Two diagonally to the right. Two horizontally to the right. Two diagonally down to the right. Two down vertically. Two diagonally down to the left. Two to the left horizontally. And two diagonally … Read more

13 – Max Number of Nodes Visited

So far we’ve worked with an isolation board with only five possible moves. In searching to end game caused huge game trees that were hard to show on the screen. How bad will it get with an interesting game board? Well let’s pull up the five by five board Shelly and I were playing on. … Read more