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 we cannot have more than 25 moves in a game. That is the maximum depth our tree is going to be. And we already know how many moves can be done in the beginning, which leaves 23 moves left. We know that each move after the first two are generally going to have 12 or fewer moves available. We’ll call this the branching factor. In worse case, we can expect 25 times 24 times 12 to the 23rd n nodes in our game tree. Shelly, how many is that? >> More than 10 to the 27th power. >> Ouch, okay that really didn’t help. Perhaps we can improve our estimate more. >> Well, we know at the end of the game there have to be progressively fewer moves available. There are zero moves in the end, one move before that, a maximum of two before that, three before that, and so on. >> You’re right. So for the last few moves, assuming a branching factor of 12 is way too much. That would be around 10 to the 13th nodes. But the maximum it could be is 12 factorial, or about 5 times 10 to the 8th. I guess we could redo our estimate as 25 times 24 times 13 12s in a row, times 5 times 10 to the 8th. That’s approximately equal to 3 times 10 to the 23rd. That is better than 10 to the 25th, or the 10 to the 27th, but still seems like a gross overestimate as most branches will have much less than the maximum branching factor. >> Let’s see if the students have a better answer than we do.