Speedup with bitboards on 64-bit CPUs

[Jacob]

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]

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

[bob]

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]

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]

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

[bob]

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

[sje]

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]

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]

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

[sje]

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.