This is totally weird ... Don't understand at all

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Greg Strong
Posts: 388
Joined: Sun Dec 21, 2008 5:57 pm
Location: Washington, DC

This is totally weird ... Don't understand at all

Post by Greg Strong » Sat Nov 13, 2010 10:21 pm

Ok, so I'm working on Quadrox (which is probably something like 2500 ELO at present) and I decided to add some statistics to try to get a feel for some things... The first thing I notice is that my QNode % gets up to almost 90 percent (!) in the midgame. So, obviously something is wrong ...

My QSearch generates captures only (pruning out captures with negative SEE scores) and doesn't generate checking moves unless a capture happens to be a check. But when a player happens to be in check in the QSearch, I generate and try all check evasions, including non-captures and losing captures. I don't return checkmate scores in QSearch.

So my first thought to try to reduce the QNode % was to only generate captures even when in check. It seems to me that this would have to reduce the total node count. But when I tried it, my total node count almost doubled! (The count of non-qnodes went up by about a third.) I can't imagine what could be going on here... Anyone have any ideas?

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

Re: This is totally weird ... Don't understand at all

Post by hgm » Sat Nov 13, 2010 10:44 pm

Sorry to barge in with an off-topic question:

Did you ever fix those two tiny problems in ChessV (the XQ rank on output being off by one, and the not having knightmate in the variant feature)?

User avatar
Greg Strong
Posts: 388
Joined: Sun Dec 21, 2008 5:57 pm
Location: Washington, DC

Re: This is totally weird ... Don't understand at all

Post by Greg Strong » Sat Nov 13, 2010 11:56 pm

Actually I did - just mailed you a new version that should (hopefully) fix both problems ...

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

Re: This is totally weird ... Don't understand at all

Post by bob » Sun Nov 14, 2010 4:07 am

Greg Strong wrote:Ok, so I'm working on Quadrox (which is probably something like 2500 ELO at present) and I decided to add some statistics to try to get a feel for some things... The first thing I notice is that my QNode % gets up to almost 90 percent (!) in the midgame. So, obviously something is wrong ...

My QSearch generates captures only (pruning out captures with negative SEE scores) and doesn't generate checking moves unless a capture happens to be a check. But when a player happens to be in check in the QSearch, I generate and try all check evasions, including non-captures and losing captures. I don't return checkmate scores in QSearch.

So my first thought to try to reduce the QNode % was to only generate captures even when in check. It seems to me that this would have to reduce the total node count. But when I tried it, my total node count almost doubled! (The count of non-qnodes went up by about a third.) I can't imagine what could be going on here... Anyone have any ideas?
90% is pretty reasonable and is pretty close to what I see in Crafty... The tree is exponential, and for every non-q-search node at the end of a branch, you will get 1 q-search node at a minimum. That is a lot...

Uri Blass
Posts: 8752
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: This is totally weird ... Don't understand at all

Post by Uri Blass » Sun Nov 14, 2010 9:20 am

I think that the first question is how do you define qsearch node.

I define qsearch node only as a node that you get after making a move inside the qsearch(in other words additional nodes that you get because of doing qsearch instead of returning evaluation).

I guess that Bob defines qnodes in a different way but by my definition you are going to get 0 qnodes in the first plies in positions like fine70 and in this case 90% in the middle game is certainly not normal and suggests that the program has a bug.

For the original question
I also do not understand why the qnodes went up(in the program of the poster) after generating only captures in reply to check so I cannot give an answer to this question.

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

Re: This is totally weird ... Don't understand at all

Post by hgm » Sun Nov 14, 2010 7:36 pm

When you generate only captures when in check, and you have none, what score do you return?

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

Re: This is totally weird ... Don't understand at all

Post by bob » Tue Nov 16, 2010 6:32 pm

Uri Blass wrote:I think that the first question is how do you define qsearch node.

