Problems with search

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

metax
Posts: 344
Joined: Wed Sep 23, 2009 5:56 pm
Location: Germany

Problems with search

Post by metax »

I currently have a very strange problem with my search. Doing extremely well in positions like the following, ...

[D]r1bqk2r/2p1bppp/p2p1n2/np2p3/P3P3/1B3N1P/1PPP1PP1/RNBQR1K1 b kq a3 0 9

...where it easily goes to depth 15-16 in 1 minute (I know this does not sound much, but for ChessMind it is :)) at 230k nodes per second.


However, in positions like this one...

[D]r3kb1r/1bqn1ppp/p2ppn2/1p4B1/3NPP2/P1N2Q2/1PP3PP/2KR1B1R w kq - 0 1

..., which is obviously originated from a 6.Lg5 Najdorf, the search is a complete mess:

Code: Select all

FEN: r3kb1r/1bqn1ppp/p2ppn2/1p4B1/3NPP2/P1N2Q2/1PP3PP/2KR1B1R w kq - 0 1 

ChessMind:
  5/18	00:01	     162.470	196.000	+0,14	Kc1b1 Sd7c5 Sd4b3 Sc5xe4 Sc3xe4
  5/20	00:01	     162.470	196.000	+0,42	f4f5 e6xf5 Lg5xf6 f5xe4 Sc3xe4 Sd7xf6
  5/20	00:01	     162.470	196.000	+0,54	Td1e1 e6e5 Lg5xf6 g7xf6 f4xe5 Lf8h6+
  5/20	00:02	     162.470	196.000	+0,70	Lf1e2 Dc7c5 Lg5xf6 g7xf6 Kc1b1
  6/20	00:03	     630.019	228.000	+0,40	Lf1e2 Dc7c5 Lg5xf6 g7xf6 Kc1b1 f6f5
  6/20	00:04	     630.019	228.000	+0,58	f4f5 Dc7c5 Lg5xf6 Sd7xf6 Kc1b1 e6e5
  7/23	00:07	   1.532.042	249.000	+0,51	f4f5 e6xf5 Lg5xf6 f5xe4 Sc3xe4 Sd7xf6 Se4xf6+
  7/23	00:08	   1.890.029	248.000	+0,54	Lf1e2 d6d5 Lg5xf6 Sd7xf6 e4xd5 Sf6xd5 Sc3xd5
  7/24	00:13	   3.150.059	258.000	+0,34	Lg5h4 Lf8e7 Lh4xf6 Sd7xf6 Kc1b1 00 Lf1e2
  7/24	00:14	   3.150.059	258.000	+0,51	Lg5xf6 g7xf6 Lf1d3 e6e5 f4xe5 d6xe5 Sd4f5
  8/24	00:16	   4.160.059	255.000	+0,28	Lg5xf6 g7xf6 Lf1d3 e6e5 f4xe5 d6xe5 Sd4f5 Lf8xa3
  8/24	00:19	   4.958.367	259.000	+0,27	Lf1e2 d6d5 Lg5xf6 Sd7xf6 e4e5 Sf6e4 Td1d3 000
  8/24	00:33	   8.398.674	250.000	+0,31	Kc1b1 d6d5 e4xd5 Sf6xd5 Sc3a2 Sd5e7 Df3b3 000
  8/25	00:38	   9.487.363	246.000	+0,56	Td1d2 e6e5 Sd4f5 Ta8c8 Lg5h4 Lb7c6 h2h3 Lc6b7
  8/25	00:44	  10.914.179	247.000	+0,64	g2g4 Ta8c8 Lg5xf6 g7xf6 Lf1e2 Lb7a8 h2h3 Lf8g7
  9/25	00:51	  12.601.292	248.000	+0,49	g2g4 Ta8c8 Lg5xf6 g7xf6 Lf1e2 Dc7b8 h2h3 Lf8g7 Kc1b1
Top
Aaron Becker
Posts: 292
Joined: Tue Jul 07, 2009 4:56 am

Re: Problems with search

Post by Aaron Becker »

