nps of Crafty same as Robbo/SF

[Chan Rasjid]

The nps reported by Crafty 23.3 seems a little too high as compared to the other programs; eg; on my Athlon 64 1cpu:-
Snailchess w/o evaluation = 1.7M nps
Crafty = about 1.7 to 2.0M nps.
Robbo/Stockfish about 1.0 M nps.

After shifting Crafty's increment of node counts to the start of the search call, the nps seems about the same as that of Robbolitto and Stockfish:

Code: Select all

int Search(TREE * RESTRICT tree, int alpha, int beta, int wtm, int depth,
    int ply, int do_null) {
  register BITBOARD start_nodes = ++tree->nodes_searched;

int QuiesceChecks(TREE * RESTRICT tree, int alpha, int beta, int wtm, int ply) {
  register int o_alpha, value;
  register int *next_move;
  register int *movep, *sortv, temp;
  ++tree->nodes_searched;  

With the code changes above, the nps = 900k to 1.0 M nps.

Rasjid

[bob]

The nps reported by Crafty 23.3 seems a little too high as compared to the other programs; eg; on my Athlon 64 1cpu:-
Snailchess w/o evaluation = 1.7M nps
Crafty = about 1.7 to 2.0M nps.
Robbo/Stockfish about 1.0 M nps.

After shifting Crafty's increment of node counts to the start of the search call, the nps seems about the same as that of Robbolitto and Stockfish:

Code: Select all

int Search(TREE * RESTRICT tree, int alpha, int beta, int wtm, int depth,
    int ply, int do_null) {
  register BITBOARD start_nodes = ++tree->nodes_searched;

int QuiesceChecks(TREE * RESTRICT tree, int alpha, int beta, int wtm, int ply) {
  register int o_alpha, value;
  register int *next_move;
  register int *movep, *sortv, temp;
  ++tree->nodes_searched;  

With the code changes above, the nps = 900k to 1.0 M nps.

Rasjid

It doesn't count correctly however, because inside the search I do a Make() and Unmake() for move that get pruned, and that does not get counted, yet it incurs all the overhead of updating the board and such...

[Chan Rasjid]

The nps reported by Crafty 23.3 seems a little too high as compared to the other programs; eg; on my Athlon 64 1cpu:-
Snailchess w/o evaluation = 1.7M nps
Crafty = about 1.7 to 2.0M nps.
Robbo/Stockfish about 1.0 M nps.

After shifting Crafty's increment of node counts to the start of the search call, the nps seems about the same as that of Robbolitto and Stockfish:

Code: Select all

int Search(TREE * RESTRICT tree, int alpha, int beta, int wtm, int depth,
    int ply, int do_null) {
  register BITBOARD start_nodes = ++tree->nodes_searched;

int QuiesceChecks(TREE * RESTRICT tree, int alpha, int beta, int wtm, int ply) {
  register int o_alpha, value;
  register int *next_move;
  register int *movep, *sortv, temp;
  ++tree->nodes_searched;  

With the code changes above, the nps = 900k to 1.0 M nps.

Rasjid

It doesn't count correctly however, because inside the search I do a Make() and Unmake() for move that get pruned, and that does not get counted, yet it incurs all the overhead of updating the board and such...

My guess is most programs only count nodes at the start of search(); ie only nodes that entail some work done; pruned moves
with just make() and unmake() don't get counted.

I was wondering what I did wrong that my nps without evaluation is lower than that of Crafty with a full evaluation. So Crafty seems to have many pruned nodes counted that do not call search(). Without counting these, it seems the nps of Crafty is within what I expect. It is almost the same as that of the other top programs like Robbolitto and Stockfish and both these are close in nps.

So it seems now that my Snaichess nps is still not too bad - that I have not done anything too bad.

Rasjid.

[bob]

The nps reported by Crafty 23.3 seems a little too high as compared to the other programs; eg; on my Athlon 64 1cpu:-
Snailchess w/o evaluation = 1.7M nps
Crafty = about 1.7 to 2.0M nps.
Robbo/Stockfish about 1.0 M nps.

After shifting Crafty's increment of node counts to the start of the search call, the nps seems about the same as that of Robbolitto and Stockfish:

Code: Select all

int Search(TREE * RESTRICT tree, int alpha, int beta, int wtm, int depth,
    int ply, int do_null) {
  register BITBOARD start_nodes = ++tree->nodes_searched;

int QuiesceChecks(TREE * RESTRICT tree, int alpha, int beta, int wtm, int ply) {
  register int o_alpha, value;
  register int *next_move;
  register int *movep, *sortv, temp;
  ++tree->nodes_searched;  

With the code changes above, the nps = 900k to 1.0 M nps.

Rasjid

It doesn't count correctly however, because inside the search I do a Make() and Unmake() for move that get pruned, and that does not get counted, yet it incurs all the overhead of updating the board and such...

My guess is most programs only count nodes at the start of search(); ie only nodes that entail some work done; pruned moves
with just make() and unmake() don't get counted.

I was wondering what I did wrong that my nps without evaluation is lower than that of Crafty with a full evaluation. So Crafty seems to have many pruned nodes counted that do not call search(). Without counting these, it seems the nps of Crafty is within what I expect. It is almost the same as that of the other top programs like Robbolitto and Stockfish and both these are close in nps.

So it seems now that my Snaichess nps is still not too bad - that I have not done anything too bad.

Rasjid.

I suppose you can count 'em any way you want. The general definition has always been "node" == "chess position". And clearly, once you Make() a move, you have a new position. Until the idea of making/discarding/unmaking moves came along, incrementing the counter at the top of search was almost the same. And today, some programs use what is to me a bizarre approach of doing their search code, such that they choose a move to search, and recursively call search which makes that move, generates the next set, picks one, calls search, etc.

That approach counts like I count. I modified the way I count nodes when I found myself making/unmaking moves but not calling search in many cases in the last 4 plies where I do forward pruning.

So the bottom line is, how do you define "node". I still subscribe to "node = position" and the way I count nodes at present is exactly that. If you count calls to search, that may or may not be the same thing. No forward pruning? Then either way works exactly the same. But with forward pruning? My way keeps the traditional meaning of "node == position".

Doesn't really matter which way it's counted, but if you spend the time generating a move, selecting it for search, then making and unmaking it, without counting that effort unless you actually recursively call search between the make and unmake, then you are really counting something other than the traditional concept of "node"... Since most programs disagree on ply/depth due to differing extensions, it probably doesn't matter that much anyway.

[Mangar]

Hi,

it is today very hard to compare node count of programs. If you have foreward pruning in the move loop you may have the following problem:

Spike:

Do Move
Check for late move based pruning
Undo Move

Stockfish (if I remember right):

Check for late move based pruning
Do Move
Undo Move

Spike needs the Do Move for to find "non pruning" conditions (such as checking moves). Stockfish has an algorithm to find this without doing a move.

If I follow Bob Spike should count the prunings and Stockfish should not as it does not need a do move for pruning checks.

The only solution I have is: do not compare nps if you do not know how it is calcuated.

Greetings Volker

[Chan Rasjid]

A chess program computes the nps to give an idea how well the program is implemented and also if certain features are costly. Other things being equal, a high nps is a very important target - it means the program is implemented very efficiently and could process many nodes per second. If nps of different programs could be compared, it would be better as then we can know if we are doing things as best as is possible.

Because there could be different views on nodes or the way to count nodes, the simplest way most programs do is to increment the nodes counter at the top of a new search representing a new node visited - very likely, programs do not count wrongly in this manner! We don't have to always keep track of when and where if we edit our program with new makemove()s in our program.

Counting nodes at the start of search simplifies many things. The programmer wants to know how fast it processes a node in general and only those that require special processing. Because of this, not counting pruned nodes is trivial; it is also the more normal way most would count nodes. One of the most important thing nps tell us is how much we are doing with evaluation? Too much brings down the nps drastically and too little means we could afford to put more knowledge in our program. So the nps is like a figure to tell us what next we should do to improve our program.

Rasjid.

[bob]

A chess program computes the nps to give an idea how well the program is implemented and also if certain features are costly. Other things being equal, a high nps is a very important target - it means the program is implemented very efficiently and could process many nodes per second. If nps of different programs could be compared, it would be better as then we can know if we are doing things as best as is possible.

Because there could be different views on nodes or the way to count nodes, the simplest way most programs do is to increment the nodes counter at the top of a new search representing a new node visited - very likely, programs do not count wrongly in this manner! We don't have to always keep track of when and where if we edit our program with new makemove()s in our program.

Counting nodes at the start of search simplifies many things. The programmer wants to know how fast it processes a node in general and only those that require special processing. Because of this, not counting pruned nodes is trivial; it is also the more normal way most would count nodes. One of the most important thing nps tell us is how much we are doing with evaluation? Too much brings down the nps drastically and too little means we could afford to put more knowledge in our program. So the nps is like a figure to tell us what next we should do to improve our program.

Rasjid.

That's all well and good, but this isn't about simplicity, it is about accuracy. Since the classic AI definition of "node" is "chess position" I'm trying to count nodes in a way that is consistent with that definition.

I have not looked at how stockfish does pruning. If, as Volker says, they make their decision to prune a move before they make the move, then I would not count that pruned move as a node since it did not result in a new position, having never been made. In my case, making and unmaking a move has a definite cost, as does asking the question "does this move check the opponent?". I first Make() the move, which produces a new position/node, I then do additional work to determine what to do. And if I prune, I have to Unmake() the move and loop again.

In Quiesce() I do not count an entry to Quiesce() as a node. That was counted at the previous ply where I made the move to produce the position that Quiesce() receives. If Quiesce() makes any moves to search deeper, those are counted. Otherwise a call to Quiesce() that results in no captures does not get counted since it was already counted when the move was made.

If you don't want to count pruned moves as nodes, that's ok. But if you make/unmake a move, determine if it delivers check, possibly do a static evaluation to make pruning or reduction or extension decisions, and then decide to prune that move, not counting it is incorrect by the classic definition of node. Doesn't matter how many other programs use a different definition, a node is a new position, PI is 3.141592, branching factor in chess can never average less than 2 over a game, effective branching factor can, etc. Common and consistent terminology is critical in reporting results. I don't think my numbers are inflated at all. And I'm not going to try to change my numbers to match those that are not calculating them correctly in the strictest sense of the term.

If the goal is to produce the lowest possible NPS, then not counting a node whenever possible will produce that. If the goal is to produce the highest possible NPS, then counting things that are really not nodes can help. I only want to count "real" nodes... how many positions did I encounter during that search? the node count is exact for that question.

[Chan Rasjid]

Ok, It is correct. In an academic sense, nodes and the search space have a stricter interpretation and keeping to that is correct. Crafty is also an academic program.

My earlier post is more on the practical and utilitarian aspect of nodes-keeping.

Best Regards,
Rasjid

[bob]

Ok, It is correct. In an academic sense, nodes and the search space have a stricter interpretation and keeping to that is correct. Crafty is also an academic program.

My earlier post is more on the practical and utilitarian aspect of nodes-keeping.

Best Regards,
Rasjid

No question that nodes++ at the top of search() and quiesce() is the simplest approach. But a simple question. You take a program that does that, and inside the search loop you add new code to make and unmake every last move, do an evaluation, etc. And out of that set of moves, you decide that only one deserves searching to the next ply. Did you _really_ think that program's nps just dropped by some big factor, because you added forward-pruning? There's been a years-old argument about hash hits, since with a hash hit you effectively re-search that entire sub-tree instantly. And one could make a legitimate argument that hashing is an optimization that saves time but searches the same tree. I've never tried to count nodes and store them in a hash entry, because we also allow hits on draft > depth, not just on draft = depth, which would inflate things.

I watch my NPS quite carefully. Not to compare with others. But to compare with an older version when I make changes. If it drops, I look for more efficient ways to do whatever I changed. I'm not a big fan of comparing nodes, nps, depth, and such between different programs because non everyone counts nodes the same way, and most certainly depth is pretty meaningless since some extend a lot, some reduce a lot, each of which affects the reported depth (but not necessarily the reported result) in wildly different ways.

[Chan Rasjid]

But a simple question. You take a program that does that, and inside the search loop you add new code to make and unmake every last move, do an evaluation, etc. And out of that set of moves, you decide that only one deserves searching to the next ply. Did you _really_ think that program's nps just dropped by some big factor, because you added forward-pruning? There's been a years-old argument about hash hits, since with a hash hit you effectively re-search that entire sub-tree instantly. And one could make a legitimate argument that hashing is an optimization that saves time but searches the same tree.

The only reason most keep an nps is to see the effect and effectiveness when changes are made to a program. I earlier found my nps too low as compared to those of Robbolitto and stockfish; so now I did some optimization and it seems I could make further changes that could make my program faster. One thing my low nps hint at is that I am not doing my evaluation correctly; I now have an idea of how better to re-write my evaluator. So this is the practical use of keeping an nps. In my case, comparison with the nps of other programs is helpful.

Rasjid