For perft nps, what is a node?

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
AxolotlFever
Posts: 19
Joined: Sun Nov 11, 2018 8:26 pm
Location: Germany
Full name: Louis Mackenzie-Smith

For perft nps, what is a node?

Post by AxolotlFever » Thu Dec 06, 2018 10:38 pm

Hi all,

In making adjustements to Axolotl, I am unsure about how to calculate nps.

1. During perft (so no evaluation or anything), do you include the last level in the numbers you use to calculate perft? Do you do this even if you do not make and unmake a move at the final level?

2. During regular engine activity, currently I calculate nps as regular moves made + quiescent moves made. Is this more or less standard?

Thanks in advance, and apologies for the basic topic, but I have seen many different answers, and so just wanted to get up to date information.

Best regards,
Louis
My chess engine is Axolotl: https://github.com/louism33/Axolotl

phhnguyen
Posts: 291
Joined: Wed Apr 21, 2010 2:58 am
Location: Australia
Full name: Nguyen Hong Pham
Contact:

Re: For perft nps, what is a node?

Post by phhnguyen » Fri Dec 07, 2018 6:00 am

AxolotlFever wrote:
Thu Dec 06, 2018 10:38 pm
Hi all,

In making adjustements to Axolotl, I am unsure about how to calculate nps.

1. During perft (so no evaluation or anything), do you include the last level in the numbers you use to calculate perft?
Yes. Basically it is a recursive function, level n is counted from n - 1.
AxolotlFever wrote:
Thu Dec 06, 2018 10:38 pm

Do you do this even if you do not make and unmake a move at the final level?
The number of nodes in Perft is actually the number of calling make_move function. No move to make, the number must be zero. Beware that we count legal moves to make only.
AxolotlFever wrote:
Thu Dec 06, 2018 10:38 pm

2. During regular engine activity, currently I calculate nps as regular moves made + quiescent moves made. Is this more or less standard?

Thanks in advance, and apologies for the basic topic, but I have seen many different answers, and so just wanted to get up to date information.

Best regards,
Louis
The main purpose of perft is to measure the correctness of (full) generating, incheck, make and unmake functions as well as speed of them. Thus you should not use your quiescent-moves-made if it is too special and / or cannot make normal moves. The Perft function is so simple and won't be run frequently, you should implement it independently with others.

BTW, it is not hard but there is few tricky for both understanding and implementing. If you implement it in your way, you may not compare your results with other programmers (harder to debug your functions). I suggest you to take a look at CPW and may implement your Perft as some psedo codes in that page:

https://www.chessprogramming.org/Perft

User avatar
xr_a_y
Posts: 259
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: For perft nps, what is a node?

Post by xr_a_y » Fri Dec 07, 2018 6:06 am

There are many possibilities.
A node might be :
- when a move is made
- when an evaluation is made
- when the search routine and th qsearch routine is entered

I guess many engines use the last one. Anyway for self speed test, all of then will work.

