Impossible perft question

Discussion of chess software programming and technical issues.

Moderator: Ras

User avatar
trojanfoe
Posts: 65
Joined: Sun Jul 31, 2011 11:57 am
Location: Waterlooville, Hampshire, UK

Impossible perft question

Post by trojanfoe »

After a couple of years of assuming my move generator was just perfect, I decided to add unit tests and low and behold it was broken! Anyway I used positions and perft numbers from the Chess Programming Wiki which revealed a couple of not-so-hard-to-fix bugs, however one appears to remain and I wondered if you guys have any idea where it might be, given the numbers involved.

Position 3 at depth 5 is giving me 674469 instead of 674624, which is pretty near miss at that depth.

[d]8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1

Any suggestions appreciated.
Andy
Top
User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 8:30 pm
Location: Chicago, Illinois, USA

Re: Impossible perft question

Post by michiguel »

trojanfoe wrote:After a couple of years of assuming my move generator was just perfect, I decided to add unit tests and low and behold it was broken! Anyway I used positions and perft numbers from the Chess Programming Wiki which revealed a couple of not-so-hard-to-fix bugs, however one appears to remain and I wondered if you guys have any idea where it might be, given the numbers involved.

Position 3 at depth 5 is giving me 674469 instead of 674624, which is pretty near miss at that depth.

[d]8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1

Any suggestions appreciated.
Andy
I am willing to bet that after black's c5, the engine may think bxc6 is a legal move but it is not (R checks!). Same with g4 fxg3, and e4 fxe3. This a typical problem.

Yo can debug very well with perftdiv (reports perft-1 after each move)

Gaviota's output in console is

Code: Select all

setboard 8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1
display
+-----------------+
| . . . . . . . . |
| . . p . . . . . |
| . . . p . . . . |
| K P . . . . . r |    Castling: 
| . R . . . p . k |    ep: -
| . . . . . . . . |
| . . . . P . P . |
| . . . . . . . . | [White]
+-----------------+

perftdiv 5
   -->   Rb4xf4       10776
   -->    e2-e4       36889
   -->    g2-g4       53895
   -->    e2-e3       45326
   -->    g2-g3       14747
   -->   Rb4-d4       59574
   -->   Rb4-e4       54192
   -->   Rb4-c4       63781
   -->   Rb4-b3       59719
   -->   Rb4-b2       48498
   -->   Rb4-a4       45591
   -->   Rb4-b1       69665
   -->   Ka5-a4       52943
   -->   Ka5-a6       59028
depth 5: leaves:     674624
seconds: 0.07 nps: 9637485.71
Miguel
Top
User avatar
trojanfoe
Posts: 65
Joined: Sun Jul 31, 2011 11:57 am
Location: Waterlooville, Hampshire, UK

Re: Impossible perft question

Post by trojanfoe »

michiguel wrote: I am willing to bet that after black's c5, the engine may think bxc6 is a legal move but it is not (R checks!). Same with g4 fxg3, and e4 fxe3. This a typical problem.
Indeed and this was the first bug I needed to fix. My move generator excludes pinned pieces and those are now correctly identified as 'en-passant pinned' which means they can move, but they cannot capture. However those are all depth-2 issues, not depth-5. Something's happening much later which I am not accounting for...

Thanks for confirming the expected nodes are correct and I'll look into perftdiv.
Top
User avatar
trojanfoe
Posts: 65
Joined: Sun Jul 31, 2011 11:57 am
Location: Waterlooville, Hampshire, UK

Re: Impossible perft question

Post by trojanfoe »

I've implemented a similar function in my test program, which should help me track down this issue. Thanks once again for the inspiration and providing a tool I can compare my own code against.

Code: Select all

$ build/ccore --debuglog -f '8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1' -d 5 perftdiv
ChessCore Test Tool (ccore). Copyright (c)2008-2013 Andy Duplain <andy@trojanfoe.com>
ChessCore v0.7.0 (1992) x64 Debug

Using log file /var/folders/dj/98h5kr9s0x5d6c14w7nx60qr0000gn/T/ccore.log
+---------------+
|-|.|-|.|-|.|-|.| ply=0 (wtm)
|.|-|p|-|.|-|.|-| flags=
|-|.|-|p|-|.|-|.| ep=0
|K|P|.|-|.|-|.|r| hmclock=0
|-|R|-|.|-|p|-|k| lastMove=null
|.|-|.|-|.|-|.|-|
|-|.|-|.|P|.|P|.|
|.|-|.|-|.|-|.|-|
+---------------+

          e3:        45315
          e4:        36881
          g3:        14736
          g4:        53885
         Rb1:        69651
         Rb2:        48488
         Rb3:        59706
         Ra4:        45579
         Rc4:        63769
         Rd4:        59555
         Re4:        54176
        Rxf4:        10759
         Ka4:        52942
         Ka6:        59027
 Total nodes:       674469
