How to implement iterative deepening with alpha beta pruning

Question

I'm writing a program to play Dots and Boxes and I want to increase my time efficiency by ordering the moves I consider in alphaBeta based on their heuristic values in a iterative deepening scheme. Essentially, I want to go into the search tree, increasing the depth with each iteration, and evaluate each node with alphaBeta. In each successive iteration, the order in which I consider nodes will be dictated by the heuristic values of the nodes from the previous iteration. However, I'm having trouble understanding how this would be implemented. Could someone provide pseudocode for how a standard alphaBeta program would be adapted to search using iterative deepening? Thank you!

Answer 1

Well, Iterative Deepening is not really difficult to implement. If you already have a function to perform a search, let's call it alphaBetaAtRoot, which performs a search with a fixed distance, you just call it repeatedly, starting with distance 1:

for(int distance = 1; distance < MAX_DISTANCE && !outOfTime(); distance++) {
  bestmove = alphaBetaAtRoot(position, distance);
}
play(bestmove);

What is important, though, is that you implement a Transposition Table. Otherwise, you will not benefit from a better move ordering, as each search will just start with zero knowledge.

Answer 2

I have found the following link: https://github.com/nealyoung/CS171/blob/master/AI.java I hope that helps you.