Side to Move Bonus---does it help?

Uri Blass · Post by **Uri Blass** » Fri Jun 19, 2009 8:24 am

I do not see how to use these value for more aggressive null move pruning.
The question if it is safe to prune is not the average case but the worst cases.

If in 10% of the cases the side to move is worth almost nothing(not more than the practical side to move bonus in Crafty) then it is not safe to do more aggressive pruning.

bob · Post by **bob** » Fri Jun 19, 2009 10:16 pm

mjlef wrote:
jwes wrote:
Eelco de Groot wrote:
jwes wrote:I ran a small experiment. I hacked crafty to save the position at the call to Evaluate once for every million calls. I then analyzed a file of grandmaster games at a low depth, and got roughly one position per game. I then analyzed these positions for 30 seconds with white to move and with black to move. I removed positions with either side in check and positions where a mate was found. I calculated the side to move bonus that would make the evaluations equal and it came out 2.44 pawns. This seemed bizarre but when I looked at a number of positions, there was that much difference in scores. I then reran the experiment taking only positions where the score was between alpha and beta and there are no more good captures. This time the side to move bonus was .93 pawns. I am sometimes amazed that alpha-beta works at all for chess. I would be interested in any explanations on how no or small side to move bonuses work when the actual value of the move is much higher.
It is interesting. Maybe as a supplement to what Bob is saying, you could run the same kind of test with Crafty only doing a nullmove search in the same positions that you let continue for thirty seconds and compare it with the outcome of a normal search for the side to move in the game run for thirty seconds. Would that not be the same test? 2.44 pawns seems a lot but what Robert says it would seem that it is the effect of side to move that is enlarged by a searchtree of approximately thirty seconds. It would imply that having the right to move twice in a row in a game is almost enough for making up the difference of a minor piece. Maybe it also means that deep nullmove searches should be treated different from shallow nullmove searches. I have never really tested anything like this, but if score differences grow quickly enough it would seem to mean that -a lot? - more moves get rejected because of a bad nullmove result on deeper searches. One may question if nullmove is always sound if nullmove enlarges the side to move advantage this much as your experiment seems to indicate it does, and this difference is proportional to searchdepth. (Like Robert say this side to move advantage is different from the side to move bonus, which has to be an average and only makes up for differences in evaluation in a one ply search, in my opinion).

I already do not trust deep nulmove searches much because they would in theory become more unrealistic with greater depth, but the difficulty is that if you replace it with other forward pruning techniques these have other drawbacks.

One would like to know what exactly the thoughts of programmers like Richard Lang and Ed Schröder are on this matter Because they are from the days before nullmove

Regards, Eelco
A few notes:
The actual difference is twice the side to move bonus, so for random positions when Evaluate is called, the difference is almost a rook.
I ran two more tests:
1. Searched the first test set for 1 second instead of 30 seconds. The side to move bonus dropped slightly to 2.29 pawns.
2. Searched positions taken from grandmaster games rather than after a short search. The side to move bonus was 1.09 pawns.
could these values be used to make a more agressive null search? If a double move is not worth this amount, might it be safe to prune?

The more I think about it, the more logical this big bonus is, but it doesn't apply to the evaluation in a chess engine.

In a GM game, every move carries a threat. If the opponent gets to reply, then he parries the threat and maintains equality. If the other side gets to move again (a second move in a row) then obviously that is worth a lot as now I can find yet another threat, and you can only defend against one of them, in most cases. This would be a huge advantage. And +1.x is not surprising.

But that will kill a chess program. It is certainly easy enough to change's Crafty's STM bonus. By the time you get to 0.50, it will be dropping pawns right and left as just reaching a terminal position with WTM will be +1.00 better than reaching a position with black to move.

Eelco de Groot · Post by **Eelco de Groot** » Sat Jun 20, 2009 2:00 am

jwes wrote: A few notes:
The actual difference is twice the side to move bonus, so for random positions when Evaluate is called, the difference is almost a rook.
I ran two more tests:
1. Searched the first test set for 1 second instead of 30 seconds. The side to move bonus dropped slightly to 2.29 pawns.
2. Searched positions taken from grandmaster games rather than after a short search. The side to move bonus was 1.09 pawns.

Thanks for the additional tests! It helps giving a better idea whether the advantage of doing two moves is rising so fast that deep nullmove searches should be treated differently from shallow nullmove searches if the score quickly becomes winning. I think your data after the one second searches shows that that is probably not the case, the eval typically is already high here after a one second search where you would just test for eval being higher than beta (instead of eval +/- some constant to make null move more or less aggressive).

The other difference you find probably means that positions when still on the board are more balanced than positions deeper in the searchtree, so the effect of an extra tempo is not yet directly as decisive. Whether that would mean that the nullmove eval is climbing faster for positions deeper in the tree I don't know and also not if that means you could use different constants for deeper searches.

I am still running a simple experiment, just searching a single position with a set of constants that I just threw together. Sorry Mark, in response to your question, so far I have not seen much that is very encouraging for improving the evaluation from this

