iterative deepeniing and branching factor

[Tord Romstad]

I've never had a side to move bonus, except for pawn endings where the side to move determines whether a pawn is catchable, or whether a pawn is unstoppable due to opposition. But for normal positions, I don't do it because I know of no reliable way to do so. And with the depths we see today, and the extensions/reductions in use, it ends up being apples-to-oranges anyway...

I am not sure I quite understand what you mean here, but to me a side to move bonus is one of the most unquestionably "correct" evaluation terms in existence, apart from material. In almost all chess positions, having the move is an advantage.

How big the side to move bonus should be is a difficult question, however. Should it be a constant, or should it depend on other components of the evaluation? I currently use a constant value of 0.2 in the middle game and 0.08 in the endgame, but these numbers are completely untuned (the only thing I have verified is that these numbers perform better than no side to move bonus at all). Interesting ideas to play with would be to consider the king safety and/or passed pawn scores (if both sides have a strong king attack, having the move is usually more important, and similarly for positions where both sides have high passed pawn scores), or to let the side to move bonus depend on how open the position is.

Perhaps it would also be possible to determine good values of the side to move bonus experimentally: Start with a large set of quiescent positions, and search each position to depth N, first with white to move, then with black to move. Half of the median of the differences between the scores when white moves and when black moves would be a natural value to use for the side to move bonus.

True: For time managment reasons, one ply is probably a better increment than two plies. But I don't see any a priori reason to believe that an increment of exactly one ply is optimal - it is possible that a value of slightly above or below one ply would work better. It might also depend on the phase of the game, and on other considerations. For instance, at the end of an iteration, if you have some time left, but probably not quite enough to finish another iteration with a full ply more, it makes some sense to only increase the depth by only half a ply for the next iteration.

I have personally never tried anything else than exactly one ply per iteration, but I think it might be worth some experiments.

In Crafty it is trivial.

It's trivial in all programs. The only non-trivial thing is to find the time to test it, when there are always countless other things waiting to be tried.

Several years ago I tried several options, including 1/2 and 3/4 of a ply. In some cases it works better (those positions where iteration N+1 somehow blows up and takes way longer than expected). But in more cases, it was worse...

But did you try to use half a ply only at the last iteration, and only when there was not much left of the allocated time? This seems to me like an interesting thing to try. Another idea is to use more than one ply per iteration in simple endgames, where the branching factor is low. As has been pointed out elsewhere in the thread, an increment of two plies works well in checkers, so why not in simple chess endgames as well.

Tord

[bob]

I've never had a side to move bonus, except for pawn endings where the side to move determines whether a pawn is catchable, or whether a pawn is unstoppable due to opposition. But for normal positions, I don't do it because I know of no reliable way to do so. And with the depths we see today, and the extensions/reductions in use, it ends up being apples-to-oranges anyway...

I am not sure I quite understand what you mean here, but to me a side to move bonus is one of the most unquestionably "correct" evaluation terms in existence, apart from material. In almost all chess positions, having the move is an advantage.

How big the side to move bonus should be is a difficult question, however. Should it be a constant, or should it depend on other components of the evaluation? I currently use a constant value of 0.2 in the middle game and 0.08 in the endgame, but these numbers are completely untuned (the only thing I have verified is that these numbers perform better than no side to move bonus at all). Interesting ideas to play with would be to consider the king safety and/or passed pawn scores (if both sides have a strong king attack, having the move is usually more important, and similarly for positions where both sides have high passed pawn scores), or to let the side to move bonus depend on how open the position is.

Perhaps it would also be possible to determine good values of the side to move bonus experimentally: Start with a large set of quiescent positions, and search each position to depth N, first with white to move, then with black to move. Half of the median of the differences between the scores when white moves and when black moves would be a natural value to use for the side to move bonus.

