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!

Magulac

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.

Deferential

Thank you! I didn't realize the necessity of a transposition table. I've done some more reading and this has helped a lot. – Magulac

I'm not sure how well this works, because each incrementation of distance, you will search the previous depth again. For example, after searching everything at distance 1, you will have to research everything at distance one again before searching at depth 2. – Marriott

@DavidChopin It is a combination of two observations: First, move ordering is very important. Starting with the best move can save a significant part of the search tree. Second, as the search tree exponentially grows with the search depth, researching is less of an overhead, as it seems. In the end, the trees that you needs to search again are exponentially smaller then the tree at the highest level. – Barleycorn

Ah, good point. After searching a given depth, we can prune far more sibling nodes for any subsequent searches at a deeper depth I suppose. – Marriott

Answer 2

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

Tum

Welcome to SO. Please note that link-only answers do not fulfill the standards of this site. See stackoverflow.com/help/how-to-answer – Illsorted

Wow! Thank you so much! – Magulac