. More interesting is however a big effect on the branching factor, I had not expected that to be this large

It does however not seem to lead to better evaluatons for Ancalagon

This may be dependant on the engine though, how your null move is tuned with R (The reduction in search depth of null move searches, and the main way of tuning null move) and on further tuning, as opposed to no tuning at all now, for the set of constants you would use. Especially in my second run the branching factor is so bad that you would think a better version should be possible at the other end.

The two runs differ in that in the first run I subtract a constant from beta to make null move more aggressive. In the second run I reversed the sign to add the constant, making null move less aggressive. The default is using no constants at all and seems to give the best evaluation.

The position is from the Hiarcs - Ktulu 9 game from Leiden ICC where there is a difficult to find continuation after Hiarcs' 14. Ba5.

The game again:

[Event "Blitz:80'"]
[Site "?"]
[Date "2009.06.06"]
[Round "?"]
[White "HIARCS 12.280 MP"]
[Black "Ktulu"]
[Result "1-0"]

1. e4 {B/0 0} c6 {8} 2. Nf3 {B/0 0} d5 {23} 3. e5 {B/0 0}
Bg4 {9} 4. Be2 {B/0 0} c5 {7} 5. O-O {B/0 0} Nc6 {10} 6. c4
{B/0 0} dxc4 {13} 7. Na3 {B/0 0} Qc7 {79} 8. Nxc4 {0.17/17
212} O-O-O {319} 9. a3 {0.57/17 0} Kb8 {(h5) 300} 10. b4
{0.61/18 160} e6 {126} 11. Bb2 {0.65/18 0} cxb4 {(Nh6) 83}
12. Qa4 {0.86/17 171} bxa3 {108} 13. Bc3 {0.78/17 0} h5
{99} 14. Ba5 {2.03/17 144} Nxa5 {132} 15. Nxa5 {2.02/18 0}
Bf5 {(Rd5) 38} (15... Rd5 16. Nxb7 Qd7 17. Qa6 Qxb7
18. Rfb1 Bb4 19. Qxb7+ Kxb7 20. Rxb4+ See analysis of this line below)
16. Rfb1 {2.84/17 142} Bxb1 {72} 17. Rxb1 {3.63/18 23} Rc8 {0}
18. Rxb7+ {4.35/18 270} Qxb7 {0} 19. Nxb7 {4.36/19 71} Rc1+ {172}
20. Bf1 {4.56/20 0} Kxb7 {88} 21. Nd4 {4.58/18 0} Ne7
{(Nh6) 136} 22. Qxa3 {4.88/18 95} Rc7 {55} 23. Qa6+
{4.96/18 0} Ka8 {107} 24. Nb5 {6.32/20 0} Rb7 {0} 25. g3
{6.58/20 101} 1-0

Hiarcs expected Ktulu to play 15... Rd5 and that seems critical, White's eval does not climb very quickly after this and especially a bit later on there seem to be some other critical moves that in a consisent PV you would probably have to find as well

The problem is it is 14 plies away from 14. Ba5...

After a possible main line

15... Rd5 16. Nxb7 Qd7 17. Qa6 Qxb7
18. Rfb1 Bb4 19. Qxb7+ Kxb7 20. Rxb4+ Ka8

it seems you have to find 21.h3 to get an eval big enough to consider 14. Ba5 as winning. The object of the testposition is to get an eval that is dropping fast enough, from Black's point of view, to make finding 14. Ba5 feasible in a game if you have a high quality PV. So far a nine ply search after 20. Rxb4 seems the minimum and because this is (well mostly it is, but this is a bit blurred in Ancalagon) with a PV search (the function is called search_pv() in Tord's Glaurung) a nullwindow search probably needs more depth to find it in the game.

With the default I get the best result:

[D]6nr/pk3pp1/4p3/3rP2p/1R4b1/p4N2/3PBPPP/R5K1 b - -

Engine: Ancalagon 1.3 WS180 Build 147 (Athlon 2009 MHz, 256 MB)
by Romstad, Costalba, Kiiski, de Groot

2.00 0:00 -1.92 20...Kc6 21.Rxa3 (1.503) 6

2.00 0:00 -1.91 20...Kc8 (4.312) 18

2.00 0:00 -1.91 20...Ka8 (5.093) 20

3.00 0:00 -1.49 20...Ka8 21.Rxa3 Ne7 (7.145) 28

3.00 0:00 -1.07 20...Kc6 21.Rxa3 Bxf3 22.Bxf3 (23.366) 83

4.00 0:00 -1.82 20...Kc6 21.Rxa3 a5 22.Rc3+ Rc5
23.Rxc5+ Kxc5 24.Rb5+ Kc6 25.Nd4+ Kc7
26.Rxa5 Bxe2 27.Nxe2 (75.208) 200

4.00 0:00 -1.50 20...Ka8 21.Rxa3 Ne7 22.Rc3 (84.275) 215

5.00 0:00 -1.21 20...Ka8 21.Rxa3 Ne7 22.Rc4 Rd7 (120.604) 266

