Perft for all recognized draughts variants

[Rein Halbersma]

van http://www.friesdammen.nl/dam/page3.php?articleID=260

Concurrentie voor Lusoris?

Maar wellicht dat Rein nu ook al een speelbare versie heeft?

Yes and no. I have a Frisian move generator which knows all the rules except the maximum of 3 consecutive king moves. (I also don't have implemented yet the 50-ply non-conversion rule for international draughts) My program is not ready to be distributed. When it will, Frisian will likely be a supported variant. Below the non-duplicates removed perft results for the initial position (Frisian draughts has diagonal and orthogonal captures, a majority capture rules which weighs [n] kings between [2n-1] and [2n] men, and which has mandatory king capture as tie-breaker precedence rule).

Note that in Frisian draughts, the first kings appear already at d=7 in the initial position. This means that at d=13 the 4th consecutive king move can be made. The results below should therefore be correct, barring any mistake from my side. Any independent computation would be welcome! Also note that the speed for Frisian draughts is around 50% of the speed of international draughts. This is due to the 8 rather than 4 capture directions that need to be checked.

Code: Select all

 
  b   b   b   b   b
 b   b   b   b   b
  b   b   b   b   b
 b   b   b   b   b
   .   .   .   .   .
 .   .   .   .   .
  w   w   w   w   w
 w   w   w   w   w
  w   w   w   w   w
 w   w   w   w   w

W:B1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20:W31,32,33,34,35,36,37,38,3
9,40,41,42,43,44,45,46,47,48,49,50"

Searching starting position to nominal depth=11

perft( 1)            9 nodes,   0.00s,   0.01 Mnps
perft( 2)           81 nodes,   0.00s,   0.08 Mnps
perft( 3)          658 nodes,   0.00s,   0.66 Mnps
perft( 4)         3880 nodes,   0.00s,   3.88 Mnps
perft( 5)        21345 nodes,   0.00s,  21.34 Mnps
perft( 6)       103584 nodes,   0.02s,   6.47 Mnps
perft( 7)       550314 nodes,   0.05s,  11.46 Mnps
perft( 8)      2907905 nodes,   0.24s,  12.32 Mnps
perft( 9)     16204497 nodes,   1.20s,  13.46 Mnps
perft(10)     90161025 nodes,   6.72s,  13.42 Mnps
perft(11)    521287205 nodes,  37.88s,  13.76 Mnps

As you can see below, for Frisian draughts, duplicate captures already happen at d=4 and at d=11 the perft numbers differ by more than 6%. As you can see, the overhead of the duplicate removal pays off since the overall time to depth is slightly faster!

Code: Select all

perft( 1)            9 nodes,   0.00s,   0.01 Mnps
perft( 2)           81 nodes,   0.00s,   0.08 Mnps
perft( 3)          658 nodes,   0.00s,   0.66 Mnps
perft( 4)         3874 nodes,   0.00s,   3.87 Mnps
perft( 5)        21265 nodes,   0.00s,  21.26 Mnps
perft( 6)       102431 nodes,   0.02s,   6.40 Mnps
perft( 7)       540126 nodes,   0.05s,  11.25 Mnps
perft( 8)      2825779 nodes,   0.24s,  11.97 Mnps
perft( 9)     15605069 nodes,   1.22s,  12.80 Mnps
perft(10)     85817725 nodes,   6.55s,  13.11 Mnps
perft(11)    491186430 nodes,  36.95s,  13.29 Mnps

[Rein Halbersma]

van http://www.friesdammen.nl/dam/page3.php?articleID=260

Concurrentie voor Lusoris?

De meeste Friese dammers zullen het computerprogramma Lusoris wel kennen. Dat programma heeft nu mogelijk concurrentie gekregen uit Zweden. Mats Winther meldt althans op zijn homepage dat hij een programma geschreven heeft waarmee men het Friese damspel ("a wild form of checkers", zoals hij het kenschetst) kan spelen. Zie op:

http://hem.passagen.se/melki9

Het programma zelf is gratis, maar om het te kunnen spelen heeft u wel eerst het programma Zillions of Games nodig. Als ik het goed begrijp, kost een downloadversie van dat programma ongeveer 25 dollar; het laten toesturen van het programma op CD wordt ongeveer twee keer zo duur.

Welke Friese dammer test dit programma eens, en doet daar voor anderen verslag van, bijvoorbeeld in Oer Alles?

Siebren Dyk

Maar wellicht dat Rein nu ook al een speelbare versie heeft?

Aurora Borealis is also available for EUR 25, and at the website of draughts club Het Noorden you can play Frisian online.

[Rein Halbersma]

This post is to correct the previously given perft numbers for Thai draughts. I made a small mistake in the interpretation of the capture rules. A king is long-ranged in Thai draughts, but with a few subtleties. The landing square after the final capture is immediately behind the last captured piece. But also the landing square after an intermediate capture is behind the piece just captured. Any subsequent captures are generated from this square only. In my previous post, I had not implemented this particular restriction.

The rules are described in detail on this site: http://www.mindsports.nl/index.php/on-t ... s/500-thai


A simple example to illustrate the intermediate landing rule. White has to capture a1xd4, and not a1 x c7, because the second capture has to start from d4.


Another example to illustrate the capture reversal rule. White has to capture all 3 black pieces with either d4xb2 or with d4xh8. The latter capture can be done in two different orders: d4 x b2 x f6 x h8 or also d4 x f6 x b2 x h8. This also requires the intermediate capture removal rule. Note that even with 3 captured pieces one can have two identical capture moves in different order (most other draughts variants need at least 4 captured pieces for capture ambiguity).


A final example to illustrate the piece removal rule. White has to capture all 7 black pieces with a3 x f4, in the sequence a3 x d6 x g3 x e1 x b4 x f8 x h6 x f4. The pieces on c5 and f4 are removed immediately after they are captured, clearing the way to pass these squares in the rest of the capture sequence. In particular, the white king lands on a square it just captured a piece on.

[Rein Halbersma]

Here are the new perft numbers for the initial position in Thai draughts (2 rows of men only)

Code: Select all

   b   b   b   b
 b   b   b   b
   .   .   .   .
 .   .   .   .
   .   .   .   .
 .   .   .   .
   w   w   w   w
 w   w   w   w

"W:B1,2,3,4,5,6,7,8:W25,26,27,28,29,30,31,32"

Searching to nominal depth=11

info depth  1 leafs            7 nodes            1 time      0 nps       1 hashfull    0
info depth  2 leafs           49 nodes            8 time    141 nps      57 hashfull    0
info depth  3 leafs          392 nodes           57 time    282 nps     404 hashfull    0
info depth  4 leafs         3136 nodes          449 time    422 nps    3207 hashfull    0
info depth  5 leafs        26592 nodes         2409 time    594 nps   14006 hashfull    0
info depth  6 leafs       218695 nodes        12495 time    797 nps   61552 hashfull    0
info depth  7 leafs      1820189 nodes        46567 time    969 nps  270738 hashfull    1
info depth  8 leafs     14533014 nodes       166374 time   1204 nps  707974 hashfull    4
info depth  9 leafs    114530830 nodes       505158 time   1688 nps 1043715 hashfull   13
info depth 10 leafs    861842812 nodes      1488219 time   2829 nps 1304311 hashfull   36
info depth 11 leafs   6304986761 nodes      3983530 time   5594 nps 1440698 hashfull   99

The previous numbers were different for depth >= 9

Code: Select all

info depth  9 leafs    114530866 nodes       505158 time   1641 nps 1043715 hashfull   13
info depth 10 leafs    861843865 nodes      1488228 time   2735 nps 1360355 hashfull   36
info depth 11 leafs   6305003332 nodes      3983683 time   5485 nps 1448612 hashfull   99

These numbers weren't and aren't influenced by capture ambiguities.

Here are the new perft numbers for the initial position in Thai draughts with 3 rows of men

Code: Select all

   b   b   b   b
 b   b   b   b
   b   b   b   b
 .   .   .   .
   .   .   .   .
 w   w   w   w
   w   w   w   w
 w   w   w   w

"W:B1,2,3,4,5,6,7,8,9,10,11,12:W21,22,23,24,25,26,27,28,29,30,31,32"

Searching to nominal depth=13

info depth  1 leafs            7 nodes            1 time      0 nps       1 hashfull    0
info depth  2 leafs           49 nodes            8 time    125 nps      64 hashfull    0
info depth  3 leafs          302 nodes           57 time    266 nps     404 hashfull    0
info depth  4 leafs         1469 nodes          359 time    406 nps    2564 hashfull    0
info depth  5 leafs         7361 nodes         1384 time    563 nps    8815 hashfull    0
info depth  6 leafs        36768 nodes         5175 time    703 nps   36964 hashfull    0
info depth  7 leafs       179740 nodes        17602 time    860 nps  112115 hashfull    1
info depth  8 leafs       845931 nodes        57799 time   1031 nps  338006 hashfull    2
info depth  9 leafs      3963648 nodes       176781 time   1328 nps  595222 hashfull    8
info depth 10 leafs     18363523 nodes       546523 time   1938 nps  895939 hashfull   23
info depth 11 leafs     84892793 nodes      1651203 time   3485 nps 1067358 hashfull   68
info depth 12 leafs    385719334 nodes      5036864 time   8781 nps 1060392 hashfull  196
info depth 13 leafs   1745725339 nodes     15026490 time  22171 nps 1122217 hashfull  484

The previous numbers without capture ambiguity removal were different for depth >= 11

Code: Select all

info depth 11 leafs     84892782 nodes      1651203 time   3422 nps 1089184 hashfull   68
info depth 12 leafs    385724806 nodes      5036854 time   7844 nps 1139044 hashfull  196
info depth 13 leafs   1745809229 nodes     15027238 time  21672 nps 1086725 hashfull  484

With ambiguous captures removed, the new numbers are slightly smaller for depth >= 12:

Code: Select all

info depth 12 leafs    385713660 nodes      5036864 time   7969 nps 1123297 hashfull  196
info depth 13 leafs   1745666630 nodes     15026326 time  21406 nps 1118280 hashfull  484

With capture ambiguity removal, the old numbers were slightly smaller for d >= 12

Code: Select all

info depth 12 leafs    385719132 nodes      5036854 time   7860 nps 1139044 hashfull  196
info depth 13 leafs   1745750520 nodes     15027074 time  21875 nps 1072214 hashfull  484

Notice that capture ambiguity removed numbers are always smaller than the corresponding numbers without capture ambiguity removal. It is also true that for any position with the correct intermediate capture landing rule, the number of legal moves is never greater than under the incorrect old rule. However, the allowed captures under the new rule are not a subset of the captures allowed under the incorrect old rule. See e.g. the first diagram in the previous post. The correct capture rule gives a position where black has 2 moves, whereas the old rule gave a position where black had no more moves. Therefore the perft numbers under the new rule are not guaranteed to be smaller or equal under the incorrect old rule. See e.g. the perft numbers for depth = 11 for the initial position with 3 rows of men. This peculiar data point really had me searching for another bug but it turns out to be correct after all!

Any confirmation would be welcome!

[ildjarn]

Is it possible to check for unique positions in the perft tables, i.e. positions which can be reached only through exactly one game?

[Rein Halbersma]

Is it possible to check for unique positions in the perft tables, i.e. positions which can be reached only through exactly one game?

You could try do that using a hashtable where you store the entire position. (This is the same technique that Aart Bik used in his mega-perft simulations for 8x8 checkers). There is the slight problem that if perft(N) finds some unique positions, that perft(N+k) for some k will find the same position (because of some backward capture sequence that delays the position). Moreover, you are not guaranteed to find all uniquely reachable positions because the hashtable will quickly become full.

To make sure you get correct results for small games (on 6x6 boards e.g.), you could generate a "reachability" database by repeatedly marking successors of the initial position. For 10x10 draughts, this is impractical (you would have to make the 20m20m database, good luck with that!)

I can try to get some results for you.

UPDATE:

I haven't done any calculations yet, but it seems that uniquely reachable positions are very rare. E.g. the inital position and all ply=1 and ply=2 positions are uniquely reachable. After that, you need a forcing capture sequence to force uniqueness.

E.g. you can easily make a ply=22 capture sequence from the initial position:
1. 31-26 17-21 2. 26x17 12x21 3. 32-27 21x32 4. 38x27 18-22 5. 27x18 13x22 6. 33-28 22x33 7. 39x28 19-23 8. 28x19 14x23 9. 34-29 23x34 10. 40x29 20-24 11. 29x20 15x24.

However, checking this for uniqueness is very hard because perft(22) is out of range for existing hardware (OK, enter Aart Bik here...).

[Rein Halbersma]

van http://www.friesdammen.nl/dam/page3.php?articleID=260

Concurrentie voor Lusoris?

Maar wellicht dat Rein nu ook al een speelbare versie heeft?

Yes and no. I have a Frisian move generator which knows all the rules except the maximum of 3 consecutive king moves. (I also don't have implemented yet the 50-ply non-conversion rule for international draughts) My program is not ready to be distributed. When it will, Frisian will likely be a supported variant. Below the non-duplicates removed perft results for the initial position (Frisian draughts has diagonal and orthogonal captures, a majority capture rules which weighs [n] kings between [2n-1] and [2n] men, and which has mandatory king capture as tie-breaker precedence rule).

Note that in Frisian draughts, the first kings appear already at d=7 in the initial position. This means that at d=13 the 4th consecutive king move can be made. The results below should therefore be correct, barring any mistake from my side. Any independent computation would be welcome! Also note that the speed for Frisian draughts is around 50% of the speed of international draughts. This is due to the 8 rather than 4 capture directions that need to be checked.

Code: Select all

 
  b   b   b   b   b
 b   b   b   b   b
  b   b   b   b   b
 b   b   b   b   b
   .   .   .   .   .
 .   .   .   .   .
  w   w   w   w   w
 w   w   w   w   w
  w   w   w   w   w
 w   w   w   w   w

W:B1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20:W31,32,33,34,35,36,37,38,3
9,40,41,42,43,44,45,46,47,48,49,50"

Searching starting position to nominal depth=11

perft( 1)            9 nodes,   0.00s,   0.01 Mnps
perft( 2)           81 nodes,   0.00s,   0.08 Mnps
perft( 3)          658 nodes,   0.00s,   0.66 Mnps
perft( 4)         3880 nodes,   0.00s,   3.88 Mnps
perft( 5)        21345 nodes,   0.00s,  21.34 Mnps
perft( 6)       103584 nodes,   0.02s,   6.47 Mnps
perft( 7)       550314 nodes,   0.05s,  11.46 Mnps
perft( 8)      2907905 nodes,   0.24s,  12.32 Mnps
perft( 9)     16204497 nodes,   1.20s,  13.46 Mnps
perft(10)     90161025 nodes,   6.72s,  13.42 Mnps
perft(11)    521287205 nodes,  37.88s,  13.76 Mnps

As you can see below, for Frisian draughts, duplicate captures already happen at d=4 and at d=11 the perft numbers differ by more than 6%. As you can see, the overhead of the duplicate removal pays off since the overall time to depth is slightly faster!

Code: Select all

perft( 1)            9 nodes,   0.00s,   0.01 Mnps
perft( 2)           81 nodes,   0.00s,   0.08 Mnps
perft( 3)          658 nodes,   0.00s,   0.66 Mnps
perft( 4)         3874 nodes,   0.00s,   3.87 Mnps
perft( 5)        21265 nodes,   0.00s,  21.26 Mnps
perft( 6)       102431 nodes,   0.02s,   6.40 Mnps
perft( 7)       540126 nodes,   0.05s,  11.25 Mnps
perft( 8)      2825779 nodes,   0.24s,  11.97 Mnps
perft( 9)     15605069 nodes,   1.22s,  12.80 Mnps
perft(10)     85817725 nodes,   6.55s,  13.11 Mnps
perft(11)    491186430 nodes,  36.95s,  13.29 Mnps

Fabien Letouzey has told me in private communication that he has confirmed these numbers!

[Alvaro]

Sorry I made a mistake by clicking the "Report this post" button instead of "Post a reply", moderation please ignore my mistake.
I just want to report a little difference for spanish checkers, all numbers confirmed until depth 11. But starting from depth 12 I have:
perft(12) 365,728,331
perft(13) 1,637,958,247
I guess your move generator has duplicates.

best regards,
Alvaro

[Rein Halbersma]

Sorry I made a mistake by clicking the "Report this post" button instead of "Post a reply", moderation please ignore my mistake.
I just want to report a little difference for spanish checkers, all numbers confirmed until depth 11. But starting from depth 12 I have:
perft(12) 365,728,331
perft(13) 1,637,958,247
I guess your move generator has duplicates.

best regards,
Alvaro

I posted both the duplicate and unique Perft numbers on the first page of this thread. I had the same numbers as you have for d=12,13. See the Perft-unique table image in http://laatste.info/bb3/viewtopic.php?f ... 822#p80038 Thanks for confirming them!