Search: Horizon problem

[milix]

Hi all. I noticed this in my program: during a bullet game (1 min) in a slow hardware against a friend, AICE reached the following position:

[diag]r1bqkbnr/1p1p1ppp/p3p3/2p5/B2nP3/2N2N2/PPPP1PPP/R1BQK2R w KQkq - 0 6[/diag]
r1bqkbnr/1p1p1ppp/p3p3/2p5/B2nP3/2N2N2/PPPP1PPP/R1BQK2R w KQkq - 0 6

and here AICE did a 6-ply search and played 1. O-O which of course looses a piece. AICE's thinking was something like
1. O-O b5 2. Bb3 Nxf3 3. Qxf3 c4 4. e5, which is a 7-ply search due to the check extension in Nxf3. And then QS is called and sees no problem because of 4... cxb3 5. Qxa8 bxa2. Is this a bug or I missunterstood QS? If not, how you deal with such horizon problems?

[Tord Romstad]

Hi all. I noticed this in my program: during a bullet game (1 min) in a slow hardware against a friend, AICE reached the following position:

[diag]r1bqkbnr/1p1p1ppp/p3p3/2p5/B2nP3/2N2N2/PPPP1PPP/R1BQK2R w KQkq - 0 6[/diag]
r1bqkbnr/1p1p1ppp/p3p3/2p5/B2nP3/2N2N2/PPPP1PPP/R1BQK2R w KQkq - 0 6

and here AICE did a 6-ply search and played 1. O-O which of course looses a piece. AICE's thinking was something like
1. O-O b5 2. Bb3 Nxf3 3. Qxf3 c4 4. e5, which is a 7-ply search due to the check extension in Nxf3. And then QS is called and sees no problem because of 4... cxb3 5. Qxa8 bxa2. Is this a bug or I missunterstood QS?

Your QS is correct, I think. In the position after 4. e5, a conventional QS will not see that black wins a piece. Black has no capture which wins material. Only non-capturing moves like 4... Rb8 win for black, and most programs don't search such moves in the QS.

If not, how you deal with such horizon problems?

The most popular "solution" these days is to simply ignore the problems and hope that they disappear at bigger search depths. I think much more effort is spent on horizon problems in computer shogi, where such problems are more frequent and serious. With some luck you might be able to find some interesting ideas in computer shogi papers.

Tord

[Anonymous]

I think that it is not a bug. If you search just 6 plyes, the QS can't do miracles. This position needs more depth, to be correctly analized.
Maybe, you can consider to extend the search in some "strange" situation, like a piece offended by a pawn but not taken suddenly. But, in a bullet game, this could make you spend to much time.

Stefano

[Tord Romstad]

I think that it is not a bug. If you search just 6 plyes, the QS can't do miracles. This position needs more depth, to be correctly analized.
Maybe, you can consider to extend the search in some "strange" situation, like a piece offended by a pawn but not taken suddenly.