6.00 0:00 -1.25 20...Ka8 21.Rxa3 Ne7 22.Rc4 Rd7
23.Rac3 (189.318) 336

7.00 0:00 -1.37 20...Ka8 21.Rxa3 Ne7 22.Ba6 Rd7
23.Bb5 Rc7 (279.569) 406

8.00 0:00 -1.09 20...Ka8 (443.400) 472

9.00 0:03 -1.78 {This is a low enough evaluation} 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rxa3 Ne7 24.Rba4 a6 25.Nc4 Bxc4
26.Rxc4 (1.890.100) 617

10.01 0:03 -1.78 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rxa3 Ne7 24.Rba4 a6 25.Nc4 Bxc4
26.Rxc4 (2.302.505) 632

11.01 0:05 -1.94 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Nc4 Ne7 24.Rxa3 Bxc4 25.Rxc4 Rb8
26.Rc7 Rb1+ 27.Kh2 (3.364.971) 672

12.01 0:08 -1.72 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rxa3 Ne7 24.Nc4 Bxc4 25.Rxc4 Rb8
26.Rg3 Nf5 27.Rgc3 (5.829.237) 720

13.01 0:15 -1.62 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rxa3 Ne7 24.Nc4 Bxc4 25.Rba4 Nc6
26.Rxc4 Rc8 27.Rf3 Rc7 (11.663.515) 750

14.01 0:37 -2.03 20...Ka8 21.h3 (28.198.076) 758

15.01 0:57 -2.00 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Ne4 Ne7 24.Rb3 Rd8 25.Rbxa3 a6
26.Nd6 f6 27.Re1 fxe5 28.Rxe2 Rxd6
29.Rxe5 (44.906.595) 785

16.01 2:11 -2.64 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Ne4 Ne7 24.Rxa3 Nc6 25.Rb2 Bc4
26.Nd6 Bd5 27.Rb7 Rd8 28.Rxf7 Nxe5
29.Rfxa7+ Kb8 30.f4 (102.388.833) 779

17.01 4:18 -2.49 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Ne4 Ne7 24.Rxa3 Nc6 25.Rb2 Bc4
26.Nd6 Bd5 27.Rb7 Rf8 28.f3 g5
29.Rxf7 Rxf7 30.Nxf7 (195.550.035) 757

18.01 7:22 -2.56 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rxa3 Nh6 24.Ne4 Rb8 25.Rxb8+ Kxb8
26.Nd6 g6 27.f4 a6 28.Kf2 Bb5
29.Nxb5 axb5 30.Rb3 Nf5 31.Rxb5+ Kc7
32.Rb3 (328.032.341) 741

19.01 15:14 -2.88 20...Ka8 21.h3 (676.680.867) 739

20.01 29:49 -3.00 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Ne4 Ne7 24.Nd6 Rb8 25.Rxb8+ Kxb8
26.Rxa3 Nf5 27.Nxf7 g6 28.Nd6 a6
29.Rc3 Bb5 30.Kh2 Ka7 31.Nxf5 gxf5
32.Kg3 (1.292.181.433) 721

21.01 58:34 -3.05 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Ne4 Ne7 24.Nd6 Rb8 25.Rxb8+ Kxb8
26.Rxa3 Nf5 27.Nxf7 g6 28.Rb3+ Kc7
29.Ng5 Kd7 30.Rb7+ Kc6 31.Rxa7 Bc4
32.f4 Kd5 33.Kf2 (2.511.041.983) 714

22.01 119:16 -3.09 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Ne4 Ne7 24.Nd6 Rb8 25.Rxb8+ Kxb8
26.Rxa3 g6 27.Rb3+ Ka8 28.Rb7 Nd5
29.Rb2 Bd3 30.Nxf7 Nf4 31.Nd6 Nd5
32.g3 g5 33.Rb7 (5.020.718.909) 701

23.01 259:03 -3.11 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Ne4 Ne7 24.Nd6 Rb8 25.Rxb8+ Kxb8
26.Rxa3 g6 27.Rb3+ Ka8 28.Rb7 Nd5
29.Rb2 Ba6 30.Nxf7 Nf4 31.Ng5 Nd3
32.Rb3 Nc1 33.Ra3 Bc4 (10.803.975.628) 695

24.01 957:23 -3.31 20...Ka8 21.h3 (39.799.280.781) 692

best move: Kb7-a8 time: 1058:29.156 min n/s: 695.077 nodes: 44.143.740.517

First I will show you what happens if you add a constant to make null move less aggressive, there is a dramatic increase in the time to reach any depth and unfortunately the evaluation does not improve. I had wanted to show you guys iteration No. 20 as final datapoint for build 156 but it is still not finished, so I just started to write my answer without it..

6nr/pk3pp1/4p3/3rP2p/1R4b1/p4N2/3PBPPP/R5K1 b - -

Engine: Ancalagon 1.3 WS180 Build 156 with less aggressive null move (Athlon 2009 MHz, 256 MB)
by Romstad, Costalba, Kiiski, de Groot