True: For time managment reasons, one ply is probably a better increment than two plies. But I don't see any a priori reason to believe that an increment of exactly one ply is optimal - it is possible that a value of slightly above or below one ply would work better. It might also depend on the phase of the game, and on other considerations. For instance, at the end of an iteration, if you have some time left, but probably not quite enough to finish another iteration with a full ply more, it makes some sense to only increase the depth by only half a ply for the next iteration.

I have personally never tried anything else than exactly one ply per iteration, but I think it might be worth some experiments.

In Crafty it is trivial.

It's trivial in all programs. The only non-trivial thing is to find the time to test it, when there are always countless other things waiting to be tried.

Several years ago I tried several options, including 1/2 and 3/4 of a ply. In some cases it works better (those positions where iteration N+1 somehow blows up and takes way longer than expected). But in more cases, it was worse...

But did you try to use half a ply only at the last iteration, and only when there was not much left of the allocated time? This seems to me like an interesting thing to try. Another idea is to use more than one ply per iteration in simple endgames, where the branching factor is low. As has been pointed out elsewhere in the thread, an increment of two plies works well in checkers, so why not in simple chess endgames as well.


Tord

On my todo list is "adaptive iterative deepening" which would behave like you mention to some extent. That is, incrementing by more than a ply once some threshold branching factor is reached.

But I haven't done the "can I complete the next iteration" sort of thing since the late 1970's... I don't like the idea and have found that on occasion where I might say "OK, no hope to complete the next search given the current time limit, I stop..." Only to find that had I started that search iteration anyway, it would have quickly failed low and I would have avoided a game-losing blunder.

Whether that is right or not is unknown, but I've been doing it since somewhere around 1980 when Cray Blitz was "born" on the Cray-1.

My adaptive deepening idea stems from noticing that on occasion, you start N+1 and it takes _forever_ to get something back. It has proven helpful in those cases to try N+.5 in informal testing, as the N+.5 and then N+1 complete quicker together than N+1 by itself, because something new tactically is happening and N+1 move ordering is therefore busted.

[Michael Sherwin]

How big the side to move bonus should be is a difficult question, however. Should it be a constant, or should it depend on other components of the evaluation? I currently use a constant value of 0.2 in the middle game and 0.08 in the endgame, but these numbers are completely untuned (the only thing I have verified is that these numbers perform better than no side to move bonus at all).

RomiChess also gives a 0.2 move bonus. I did test other values and 0.2 was best.

[wgarvin]

So this "side to move" bonus would cause the engine to score positions at even depths where it is to move, at 0.4 pawns above positions at odd depths where the opponent is to move.

Is this basically pretending that the engine can do something, on average, worth 0.4 pawns in those positions?

Or is the real effect just to discourage decision-making based on odd-depth positions where the opponent was to move, preferring instead to aim for positions where its our turn again?


Also, is there any way to detect zugzwang positions in eval and turn it off for those? (I guess thats why you use a much smaller bonus in endgames). I read something about verified null-move pruning recently that led me to believe it could be used to detect some zugzwang positions, but only in the interior of the tree..

[Uri Blass]

I've never had a side to move bonus, except for pawn endings where the side to move determines whether a pawn is catchable, or whether a pawn is unstoppable due to opposition. But for normal positions, I don't do it because I know of no reliable way to do so. And with the depths we see today, and the extensions/reductions in use, it ends up being apples-to-oranges anyway...

I am not sure I quite understand what you mean here, but to me a side to move bonus is one of the most unquestionably "correct" evaluation terms in existence, apart from material. In almost all chess positions, having the move is an advantage.

How big the side to move bonus should be is a difficult question, however. Should it be a constant, or should it depend on other components of the evaluation? I currently use a constant value of 0.2 in the middle game and 0.08 in the endgame, but these numbers are completely untuned (the only thing I have verified is that these numbers perform better than no side to move bonus at all). Interesting ideas to play with would be to consider the king safety and/or passed pawn scores (if both sides have a strong king attack, having the move is usually more important, and similarly for positions where both sides have high passed pawn scores), or to let the side to move bonus depend on how open the position is.

Tord

