Another GHI example in SF (maybe)

Code, algorithms, languages, construction...
Post Reply
BB+
Posts: 1484
Joined: Thu Jun 10, 2010 4:26 am

Another GHI example in SF (maybe)

Post by BB+ » Wed Dec 30, 2015 3:49 am

If I am not mistaken, analysis of the recent Yu Yangyi versus Wesley So game can run into a graph history interaction example in Stockfish. Obviously these can be tough to reproduce (especially with SMP and TBs involved), but here's what I observed:
[White "Yu Yangyi"][Black "Wesley So"][FEN "6k1/r5p1/P1n5/8/R7/5PPK/4P2P/8 w - - 3 49"]
49. e4 Nb8 50. Rb4 Nxa6 51. Ra4 Ra8 52. Kg4 Nc7 53. Rxa8+ Nxa8 54. f4 Nb6 55. h4 Nc4 56. h5 Nd2 57. e5 Kf7 58. f5 Ne4 59. Kh4 Nd2 60. Kg5 Nf3+ 61. Kf4 Ng1 62. Kg4 Ne2 63. Kf3 Ng1+ 64. Kg2After the line 49. e4 Nb8 50. Rb4 Nxa6 51. Ra4 Ra8 52. Kg4 Nc7 53. Rxa8+ Nxa8, the score gets up to +10 rather quickly, but then becomes volatile, sometimes crashing to 0.00 around the one minute mark (though then sometimes returning back to +90). Black can make White dance around quite subtly: 54. f4 Nb6 55. h4 Nc4 56. h5 Nd2 57. e5 Kf7 58. f5 Ne4 59. Kh4 Nd2 60. Kg5 Nf3+ 61. Kf4 Ng1 62. Kg4 Ne2 63. Kf3 Ng1+ 64. Kg2, and it seems there are many chances for a repetition line to be spliced into the transposition table (again, SMP can make this worse, and as I didn't have the "latest" SF at hand in any event, I didn't bother to try to get a reproducible version). I think I started the analysis at move 54 when I first saw the problem.

BB+
Posts: 1484
Joined: Thu Jun 10, 2010 4:26 am

Re: Another GHI example in SF (maybe)

Post by BB+ » Wed Dec 30, 2015 6:24 am

To continue the winning line a bit more, 64. Kg2 Ne2 65. g4 Nd4 66. Kg3 Ne2+ 67. Kh4 Nd4 68. Kg5 Nf3+ 69. Kf4 with the White moves being forced I think. Even after 65. g4, I can get GHI with 65... Nf4+ shown as 0.00 sometimes.

syzygy
Posts: 148
Joined: Sun Oct 16, 2011 4:21 pm

Re: Another GHI example in SF (maybe)

Post by syzygy » Sun Jan 17, 2016 12:24 am

Starting from the position before 64.Kg4 and with an empty hashtable, my private engine still reports a draw score (wanting to play e.g. 62.Ke3 or 62.g4 or 62.e6+). Forcing Kg4 will make it see that white is winning. Taking back that move, it again shows a draw score.

That was with TBs. Without TBs, it wants to play 64.Kg4 with a very positive score.

Another try with TBs and now it shows a winning score for 62.Kg4. But most runs get stuck at +0.000.

hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Another GHI example in SF (maybe)

Post by hyatt » Sun Jan 17, 2016 5:37 pm

There's a simple solution that is easy to try. Replace the draft >= depth with draft == depth. It almost eliminates this 100%. But there is an absolutely huge cost. Crafty searches fine70 to depth 50 on my 1.7ghz macbook using one thread, in 5 seconds. It sees winning a pawn at depth=25 in 0 seconds. With the "fix", it reaches depth 27 in 70 seconds and does not yet see winning a pawn.

GHI is simply an issue that won't go away easily, and in general it is a good thing. The one thing this position leaves out is game history which has an effect on reps. I didn't run with the GHI "fix" as the search is too slow to even think about using that approach, but it would likely mitigate this even though there is a huge cost.

BTW, if you search the tree with perfect ordering, this won't happen. The worse the order, the more likely it is to happen. Old versions of Crafty used to solve fine70 at depth 17-18, the current version requires depth 25, because better move ordering reduces the GHI problems significantly.

Post Reply