2.00 0:00 -1.92 20...Kc6 21.Rxa3 (1.503) 6

2.00 0:00 -1.91 20...Kc8 (4.312) 17

2.00 0:00 -1.91 20...Ka8 (5.093) 20

3.00 0:00 -1.49 20...Ka8 21.Rxa3 Ne7 (7.110) 28

3.00 0:00 -1.07 20...Kc6 21.Rxa3 Bxf3 22.Bxf3 (23.213) 82

4.00 0:00 -1.84 20...Kc6 21.Rxa3 Bxf3 22.Rc3+ Kd7
23.Bxf3 Rxd2 24.Rb7+ Ke8 25.Rxa7 (68.433) 190

4.00 0:00 -1.50 20...Ka8 21.Rxa3 Ne7 22.Rc3 (77.214) 205

5.00 0:00 -1.21 20...Ka8 21.Rxa3 Ne7 22.Rc4 Rd7 (114.887) 262

6.00 0:00 -1.25 20...Ka8 21.Rxa3 Ne7 22.Rc4 Rd7
23.Rac3 (201.653) 358

7.00 0:00 -1.03 20...Ka8 21.Rxa3 Ne7 22.Bc4 Rdd8
23.Rba4 Nc6 (318.947) 444

8.00 0:01 -1.09 20...Ka8 21.Ba6 Rc5 22.Rxa3 Rc1+
23.Bf1 Ne7 24.Rba4 Rc7 (982.375) 593

9.01 0:03 -1.43 20...Ka8 21.h3 (2.082.707) 647

10.01 0:05 -1.54 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rd4 Nh6 24.Rxa3 Bb5 25.Rb4 Rb8 (3.450.903) 685

11.01 0:08 -1.52 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rd4 Nh6 24.Rxa3 Bb5 25.Rb4 Rb8
26.Rab3 (6.521.736) 742

12.01 0:15 -1.78 20...Ka8 21.h3 (12.239.005) 788

13.01 1:37 -2.50 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Ne4 Nh6 24.Ra2 Bd3 25.Nc5 Rd8
26.Rxa3 Be2 27.Rba4 Rd1+ 28.Kh2 a6
29.Nxa6 (79.664.609) 821

14.01 2:24 -2.50 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Ne4 Nh6 24.Ra2 Bd3 25.Nc5 Rd8
26.Rxa3 Be2 27.Rba4 Rd1+ 28.Kh2 a6
29.Nxa6 (114.655.602) 796

15.01 4:21 -2.52 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rxa3 Ne7 24.Ne4 Nc6 25.Rb2 Bc4
26.Nd6 Bd5 27.Rb7 Rf8 28.Rxf7 Rxf7
29.Nxf7 (208.686.107) 797

16.01 10:08 -2.54 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Ne4 Ne7 24.Rxa3 Nc6 25.Rb2 Bc4
26.Nd6 Bd5 27.Rb7 Rf8 28.Rd7 f6
29.Rxg7 fxe5 (481.355.971) 791

17.01 30:06 -2.49 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rxa3 Ne7 24.Ne4 Nc6 25.Rb2 Bc4
26.Nd6 Bd5 27.Rb7 Rf8 28.f3 g5
29.Rxf7 Rxf7 30.Nxf7 (1.376.181.435) 761

18.01 82:35 -2.45 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rxa3 Ne7 24.Ne4 Nc6 25.Rb2 Bc4
26.Nd6 Bd5 27.Rb7 f6 28.Rxg7 fxe5
29.Ra4 Rb8 (3.695.811.155) 745

19.01 205:53 -2.64 20...Ka8 21.h3 (9.217.180.733) 746

The branching factor is terrible

Build 155 was with a subtracted set of constants and it certainly speeds things up compared also to the default. However also here the evaluation seems to suffer.

6nr/pk3pp1/4p3/3rP2p/1R4b1/p4N2/3PBPPP/R5K1 b - -

Engine: Ancalagon 1.3 WS180 Build 155 more aggressive null move (Athlon 2009 MHz, 256 MB)
by Romstad, Costalba, Kiiski, de Groot

2.00 0:00 -1.92 20...Kc6 21.Rxa3 (1.546) 7

2.00 0:00 -1.91 20...Kc8 (4.295) 19

2.00 0:00 -1.91 20...Ka8 (5.069) 23

3.00 0:00 -1.49 20...Ka8 21.Rxa3 Ne7 (6.634) 30

3.00 0:00 -1.07 20...Kc6 21.Rxa3 Bxf3 22.Bxf3 (22.312) 89

4.00 0:00 -1.84 20...Kc6 21.Rxa3 Bxf3 22.Rc3+ Kd7
23.Bxf3 Rxd2 24.Rb7+ Ke8 25.Rxa7 (72.086) 209

4.00 0:00 -1.76 20...Ka8 21.Ba6 Rc5 22.Rxa3 (82.049) 228

5.00 0:00 -1.21 20...Ka8 21.Rxa3 Ne7 22.Rc4 Rd7 (120.115) 284