This doesn't in itself indicate a problem with your engine. The second position is legitimately much harder to search. For example, on my machine stockfish searches the first position to depth 15 in 4.5s. To reach depth 15 on the second position takes 48s.
Top
User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 8:30 pm
Location: Chicago, Illinois, USA

Re: Problems with search

Post by michiguel »

metax wrote:I currently have a very strange problem with my search. Doing extremely well in positions like the following, ...

[D]r1bqk2r/2p1bppp/p2p1n2/np2p3/P3P3/1B3N1P/1PPP1PP1/RNBQR1K1 b kq a3 0 9

...where it easily goes to depth 15-16 in 1 minute (I know this does not sound much, but for ChessMind it is :)) at 230k nodes per second.


However, in positions like this one...

[D]r3kb1r/1bqn1ppp/p2ppn2/1p4B1/3NPP2/P1N2Q2/1PP3PP/2KR1B1R w kq - 0 1

..., which is obviously originated from a 6.Lg5 Najdorf, the search is a complete mess:

Code: Select all

FEN: r3kb1r/1bqn1ppp/p2ppn2/1p4B1/3NPP2/P1N2Q2/1PP3PP/2KR1B1R w kq - 0 1 

ChessMind:
  5/18	00:01	     162.470	196.000	+0,14	Kc1b1 Sd7c5 Sd4b3 Sc5xe4 Sc3xe4
  5/20	00:01	     162.470	196.000	+0,42	f4f5 e6xf5 Lg5xf6 f5xe4 Sc3xe4 Sd7xf6
  5/20	00:01	     162.470	196.000	+0,54	Td1e1 e6e5 Lg5xf6 g7xf6 f4xe5 Lf8h6+
  5/20	00:02	     162.470	196.000	+0,70	Lf1e2 Dc7c5 Lg5xf6 g7xf6 Kc1b1
  6/20	00:03	     630.019	228.000	+0,40	Lf1e2 Dc7c5 Lg5xf6 g7xf6 Kc1b1 f6f5
  6/20	00:04	     630.019	228.000	+0,58	f4f5 Dc7c5 Lg5xf6 Sd7xf6 Kc1b1 e6e5
  7/23	00:07	   1.532.042	249.000	+0,51	f4f5 e6xf5 Lg5xf6 f5xe4 Sc3xe4 Sd7xf6 Se4xf6+
  7/23	00:08	   1.890.029	248.000	+0,54	Lf1e2 d6d5 Lg5xf6 Sd7xf6 e4xd5 Sf6xd5 Sc3xd5
  7/24	00:13	   3.150.059	258.000	+0,34	Lg5h4 Lf8e7 Lh4xf6 Sd7xf6 Kc1b1 00 Lf1e2
  7/24	00:14	   3.150.059	258.000	+0,51	Lg5xf6 g7xf6 Lf1d3 e6e5 f4xe5 d6xe5 Sd4f5
  8/24	00:16	   4.160.059	255.000	+0,28	Lg5xf6 g7xf6 Lf1d3 e6e5 f4xe5 d6xe5 Sd4f5 Lf8xa3
  8/24	00:19	   4.958.367	259.000	+0,27	Lf1e2 d6d5 Lg5xf6 Sd7xf6 e4e5 Sf6e4 Td1d3 000
  8/24	00:33	   8.398.674	250.000	+0,31	Kc1b1 d6d5 e4xd5 Sf6xd5 Sc3a2 Sd5e7 Df3b3 000
  8/25	00:38	   9.487.363	246.000	+0,56	Td1d2 e6e5 Sd4f5 Ta8c8 Lg5h4 Lb7c6 h2h3 Lc6b7
  8/25	00:44	  10.914.179	247.000	+0,64	g2g4 Ta8c8 Lg5xf6 g7xf6 Lf1e2 Lb7a8 h2h3 Lf8g7
  9/25	00:51	  12.601.292	248.000	+0,49	g2g4 Ta8c8 Lg5xf6 g7xf6 Lf1e2 Dc7b8 h2h3 Lf8g7 Kc1b1
You think you have a problem?

Gaviota takes 40s to reach ply 10 in the first position and 66s in the second one (at 300 knps in AMD 2.4 Ghz 1 core 32 bits).

My search always sucked big time and I may have to do something about it.