I define qsearch node only as a node that you get after making a move inside the qsearch(in other words additional nodes that you get because of doing qsearch instead of returning evaluation).

I guess that Bob defines qnodes in a different way but by my definition you are going to get 0 qnodes in the first plies in positions like fine70 and in this case 90% in the middle game is certainly not normal and suggests that the program has a bug.

For the original question
I also do not understand why the qnodes went up(in the program of the poster) after generating only captures in reply to check so I cannot give an answer to this question.
I use the classic definition, that is, any node where you have the option of standing pat, or searching one or more moves.

The better alternative might be to go to a more technical set of terms:

1. Internal nodes: nodes where remaining depth > 0 and there is no stand pat option at all.

2. Frontier nodes: The node you first reach the q-search code with remaining depth=0. In any single path, this would be the _first_ node where you have a stand-pat option.

3. q-search node: Nodes beyond the frontier that are only reached by selectively searching (usually just captures, but could include checks, etc.)

4. Leaf node: A node where there are no additional moves to search and all you can do is return the static evaluation.


But basically, inside a chess engine that has Search() and Quiesce() functions, Search() includes (1) above, Quiesce() includes the remaining 3 types... And hence they get called q-search nodes...

Gerd Isenberg
Posts: 2146
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: This is totally weird ... Don't understand at all

Post by Gerd Isenberg » Tue Nov 16, 2010 7:25 pm

bob wrote:
Uri Blass wrote:I think that the first question is how do you define qsearch node.

I define qsearch node only as a node that you get after making a move inside the qsearch(in other words additional nodes that you get because of doing qsearch instead of returning evaluation).

I guess that Bob defines qnodes in a different way but by my definition you are going to get 0 qnodes in the first plies in positions like fine70 and in this case 90% in the middle game is certainly not normal and suggests that the program has a bug.

For the original question
I also do not understand why the qnodes went up(in the program of the poster) after generating only captures in reply to check so I cannot give an answer to this question.
I use the classic definition, that is, any node where you have the option of standing pat, or searching one or more moves.

The better alternative might be to go to a more technical set of terms:

1. Internal nodes: nodes where remaining depth > 0 and there is no stand pat option at all.

2. Frontier nodes: The node you first reach the q-search code with remaining depth=0. In any single path, this would be the _first_ node where you have a stand-pat option.

3. q-search node: Nodes beyond the frontier that are only reached by selectively searching (usually just captures, but could include checks, etc.)

4. Leaf node: A node where there are no additional moves to search and all you can do is return the static evaluation.


But basically, inside a chess engine that has Search() and Quiesce() functions, Search() includes (1) above, Quiesce() includes the remaining 3 types... And hence they get called q-search nodes...
The CPW Node page also gives Heinz' definitions beside Hyatt's. Agreement on Quiescent nodes. Heinz defined Horizon nodes with depth 0 as member of Quiescent nodes, but not Frontier nodes (Heinz depth 1 vs. Hyatt depth 0). Who was first? ;-)

Heinz' used his definition in ICCA/ICGA papers on extended futility pruning and that like, his thesis and his book Scalable Search in Computer Chess, all certainly proofread by experts I guess.

Internal or Interior nodes and Leaf nodes are to my knowledge not depth but only topology dependent, that is whether they were further expanded or not, and may occur at depth > 0, == 0 or < 0. A terminal node (subset of leaves) with mate, stalemate or repetition may for instance occur at depth > 0.

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

Re: This is totally weird ... Don't understand at all

Post by bob » Tue Nov 16, 2010 8:53 pm

Gerd Isenberg wrote:
bob wrote:
Uri Blass wrote:I think that the first question is how do you define qsearch node.

I define qsearch node only as a node that you get after making a move inside the qsearch(in other words additional nodes that you get because of doing qsearch instead of returning evaluation).

I guess that Bob defines qnodes in a different way but by my definition you are going to get 0 qnodes in the first plies in positions like fine70 and in this case 90% in the middle game is certainly not normal and suggests that the program has a bug.