6.00 0:00 -1.25 20...Ka8 21.Rxa3 Ne7 22.Rc4 Rd7
23.Rac3 (167.682) 346

7.00 0:00 -1.07 20...Ka8 21.Rxa3 Ne7 22.d4 Bf5
23.Ng5 Nc6 (325.494) 452

8.00 0:01 -1.13 20...Ka8 21.Rb3 Ne7 22.Rbxa3 Nc6
23.Ra6 Rc8 24.d4 (562.898) 530

9.01 0:01 -0.84 20...Ka8 (975.800) 589

10.01 0:03 -0.84 20...Ka8 21.Rc4 Ra5 22.Rc8+ Kb7
23.Rf8 f6 24.Rf7+ Ka8 25.d4 fxe5
26.dxe5 g5 (1.987.701) 633

11.01 0:04 -0.84 20...Ka8 21.Rc4 Ra5 22.Rc8+ Kb7
23.Rf8 f6 24.Rf7+ Ka8 25.h3 Bf5
26.d4 fxe5 27.Nxe5 (2.810.112) 661

12.01 0:07 -1.13 20...Ka8 21.Rc4 (4.753.963) 670

13.01 0:36 -1.47 20...Ka8 21.Rc4 Nh6 22.h3 Rxd2
23.Nxd2 Bxe2 24.Ra4 a6 25.Nc4 Kb7
26.R1xa3 Kc6 27.Nd6 Rb8 (25.480.738) 705

14.01 0:40 -1.58 20...Ka8 21.Rc4 Nh6 22.h3 Rxd2
23.Nxd2 Bxe2 24.Rc3 Bb5 25.Rcxa3 a6
26.Ne4 Rd8 27.Nd6 Kb8 (29.242.870) 717

15.01 0:47 -1.52 20...Ka8 21.Rc4 Nh6 22.h3 Rxd2
23.Nxd2 Bxe2 24.Rc3 Rd8 25.Ne4 Nf5
26.Rcxa3 Rd7 27.Nd6 Nxd6 28.exd6 a6
29.Rg3 Rxd6 30.Rxg7 (34.557.011) 727

16.01 1:04 -1.76 20...Ka8 21.h3 (48.418.036) 745

17.01 1:50 -2.45 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Ne4 Ne7 24.Rxa3 Nc6 25.Rb2 Bc4
26.Nd6 Bd5 27.Rb7 f6 28.Rxg7 fxe5
29.Ra4 Rb8 (86.061.122) 779

18.01 3:07 -2.45 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Ne4 Ne7 24.Rxa3 Nc6 25.Rb2 Bc4
26.Nd6 Bd5 27.Rb7 f6 28.Rxg7 fxe5
29.Ra4 Rb8 (143.340.209) 765

19.01 3:57 -2.43 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rxa3 Ne7 24.Ne4 Nc6 25.Rb2 Bc4
26.Nd6 Bd5 27.Rb7 f6 28.Rxg7 fxe5
29.Ra4 Rb8 30.f3 (184.919.489) 779

20.01 5:27 -2.62 20...Ka8 21.h3 (253.416.237) 774

21.01 9:41 -2.47 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rxa3 Ne7 24.Ne4 Nc6 25.Rb2 Bc4
26.Nd6 Bd5 27.Rb7 Rf8 28.Rxf7 Rxf7
29.Nxf7 Kb7 30.Rg3 a5 31.f4 a4
32.Nd6+ Kb6 33.Rxg7 (449.021.427) 772

22.01 14:39 -2.33 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rxa3 Ne7 24.Ne4 Nc6 25.Rb2 Bc4
26.Nd6 Bd5 27.Rb7 Rf8 28.Rxf7 Rxf7
29.Nxf7 a5 30.Rg3 Ka7 31.Rxg7 a4
32.Rg3 Kb6 (684.218.591) 777

23.01 19:46 -2.39 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rxa3 Ne7 24.Ne4 Nc6 25.Rb2 Bc4
26.Nd6 Bd5 27.Rb7 Rf8 28.Kf1 f6
29.Rxg7 fxe5 30.Rc3 Rb8 31.Ke2 Rd8
32.Nc4 Nd4+ 33.Kd2 (924.078.765) 778

24.01 25:41 -2.41 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rxa3 Ne7 24.Nc4 Bxc4 25.Rxc4 Rb8
26.Rf3 Nf5 27.Rd3 a5 28.Rc7 Rb1+
29.Kh2 Rb7 30.Rc5 Ra7 31.Rb5 Rc7
32.Rxa5+ Kb7 33.Rb5+ Kc8 (1.201.626.828) 779

25.01 35:44 -2.45 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Rxa3 Ne7 24.Ne4 Nc6 25.Rb2 Bc4
26.Nd6 Bd5 27.Rb7 Rf8 28.Kh2 a5
29.Kg3 g6 30.Rxf7 Rxf7 31.Nxf7 Kb7
32.f3 Kb6 33.Kf4 Kc5 (1.671.100.490) 779

