What is perft(x) exactly meaning?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Jouni
Posts: 1854
Joined: Wed Mar 08, 2006 7:15 pm

What is perft(x) exactly meaning?

Post by Jouni » Mon Apr 06, 2009 10:44 am

Perft calculation got my interest and I ask:

Is it number of possible positions AFTER x plies? Or UNTIL x plies? Is it
counting DIFFERENT positions or ALL positions? Or is it may be actually counting different GAMES?

thanks Jouni

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: What is perft(x) exactly meaning?

Post by sje » Mon Apr 06, 2009 10:58 am

Perft(n) is the number of different move paths of exactly length N from the given position, usually the initial array position.

User avatar
hgm
Posts: 22588
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: What is perft(x) exactly meaning?

Post by hgm » Mon Apr 06, 2009 11:00 am

It counts different games of exactly x plies. So if you are checkmated in less than x plies it does not count. But repdraws are ignored.

MattieShoes
Posts: 718
Joined: Fri Mar 20, 2009 7:59 pm

Re: What is perft(x) exactly meaning?

Post by MattieShoes » Mon Apr 06, 2009 12:28 pm

for the initial position:
perft(0) == 1 (the root node)
perft(1) == 20 (20 legal moves from the initial position)
perft(2) == 400 (20 legal responses for each of the 20 legal moves)
etc.

Note node count is different than perft numbers. You'd expect the node count for perft(2) to be 421 due to 21 internal nodes.

The mates thing threw me off originally.
1. f4 e6
2. g4 Qh4#
Shows up in perft(4) but in perft(5)

The "correct" perft numbers can be found here
If you remove transpositions, it'd look more like this

There's a bunch of cross-referenced sequences related to chess there, though they're mostly just fun for curiosity's sake. :-)

User avatar
Matthias Gemuh
Posts: 3238
Joined: Thu Mar 09, 2006 8:10 am
Contact:

Re: What is perft(x) exactly meaning?

Post by Matthias Gemuh » Mon Apr 06, 2009 4:20 pm

It is the total number of legal moves at ply x, if all legal paths to ply x are considered.
My engine was quite strong till I added knowledge to it.
http://www.chess.hylogic.de

bob
Posts: 20357
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: What is perft(x) exactly meaning?

Post by bob » Mon Apr 06, 2009 5:50 pm

Jouni wrote:Perft calculation got my interest and I ask:

Is it number of possible positions AFTER x plies? Or UNTIL x plies? Is it
counting DIFFERENT positions or ALL positions? Or is it may be actually counting different GAMES?

thanks Jouni
It counts every node for a search to depth (n), counting each interior and tip node that is reached. It is not "iterative" so perft(5) does not include perft(1) through perft(4) nodes...

MattieShoes
Posts: 718
Joined: Fri Mar 20, 2009 7:59 pm

Re: What is perft(x) exactly meaning?

Post by MattieShoes » Tue Apr 07, 2009 4:15 am

Wat? Crafty does not count interior nodes in perft, only tips. perft(2) shows 400, not 421...

Post Reply