Iterative deepening speed expectation

Question

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.

Answer 1

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.