Negamax freezes

Question

In a game I've created Negamax works well for low depth searches but larger depth increases causes it to freeze. I thought about changing depth to type 'long' instead of 'integer' but not sure what else I can do. I know computation will take longer so it is possible it is calculating behind the scenes and I'm interpreting as freeze up. Any advice would be appreciated. In the game a player can only make 1 of 3 possible moves in a position and it is not like chess where there are large numbers of moves possible in anyone position and terminal position is difficult to reach.

Thanks

Daz

Answer 1

What counts as larger depth? Remember that these trees grow exponentially, so if you have 3 options on the first choice, you have 9 when you're 2 deep, 59049 options to check when you're 10 deep, and so on. Another possible reason for things to slow down drastically is if you start using the page file; that is if you're storing your whole tree and suddenly run out of Ram once you get to a "larger" depth. You can probably hear that, or see the blinking hard drive light, if that's contributing.

Your best bet is to get some feedback; get it to print out a new number every x thousand options it checks, so that you can find out instead of guessing at whether it's still trying and how far it has to go. Once you know what it's doing and assuming it is just munching through, look into something like alpha-beta pruning to prevent the tree from growing as quickly.