Miguel
Top
jwes
Posts: 778
Joined: Sat Jul 01, 2006 7:11 am

Re: Problems with search

Post by jwes »

Do you output statistics on reductions, extensions, fail high first rates, null move cutoffs, etc? These can be very useful to show what part of your search needs to be improved most.
Top
metax
Posts: 344
Joined: Wed Sep 23, 2009 5:56 pm
Location: Germany

Re: Problems with search

Post by metax »

michiguel wrote:You think you have a problem?

Gaviota takes 40s to reach ply 10 in the first position and 66s in the second one (at 300 knps in AMD 2.4 Ghz 1 core 32 bits).

My search always sucked big time and I may have to do something about it.

Miguel
My problem is not only the depth itself - when the engine plays no extremely bad moves, that is OK. But moves like Bh4, Rd2 and Re1 should NOT be a PV at all if the depth is greater than, say, 4! These moves are simply bad!

Could you post the analysis of Gaviota for this position, please? Even if your depth is roughly the same - I'm almost sure it will not consider moves as Bh4 or Rd2... this annoys me.
Top
metax
Posts: 344
Joined: Wed Sep 23, 2009 5:56 pm
Location: Germany

Re: Problems with search

Post by metax »

I just wondered if there was a bug in the root search:

Code: Select all

7/23   00:08      1.890.029   248.000   +0,54   Lf1e2 d6d5 Lg5xf6 Sd7xf6 e4xd5 Sf6xd5 Sc3xd5
  7/24   00:13      3.150.059   258.000   +0,34   Lg5h4 Lf8e7 Lh4xf6 Sd7xf6 Kc1b1 00 Lf1e2
Same depth, lower evaluation, but the PV is changed... I think this is because after a null-window search I do not check properly if the result is higher again...

This is also a problem - many null-window searches fail high but the result does not which wastes a lot of time... this is probably a search stability issue.
Top
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Problems with search

Post by Sven »

metax wrote:
michiguel wrote:You think you have a problem?

Gaviota takes 40s to reach ply 10 in the first position and 66s in the second one (at 300 knps in AMD 2.4 Ghz 1 core 32 bits).

My search always sucked big time and I may have to do something about it.

Miguel
My problem is not only the depth itself - when the engine plays no extremely bad moves, that is OK. But moves like Bh4, Rd2 and Re1 should NOT be a PV at all if the depth is greater than, say, 4! These moves are simply bad!

Could you post the analysis of Gaviota for this position, please? Even if your depth is roughly the same - I'm almost sure it will not consider moves as Bh4 or Rd2... this annoys me.
Your search returns the following moves as the final PV moves per iteration (omitting intermediate best moves which were then improved by other moves searched later):

5: Be2
6: f5
7: Bxf6
8: g4
9: g4 (iteration probably not completed before timeout)

So the engine does frequently change its mind. But none of these moves is a bad move. The moves you have critized were only intermediate best moves, but even these are not complete rubbish, e.g. Bh4 prepares g4-g5 and Rd2 prepares doubling of rooks. Be aware that the given position is indeed a difficult one with few immediate tactics and many playable moves which are no obvious losers.

This is Delfi 5.1 (CCRL 40/40=ELO 2732) analysis output for your second position:
[D]r3kb1r/1bqn1ppp/p2ppn2/1p4B1/3NPP2/P1N2Q2/1PP3PP/2KR1B1R w kq - 0 1[/D]

