Speedup with bitboards on 64-bit CPUs

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.
Jacob

Re: Speedup with bitboards on 64-bit CPUs

Post by Jacob » Mon May 28, 2007 9:49 pm

Chan Rasjid wrote:Hello,
But once again, in the hope that one day it will sink in, ....
Vasik Rajlich has become sort of Jesus Christ in computer chess, Osipov has become sort of Son of Jesus Christ in computer chess and Sergei Markoff is very like St. Peter...If after the appearance of sort of Messiah preaching the Gospel of Bitboards in computer chess and things don't sink in, it never will.

But it is still better that Vincent comes back from retirement as St.George without the Dragon don't an epic make.
So while you might be a bit faster in generating _all_ moves, you won't be as fast generating just captures, and for my program, that happens _far_ more frequently.
I'm not sure your statistic is correct here as my QS nodes is about average 30-40%

Rasjid
If I understand it correctly, Crafty generates and tries captures before noncaptures in the main search, so if those moves cause cutoffs, the normal moves won't have to be generated at all. QS isn't the only place for savings.

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: Speedup with bitboards on 64-bit CPUs

Post by Chan Rasjid » Tue May 29, 2007 5:58 am

Hello,
If I understand it correctly, Crafty generates and tries captures before noncaptures in the main search, so if those moves cause cutoffs, the normal moves won't have to be generated at all. QS isn't the only place for savings.
The arithmetic seems like this:-
for every fail high node, there is a corresponding fail low child node that needs to generate and try all moves assuming no exceptional pruning. Main search with mid-game average of 36 moves means non-qs nodes (60-70%) have a crude average of searching about 18 moves per node. So it seems that there is more generation of non-qs moves in general.

Best Regards,
Rasjid
Don't believe when you're told "There's no free lunch!" There is Linux.

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

Re: Speedup with bitboards on 64-bit CPUs

Post by bob » Tue May 29, 2007 3:15 pm

Chan Rasjid wrote:Hello,
But once again, in the hope that one day it will sink in, ....
Vasik Rajlich has become sort of Jesus Christ in computer chess, Osipov has become sort of Son of Jesus Christ in computer chess and Sergei Markoff is very like St. Peter...If after the appearance of sort of Messiah preaching the Gospel of Bitboards in computer chess and things don't sink in, it never will.

But it is still better that Vincent comes back from retirement as St.George without the Dragon don't an epic make.
So while you might be a bit faster in generating _all_ moves, you won't be as fast generating just captures, and for my program, that happens _far_ more frequently.
I'm not sure your statistic is correct here as my QS nodes is about average 30-40%

Rasjid
can't be. At some point you reach depth=0 and have to generate captures. How can that be smaller than the number of nodes at the previous ply? And that assumes that every time you reach depth=0, you have zero captures and don't advance to the next ply. Most don't count the first encounter of depth=0 as a q-search node, it is more commonly called a "frontier" node. But it is still a captures-only type node.

More importantly, captures need to be searched first even in interior nodes (where you have no hash move). Again, generating captures-only efficiently helps...

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

Re: Speedup with bitboards on 64-bit CPUs

Post by bob » Tue May 29, 2007 3:18 pm

Chan Rasjid wrote:Hello,
If I understand it correctly, Crafty generates and tries captures before noncaptures in the main search, so if those moves cause cutoffs, the normal moves won't have to be generated at all. QS isn't the only place for savings.
The arithmetic seems like this:-
for every fail high node, there is a corresponding fail low child node that needs to generate and try all moves assuming no exceptional pruning. Main search with mid-game average of 36 moves means non-qs nodes (60-70%) have a crude average of searching about 18 moves per node. So it seems that there is more generation of non-qs moves in general.

Best Regards,
Rasjid
You are counting the wrong thing. You don't count the number of non-capture and capturing moves. You count the number of times you have to _generate_ captures only vs generating non-captures.

That changes the math a lot. The q-search almost has to be > 50% of the total nodes searched unless you look at simple endings like fine 70. Every branch reaches a depth=0 point where it transitions to the q-search. Exponential trees mean this is a big percentage of total nodes searched since these are the deepest nodes searched.

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: Speedup with bitboards on 64-bit CPUs