For the original question
I also do not understand why the qnodes went up(in the program of the poster) after generating only captures in reply to check so I cannot give an answer to this question.
I use the classic definition, that is, any node where you have the option of standing pat, or searching one or more moves.

The better alternative might be to go to a more technical set of terms:

1. Internal nodes: nodes where remaining depth > 0 and there is no stand pat option at all.

2. Frontier nodes: The node you first reach the q-search code with remaining depth=0. In any single path, this would be the _first_ node where you have a stand-pat option.

3. q-search node: Nodes beyond the frontier that are only reached by selectively searching (usually just captures, but could include checks, etc.)

4. Leaf node: A node where there are no additional moves to search and all you can do is return the static evaluation.


But basically, inside a chess engine that has Search() and Quiesce() functions, Search() includes (1) above, Quiesce() includes the remaining 3 types... And hence they get called q-search nodes...
The CPW Node page also gives Heinz' definitions beside Hyatt's. Agreement on Quiescent nodes. Heinz defined Horizon nodes with depth 0 as member of Quiescent nodes, but not Frontier nodes (Heinz depth 1 vs. Hyatt depth 0). Who was first? ;-)

Heinz' used his definition in ICCA/ICGA papers on extended futility pruning and that like, his thesis and his book Scalable Search in Computer Chess, all certainly proofread by experts I guess.

Internal or Interior nodes and Leaf nodes are to my knowledge not depth but only topology dependent, that is whether they were further expanded or not, and may occur at depth > 0, == 0 or < 0. A terminal node (subset of leaves) with mate, stalemate or repetition may for instance occur at depth > 0.
Heinz had an extremely demented approach to search. He was off by 1 ply in his terminology, which caused lots of confusion. It makes understanding his terms for futility pruning and such difficult since his numbers are off by 1 from everyone else's. For example, for me, depth=1 is a full-width ply. Not for Heinz. Took me a while to get my head around that terminology when I first played with futility and extended futility pruning...

As far as "who was first" that is easy to answer. My first full-width program was Blitz version 6, circa 1979 or so after it had become apparent that full-width was here to stay (Chess 4.x, Duchess, Belle, etc.) We all used the idea of depth=0 as the "frontier" (or as we called it, the start of the q-search). So depth=0 has been around a lot longer than Dark Thought. Ken Thompson's original negamax used that in fact (if depth - 1 > 0 then v=-Search(etc) else v=-Quiesce(etc);

Gerd Isenberg
Posts: 2146
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: This is totally weird ... Don't understand at all

Post by Gerd Isenberg » Tue Nov 16, 2010 9:55 pm

bob wrote: Heinz had an extremely demented approach to search. He was off by 1 ply in his terminology, which caused lots of confusion. It makes understanding his terms for futility pruning and such difficult since his numbers are off by 1 from everyone else's. For example, for me, depth=1 is a full-width ply. Not for Heinz. Took me a while to get my head around that terminology when I first played with futility and extended futility pruning...

As far as "who was first" that is easy to answer. My first full-width program was Blitz version 6, circa 1979 or so after it had become apparent that full-width was here to stay (Chess 4.x, Duchess, Belle, etc.) We all used the idea of depth=0 as the "frontier" (or as we called it, the start of the q-search). So depth=0 has been around a lot longer than Dark Thought. Ken Thompson's original negamax used that in fact (if depth - 1 > 0 then v=-Search(etc) else v=-Quiesce(etc);
Sure, your program was first, but I mean an explicit definition of "frontier node" written in some paper, but no implicit semantic, which might be different due to language issues or whatever.

By the way, Heinz depth == 1 nodes are also (the frontier of) full-width nodes, only conditionally subject of futility pruning, that is to exploit the peculiarities of "standing pat'' at depth <= 0 nodes.

http://people.csail.mit.edu/heinz/dt/node18.html

Post Reply