5
$\begingroup$

I'm implementing a chess engine.

Like many engines, the search for the next best move is done with the alpha-beta algorithm. There are many improvements that can be made to make the algorithm faster and make it able to search deeper into the search tree.

I'm currently considering Iterative Deepening for move ordering so the final search tree hopefully comes close to a perfectly ordered tree. Before implementing this, I want to be somewhat assured that this approach is most likely to introduce an improvement.

It can be shown that the number of static evaluations in a perfectly ordered tree using alpha beta is:

$evals(b,d) = \begin{cases} 2b^{d/2} -1, \text{d is even} \\ b^{(d+1)/2} + b^{(d-1)/2} - 1 , \text{d is odd} \end{cases} $

where $b$ and $d$ are the branching factor and depth respectively. This is order $O(b^{d/2})$.

It is also easy to realise that the worst ordered tree has $ b^d$ static evaluations, which is the number of leafs in the search tree (early terminations such as checkmate are ignored for the analysis).

According to wikipedia the order is $O(b^{3d/4})$ for randomly ordered trees. I assume this is the order applicable to my current algorithm (as opposed to $b^d$ evaluations in the worst case).

If I want a search tree of depth $d$ that is close to being a perfectly ordered tree, I would need to compute the perfectly ordered search tree of depth $d -1$ first (you smell the recursion).

I think it is possible to determine if Iterative Deepening is beneficial or not in two ways.

A somewhat informal way is assuming that Iterative Deepening always result in perfectly ordered trees and proving that

$\sum\limits_{i = 1}^d evals(b,d) < \text{average number of evaluations}$

I can not find a formula to determine the number of average evaluations.

A somewhat formal way is using complexity theory and proving that the order of evaluations in the Iterative deepening algorithm (which is??) is better than $O(b^{3d/4})$.

$O(\sum\limits_{i = 1}^d evals(b,d)) + O(b*\log(b)) < O(b^{3d/4})$

$O(b*\log(b))$ is the order of the sorting algorithm used to sort the moves according to their evaluations.

I don't require a full proof perse. It would be nice to hear if my thoughts are correct or not. Any references that discuss this and/or confirm the benefits of this algorithm are also appreciated.

EDIT: I've ran some numbers in matlab and found that the method above results in less evaluations if and only if $b > 2 \wedge d > 0 \vee b = 2 \wedge d \geq 5$. I've also come to the realisation that using this method requires exponential memory and is therefore wiped from the table.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.