Post by Chan Rasjid » Tue May 29, 2007 4:09 pm

Hello,
That changes the math a lot. The q-search almost has to be > 50% of the total nodes searched unless you look at simple endings like fine 70. Every branch reaches a depth=0 point where it transitions to the q-search. Exponential trees mean this is a big percentage of total nodes searched since these are the deepest nodes searched.
I count qs-node as a node reached after a legal move that is generated by a qs-generator(capture/ep/promote). So this include your frontier nodes.

It is ok now, I think closer to above 50% after I disabled pruning of "bad" qs moves (not with SEE) which may be done too drastically. But near endgame and if it is winning it seems qs-node% drops quite low to 10-30%.

Rasjid
Don't believe when you're told "There's no free lunch!" There is Linux.

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

Re: Speedup with bitboards on 64-bit CPUs

Post by bob » Tue May 29, 2007 9:23 pm

Chan Rasjid wrote:Hello,
That changes the math a lot. The q-search almost has to be > 50% of the total nodes searched unless you look at simple endings like fine 70. Every branch reaches a depth=0 point where it transitions to the q-search. Exponential trees mean this is a big percentage of total nodes searched since these are the deepest nodes searched.
I count qs-node as a node reached after a legal move that is generated by a qs-generator(capture/ep/promote). So this include your frontier nodes.

It is ok now, I think closer to above 50% after I disabled pruning of "bad" qs moves (not with SEE) which may be done too drastically. But near endgame and if it is winning it seems qs-node% drops quite low to 10-30%.

Rasjid
The obvious question is where are the other 70% of the "good moves" showing up? second? third? last?

I'd suspect an error in how you are measuring the statistic rather than something that appears to be nearly random move ordering. You should be able to print a tree for something like fine70 and determine what is happening...

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

Quiescence search width

Post by sje » Tue May 29, 2007 10:02 pm

How many moves on average are present at a quiescence node? Counting only captures and promotions, it's usually not too many.

I note that Paradise almost always looked at only one move per quiescence node and that included non gainers.

What would happen if someone took a traditional AB quiescence search and artificially limited the width to one or two moves? It might be a worthwhile experiment.

Greg McGlynn

Re: Quiescence search width

Post by Greg McGlynn » Wed May 30, 2007 3:36 pm

sje wrote:How many moves on average are present at a quiescence node? Counting only captures and promotions, it's usually not too many.

I note that Paradise almost always looked at only one move per quiescence node and that included non gainers.

What would happen if someone took a traditional AB quiescence search and artificially limited the width to one or two moves? It might be a worthwhile experiment.
I tested this out in my own program. I limited the quiescence search to 1 move searched per node and played it against the original version. My quiescence search uses MVV/LVA move ordering and prunes losing captures, so this is simply trying the biggest nonlosing capture at each quiescence node. I think this sometimes saves significant numbers of nodes in middlegame positions (less so in the endgame when fewer captures are available). After 255 games (1s per move) the modified version got a result of +85 -99 =72 against the normal version, which looks like a statistically significant drop. Perhaps a more sophisticated limitation of moves searched could do better.

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

Re: Quiescence search width

Post by bob » Thu May 31, 2007 1:45 am

sje wrote:How many moves on average are present at a quiescence node? Counting only captures and promotions, it's usually not too many.

I note that Paradise almost always looked at only one move per quiescence node and that included non gainers.

What would happen if someone took a traditional AB quiescence search and artificially limited the width to one or two moves? It might be a worthwhile experiment.
Good question. Typically the number is small except when things get wild. Restricting it to just one capture might well be a workable idea that is worth testing...

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

Re: Quiescence search width

Post by sje » Thu May 31, 2007 2:16 am

bob wrote:Good question. Typically the number is small except when things get wild. Restricting it to just one capture might well be a workable idea that is worth testing...
It might also be interesting to have the search dump the positions and moves where the quiescence search had a fail high on the second or later move. The idea would be to tally these exceptions and try to figure out why they were occurring.

Post Reply