Code: Select all

 14	+0.16	54.4M	0:49.21	f5 e5. Nb3 Be7. h4 O-O. Kb1 Nc5. Nxc5 dxc5. g4 Rfd8. Nd5 Nxd5. exd5 Rd6.
 13	+0.21	31.0M	0:28.40	f5 e5. Nb3 Be7. h4 O-O. Kb1 Nc5. Nxc5 dxc5. Be2 h6. Be3 Rfd8.
 12	+0.16	16.5M	0:15.42	f5 e5. Nb3 Be7. h4 O-O. Kb1 Rfd8. Bd3 Nc5. g4 Nxd3. Rxd3
 12	+0.13	14.0M	0:13.10	g4 Be7. Bg2 O-O. Rhe1 Nb6. Bh4 Rac8. g5 Nfd7. Kb1 Nc4.
 11	+0.21	7.7M	0:07.20	g4 Be7. Bg2 O-O. Rhe1 Nc5. Kb1 Rfc8. Qe2 Rab8. h4
 11	+0.17	5.3M	0:04.81	f5 e5. Nb3 Be7. h4 Rd8. Kb1 O-O. Bd3 Nc5. g4 Nxd3. Rxd3
 10	+0.26	2.7M	0:02.50	f5 e5. Nb3 Be7. h4 Rc8. Bd3 O-O. Kb1 Nc5. Nxc5 Qxc5.
  9	+0.29	2.1M	0:01.90	f5 e5. Nb3 Be7. Be2 O-O. Kb1 Rac8. Be3
  9	+0.20	1.1M	0:01.03	Be2 Be7. Qe3 O-O. Kb1 Rac8. Nb3 Nc5. Nxc5 Qxc5. Qxc5 Rxc5.
  8	+0.29	563538	0:00.53	Be2 Be7. Qe3 O-O. Kb1 Rac8. h4 Nc5.
  8	+0.23	468361	0:00.42	Kb1 Be7. g4 O-O. Bg2 Rac8. h4 Qc4.
  7	+0.32	144605	0:00.14	Kb1 Be7. g4 O-O. Bg2 Rac8. h4
  6	+0.38	57334	0:00.04	Kb1 Be7. Be2 O-O. Qe3 Rac8.
  5	+0.52	13277	0:00.01	Kb1 Be7. f5 e5. Nb3
Here Delfi considers nearly the same PV moves as your engine, and it also changes its mind a few times. Regarding all these intermediate best moves appearing in your search, this may be a move ordering issue.

So I think at least you're not too far off.

Sven
Top
User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 8:30 pm
Location: Chicago, Illinois, USA

Re: Problems with search

Post by michiguel »

metax wrote:
michiguel wrote:You think you have a problem?

Gaviota takes 40s to reach ply 10 in the first position and 66s in the second one (at 300 knps in AMD 2.4 Ghz 1 core 32 bits).

My search always sucked big time and I may have to do something about it.

Miguel
My problem is not only the depth itself - when the engine plays no extremely bad moves, that is OK. But moves like Bh4, Rd2 and Re1 should NOT be a PV at all if the depth is greater than, say, 4! These moves are simply bad!

Could you post the analysis of Gaviota for this position, please? Even if your depth is roughly the same - I'm almost sure it will not consider moves as Bh4 or Rd2... this annoys me.
Here it is,
Miguel