I know that SmarThink used to do something like this (perhaps it still does, I don't know): When the remaining depth is <= 2 plies, make a small extension for moves which attack a more valuable piece. I tried this in Glaurung some time ago, but it didn't work very well.

Tord

[Tony van Roon-Werten]

I think that it is not a bug. If you search just 6 plyes, the QS can't do miracles. This position needs more depth, to be correctly analized.
Maybe, you can consider to extend the search in some "strange" situation, like a piece offended by a pawn but not taken suddenly.

I know that SmarThink used to do something like this (perhaps it still does, I don't know): When the remaining depth is <= 2 plies, make a small extension for moves which attack a more valuable piece. I tried this in Glaurung some time ago, but it didn't work very well.

Tord

Alternatively, you can give a bonus/malus for hanging pieces in your evaluation. Smaller when it's a side to move piece, bigger when it's a sntm piece, even bigger if the piece is pinned and even bigger if there is more than one. ( But smaller of course if the other side also has hanging pieces except when there is a big difference in SEE values. )

Off coarse, this only works if you have this information available.

Some engines just ignore it. "quiescence is full of mistakes anyway, so why spend time improving it, I'd rather just search a ply deeper "

Tony

[diepeveen]

Hi all. I noticed this in my program: during a bullet game (1 min) in a slow hardware against a friend, AICE reached the following position:

[diag]r1bqkbnr/1p1p1ppp/p3p3/2p5/B2nP3/2N2N2/PPPP1PPP/R1BQK2R w KQkq - 0 6[/diag]
r1bqkbnr/1p1p1ppp/p3p3/2p5/B2nP3/2N2N2/PPPP1PPP/R1BQK2R w KQkq - 0 6

and here AICE did a 6-ply search and played 1. O-O which of course looses a piece. AICE's thinking was something like
1. O-O b5 2. Bb3 Nxf3 3. Qxf3 c4 4. e5, which is a 7-ply search due to the check extension in Nxf3. And then QS is called and sees no problem because of 4... cxb3 5. Qxa8 bxa2. Is this a bug or I missunterstood QS? If not, how you deal with such horizon problems?

Hi Milix,

Diep has hung piece code in its eval:

After o-o it sees at 5 ply it's losing a piece, though i also have to
debug a bit why the score is so little for diep's eval. probably too happy with passed pawns

00:00 150 6 0 (1) 1 (0,0) -1.925 Nd4xf3 Qd1xf3 (64)
00:00 275 11 0 (1) 1 (0,0) -1.299 Ng8-h6 Nf3xd4 (31) c5xd4 (31)
00:00 350 14 0 (1) 1 (0,0) -0.913 Bf8-d6
00:00 425 17 0 (1) 1 (0,0) -0.683 Ng8-f6
00:00 2200 88 0 (1) 2 (0,1) -1.622 Ng8-f6 d2-d3 (65)
++ d8-f6 procnr=0 terug=-1591 org=[-1622;-1621] newwindow=[-1622;520000]
00:00 6500 260 0 (1) 2 (0,1) -1.146 Qd8-f6 d2-d3 (65) Nd4xf3 (31) Qd1xf3 (31)
Qf6xf3 (31) g2xf3 (31)
++ b7-b5 procnr=0 terug=-762 org=[-1146;-1145] newwindow=[-1146;520000]
00:00 6166 370 0 (1) 2 (0,1) -0.762 b7-b5 Ba4-b3 (65) Nd4xb3 (31) a2xb3 (31)
00:00 12700 762 0 (1) 3 (0,2) 0.156 b7-b5 Ba4-b3 (66) Bc8-b7 (65)
00:00 21125 1690 0 (1) 4 (0,3) -0.435 b7-b5 Ba4-b3 (67) Bc8-b7 (66) d2-d3 (65)

00:00 44841 5381 0 (1) 5 (0,4) 0.245 b7-b5 Nf3xd4 (68) c5xd4 (67) Nc3xb5 (66) a
6xb5 (65) Ba4xb5 (31)
00:00 61600 8624 0 (1) 6 (0,5) 0.245 b7-b5 Nf3xd4 (69) c5xd4 (68) Nc3xb5 (67) a
6xb5 (66) Ba4xb5 (65)
++ d4-f3 procnr=0 terug=246 org=[245;246] newwindow=[245;520000]
00:00 63952 14709 0 (1) 6 (0,5) 0.317 Nd4xf3 Qd1xf3 (69) b7-b5 (69) Ba4-b3 (68)
c5-c4 (67) d2-d3 (66) c4xb3 (65) a2xb3 (31)
00:00 74300 25262 0 (1) 7 (0,6) 0.120 Nd4xf3 Qd1xf3 (70) b7-b5 (70) Ba4-b3 (69)
c5-c4 (68) Bb3xc4 (67) b5xc4 (66) d2-d3 (65) c4xd3 (31) c2xd3 (31)
00:01 74919 92151 0 (1) 8 (0,7) 0.918 Nd4xf3 Qd1xf3 (71) b7-b5 (71) d2-d3 (70)
b5xa4 (69) e4-e5 (68) Ra8-a7 (67) Bc1-e3 (66) d7-d6 (65)
00:02 79683 168132 0 (1) 9 (0,8) 0.428 Nd4xf3 Qd1xf3 (72) b7-b5 (72) Ba4-b3 (71
) c5-c4 (70) d2-d3 (69) c4xb3 (68) a2xb3 (67) Bc8-b7 (66) Bc1-f4 (65)
00:12 74003 914683 0 (1) 10 (0,9) 0.908 Nd4xf3 Qd1xf3 (73) b7-b5 (73) Nc3xb5 (7
2) a6xb5 (71) Ba4xb5 (70) Bc8-b7 (69) d2-d4 (68) Ng8-f6 (67) Bc1-g5 (66) Bf8-e7
(65)
++ b7-b5 procnr=0 terug=909 org=[908;909] newwindow=[908;520000]
00:23 74250 1759004 0 (1) 11 (0,10) 0.636 Nd4xf3 Qd1xf3 (74) b7-b5 (74) Nc3xb5
(73) a6xb5 (72) Ba4xb5 (71) Bc8-b7 (70) d2-d3 (69) Qd8-f6 (68) Qf3-g3 (67) Bf8-e
7 (66) a2-a4 (65)
++ b7-b5 procnr=0 terug=637 org=[636;637] newwindow=[636;520000]
00:33 74550 2528755 0 (1) 11 (0,10) 0.887 b7-b5 Ba4-b3 (74) Nd4xf3 (73) Qd1xf3
(72) c5-c4 (72) Bb3xc4 (71) b5xc4 (70) d2-d3 (69) Bc8-b7 (68) Bc1-f4 (67) Bf8-b4
(66) Qf3-g3 (65)

01:00 74636 4488658 0 (1) 12 (0,11) 1.081 b7-b5 Nf3xd4 (75) c5xd4 (74) Nc3xb5 (
73) Qd8-a5 (72) d2-d3 (71) a6xb5 (70) Ba4-b3 (69) Bc8-b7 (68) Bc1-f4 (67) Ng8-f6
(66) Qd1-f3 (65)

Now if i try a stupid beancounter:
finished 0 ply; nodes=27 time=0.01 nps=2700 score=0.-50
pvs=0 ab=0 q=27 futile=0
==> f8d6
finished 1 ply; nodes=120 time=0.01 nps=12000 score=0.150
pvs=1 ab=0 q=119 futile=3
==> f8d6 f1e1
finished 2 ply; nodes=395 time=0.01 nps=39500 score=0.065
pvs=3 ab=34 q=358 futile=28
==> f8d6 g1h1 d4f3
finished 3 ply; nodes=4488 time=0.01 nps=448800 score=0.-70
pvs=24 ab=355 q=4109 futile=2157
==> d8f6 a4b3 f8d6 f3d4
finished 4 ply; nodes=10196 time=0.01 nps=1019600 score=0.025
pvs=42 ab=1213 q=8941 futile=5348
==> f8e7 a4b3 g8f6 f3d4 c5d4
finished 5 ply; nodes=51189 time=0.03 nps=1706300 score=0.000
pvs=108 ab=5862 q=45219 futile=25218
==> b7b5 f3d4 c5d4 c3b5 a6b5 a4b5
finished 6 ply; nodes=253977 time=0.16 nps=1587356 score=1.815
pvs=298 ab=43126 q=210553 futile=187617
==> b7b5 a4b3 d7d5 e4d5 d4b3 a2b3 e6d5
finished 7 ply; nodes=748816 time=0.47 nps=1593225 score=0.000
pvs=435 ab=127147 q=621234 futile=602911
==> b7b5 a4b3 d4f3 d1f3 c5c4 e4e5 a8b8 c3e4 c4b3
finished 8 ply; nodes=809068 time=0.50 nps=1618136 score=2.025
pvs=508 ab=141529 q=667031 futile=645380
==> b7b5 a4b3 d4f3 d1f3 c5c4 e4e5 a8b8 c3e4 c4b3 c2b3
finished 9 ply; nodes=954420 time=0.59 nps=1617661 score=2.025
pvs=704 ab=173761 q=779955 futile=756390
==> b7b5 f3d4 c5d4 c3b5 a6b5 a4b5 a8a5 b5c4 d7d5 c4d3
finished 10 ply; nodes=1588009 time=0.94 nps=1689371 score=1.990
pvs=1207 ab=259349 q=1327453 futile=1059125

Hmm at 7 ply for some weird reason the score drops again,
perhaps some debugging needed there too

But well it gets 9 ply within 1 second, not even counting futile evaluated nodes which are also 1 million in total. Counting the futile evaluated nodes to the nps it would become 2.6 million / 0.94 seconds = 2.78 mln nps

This all single cpu k7 2.1Ghz in debug mode (diep in debug mode,
not the beancounter search).

So you see the real trick. Get a ply or 12-14