Note that nps will decrease as engine makes more and more pruning (see http://talkchess.com/forum3/viewtopic.p ... 77#p774538).

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

Re: For perft nps, what is a node?

Post by hgm » Fri Dec 07, 2018 8:12 am

There is a large difference between nodes per second and moves per second. In an engine leaf nodes of the search typically generate moves (sometimes captures only), to conclude that none of those deserves to be searched. So that there aren't any subsequent calls to MakeMove. Under those conditions the number of MakeMoves is equal to the number of calls to MoveGen, so it makes no difference which of the two you count.

This is very different in perft, when you do perform MakeMove on the moves of the deepest level, only to immediately unmaking them. The the number of MakeMove calls is about 30 times larger than the number of MoveGens. And because MakeMove is typically orders of magnitude faster than MoveGen, this gives you enormously large speeds. Which are then totally unrelated to the speed of the corresponding search, which uses a 1:1 mix.

So the best way to guage perft is to just count the moves of the final ply, but refrain from making them. (And then it doesn't matter whether you count MoveGens or MakeMoves.) When you do make the final ply it is best to count MoveGens rather than MakeMoves. The result then typically is about a factor 2 lower than that of the corresponding engine, rather than some 50 times faster.

AxolotlFever
Posts: 19
Joined: Sun Nov 11, 2018 8:26 pm
Location: Germany
Full name: Louis Mackenzie-Smith

Re: For perft nps, what is a node?

Post by AxolotlFever » Fri Dec 07, 2018 8:15 am

Hi, and thanks for your replies,

I have tested my perft routine a lot, and I am confident that it is correct. I am now interested in trying to speed my engine up, so I need some kind of way to compare it to other engines. At the moment I am looking at move gen only, and I get

Code: Select all

Perft 6 (regular board):
Final Nodes at Depth 6: 119060324
Depth 6 took 5 seconds (5569 milliseconds).
NPS: 22289000

Perft 7:
Final Nodes at Depth 7: 3195901860
Depth 7 took 135 seconds (135118 milliseconds).
NPS: 24571000
To calculate NPS, I just do 1000 * node / milliseconds.
1. Does this seem like the right way to calculate nps?
2. Do some engines really break 200 million nps? I am at 20 and stuck!

Kind regards and thanks for your time,
Louis
My chess engine is Axolotl: https://github.com/louism33/Axolotl

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

Re: For perft nps, what is a node?

Post by hgm » Fri Dec 07, 2018 9:43 am

That is moves/sec, not nodes/sec.

Joost Buijs
Posts: 772
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: For perft nps, what is a node?

Post by Joost Buijs » Fri Dec 07, 2018 10:20 am

AxolotlFever wrote:
Fri Dec 07, 2018 8:15 am
Hi, and thanks for your replies,

I have tested my perft routine a lot, and I am confident that it is correct. I am now interested in trying to speed my engine up, so I need some kind of way to compare it to other engines. At the moment I am looking at move gen only, and I get

Code: Select all

Perft 6 (regular board):
Final Nodes at Depth 6: 119060324
Depth 6 took 5 seconds (5569 milliseconds).
NPS: 22289000

Perft 7:
Final Nodes at Depth 7: 3195901860
Depth 7 took 135 seconds (135118 milliseconds).
NPS: 24571000
To calculate NPS, I just do 1000 * node / milliseconds.
1. Does this seem like the right way to calculate nps?
2. Do some engines really break 200 million nps? I am at 20 and stuck!

Kind regards and thanks for your time,
Louis
Your m/s numbers for the initial position are ok, but you'll need a lot of other positions to determine if your move-generator is really bug free, the initial position alone is not enough.

The speed depends upon a lot of different things, so it is difficult to say something about that. My move-generator/do-undo-move combo does anywhere from 70 million m/s to over 200 million m/s depending upon the position I test it with, this is on a 4 GHz. Intel core. For instance on the initial position I get 120 million m/s, this is with full up/down-dating of all the hash-keys and material score.

Perft speed figures don't mean much because (in my case) Perft is largely run from the cache, these figures are usually a lot worse with normal engine use.

zullil
Posts: 5047
Joined: Mon Jan 08, 2007 11:31 pm
Location: PA USA
Full name: Louis Zulli

Re: For perft nps, what is a node?

Post by zullil » Fri Dec 07, 2018 3:38 pm

AxolotlFever wrote:
Fri Dec 07, 2018 8:15 am
Hi, and thanks for your replies,

I have tested my perft routine a lot, and I am confident that it is correct. I am now interested in trying to speed my engine up, so I need some kind of way to compare it to other engines. At the moment I am looking at move gen only, and I get

Code: Select all

Perft 6 (regular board):
Final Nodes at Depth 6: 119060324
Depth 6 took 5 seconds (5569 milliseconds).
NPS: 22289000

Perft 7:
Final Nodes at Depth 7: 3195901860
Depth 7 took 135 seconds (135118 milliseconds).
NPS: 24571000
To calculate NPS, I just do 1000 * node / milliseconds.
1. Does this seem like the right way to calculate nps?
2. Do some engines really break 200 million nps? I am at 20 and stuck!

Kind regards and thanks for your time,
Louis
Well, our node counts agree, but you should test more positions. Take a look at https://www.chessprogramming.net/perfect-perft/

/Chess/Kirby$ ./perft
FEN string = rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
Depth = 6
Leaf nodes = 119060324
Time taken = 2446 ms

/Chess/Kirby$ ./perft
FEN string = rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
Depth = 7
Leaf nodes = 3195901860
Time taken = 57595 ms

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

Re: For perft nps, what is a node?

Post by Sven » Fri Dec 07, 2018 9:47 pm

AxolotlFever wrote:
Thu Dec 06, 2018 10:38 pm
Hi all,

In making adjustements to Axolotl, I am unsure about how to calculate nps.

1. During perft (so no evaluation or anything), do you include the last level in the numbers you use to calculate perft? Do you do this even if you do not make and unmake a move at the final level?

2. During regular engine activity, currently I calculate nps as regular moves made + quiescent moves made. Is this more or less standard?

Thanks in advance, and apologies for the basic topic, but I have seen many different answers, and so just wanted to get up to date information.

Best regards,
Louis
1. For perft I make a difference between "leaves" and "nodes". Counting leaves is the goal for perft so there is nothing to discuss, you *have* to include that number, otherwise you get different results. But measuring "leaves per second" as an indicator for speed is not always meaningful, especially if bulk counting is used (i.e., generate and count all legal moves at depth N-1 but do not make moves). For this purpose I count nodes that were actually visited and processed so "nps" makes sense again. If I would change my perft implementation to a much slower one that makes all moves up to the last level then nodes would include leaves and nps would be quite a bit lower.

2. Opinions differ a lot about the right way of counting nodes during search. Many engines will probably do it in the way you described. Others might omit qsearch nodes, some include illegal moves, etc. To be precise, I count nodes, not moves, and since the root node is a node as well my result would be "1 + (number of moves that were made)". This is repeated for each iteration so of course there are nodes that are visited more than once.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

Post Reply