BikMove

Discussion about development of draughts in the time of computer and Internet.
Post Reply
AartBik
Posts: 103
Joined: Wed Mar 11, 2009 01:30
Location: Mountain View
Contact:
Contact AartBik

BikMove

Post by AartBik » Tue Mar 17, 2009 19:39

Hi Checkers Programmers,

I recently became interested in checkers programming after writing a simple checkers application for the G1 Android phone, available for free at the Android Market. After that, I downloaded Martin Fierz' excellent CheckerBoard as a sparring partner to test this phone application. Since Checkerboard makes it very easy to plug-in an engine, I decided to port the Java source to C++ and implement a complete plug-in engine for Checkerboard. The result is BikMove (note, not "Big", but derived from my last name [BikJump would perhaps be better, but I used that already for my chess engine]). I wrote all source code of engine with the exception of the endgame databases probing code, which is used with kind permission of Martin Fierz.

The engine and perft-scores of the move generator can be found at http://www.aartbik.com/MISC/checkers.html
Current features:

* 8x8 straight checkers engine.
* Checkerboard-compliant
* Iterative deepening with alpha-beta pruning.
* Ability to query endgame databases during search.

Please note that this is still very much a work in progress. This first release provides hopefully a stable foundation for further improvements. I don't expect the current version to be very competitive with existing engines.

Sincerely,
Aart Bik
Top
Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:
Contact Rein Halbersma

Re: BikMove

Post by Rein Halbersma » Tue Mar 17, 2009 21:56

AartBik wrote:Hi Checkers Programmers,

I recently became interested in checkers programming after writing a simple checkers application for the G1 Android phone, available for free at the Android Market. After that, I downloaded Martin Fierz' excellent CheckerBoard as a sparring partner to test this phone application. Since Checkerboard makes it very easy to plug-in an engine, I decided to port the Java source to C++ and implement a complete plug-in engine for Checkerboard. The result is BikMove (note, not "Big", but derived from my last name [BikJump would perhaps be better, but I used that already for my chess engine]). I wrote all source code of engine with the exception of the endgame databases probing code, which is used with kind permission of Martin Fierz.

The engine and perft-scores of the move generator can be found at http://www.aartbik.com/MISC/checkers.html
Current features:

* 8x8 straight checkers engine.
* Checkerboard-compliant
* Iterative deepening with alpha-beta pruning.
* Ability to query endgame databases during search.

Please note that this is still very much a work in progress. This first release provides hopefully a stable foundation for further improvements. I don't expect the current version to be very competitive with existing engines.

Sincerely,
Aart Bik
Hi Aart,

Welcome to the forum! Very nice to have another free program. Are you also planning on doing a 10x10 international draughts program? That's the game we mostly discuss here.

Rein
Top
Ed Gilbert
Posts: 859
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:
Contact Ed Gilbert

Post by Ed Gilbert » Tue Mar 17, 2009 22:26

Hi Aart,

Congrats on BikMove. I played a quick game with it and it looks very solid. Search speed is more than 2x that of kingsrow, if we are measuring the same things.

With all those hundreds of thousands of servers you have at Google, do you think they'll let you use a few of them to build endgame databases? :-)

-- Ed
Top
AartBik
Posts: 103
Joined: Wed Mar 11, 2009 01:30
Location: Mountain View
Contact:
Contact AartBik

Re: BikMove

Post by AartBik » Tue Mar 17, 2009 22:27

Rein Halbersma wrote: Welcome to the forum! Very nice to have another free program. Are you also planning on doing a 10x10 international draughts program? That's the game we mostly discuss here.
Thanks Rein! I figured the international style would be more popular on this forum . I too grew up with a much larger checkerboard than used here in the US.
What would be the most commonly used GUI, engine protocol, and endgame databases probing code (if any?) for 10x10 international style?
Top
AartBik
Posts: 103
Joined: Wed Mar 11, 2009 01:30
Location: Mountain View
Contact:
Contact AartBik

Post by AartBik » Tue Mar 17, 2009 22:30

Ed Gilbert wrote: With all those hundreds of thousands of servers you have at Google, do you think they'll let you use a few of them to build endgame databases?
-- Ed
No comment

I was secretly thinking about (mis)using some cycles to compute perft(16) and higher (for 8x8 that is) if there would be any interest in that.
Top
Ed Gilbert
Posts: 859
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:
Contact Ed Gilbert

Re: BikMove

Post by Ed Gilbert » Tue Mar 17, 2009 23:11

