# Iterative deepening speed expectation

I have developed a chess engine with these features:

• alpha beta
• transposition tables
• iterative deepening
• use any prev result from transposition table as first move if the result cannot be used directly, e.g cutoffs or not deep enough.

The alpha beta algorithm is implemented so that check if calculated in each new node, then the legal moves are calculated progressively so that a cutoff will end new legal moves from being calculated. If no legal moves are found, it is either checkmate or stalemate depending on the previously calculated check.

The algorithm work logic wise as confirmed by letting it play against itself on different depths. Deeper versions bet more shallow ones at least 95% of the time, otherwise it's draw.

The problem is speed. On a standard computer I get these times per move (in seconds) for different depths:

{1: 0.0034837227599999986, 2: 0.013043862759999995, 3: 0.24758806587999999, 4: 1.7778337413599996, 5: 17.16384055096, 6: 70.89946676716}

I know that in ideal cases this grows as n**(d/2) where d is the depth and n is nr moves. Worst case is n**d.

So I fit a curve to match t+1=n**(alpha*d) where alpha is unknown. This gives alpha 0.17 which is less than 0.5 and not expected. Probably the number of values are too small to give an accurate estimate. But it's already taking more than a minute on depth 6! Should this be the case? I was expecting to be able to run to at least a depth of 10-15..

UPDATE

Here is data showing the performance of 3 different settings of the engine:

1.Plain alpha beta. No transpositions nor any move ordering

['depth', 'nstates', 'time/state', 'hits']
[5, 634505, 0.00032971293255529906, 0]

['depth', 'hits', 'cutoffs']
[1, 0, 43]
[2, 0, 135]
[3, 0, 6077]
[4, 0, 22345]
[5, 0, 0]

2.Alpha beta with transpositions

['depth', 'nstates', 'time/state', 'hits']
[5, 508015, 0.00017707277515624539, 159165]

['depth', 'hits', 'cutoffs']
[1, 0, 43]
[2, 0, 135]
[3, 1164, 4915]
[4, 2880, 18179]
[5, 155121, 0]

3.Alpha beta with transpositions and use best move in transpositions as first move

['depth', 'nstates', 'time/state', 'hits']
[5, 507076, 0.00020099950737759227, 158794]

['depth', 'hits', 'cutoffs']
[1, 0, 43]
[2, 0, 135]
[3, 1150, 4910]
[4, 2868, 18123]
[5, 154776, 0]

*nstates is the number of nodes traversed *time/state is the average time in seconds spent in each node

So start counting depth at 0 for the single top node, the fastest version above (3) takes over a minute on depth 5. I tried to run for depth 6 and it took about 10 times longer. Is this normal? Are the values above normal?

Observe, I'm not using bitboards yet! Not sure how much faster that will make it, but I'm in doubts.

• Can you post for reference how fast your plain alpha beta algorithm is? And maybe also not just times but node counts as well. A well implemented basic engine with these features should certainly be able to reach depth 8 or 9 within a minute, not just depth 6. Aug 17 at 20:04
• @koedem please see update above with performance data Sep 5 at 7:45
• Is this for the start position? I think the node counts look a bit high for that, but that might be due to no move ordering. One thing that is definitely slow is the time/state (usually states are called nodes in graph algorithm contexts like chess) or rather the more commonly used inverse nodes/second. Those are less than 10k/second if I read this right? Usually you would expect that in the millions, but maybe you are using a language like python or similar? Sep 5 at 9:09
• I am also a bit confused about the cutoffs column. Why are there 43 cutoffs at depth 1 already but none at depth 5? Possibly the values are misaligned by one row? Sep 5 at 9:13
• @koedem Thanks for that. I've read a bit about this now and I realize that Python is probably the biggest cause to the problem. I'll try to make it as fast as possible for python, then probably shift to C. Sep 17 at 9:57

This is completely normal if you are not using any advanced move pruning techniques. For an engine such as Stockfish, a search depth of 20 is completely reasonable. If you look at the n^(d/2) best scenario case for depth 20, assuming n = 30, you get about 6 × 10^13, which is far beyond what you would expect any computer to be able to handle.

The reason depth 20 on Stockfish is possible is that Stockfish uses many techniques such as search extensions, advanced move ordering optimizations, and obviously way more things as well.

If you want your chess engine to perform better I suggest you implement MVV-LVA, null move pruning, and probably also killer move heuristic if you haven't already.