# 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. Commented Aug 17, 2023 at 20:04
• @koedem please see update above with performance data Commented Sep 5, 2023 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? Commented Sep 5, 2023 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? Commented Sep 5, 2023 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. Commented Sep 17, 2023 at 9:57