Being silly with perft and legal move generation

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Jakob Progsch
Posts: 39
Joined: Fri Apr 16, 2021 2:44 pm
Full name: Jakob Progsch

Being silly with perft and legal move generation

Post by Jakob Progsch » Wed May 19, 2021 10:00 pm

So I was cleaning up some perft issues the other day after rewriting some legal move generation code and made sure that it correctly detects the situation where en passant removes two pieces from a rank potentially discovering a check. While I was at it I put some other "related positions" on the board including this one:



The correct perft(1) is 5. Whose legal move generation handles it correctly and who sees what is wrong with the position in the first place? :roll:

I only noticed how dumb I was after I had put in the code to fix this "problem".

amanjpro
Posts: 557
Joined: Sat Mar 13, 2021 12:47 am
Full name: Amanj Sherwany
Contact:

Re: Being silly with perft and legal move generation

Post by amanjpro » Thu May 20, 2021 12:22 am

You cannot have `c6` as enpassant square, if so that means Black's last move was c5, which is incorrect, because it means White king was in check when black moved

Sven
Posts: 4023
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Being silly with perft and legal move generation

Post by Sven » Thu May 20, 2021 6:42 am

You will need your new code for positions like the one with Ka5 instead of Ka3 and Rh5 instead of the bishop.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

Jakob Progsch
Posts: 39
Joined: Fri Apr 16, 2021 2:44 pm
Full name: Jakob Progsch

Re: Being silly with perft and legal move generation

Post by Jakob Progsch » Thu May 20, 2021 2:15 pm

Right, that was what it was looking at Position 3. I can just remove the part again that deals with the diagonals since you can never get into the situations where you discover a diagonal check via en passant captures.

User avatar
Ajedrecista
Posts: 1602
Joined: Wed Jul 13, 2011 7:04 pm
Location: Madrid, Spain.
Contact:

Re: Being silly with perft and legal move generation.

Post by Ajedrecista » Sat May 22, 2021 12:22 pm

Hello:
Sven wrote:
Thu May 20, 2021 6:42 am
You will need your new code for positions like the one with Ka5 instead of Ka3 and Rh5 instead of the bishop.
[d]7k/8/8/K1pP3r/8/8/8/8 w - c6 0 1

Results by gperft 1.1 perft counter, just for verification purposes:

Code: Select all

7k/8/8/K1pP3r/8/8/8/8 w - c6 0 1

perft( 1) =                           5
perft( 2) =                          70
perft( 3) =                         438
perft( 4) =                       7,051
perft( 5) =                      44,848
perft( 6) =                     755,356
perft( 7) =                   4,974,982
perft( 8) =                  86,145,861
perft( 9) =                 595,880,030
perft(10) =              10,426,269,776
perft(11) =              78,890,702,310
perft(12) =           1,375,625,797,968
perft(13) =          12,134,403,134,290
perft(14) =         207,662,593,212,810
perft(15) =       2,276,925,685,154,826
perft(16) =      37,827,431,931,588,143
perft(17) =     521,786,723,984,213,452
perft(18) =   8,409,138,612,936,860,168
perft(19) = 138,964,639,054,506,999,150
There were integer overflows in perft(19) computation with d6 and Kb6 moves plus the total result, so I fixed them via Montecarlo perft estimates. Here are the divided results, once fixing perft(19) divided results:

Code: Select all

perft(1)

d6         1
Ka6        1
Kb6        1
Kb5        1
Ka4        1
TOTAL      5

Code: Select all

perft(2)

d6         14
Ka4        14
Kb5        14
Ka6        14
Kb6        14
TOTAL      70

Code: Select all

perft(3)

d6         68
Ka6        80
Kb6       119
Ka4        66
Kb5       105
TOTAL     438

Code: Select all

perft(4)

d6         1,092
Ka4        1,069
Kb5        1,673
Ka6        1,298
Kb6        1,919
TOTAL      7,051

Code: Select all

perft(5)

d6         7,106
Ka6        8,444
Kb6       12,984
Kb5       10,357
Ka4        5,957
TOTAL     44,848

Code: Select all

perft(6)

d6         115,571
Ka4        100,723
Kb5        174,804
Ka6        143,901
Kb6        220,357
TOTAL      755,356

Code: Select all

perft(7)

d6         847,131
Ka6        915,972
Kb6      1,454,261
Kb5      1,155,290
Ka4        602,328
TOTAL    4,974,982

Code: Select all

perft(8)

d6         14,082,586
Ka4        10,464,646
Ka6        16,072,232
Kb5        20,084,640
Kb6        25,441,757
TOTAL      86,145,861

Code: Select all

perft(9)

d6         119,854,779
Ka6        105,852,060
Kb6        169,701,194
Kb5        134,084,290
Ka4         66,387,707
TOTAL      595,880,030

Code: Select all

perft(10)

d6         1,994,070,687
Ka4        1,169,871,460
Kb5        2,366,937,259
Ka6        1,884,773,451
Kb6        3,010,616,919
TOTAL     10,426,269,776

Code: Select all

perft(11)

d6         20,589,021,207
Ka6        13,045,208,442
Kb6        20,839,113,338
Kb5        16,491,349,021
Ka4         7,926,010,302
TOTAL      78,890,702,310

Code: Select all

perft(12)

d6         338,718,421,322
Ka4        140,117,526,844
Kb5        292,522,800,134
Ka6        232,876,879,161
Kb6        371,390,170,507
TOTAL    1,375,625,797,968

Code: Select all

perft(13)

d6         4,304,573,224,115
Ka6        1,763,784,328,265
Kb6        2,792,422,261,839
Kb5        2,215,862,239,207
Ka4        1,057,761,080,864
TOTAL     12,134,403,134,290

Code: Select all

perft(14)

d6         69,546,763,757,408
Ka4        18,510,942,749,938
Kb5        38,999,692,301,198
Ka6        31,207,416,988,191
Kb6        49,397,777,416,075
TOTAL     207,662,593,212,810

Code: Select all

perft(15)

d6         1,058,080,778,363,622
Ka6          276,979,657,617,381
Kb6          431,847,311,342,831
Kb5          344,123,344,651,931
Ka4          165,894,593,179,061
TOTAL      2,276,925,685,154,826

Code: Select all

perft(16)

d6         16,792,820,652,719,061
Ka4         2,833,360,711,624,498
Kb5         5,929,055,981,019,168
Ka6         4,789,791,310,714,347
Kb6         7,482,403,275,511,069
TOTAL      37,827,431,931,588,143

Code: Select all

perft(17)

d6         290,123,468,847,663,156
Ka6         53,076,027,156,797,599
Ka4         31,858,137,074,923,150
Kb6         81,581,028,784,286,182
Kb5         65,148,062,120,543,365
TOTAL      521,786,723,984,213,452

Code: Select all

perft(18)

d6         4,536,879,107,624,830,021
Ka4          526,508,148,865,929,241
Ka6          888,674,005,531,499,407
Kb5        1,087,257,223,589,074,633
Kb6        1,369,820,127,325,526,866
TOTAL      8,409,138,612,936,860,168

Code: Select all

perft(19)

d6         85,133,178,701,520,981,364
Ka6        12,413,053,881,739,686,998
Ka4         7,416,973,917,002,233,834
Kb5        15,084,817,799,376,137,386
Kb6        18,916,614,754,867,959,568
TOTAL     138,964,639,054,506,999,150
Regards from Spain.

Ajedrecista.

Post Reply