26.01 51:21 -2.64 20...Ka8 21.h3 (2.419.895.717) 785

27.01 218:21 -2.84 20...Ka8 21.h3 Rxd2 22.Nxd2 Bxe2
23.Ne4 Ne7 24.Rxa3 Nc6 25.Rb2 Bc4
26.Nd6 Bd5 27.Rb7 f5 28.Rxg7 Rb8
29.Kh2 a5 30.Rh7 Rb4 31.Ne8 Kb8
32.Nf6 Bc4 33.f4 h4 (9.150.735.346) 698

best move: Kb7-a8 time: 234:38.203 min n/s: 678.218 nodes: 9.548.040.405

27 plies deep where the version with less aggressive null move can't even reach twenty plies, after almost a full day and night of searching! Ed Schröder would call Build 155 a Schumacher version, like a similar Pro Deo that used to fly through the plies

It was not the most successful Pro Deo ever though...

This is my set of constants, they are probably much too much but this was just for testing the effect on search:

Code: Select all


  // Null move futility pruning. The idea is to tune null move searches with this but the present first set of constants
 // is not very good at all and only alters the branching factor.

  // NullMoveDepth&#58;                       0 ply        0.5 ply      1 ply        1.5 ply      2 ply        2.5 ply      3 ply        3.5 ply      4 ply        4.5 ply
  const Value NullMoveBetaMargins&#91;40&#93; = &#123; Value&#40;-4&#41;,   Value&#40;-2&#41;,   Value&#40;0&#41;,    Value&#40;0&#41;,    Value&#40;0&#41;,    Value &#40;0&#41;,   Value&#40;0x2&#41;,  Value&#40;0x4&#41;,  Value&#40;0x6&#41;,  Value&#40;0x8&#41;,
  //                                      5 ply        5.5 ply      6 ply        6.5 ply      7 ply        7.5 ply      8 ply        8.5 ply      9 ply        9.5 ply
	                                      Value&#40;0xA&#41;,  Value&#40;0xD&#41;,  Value&#40;0x10&#41;, Value&#40;0x14&#41;, Value&#40;0x18&#41;, Value&#40;0x1C&#41;, Value&#40;0x20&#41;, Value&#40;0x25&#41;, Value&#40;0x2A&#41;, Value&#40;0x2F&#41;,
  //                                      10 ply       10.5 ply     11 ply       11.5 ply     12 ply       12.5 ply     13 ply       13.5 ply     14 ply       14.5 ply
									      Value&#40;0x34&#41;, Value&#40;0x39&#41;, Value&#40;0x3F&#41;, Value&#40;0x45&#41;, Value&#40;0x4B&#41;, Value&#40;0x51&#41;, Value&#40;0x57&#41;, Value&#40;0x5D&#41;, Value&#40;0x63&#41;, Value&#40;0x69&#41;,
  //                                      15 ply       15.5 ply     16 ply       16.5 ply     17 ply       17.5 ply     18 ply       18.5 ply     19 ply       19.5 ply
									      Value&#40;0x6F&#41;, Value&#40;0x75&#41;, Value&#40;0x7B&#41;, Value&#40;0x81&#41;, Value&#40;0x87&#41;, Value&#40;0x8D&#41;, Value&#40;0x93&#41;, Value&#40;0x99&#41;, Value&#40;0x105&#41;,Value&#40;0x10B&#41; &#125;;

The constants are used in the null move search at this point in the code, after null move search has returned a nullValue, build 156 adds the NullMoveBetaMargins but subtracting, to get a more aggressive null move pruning, is probably the better approach:

Code: Select all

        pos.undo_null_move&#40;);

        if &#40;value_is_mate&#40;nullValue&#41;)
        &#123;
            /* Do not return unproven mates */
        &#125;
        else if (&#40;nullValue >= beta + NullMoveBetaMargins&#91;Min&#40;Max&#40;int&#40;NullMoveDepth&#41;, 0&#41;, 39&#41;&#93;) && verificationsearchValue >= beta&#41;
        &#123;
            if &#40;depth < 6 * OnePly&#41;
                return beta;

            // Do zugzwang verification search
            verificationsearchValue = search&#40;pos, ss, beta, depth-5*OnePly, ply, false, threadID&#41;;
            if &#40;verificationsearchValue >= beta&#41;
                return beta;
        &#125;

Eelco

Uri Blass · Post by **Uri Blass** » Sat Jun 20, 2009 5:46 am

bob wrote:
mjlef wrote:
jwes wrote:
Eelco de Groot wrote:
jwes wrote:I ran a small experiment. I hacked crafty to save the position at the call to Evaluate once for every million calls. I then analyzed a file of grandmaster games at a low depth, and got roughly one position per game. I then analyzed these positions for 30 seconds with white to move and with black to move. I removed positions with either side in check and positions where a mate was found. I calculated the side to move bonus that would make the evaluations equal and it came out 2.44 pawns. This seemed bizarre but when I looked at a number of positions, there was that much difference in scores. I then reran the experiment taking only positions where the score was between alpha and beta and there are no more good captures. This time the side to move bonus was .93 pawns. I am sometimes amazed that alpha-beta works at all for chess. I would be interested in any explanations on how no or small side to move bonuses work when the actual value of the move is much higher.
It is interesting. Maybe as a supplement to what Bob is saying, you could run the same kind of test with Crafty only doing a nullmove search in the same positions that you let continue for thirty seconds and compare it with the outcome of a normal search for the side to move in the game run for thirty seconds. Would that not be the same test? 2.44 pawns seems a lot but what Robert says it would seem that it is the effect of side to move that is enlarged by a searchtree of approximately thirty seconds. It would imply that having the right to move twice in a row in a game is almost enough for making up the difference of a minor piece. Maybe it also means that deep nullmove searches should be treated different from shallow nullmove searches. I have never really tested anything like this, but if score differences grow quickly enough it would seem to mean that -a lot? - more moves get rejected because of a bad nullmove result on deeper searches. One may question if nullmove is always sound if nullmove enlarges the side to move advantage this much as your experiment seems to indicate it does, and this difference is proportional to searchdepth. (Like Robert say this side to move advantage is different from the side to move bonus, which has to be an average and only makes up for differences in evaluation in a one ply search, in my opinion).

I already do not trust deep nulmove searches much because they would in theory become more unrealistic with greater depth, but the difficulty is that if you replace it with other forward pruning techniques these have other drawbacks.

One would like to know what exactly the thoughts of programmers like Richard Lang and Ed Schröder are on this matter Because they are from the days before nullmove

Regards, Eelco
A few notes:
The actual difference is twice the side to move bonus, so for random positions when Evaluate is called, the difference is almost a rook.
I ran two more tests:
1. Searched the first test set for 1 second instead of 30 seconds. The side to move bonus dropped slightly to 2.29 pawns.
2. Searched positions taken from grandmaster games rather than after a short search. The side to move bonus was 1.09 pawns.
could these values be used to make a more agressive null search? If a double move is not worth this amount, might it be safe to prune?
The more I think about it, the more logical this big bonus is, but it doesn't apply to the evaluation in a chess engine.

In a GM game, every move carries a threat. If the opponent gets to reply, then he parries the threat and maintains equality. If the other side gets to move again (a second move in a row) then obviously that is worth a lot as now I can find yet another threat, and you can only defend against one of them, in most cases. This would be a huge advantage. And +1.x is not surprising.

But that will kill a chess program. It is certainly easy enough to change's Crafty's STM bonus. By the time you get to 0.50, it will be dropping pawns right and left as just reaching a terminal position with WTM will be +1.00 better than reaching a position with black to move.

I do not agree that every move carries a threat but we are talking about average and significant part of the moves that threat to win something big can clearly influence the average.

I guess that the median of the side to move advantage is going to be clearly smaller and I guess that the difference between white to move and black to move is going to be less than a pawn in most cases(that means less than 0.5 pawn side to move advantage).

Uri

jwes · Post by **jwes** » Sat Jun 20, 2009 6:17 am

Uri Blass wrote:
jwes wrote:I ran a small experiment. I hacked crafty to save the position at the call to Evaluate once for every million calls. I then analyzed a file of grandmaster games at a low depth, and got roughly one position per game. I then analyzed these positions for 30 seconds with white to move and with black to move. I removed positions with either side in check and positions where a mate was found. I calculated the side to move bonus that would make the evaluations equal and it came out 2.44 pawns. This seemed bizarre but when I looked at a number of positions, there was that much difference in scores. I then reran the experiment taking only positions where the score was between alpha and beta and there are no more good captures. This time the side to move bonus was .93 pawns. I am sometimes amazed that alpha-beta works at all for chess. I would be interested in any explanations on how no or small side to move bonuses work when the actual value of the move is much higher.
I do not think that it seems bizarre.
Chess is a tactical game and in many position you threat to win material.

The actual value of the side to move is simply not relevant because there are non quiet positions that you cannot get as leaf position

1.e4 e5 2.Nf3 Qh4

The value of the side to move here is a queen but you simply never evaluate it as leaf position when white to move.

Uri

I am surprised at the size of the difference. I did not expect that average value of the move on the average when Evaluate is called would be about a rook. I ran another experiment where I output positions when Evaluate is called and neither side has a good capture, so they all could be leaf nodes. The difference was 1.5 pawns or a side to move bonus of .75 pawns.

wgarvin · Post by **wgarvin** » Sat Jun 20, 2009 6:54 am

bob wrote:The more I think about it, the more logical this big bonus is, but it doesn't apply to the evaluation in a chess engine.

In a GM game, every move carries a threat. If the opponent gets to reply, then he parries the threat and maintains equality. If the other side gets to move again (a second move in a row) then obviously that is worth a lot as now I can find yet another threat, and you can only defend against one of them, in most cases. This would be a huge advantage. And +1.x is not surprising.

But that will kill a chess program. It is certainly easy enough to change's Crafty's STM bonus. By the time you get to 0.50, it will be dropping pawns right and left as just reaching a terminal position with WTM will be +1.00 better than reaching a position with black to move.

Being able to make two moves in a row might be worth a large bonus, but like you say, it would make no sense to put that into eval. I think if you used this as the side-to-move bonus in eval, it would effectively make the engine assume that its opponent can be forced into zugzwang, and/or that the opponent will blunder away a tempo.

Its ridiculous, because the engine will not actually get to play two moves in a row! All we really want to do is reward the player who currently has the move, and the reason why this should be rewarded at all (as I argued earlier in the thread) is that the player making the current move will get to make (on average) 0.5 moves more than his opponent. So the bonus should be about half of the value of being able to play one move in a row. When viewed in that light, it seems obvious that the value should be quite small, probably less than the value of a tempo -- certainly way less than the value of two moves in a row. I don't understand the practical effect of the bonus (making the search tree smaller) but at least it makes sense to me that the bonus should be nonzero, but small.

Here again is the argument for the 0.5 moves more. If side-to-move will also get to play the final move (by delivering checkmate or forcing stalemate), then he gets N+1 moves before the end of the game, while the opponent gets only N replies. But if side-to-move does NOT play the final move, then both players have M remaining moves. If you assume both players have an equal chance (0.5) of winning, then side-to-move gets 0.5*(N+1)+0.5*M moves compared to the other player's 0.5*N+0.5*M moves. So on average, the side-to-move has 0.5 moves more than the opponent, giving him slightly more ability to influence the outcome of the game through his remaining moves. I think this is what the side-to-move bonus is supposed to approximate.

bob · Post by **bob** » Sat Jun 20, 2009 4:31 pm

Dann Corbit wrote:
Osipov Jury wrote:Perhaps the best realization of this issue (from one very strong engine):

stage = majors * 2 + minors;
phase = ((double)stage) / 24.0;
SideToMoveBonus = (int)((1.0 - phase) * 0.0 + phase * 9.0);
seems to me that this part:
(int)((1.0 - phase) * 0.0
is always going to equal zero. So why bother with that part of the calculation?

Doesn't hurt. Compiler will throw that away anyway since it does nothing.

However, just because "a very strong program" does this (different bonus for opening/ending) doesn't mean it is correct. I tested a _bunch_ of games to get to the current crafty approach of a 10 point bonus for MG and 16 for EG. And I tested each independently to optimize serially.

Eelco de Groot · Post by **Eelco de Groot** » Sat Jun 20, 2009 7:37 pm

Eelco de Groot wrote:
19.01 205:53 -2.64 20...Ka8 21.h3 (9.217.180.733) 746

The branching factor is terrible

Had to stop the analysis because no iteration No. 20 did appear. Not sure why this is because build 155 did go to plydepth 27. Build 156 stopped by me after 2051 minutes

19.01 205:53 -2.64 20...Ka8 21.h3 (9.217.180.733) 746

best move: Kb7-a8 time: 2051:56.437 min n/s: 713.225 nodes: 87.809.580.568

Eelco

jwes · Post by **jwes** » Sat Jun 20, 2009 8:03 pm

bob wrote:
Dann Corbit wrote:
Osipov Jury wrote:Perhaps the best realization of this issue (from one very strong engine):

stage = majors * 2 + minors;
phase = ((double)stage) / 24.0;
SideToMoveBonus = (int)((1.0 - phase) * 0.0 + phase * 9.0);
seems to me that this part:
(int)((1.0 - phase) * 0.0
is always going to equal zero. So why bother with that part of the calculation?
Doesn't hurt. Compiler will throw that away anyway since it does nothing.

However, just because "a very strong program" does this (different bonus for opening/ending) doesn't mean it is correct. I tested a _bunch_ of games to get to the current crafty approach of a 10 point bonus for MG and 16 for EG. And I tested each independently to optimize serially.

The value of the side to move is highly position dependent and I believe that if you set the the side to move bonus to the average value, it would drive the search to positions where the actual value is much lower, which would cause these positions to be significantly misevaluated.

wgarvin · Post by **wgarvin** » Sun Jun 21, 2009 3:18 am

jwes wrote:The value of the side to move is highly position dependent and I believe that if you set the the side to move bonus to the average value, it would drive the search to positions where the actual value is much lower, which would cause these positions to be significantly misevaluated.

I don't understand what is position dependent about it. Q-search should take care of that, leaving you to evaluate a position where you can probably only make a small positional gain. Shouldn't the value of being able to make one move in a quiet position, almost always be small?

Side to Move Bonus---does it help?

Re: Side to Move Bonus---does it help?

Re: Side to Move Bonus---does it help?

Re: Side to Move Bonus---does it help?

Re: Side to Move Bonus---does it help?

Re: Side to Move Bonus---does it help?

Re: Side to Move Bonus---does it help?

Re: Side to Move Bonus---does it help?

Re: Side to Move Bonus---does it help?

Re: Side to Move Bonus---does it help?

Re: Side to Move Bonus---does it help?