definition of a node

[AndrewShort]

if you count before the if (depth == 0)
you would count leaf nodes twice. Once in AlphaBeta and the second time in QS

that's right, which is why I find it hard to believe people count nodes at the very top of search. It means double counting....

How do you figure that? I count at the top of search, where I enter once for each move made at previous level in tree. I then call quiesce after making a move, which is a new position. So I don't see how you can possibly call that "double counting"...

if the code is:

search(...)
{
nodes++;
if depth == 0 then qsearch(...);
more code here...;
}

then if depth is 0, you count the node (position), then you count the same position again at the top of qsearch. Isn't that double counting?

[bob]

When I was looking at Heinz's futility/razoring/extended-futility stuff, his way of calling search gave me a headache. He selects a move, then recursively calls search and passes it that move to make/unmake. This changes the "depth value" by one ply which was confusing. My search is the classic:

Int Search (int alpha, int beta) {

For (mv = NextMove(); mv; ) {
Make(mv)
if (depth - 1 > 0)
v = -Search(-beta, -alpha)
else
v = -Quiesce(-beta, -alpha)
{normal alpha/beta stuff here}
}

}

[bob]

if you count before the if (depth == 0)
you would count leaf nodes twice. Once in AlphaBeta and the second time in QS

that's right, which is why I find it hard to believe people count nodes at the very top of search. It means double counting....

How do you figure that? I count at the top of search, where I enter once for each move made at previous level in tree. I then call quiesce after making a move, which is a new position. So I don't see how you can possibly call that "double counting"...

if the code is:

search(...)
{
nodes++;
if depth == 0 then qsearch(...);
more code here...;
}

then if depth is 0, you count the node (position), then you count the same position again at the top of qsearch. Isn't that double counting?

Why would you write the code like that???

I gave a simple recursive search in my other response, and I think that is much easier to understand. Why would you first call search, and then at the top of search test for depth==0 and call Quiesce() if true? Why not directly call Quiesce() if depth==1 at previous ply and save the overhead of the unnecessary procedure call???

Most of us do this inside search:

....
....
MakeMove()
if (depth - 1 > 0)
v = -Search(....)
else
v = -Quiesce(....)
UnmakeMove()

That is far cleaner and easier to follow. not to mention faster.

If you are determined to write it like that, just move the nodes++ to right below the test/call to quiesce() and the problem goes away, although the performance problem is still present and accounted for...

[michiguel]

if you count before the if (depth == 0)
you would count leaf nodes twice. Once in AlphaBeta and the second time in QS

that's right, which is why I find it hard to believe people count nodes at the very top of search. It means double counting....

You better believe it buddy. I double count . Its not completely clear what a better way of doing it is (with no overhead) but if someone posts one I guess I will conform. I just want to do what others do so I can compare, node counts for their own sake are not that interesting to me.

-Sam

Conceptually, this is what I do:

Code: Select all

makemove ()
{
     makemoves++;
     etc.
     return;
}


So, in search

loop over moves {

     makemove();
     if move was illegal {
        unmakemove;
        makemoves--;
        continue;
     }
     search()
     etc.
}

My node counts are number or legal makemoves.

Miguel

[Edmund]

When I was looking at Heinz's futility/razoring/extended-futility stuff, his way of calling search gave me a headache. He selects a move, then recursively calls search and passes it that move to make/unmake. This changes the "depth value" by one ply which was confusing. My search is the classic:

Int Search (int alpha, int beta) {

For (mv = NextMove(); mv; ) {
Make(mv)
if (depth - 1 > 0)
v = -Search(-beta, -alpha)
else
v = -Quiesce(-beta, -alpha)
{normal alpha/beta stuff here}
}

}

calling the QS in the next iteration is as well done in TSCP,
Bruce Moreland's chess tutorial and CPW. So I did it too not knowing any other. Changing to this version described here (and thus saving one function call) increased my nps by about 4% ... thanks for the info.

regards Edmund

[Gerd Isenberg]

calling the QS in the next iteration is as well done in TSCP,
Bruce Moreland's chess tutorial and CPW. So I did it too not knowing any other. Changing to this version described here (and thus saving one function call) increased my nps by about 4% ... thanks for the info.

regards Edmund

Nice improvement! Often Pseudo or didactical code deals with clarification rather than efficiency.

From Schaeffer's pdf course 1. Introduction

Search Reality

• Most of the core AI search algorithms
can be expressed in 20 lines of code
• Is search really that simple?

M. Newborn, 1985

“If the search algorithm is really 20 lines of
code, then why is my search routine over 20
pages of code?”

[sje]

If you have a legal move only generator:

Code: Select all

  ExecuteMove();
  node_count++;

If you don't:

Code: Select all

  ExecuteMove();
  if (LegalPosition())
    node_count++;

[BubbaTough]

Conceptually, this is what I do:

Code: Select all

makemove ()
{
     makemoves++;
     etc.
     return;
}


So, in search

loop over moves {

     makemove();
     if move was illegal {
        unmakemove;
        makemoves--;
        continue;
     }
     search()
     etc.
}

My node counts are number or legal makemoves.

Miguel

This makes sense, and has no extra overhead. I will switch to this if this or an equivalent is the most common approach. Sigh. It was already frustrating to see a number of programs (Crafty, Romi,...) with better node counts than me and this is just going to make it worse .

-Sam

[CThinker]

If you have a legal move only generator:

Code: Select all

  ExecuteMove();
  node_count++;

If you don't:

Code: Select all

  ExecuteMove();
  if (LegalPosition())
    node_count++;

Exactly!

In Thinker, the test for legal move is done before any calls to MakeMove. The effect is that MakeMove() only gets called for legal moves.

So, the node count increment is simply in MakeMove() - in just one place - instead of sprinkled all over Search/RootSearch/QSearch/VerficationSearch/etc.

[Tony Thomas]

Conceptually, this is what I do:

Code: Select all

makemove ()
{
     makemoves++;
     etc.
     return;
}


So, in search

loop over moves {

     makemove();
     if move was illegal {
        unmakemove;
        makemoves--;
        continue;
     }
     search()
     etc.
}

My node counts are number or legal makemoves.

Miguel

This makes sense, and has no extra overhead. I will switch to this if this or an equivalent is the most common approach. Sigh. It was already frustrating to see a number of programs (Crafty, Romi,...) with better node counts than me and this is just going to make it worse .

-Sam

They might have a higher node count, but are they stronger than your program? Crafty might be stronger on a parallel system, but romi, not yet. Then again if your program is the strongest, you could divide your nodes by 1000 and gets away with it saying you have an extra smart search routine.