Top
User avatar
trojanfoe
Posts: 65
Joined: Sun Jul 31, 2011 11:57 am
Location: Waterlooville, Hampshire, UK

Re: Impossible perft question

Post by trojanfoe »

OK, after adding functionality to generate 'random' positions and comparing the perft results of Gaviota and ccore at depth 1, I have the following position:

[d]1N6/6k1/8/8/7B/8/8/4K3 w - - 19 103

Gaviota gives:

Code: Select all

perftdiv 1
   -->   Nb8-c6           1
   -->   Ke1-f2           1
   -->   Ke1-e2           1
   -->   Ke1-f1           1
   -->   Nb8-d7           1
   -->   Ke1-d2           1
   -->   Bh4-d8           1
   -->   Bh4-e7           1
   -->   Bh4-g5           1
   -->   Bh4-f6           1
depth 1: leaves:         10
And ccore gives:

Code: Select all

         Na6:            1
         Nc6:            1
         Nd7:            1
         Bf2:            1
         Bg3:            1
         Bg5:            1
         Bf6:            1
         Be7:            1
         Bd8:            1
         Kd1:            1
         Kf1:            1
         Kd2:            1
         Ke2:            1
         Kf2:            1
 Total nodes:           14
However I cannot see why ccore is wrong here...
Top
zullil
Posts: 6442
Joined: Tue Jan 09, 2007 12:31 am
Location: PA USA
Full name: Louis Zulli

Re: Impossible perft question

Post by zullil »

trojanfoe wrote:OK, after adding functionality to generate 'random' positions and comparing the perft results of Gaviota and ccore at depth 1, I have the following position:

[d]1N6/6k1/8/8/7B/8/8/4K3 w - - 19 103

Gaviota gives:

Code: Select all

perftdiv 1
   -->   Nb8-c6           1
   -->   Ke1-f2           1
   -->   Ke1-e2           1
   -->   Ke1-f1           1
   -->   Nb8-d7           1
   -->   Ke1-d2           1
   -->   Bh4-d8           1
   -->   Bh4-e7           1
   -->   Bh4-g5           1
   -->   Bh4-f6           1
depth 1: leaves:         10
And ccore gives:

Code: Select all

         Na6:            1
         Nc6:            1
         Nd7:            1
         Bf2:            1
         Bg3:            1
         Bg5:            1
         Bf6:            1
         Be7:            1
         Bd8:            1
         Kd1:            1
         Kf1:            1
         Kd2:            1
         Ke2:            1
         Kf2:            1
 Total nodes:           14
However I cannot see why ccore is wrong here...
Obviously ccore is correct here. But Gaviota is correct in the original position, as confirmed by Critter here:

Code: Select all

Critter v1.6a 64-bit, by Richard Vida
hardware POPCNT enabled
setboard 8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1 
info string Opening book: "book.cbk" - 57853 entries [native]
info string GTB Init OK (5 piece set)
info string Using 8 thread(s), 2048 MB hash LP=off

    A   B   C   D   E   F   G   H
  +---+---+---+---+---+---+---+---+
8 |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
7 |   |   | p |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
6 |   |   |   | p |   |   |   |   |
  +---+---+---+---+---+---+---+---+
5 | K | P |   |   |   |   |   | r |
  +---+---+---+---+---+---+---+---+
4 |   | R |   |   |   | p |   | k |
  +---+---+---+---+---+---+---+---+
3 |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
2 |   |   |   |   | P |   | P |   |
  +---+---+---+---+---+---+---+---+
1 |   |   |   |   |   |   |   |   |
  +---+---+---+---+---+---+---+---+
FEN: 8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1
Hashkey: caa1063a908431b4 mgpsq: -0.07
Pawnkey: 199b6ed82b5ef11f egpsq: +0.03
Mtrlkey: 14a12da0

divide 5
0x0002b759: Rxf4+ = 10776
0x0000b059: Rb1 = 69665
0x0000b259: Rb2 = 48498
0x0000b459: Rb3 = 59719
0x0000b619: Ra4 = 45591
0x0000b699: Rc4 = 63781
0x0000b6d9: Rd4 = 59574
0x0000b719: Re4 = 54192
0x00005620: Ka4 = 52943
0x00005a20: Ka6 = 59028
0x0000370c: e4 = 36889
0x0000350c: e3 = 45326
0x0000378e: g4 = 53895
0x0400358e: g3+ = 14747
674624 nodes in 13 ms, 48187 knps
Good luck finding the bug.
Top
lucasart
Posts: 3241
Joined: Mon May 31, 2010 1:29 pm
Full name: lucasart

Re: Impossible perft question

Post by lucasart »

trojanfoe wrote:OK, after adding functionality to generate 'random' positions and comparing the perft results of Gaviota and ccore at depth 1, I have the following position:

[d]1N6/6k1/8/8/7B/8/8/4K3 w - - 19 103

Gaviota gives:

Code: Select all

perftdiv 1
   -->   Nb8-c6           1
   -->   Ke1-f2           1
   -->   Ke1-e2           1
   -->   Ke1-f1           1
   -->   Nb8-d7           1
   -->   Ke1-d2           1
   -->   Bh4-d8           1
   -->   Bh4-e7           1
   -->   Bh4-g5           1
   -->   Bh4-f6           1
depth 1: leaves:         10
And ccore gives:

Code: Select all

         Na6:            1
         Nc6:            1
         Nd7:            1
         Bf2:            1
         Bg3:            1
         Bg5:            1
         Bf6:            1
         Be7:            1
         Bd8:            1
         Kd1:            1
         Kf1:            1
         Kd2:            1
         Ke2:            1
         Kf2:            1
 Total nodes:           14
However I cannot see why ccore is wrong here...
I do not believe one second that Gaviota would have an incorrect perft(1) in a position that simple. Your FEN is incorrect!

Code: Select all

[d]1N6/6k1/8/8/7B/8/8/4K3 w - - 19 103
103 ???
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
Top
zullil
Posts: 6442
Joined: Tue Jan 09, 2007 12:31 am
Location: PA USA
Full name: Louis Zulli

Re: Impossible perft question

Post by zullil »

lucasart wrote:
trojanfoe wrote:OK, after adding functionality to generate 'random' positions and comparing the perft results of Gaviota and ccore at depth 1, I have the following position:

[d]1N6/6k1/8/8/7B/8/8/4K3 w - - 19 103

Gaviota gives:

Code: Select all

perftdiv 1
   -->   Nb8-c6           1
   -->   Ke1-f2           1
   -->   Ke1-e2           1
   -->   Ke1-f1           1
   -->   Nb8-d7           1
   -->   Ke1-d2           1
   -->   Bh4-d8           1
   -->   Bh4-e7           1
   -->   Bh4-g5           1
   -->   Bh4-f6           1
depth 1: leaves:         10
And ccore gives:

Code: Select all

         Na6:            1
         Nc6:            1
         Nd7:            1
         Bf2:            1
         Bg3:            1
         Bg5:            1
         Bf6:            1
         Be7:            1
         Bd8:            1
         Kd1:            1
         Kf1:            1
         Kd2:            1
         Ke2:            1
         Kf2:            1
 Total nodes:           14
However I cannot see why ccore is wrong here...
I do not believe one second that Gaviota would have an incorrect perft(1) in a position that simple. Your FEN is incorrect!

Code: Select all

[d]1N6/6k1/8/8/7B/8/8/4K3 w - - 19 103
103 ???
Why can't the fullmove number be 103?
Top
User avatar
trojanfoe
Posts: 65
Joined: Sun Jul 31, 2011 11:57 am
Location: Waterlooville, Hampshire, UK

Re: Impossible perft question

Post by trojanfoe »

lucasart wrote: (snipped)
I do not believe one second that Gaviota would have an incorrect perft(1) in a position that simple. Your FEN is incorrect!

Code: Select all

[d]1N6/6k1/8/8/7B/8/8/4K3 w - - 19 103
103 ???
The FEN was generated by taking a position in the normal starting position, and then making a random (legal) move. The number of moves made is also random so I believe the FEN is correct. What's wrong with having a move of 103?
Top
Sven
Posts: 4052
Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle

Re: Impossible perft question

Post by Sven »

trojanfoe wrote:
michiguel wrote: I am willing to bet that after black's c5, the engine may think bxc6 is a legal move but it is not (R checks!). Same with g4 fxg3, and e4 fxe3. This a typical problem.
Indeed and this was the first bug I needed to fix. My move generator excludes pinned pieces and those are now correctly identified as 'en-passant pinned' which means they can move, but they cannot capture. However those are all depth-2 issues, not depth-5. Something's happening much later which I am not accounting for...

Thanks for confirming the expected nodes are correct and I'll look into perftdiv.
When looking again at this position:
[d]
I see that the results of ccore are lower than the correct ones for all root moves, but the difference is only 1 in case of 1.Ka6 and 1.Ka4 while in all other cases it is in the range between 8 (for 1.e4) and 19 (for 1.Rd4).

My gut feeling is that you still have a problem in the context of pins, and also that it could be color dependent. I am not sure at all but the problem might arise only if the white king is on a5, hence the lower differences after moving the king away from a5 (which requires another white king move back to a5). Could it be possible that you reject the white move b5-b6 as illegal after the black c7-c5, while the corresponding situation after a white pawn's double step is handled correctly? The mobility of the white rook on d4 after 1.Rd4 c5 2.b6 <any except cxd4> seems to bigger than after any other root move which would explain why 1.Rd4 shows the maximum difference ...

Just a wild guess, of course :-)

Sven
Top

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