AartBik wrote:What would be the most commonly used GUI, engine protocol, and endgame databases probing code (if any?) for 10x10 international style?
Aart, AFAIK there are about 10 active programs for 10x10 draughts, and they all seem to have created their own GUIs. There is a standard protocol for automating games between engines. It was created by Frank Mesander and is called DamExchange. http://www.mesander.nl/ As for endgame databases, they are much larger than the 8x8 equivalents for the same number of pieces. The 7pc international draughts db is about the same size as the 9pc 8x8 db, and the 8pc international db is about 2x larger than the 10pc 8x8db. I few programs are using the 6pc db and/or builder which is available here: http://www.xs4all.nl/~hjetten/dameng.html.

-- Ed
Top
AartBik
Posts: 103
Joined: Wed Mar 11, 2009 01:30
Location: Mountain View
Contact:
Contact AartBik

Post by AartBik » Tue Mar 17, 2009 23:12

Ed Gilbert wrote: Congrats on BikMove. I played a quick game with it and it looks very solid. Search speed is more than 2x that of kingsrow, if we are measuring the same things.
-- Ed
Very kind of you to say. Kingsrow and Cake form a superb class by themselves. I am very impressed by those engines!
Top
Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:
Contact Rein Halbersma

Post by Rein Halbersma » Wed Apr 22, 2009 20:54

AartBik wrote:
Ed Gilbert wrote: With all those hundreds of thousands of servers you have at Google, do you think they'll let you use a few of them to build endgame databases?
-- Ed
No comment

I was secretly thinking about (mis)using some cycles to compute perft(16) and higher (for 8x8 that is) if there would be any interest in that.
Hi Aart,

I see on your web page that you are up to perft(17) now, which is 200 days of computing. How powerful are those machines exactly?

Rein
Top
AartBik
Posts: 103
Joined: Wed Mar 11, 2009 01:30
Location: Mountain View
Contact:
Contact AartBik

Post by AartBik » Wed Apr 22, 2009 22:23

Rein Halbersma wrote: Hi Aart,
I see on your web page that you are up to perft(17) now, which is 200 days of computing. How powerful are those machines exactly?
Rein
Hi Rein,
The quoted perft results are computed single-threaded on one 2.2 GHz Core 2 Duo. Note that perft(17) "only" took close to 5 hours. I was thinking of implementing a parallel-distributed version to go beyond d=17, but I am not sure how useful this really is (other than just fun!).
Aart

Code: Select all

 PERFT(d) for 8x8 checkers:
d=1  :            7  in        0 ms.
d=2  :           49  in        0 ms.
d=3  :          302  in        0 ms.
d=4  :         1469  in        0 ms.
d=5  :         7361  in        0 ms.
d=6  :        36768  in        1 ms.     36,768.0 KN/s
d=7  :       179740  in        5 ms.     35,948.0 KN/s
d=8  :       845931  in       23 ms.     36,779.6 KN/s
d=9  :      3963680  in       86 ms.     46,089.3 KN/s
d=10 :     18391564  in      398 ms.     46,210.0 KN/s
d=11 :     85242128  in     1821 ms.     46,810.6 KN/s
d=12 :    388623673  in     8395 ms.     46,292.3 KN/s
d=13 :   1766623630  in    37182 ms.     47,512.9 KN/s
d=14 :   7978439499  in   174947 ms.     45,604.9 KN/s
d=15 :  36263167175  in   808155 ms.     44,871.5 KN/s
d=16 : 165629569428  in  3767118 ms.     43,967.2 KN/s
d=17 : 758818810990  in 17317695 ms.     43,817.5 KN/s
Top
Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:
Contact Rein Halbersma

Post by Rein Halbersma » Thu Apr 23, 2009 07:22

AartBik wrote:
Rein Halbersma wrote: Hi Aart,
I see on your web page that you are up to perft(17) now, which is 200 days of computing. How powerful are those machines exactly?
Rein
Hi Rein,
The quoted perft results are computed single-threaded on one 2.2 GHz Core 2 Duo. Note that perft(17) "only" took close to 5 hours. I was thinking of implementing a parallel-distributed version to go beyond d=17, but I am not sure how useful this really is (other than just fun!).
Aart

Code: Select all

 PERFT(d) for 8x8 checkers:
d=1  :            7  in        0 ms.
d=2  :           49  in        0 ms.
d=3  :          302  in        0 ms.
d=4  :         1469  in        0 ms.
d=5  :         7361  in        0 ms.
d=6  :        36768  in        1 ms.     36,768.0 KN/s
d=7  :       179740  in        5 ms.     35,948.0 KN/s
d=8  :       845931  in       23 ms.     36,779.6 KN/s
d=9  :      3963680  in       86 ms.     46,089.3 KN/s
d=10 :     18391564  in      398 ms.     46,210.0 KN/s
d=11 :     85242128  in     1821 ms.     46,810.6 KN/s
d=12 :    388623673  in     8395 ms.     46,292.3 KN/s
d=13 :   1766623630  in    37182 ms.     47,512.9 KN/s
d=14 :   7978439499  in   174947 ms.     45,604.9 KN/s
d=15 :  36263167175  in   808155 ms.     44,871.5 KN/s
d=16 : 165629569428  in  3767118 ms.     43,967.2 KN/s
d=17 : 758818810990  in 17317695 ms.     43,817.5 KN/s
ah my bad! I didn't see it were miliseconds! i thought it were seconds...
You could also enable the transposition table, that would speed things up quite considerably...
Top
AartBik
Posts: 103
Joined: Wed Mar 11, 2009 01:30
Location: Mountain View
Contact:
Contact AartBik

Post by AartBik » Sat Apr 25, 2009 05:56

AartBik wrote:I was thinking of implementing a parallel-distributed version to go beyond d=17, but I am not sure how useful this really is (other than just fun!).
I guess I could not help myself. [img]images/smilies/icon_rolleyes.gif[/img]
Here are the results using a distributed version.

Code: Select all

perft(18) =   3493881706141
perft(19) =  16114043592799
Top
64_bit_checkers_engine
Posts: 62
Joined: Mon Apr 20, 2009 01:10
Contact:
Contact 64_bit_checkers_engine

Re: Perft(18)

Post by 64_bit_checkers_engine » Sat Apr 25, 2009 20:13

AartBik wrote:

Code: Select all

perft(18) =   3493881706141
perft(19) =  16114043592799
In light of our recent debugging session, I did the perft(18) by move as well, in case anyone needs to debug in the future.

I like the speed number best @ 102,466,237 nodes/second.

Code: Select all

PARENT POSITION WITH RED TO MOVE


XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   w   X#######X   w   X#######X   w   X#######X   w   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X       X#######X       X#######X       X#######X       X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   r   X#######X   r   X#######X   r   X#######X   r   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   r   X#######X   r   X#######X   r   X#######X   r   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   r   X#######X   r   X#######X   r   X#######X   r   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


=================================================================


move 1 of 7 from parent position, white to move nodes below after 17 plies = 550829166472


XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   w   X#######X   w   X#######X   w   X#######X   w   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   r   X#######X       X#######X       X#######X       X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X       X#######X   r   X#######X   r   X#######X   r   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   r   X#######X   r   X#######X   r   X#######X   r   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   r   X#######X   r   X#######X   r   X#######X   r   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


move 2 of 7 from parent position, white to move nodes below after 17 plies = 435063007630


XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   w   X#######X   w   X#######X   w   X#######X   w   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X       X#######X   r   X#######X       X#######X       X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   r   X#######X       X#######X   r   X#######X   r   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   r   X#######X   r   X#######X   r   X#######X   r   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   r   X#######X   r   X#######X   r   X#######X   r   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


move 3 of 7 from parent position, white to move nodes below after 17 plies = 566149929068


XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   w   X#######X   w   X#######X   w   X#######X   w   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   r   X#######X       X#######X       X#######X       X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   r   X#######X       X#######X   r   X#######X   r   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   r   X#######X   r   X#######X   r   X#######X   r   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   r   X#######X   r   X#######X   r   X#######X   r   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


move 4 of 7 from parent position, white to move nodes below after 17 plies = 402570639569


XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   w   X#######X   w   X#######X   w   X#######X   w   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X       X#######X       X#######X   r   X#######X       X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   r   X#######X   r   X#######X       X#######X   r   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   r   X#######X   r   X#######X   r   X#######X   r   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   r   X#######X   r   X#######X   r   X#######X   r   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


move 5 of 7 from parent position, white to move nodes below after 17 plies = 472279451484


XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   w   X#######X   w   X#######X   w   X#######X   w   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X       X#######X   r   X#######X       X#######X       X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   r   X#######X   r   X#######X       X#######X   r   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   r   X#######X   r   X#######X   r   X#######X   r   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   r   X#######X   r   X#######X   r   X#######X   r   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


move 6 of 7 from parent position, white to move nodes below after 17 plies = 625398758917


XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   w   X#######X   w   X#######X   w   X#######X   w   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X       X#######X       X#######X       X#######X   r   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   r   X#######X   r   X#######X   r   X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   r   X#######X   r   X#######X   r   X#######X   r   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   r   X#######X   r   X#######X   r   X#######X   r   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


move 7 of 7 from parent position, white to move nodes below after 17 plies = 441590753001


XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   w   X#######X   w   X#######X   w   X#######X   w   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   w   X#######X   w   X#######X   w   X#######X   w   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X       X#######X       X#######X   r   X#######X       X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   r   X#######X   r   X#######X   r   X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X   r   X#######X   r   X#######X   r   X#######X   r   X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   r   X#######X   r   X#######X   r   X#######X   r   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX



 TOTAL NODES =  3493881706141

 TOTAL TIME = 34097 seconds (9 hr 28 min 17 sec)

 SPEED = 102466237 nodes/second
Top
AartBik
Posts: 103
Joined: Wed Mar 11, 2009 01:30
Location: Mountain View
Contact:
Contact AartBik

Re: Perft(18)

Post by AartBik » Sat Apr 25, 2009 20:58

64_bit_checkers_engine wrote: I like the speed number best @ 102,466,237 nodes/second.
Ed,
This is an impressive rate given that you used a single machine (I used a cluster of machines to compute my deeper depth perft numbers).
Aart
Top
64_bit_checkers_engine
Posts: 62
Joined: Mon Apr 20, 2009 01:10
Contact:
Contact 64_bit_checkers_engine

Re: Perft(18)

Post by 64_bit_checkers_engine » Sun Apr 26, 2009 00:17

AartBik wrote:Ed,
This is an impressive rate given that you used a single machine (I used a cluster of machines to compute my deeper depth perft numbers).
Aart
Hi Aart,

I posted some code here for my attempted 100-bit engine for Intl Draughts. Hopefully the more experienced Draughts Programmers can take the idea and make good use of it.

I hand them the engine, "all they have to do" is connect it to a car. Still a good bit of work to be done, but it should have a bigger payoff for the speed of a Draughts engine than in a checkers engine.
Top
Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:
Contact Rein Halbersma

Post by Rein Halbersma » Wed May 06, 2009 19:56

AartBik wrote:
Rein Halbersma wrote: Hi Aart,
I see on your web page that you are up to perft(17) now, which is 200 days of computing. How powerful are those machines exactly?
Rein
Hi Rein,
The quoted perft results are computed single-threaded on one 2.2 GHz Core 2 Duo. Note that perft(17) "only" took close to 5 hours. I was thinking of implementing a parallel-distributed version to go beyond d=17, but I am not sure how useful this really is (other than just fun!).
Aart

Code: Select all

 PERFT(d) for 8x8 checkers:
d=1  :            7  in        0 ms.
d=2  :           49  in        0 ms.
d=3  :          302  in        0 ms.
d=4  :         1469  in        0 ms.
d=5  :         7361  in        0 ms.
d=6  :        36768  in        1 ms.     36,768.0 KN/s
d=7  :       179740  in        5 ms.     35,948.0 KN/s
d=8  :       845931  in       23 ms.     36,779.6 KN/s
d=9  :      3963680  in       86 ms.     46,089.3 KN/s
d=10 :     18391564  in      398 ms.     46,210.0 KN/s
d=11 :     85242128  in     1821 ms.     46,810.6 KN/s
d=12 :    388623673  in     8395 ms.     46,292.3 KN/s
d=13 :   1766623630  in    37182 ms.     47,512.9 KN/s
d=14 :   7978439499  in   174947 ms.     45,604.9 KN/s
d=15 :  36263167175  in   808155 ms.     44,871.5 KN/s
d=16 : 165629569428  in  3767118 ms.     43,967.2 KN/s
d=17 : 758818810990  in 17317695 ms.     43,817.5 KN/s
In case you ever get around to programming Russian checkers, here are the perft stats for that game:

Code: Select all

1 - 7 
2 - 49 
3 - 302 
4 - 1469 
5 - 7482 
6 - 37986 
7 - 190146 
8 - 929905 
9 - 4570667 
10 - 22450628 
11 - 110961169 
12 - 545059387 
13 - 2675994747 
14 - 13138899366
I copied this from the link:
http://74.125.79.132/translate_c?hl=en& ... 6csoRHdu3Q

Note that that Igor Korshunov (the guy who beat Martin Fierz in give-away checkers!) also gives perft(14) = 7978439499 for American checkers. A post from 2006. It's quite an interesting forum though, and with Google translate you can understand pretty much everything.
Top
Post Reply

Return to “Draughts, Computer, Internet”