Note only that intuitively it is not obvious that side to move bonus is productive.

The problem is that you do not evaluate a random position
and there are positions that can never be leaf position when it is white to move because white has a good capture and can be leaf position when it is black to move and in this case white is in trouble and white needs to escape.

I suspect that bonus for side to move helps more for programs that have checks in the qsearch because they have not leaf positions when the side to move is in check and is in trouble because of the check(the check may be checkmate or a fork).

Crafty does not do checks in the qsearch.

Last time that I tried bonus for the side to move I did not get clear results if the bonus helps or does not help and I decided not to have bonus to make things more simple.

Note also that a static bonus cannot be productive or counter productive if you have search that always stop at the same side to move(simple search with no extensions and no pruning and no qsearch always stops at the same side to move and it is also possible to have search with extensions and pruning that always stop at the same side to move if you are careful always to extend or prune even number of plies.


Uri

[ed]

I am not sure I quite understand what you mean here, but to me a side to move bonus is one of the most unquestionably "correct" evaluation terms in existence, apart from material. In almost all chess positions, having the move is an advantage.

How big the side to move bonus should be is a difficult question, however. Should it be a constant, or should it depend on other components of the evaluation? I currently use a constant value of 0.2 in the middle game and 0.08 in the endgame, but these numbers are completely untuned (the only thing I have verified is that these numbers perform better than no side to move bonus at all). Interesting ideas to play with would be to consider the king safety and/or passed pawn scores (if both sides have a strong king attack, having the move is usually more important, and similarly for positions where both sides have high passed pawn scores), or to let the side to move bonus depend on how open the position is.

[d]5rk1/p1qbpp2/3p1np1/1p6/2r1P3/1NN2PP1/PPP4Q/2KR4 w - -
An idea is to penalize the total score of the king safety (and/or passed pawns) for the colour that moves with 10-15-20-25%.

1.Rh1 looks dangerous but is leveled out by 1..Nh5, just decrease the king safety on the black king for 1.Rh1 with xx%.

Ed

[bob]

what am I missing?

white plays Rh1. Nh5 appears to just lose the knight to g4. Any knight move is embarassed by Qh8.

Why would you want to penalize the position after Rh1, as opposed to the position _before_ rh1 is played???

[ed]

what am I missing?

white plays Rh1. Nh5 appears to just lose the knight to g4. Any knight move is embarassed by Qh8.

Why would you want to penalize the position after Rh1, as opposed to the position _before_ rh1 is played???

The point is that after 1..Nh5 the huge king safety bonus (at least in my engine it is huge) totally has vanished. To overcome this kind of imbalances a bit one adds a penalty for the side to move.

Ed

[bob]

what am I missing?

white plays Rh1. Nh5 appears to just lose the knight to g4. Any knight move is embarassed by Qh8.

Why would you want to penalize the position after Rh1, as opposed to the position _before_ rh1 is played???

The point is that after 1..Nh5 the huge king safety bonus (at least in my engine it is huge) totally has vanished. To overcome this kind of imbalances a bit one adds a penalty for the side to move.

Ed

Here's mine:

first, for the original position with wtm:

Code: Select all

material evaluation.................  -6.30
development.........................   0.00
pawn evaluation.....................   0.19
passed pawn evaluation..............   0.00 (0.00)
passed pawn race evaluation.........   0.00
knight evaluation...................  -0.09
bishop evaluation...................   0.05
rook evaluation.....................   0.37
queen evaluation....................  -0.28
king evaluation.....................   1.29
combined evaluation.................   0.00
total evaluation....................  -5.32

then for the same position after white plays Rh1:

Code: Select all

material evaluation.................  -6.30
development.........................   0.00
pawn evaluation.....................   0.19
passed pawn evaluation..............   0.00 (0.00)
passed pawn race evaluation.........   0.00
knight evaluation...................  -0.09
bishop evaluation...................   0.05
rook evaluation.....................   0.55
queen evaluation....................  -0.28
king evaluation.....................   1.45
combined evaluation.................   0.00
total evaluation....................  -5.02

So Rh1 improved things a bit. Then after Rh1, Nh5

Code: Select all

material evaluation.................  -6.30
development.........................   0.00
pawn evaluation.....................   0.19
passed pawn evaluation..............   0.00 (0.00)
passed pawn race evaluation.........   0.00
knight evaluation...................   0.15
bishop evaluation...................   0.05
rook evaluation.....................   0.39
queen evaluation....................  -0.28
king evaluation.....................   1.29
combined evaluation.................   0.00
total evaluation....................  -5.06

So no real change after Nh5 which doesn't do much (IMHO) to help black. In this position, early iterations prefer g4 (my original plan) but later iterations switch to Nd5 instead. With black being better, but only -1.09...

I'm still missing why playing a strong move (Rh1) results in a worse score than not playing that move...

[ed]

what am I missing?

white plays Rh1. Nh5 appears to just lose the knight to g4. Any knight move is embarassed by Qh8.

Why would you want to penalize the position after Rh1, as opposed to the position _before_ rh1 is played???

The point is that after 1..Nh5 the huge king safety bonus (at least in my engine it is huge) totally has vanished. To overcome this kind of imbalances a bit one adds a penalty for the side to move.

Ed

Here's mine:

first, for the original position with wtm:

Code: Select all

material evaluation.................  -6.30
development.........................   0.00
pawn evaluation.....................   0.19
passed pawn evaluation..............   0.00 (0.00)
passed pawn race evaluation.........   0.00
knight evaluation...................  -0.09
bishop evaluation...................   0.05
rook evaluation.....................   0.37
queen evaluation....................  -0.28
king evaluation.....................   1.29
combined evaluation.................   0.00
total evaluation....................  -5.32

then for the same position after white plays Rh1:

Code: Select all

material evaluation.................  -6.30
development.........................   0.00
pawn evaluation.....................   0.19
passed pawn evaluation..............   0.00 (0.00)
passed pawn race evaluation.........   0.00
knight evaluation...................  -0.09
bishop evaluation...................   0.05
rook evaluation.....................   0.55
queen evaluation....................  -0.28
king evaluation.....................   1.45
combined evaluation.................   0.00
total evaluation....................  -5.02

So Rh1 improved things a bit. Then after Rh1, Nh5

Code: Select all

material evaluation.................  -6.30
development.........................   0.00
pawn evaluation.....................   0.19
passed pawn evaluation..............   0.00 (0.00)
passed pawn race evaluation.........   0.00
knight evaluation...................   0.15
bishop evaluation...................   0.05
rook evaluation.....................   0.39
queen evaluation....................  -0.28
king evaluation.....................   1.29
combined evaluation.................   0.00
total evaluation....................  -5.06

So no real change after Nh5 which doesn't do much (IMHO) to help black. In this position, early iterations prefer g4 (my original plan) but later iterations switch to Nd5 instead. With black being better, but only -1.09...

I'm still missing why playing a strong move (Rh1) results in a worse score than not playing that move...

If I understand your figures right 1.Rh5 improves with +0.30 from the start position and after 1..Nh5 the score hardly has changed.

Quite different in mine, the white_king_safety for 1.Rh5 is about 0.75 and after 1..Nh5 the white_king_safety score is about 0.30, a difference of 0.45 To overcome this kind of evaluation instabilities I suggest to penalize 1.Rh1 with (say) 20% resulting in the values 1.Rh1 (0.60) and 1..Nh5 (0.30).

In your case 1.Rh1 only gets 0.06 penalty (20% from 0.30) resulting in a 0.24 score which most probably means that 1.Rh1 is still the best move at depth-1.

Don't get me wrong, I don't have this code active, it's an undocumented feature that still needs to be tested.

I have Right_to_Move code in my program since the early start and although quite different than Tord I 100% agree with him that a program can't do without, the right to move is worth something.

Ed