Code: Select all

       250   1:      0.0    +0.63  1.g4
      3772   2:      0.0    +0.21  1.Bd3 Nc5
     14980   3:      0.1    +0.27  1.Re1 Nc5 2.f5
     27416   4       0.1    -0.10  1.Re1 h6 2.Bh4 Nc5
     36725   4       0.1    -0.06  1.g4 h5 2.gxh5 Rxh5
     38302   4       0.1    +0.20  1.Bd3 Nc5 2.f5 Nxd3+ 3.Rxd3
     59044   4:      0.2    +0.20  1.Bd3 Nc5 2.f5 Nxd3+ 3.Rxd3
    104814   5       0.4    +0.20  1.Bd3 h6 2.Bh4 Nc5 3.Kb1 Nxd3 4.Bxf6
                                   gxf6 5.Rxd3
    138823   5:      0.5    +0.20  1.Bd3 h6 2.Bh4 Nc5 3.Kb1 Nxd3 4.Bxf6
                                   gxf6 5.Rxd3
    151556   6       0.5    +0.12  1.Bd3 h6 2.Bxf6 Nxf6 3.f5 Bc8 4.fxe6
                                   Bxe6
    329790   6:      1.1    +0.12  1.Bd3 h6 2.Bxf6 Nxf6 3.f5 Bc8 4.fxe6
                                   Bxe6
    513682   7       1.7    +0.05  1.Bd3 Be7 2.Kb1 h6 3.Bh4 Nc5 4.Ka1 Nxd3
                                   5.cxd3
   1036799   7       3.6    +0.28  1.f5 Ne5 2.Qf4 Bc8 3.Bxf6 gxf6 4.fxe6
                                   fxe6 5.Qxf6
   1149850   7:      3.9    +0.28  1.f5 Ne5 2.Qf4 Bc8 3.Bxf6 gxf6 4.fxe6
                                   fxe6 5.Qxf6
   1370512   8       4.7    +0.28  1.f5 Ne5 2.Qf4 Bc8 3.Bxf6 gxf6 4.fxe6
                                   fxe6 5.Qxf6
   1592012   8:      5.5    +0.28  1.f5 Ne5 2.Qf4 Bc8 3.Bxf6 gxf6 4.fxe6
                                   fxe6 5.Qxf6
   2144965   9       7.3    +0.30  1.f5 Ne5 2.Qf4 Bc8 3.Bxf6 gxf6 4.fxe6
                                   fxe6 5.Qxf6 Qg7
   2890581   9:      9.8    +0.30  1.f5 Ne5 2.Qf4 Bc8 3.Bxf6 gxf6 4.fxe6
                                   fxe6 5.Qxf6 Qg7
   4006004  10      13.5    +0.16  1.f5 Ne5 2.Qf4 Bc8 3.Bxf6 gxf6 4.fxe6
                                   fxe6 5.Qxf6 Qg7 6.Qf4
  11552125  10:     38.0    +0.16  1.f5 Ne5 2.Qf4 Bc8 3.Bxf6 gxf6 4.fxe6
                                   fxe6 5.Qxf6 Qg7 6.Qf4
  16381437  11      54.0    +0.53  1.f5 Ne5 2.Qf4 Ke7 3.Qh4 h6 4.Nf3 Rd8
                                   5.fxe6 fxe6 6.Nxe5 dxe5
  17148137  11:     56.5    +0.53  1.f5 Ne5 2.Qf4 Ke7 3.Qh4 h6 4.Nf3 Rd8
                                   5.fxe6 fxe6 6.Nxe5 dxe5
  25593290  12      83.4    +0.58  1.f5 Ne5 2.Qf4 Ke7 3.Qh4 h6 4.Nf3 hxg5
                                   5.Qxh8 Nxe4 6.Nxe5 Nxc3
  28150862  12:     91.7    +0.58  1.f5 Ne5 2.Qf4 Ke7 3.Qh4 h6 4.Nf3 hxg5
                                   5.Qxh8 Nxe4 6.Nxe5 Nxc3
  57229941  13     186.4    +0.51  1.f5 Ne5 2.Qf4 Be7 3.fxe6 O-O 4.exf7+
                                   Rxf7 5.Nf5 Raf8 6.Qh4 h6 7.Nxe7+ Qxe7
                                   8.Be3 Nxe4 9.Qxe7 Rxe7 10.Nxe4 Bxe4
                                   11.Rxd6
  70036508  13:    227.2    +0.51  1.f5 Ne5 2.Qf4 Be7 3.fxe6 O-O 4.exf7+
                                   Rxf7 5.Nf5 Raf8 6.Qh4 h6 7.Nxe7+ Qxe7
                                   8.Be3 Nxe4 9.Qxe7 Rxe7 10.Nxe4 Bxe4
                                   11.Rxd6
Top
metax
Posts: 344
Joined: Wed Sep 23, 2009 5:56 pm
Location: Germany

Re: Problems with search

Post by metax »

Thanks Miguel. Your output looks better at least for me - your engine is reaching iteration 11 in the same time as CM is just reaching iteration 9, not changing its mind too often and not reporting really bad moves.

I'll now fix the bug mentioned above and then I have to work on search stability because many moves which fail high in null-window search won't fail high in the research. That costs a lot of time.
Top
metax
Posts: 344
Joined: Wed Sep 23, 2009 5:56 pm
Location: Germany

Re: Problems with search

Post by metax »

I just saw that all PV moves in your output are researched, even if the score did not change at all to the last iteration (for example at iteration 8): This seems to cost time. Why are you researching the moves with exactly the same score? This would equal an aspiration window of 0...
Top

Return to “Computer Chess Club: Programming and Technical Discussions”