Perft

Discussion about development of draughts in the time of computer and Internet.
Post Reply
Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:

Post by Rein Halbersma »

Ed Gilbert wrote:Hi Bert,
BertTuyt wrote:I assume that this duplicate moves are only possible when the number of killed pieces is greater equal 4.
Yes, and since moves with at least 4 pieces captured are relatively infrequent, it has negligible affect on speed to avoid listing these. If you do store them then your move tables have to be large enough to hold something like 700 - 800 worst case moves. With no redundant moves I think the worst case is less than 128.

-- Ed
Image

This is the highest I can get to on top of my head. There are 18 white kings, each of which can move to 7 squares, so a total of 126 moves. With captures it should be far less. Adding a black piece also reduces the number of available moves.
Last edited by Rein Halbersma on Tue Jan 04, 2011 09:02, edited 1 time in total.
Ed Gilbert
Posts: 860
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Post by Ed Gilbert »

TAILLE wrote:No worry Ed. It is only a misunderstanding of the initial position. I used to list first the men and then the kings. So, I calculated the perft function on the following position :
B:W6,9,10,11,20,21,22,23,30,K31,K33,K37,K41,K42,K43,K44,K46:BK17,K24.
With the good initial position I did not find any discrepancy with your node figures.
Good, you had me worried it might be a bug!

-- Ed
TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Post by TAILLE »

Rein Halbersma wrote: [img]http://fmjd.org/dias2/save/12154466536.png[/img]

This is the highest I can get to on top of my head. There are 18 white kings, each of which can move to 7 squares, so a total of 126 moves. With captures it should be far less. Adding a black piece also reduces the number of available moves.
Just for fun Rein : if there no black pieces that means that it is black to play. The number of possible moves in the position proposed is then 0 !
In the format used by Damy I made the assumption that the number of possible moves is less than 256.
Gérard
Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:

Post by Rein Halbersma »

TAILLE wrote:
Rein Halbersma wrote: Image

This is the highest I can get to on top of my head. There are 18 white kings, each of which can move to 7 squares, so a total of 126 moves. With captures it should be far less. Adding a black piece also reduces the number of available moves.
Just for fun Rein : if there no black pieces that means that it is black to play. The number of possible moves in the position proposed is then 0 !
In the format used by Damy I made the assumption that the number of possible moves is less than 256.
Gérard
Yes, Gérard, I know that the given position is with black to play. It was just meant as an illustration of the maximum number of moves white could have. I also made a small calculation error (there are 16*7 + 2*8=128 moves, I forgot to count the kings on 46 and 5 differently).

Image

So instead take the above position with *white to move*: 16 kings can move to 7 squares and 2 kings (3 and 15) to 6 squares. In total 124 moves. Adding any other pieces will reduce the number of legal moves. But perhaps someone has created a position in which even more moves are legal?
Last edited by Rein Halbersma on Tue Jan 04, 2011 09:03, edited 1 time in total.
TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Post by TAILLE »

Hi Rein,
Rein Halbersma wrote:[img]http://fmjd.org/dias2/save/12155141766.png[/img]
So instead take the above position with *white to move*: 16 kings can move to 7 squares and 2 kings (3 and 15) to 6 squares. In total 124 moves. Adding any other pieces will reduce the number of legal moves. But perhaps someone has created a position in which even more moves are legal?
Alway for fun Rein :
This position cannot establish the record of 124 moves because this position with white to play is illegal. What was the last bkack move ?
Gérard
User avatar
FeikeBoomstra
Posts: 306
Joined: Mon Dec 19, 2005 16:48
Location: Emmen

Post by FeikeBoomstra »

So now the contest: show the position with the highest number of moves, where the position is reachable in a normal game.
Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:

Post by Rein Halbersma »

TAILLE wrote:Hi Rein,
Rein Halbersma wrote:<img src="http://fmjd.org/dias2/save/12155141766.png">
So instead take the above position with *white to move*: 16 kings can move to 7 squares and 2 kings (3 and 15) to 6 squares. In total 124 moves. Adding any other pieces will reduce the number of legal moves. But perhaps someone has created a position in which even more moves are legal?
Alway for fun Rein :
This position cannot establish the record of 124 moves because this position with white to play is illegal. What was the last bkack move ?
Gérard
Image

Position after black moved 41-46 (promoting the man to a king): white to move has 14*7+ 2*4 + 5 + 11 = 122 moves. But I guess the next fun question you are going to ask is how could this position be reached from the initial position? I leave that as an excercise for you

The whole point was to show that I agreed with Ed's claim that it is hard to come up with positions that have more than about 128 moves and 122 is the best I can do. So having memory reserved for 256 moves seems overkill.
Last edited by Rein Halbersma on Tue Jan 04, 2011 09:04, edited 1 time in total.
Ed Gilbert
Posts: 860
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Post by Ed Gilbert »

Bert,

Does your Q6600 show a lot of variation in perft performance the way mine does? I added a command line option to set the process affinity to a particular core, and I found that perft runs almost 50% slower on core 1 than on the other 3. If I don't set the affinity to one of the upper cores then Windows seems to randomly and frequently change the core that perft is running on, thus the inconsistent times. Running on the upper cores the benchmarks are very consistent. I used the functions GetProcessAffinityMask and SetProcessAffinityMask to make this change.

I don't remember my E6700 ever having much of a difference between cores.

-- Ed
BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt »

Ed, i have now included duplicate-move checking and I now get the same numbers for the initial position.
I run the test several times for Perft(11), and I see little variation:
69.50 sec, 69.37 sec, 69.44 sec, 69.37 sec, 69.45 sec

Will do the other positions during the weekend.

Bert
Ed Gilbert
Posts: 860
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:

Post by Ed Gilbert »

Bert, your result makes me think there is something wrong with either my processor or motherboard. It seems that any program or thread that uses the first core runs a lot slower than on the other 3. I will ask about this on one of the computer forums and see if anyone else has experienced this. This also means that my parallel search benchmarks are actually better than what I measured. Searching with 4 threads I get a speedup in "time to depth" of not quite 3x, but if all 4 cores were working at the same speed it would be greater than 3x.

-- Ed
BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt »

For all friends of this 10x10 miracle world.
In the next diagram, how many man can be captured, and how many really different moves are possible ?

Image

Bert
TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Post by TAILLE »

BertTuyt wrote:For all friends of this 10x10 miracle world.
In the next diagram, how many man can be captured, and how many really different moves are possible ?

Image

Bert
Hi,
Pour Damy il y a 5 coups possibles
Gérard
TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Post by TAILLE »

Hi,
Image
This position is very similar but the advantage is the following : white has only one move in order to obtain a draw.
Gérard
Rein Halbersma
Posts: 1722
Joined: Wed Apr 14, 2004 16:04
Contact:

Post by Rein Halbersma »

Image
How many inequivalent moves are there in this position?
Last edited by Rein Halbersma on Tue Jan 04, 2011 09:05, edited 1 time in total.
TAILLE
Posts: 968
Joined: Thu Apr 26, 2007 18:51
Location: FRANCE

Post by TAILLE »

Hi Rein
Rein Halbersma wrote:Image
How many inequivalent moves are there in this position?
Damy answer : 3

The following diagram seems more difficult
Image

The draughts rules are easy but their application can be very difficult !
Gérard
Post Reply