For fixed-depth search, how much is the efficiency different between odd and even moves?

Question

If a chess engine calculates in even depth, in the final position, it has to move again, whereas if it calculates at the odd depth, then the opponent has to move at the end of calculation (ignoring quiescence search here = no wild exchanges take place).

In these cases, does the expected strength of engine drastically differ? Meaning, would we get completely different "elo" formulas if we considered even and odd search depth separately?

It obviously makes no sense to compare engine of depth 5 with engine of depth 6, but I believe there would be a different gap from going even -> odd than odd -> even.

Answer 1

In even depth search in the final position, the first player does not move again, but internally it has the side to move. At depth 0 it will normally call qsearch().

For odd depth search in the final position the second player has the side to move internally but it will not make a move.

All of these searches do need another condition that is on search depth extensions like check, pawn_push_to_7th_rank and others.

I took stockfish code and disable qsearch() and extensions. Instead of calling qsearch() I just return evaluate(). Here are the results for depth 4 vs depth 3 and depth 5 vs depth 4 in 1k games.

D4 vs D3

Score of Stockfish 070122 d4 vs Stockfish 070122 d3: 715 - 247 - 38  [0.734] 1000
...      Stockfish 070122 d4 playing White: 357 - 120 - 23  [0.737] 500
...      Stockfish 070122 d4 playing Black: 358 - 127 - 15  [0.731] 500
...      White vs Black: 484 - 478 - 38  [0.503] 1000
Elo difference: 176.3 +/- 23.8, LOS: 100.0 %, DrawRatio: 3.8 %

D5 vs D4

Score of Stockfish 070122 d5 vs Stockfish 070122 d4: 665 - 279 - 56  [0.693] 1000
...      Stockfish 070122 d5 playing White: 357 - 118 - 25  [0.739] 500
...      Stockfish 070122 d5 playing Black: 308 - 161 - 31  [0.647] 500
...      White vs Black: 518 - 426 - 56  [0.546] 1000
Elo difference: 141.4 +/- 22.6, LOS: 100.0 %, DrawRatio: 5.6 %

Answer 2

Assuming there's no horizon effect, there should be no significant difference between a position with only the who to move being changed, although the initiative does have some difference in the evaluation, it's hard to program in a static position. (Since a move can both have a positive and negative effect, this can be ignored.)

Answer 3

What you describe is called the Odd-Even Effect, see https://www.chessprogramming.org/Odd-Even_Effect There are some observations one can make here. One is that in a plain alpha-beta implementation, going from an even to an odd ply will take a longer amount of time than going from an odd to an even ply.

This has to do with how the algorithm operates. I'll explain with a toy example, consider a depth 0 search. That is just an evaluation so 1 node. A depth one search will take 20 nodes, you will have to look at each move. However, look at the depth two search. If you search the best move first (which thanks to good move ordering heuristics you might well do), let's say 1.e4, then you will need to look at 20 replies, that's 21 nodes so far. For each other worse starting move, there exists a "refutation", i.e. a response move proving that this other starting move is no better than e4. So for each of those 19 moves you only need one response each, that would make it 38 nodes, a total of 59. As you can see here, from the even depth 0 to odd depth 1 the search amount increased by a factor of 20, from the odd depth 1 to even depth 2, only by a factor of 3. This pattern continues to higher depths.

And this is what you will actually observe with weak engines that just implement a plain alpha-beta search. With strong engines that does not really happen anymore though, since those don't have a uniform search depth in the first place. So if Stockfish searches depth 10 that does not mean it searches 10 ply variations in all parts of the tree, in important parts it might search 15 or 20 plies while in irrelevant parts of the tree it might reduce heavily and only search 5 plies deep, for instance when calculating a line that gives away the Queen. Naturally with this imbalanced a tree, the effect will be very small.

Now what about playing strength? Here is where my answer becomes a bit more vague and anecdotal. When you search an odd number of plies, you will be the last one to move. E.g. for depth 1 you make one move and the search ends. This means, a naive evaluation will give higher evaluations for you there and lower evaluations for even depths. This again is what you find in weak engines, depth 0 would be evaluated 0.00, depth 1 would be evaluated e.g. +0.20 after 1.e4 and then depth 2 would be evaluated 0.00 again, after e.g. 1.e4 e5. You can work around this with a tempo bonus as has been suggested in other answers. However, this still has an effect: Loosely speaking, on odd search depths the player to move thanks to the extra tempo can play more actively, since the opponent won't be able to respond on the last ply. With weak engines this can have minor beneficial effects, since playing actively generally speaking is a good thing in chess. So you will at times see engines playing stronger on odd depths than on even depths.

However, once again, if your engine is strong, not only will it naturally have good heuristics and evaluation functions that automatically make it play this actively, they also once again don't have a pronounced Odd-Even effect due to search extensions, reductions and all sorts of other search optimizations. So I would expect whatever effect there is in Stockfish, if any, to be much smaller than it would be in a much weaker engine.

One last thought, are even or odd ply searches more "efficient" in time to playing strength, in weak engines? Based on the above thoughts I would say, it is not clear. Odd depth searches take longer but also possibly produce slightly better quality moves. How this tradeoff evaluates likely differs from engine to engine, but that is entirely speculation.

Answer 4

You are correct that using the same position evaluation function would make a difference at odd depth compared to even depth. Indeed, in many (turn-based) abstract games including chess, the average board position favours the player who has the turn. The fact that there are exceptions to the average (called zugzwang) does not change the fact that tempo is beneficial on statistical average over all positions relevant to good play. This is precisely why Stockfish include a tempo bonus. You can see that it is small but positive (≈ 0.2 times the material value for a pawn at the start of the game), indicating that the designers of Stockfish found that SF does better than if the bonus was zero or too big.

Thus the expected strength of a good chess AI based on alpha-beta search should not differ much whether you cut off the evaluation at odd or even depth, precisely because its position evaluation function ought to already (statistically) correct for the difference in tempo.