Rotated Bitboards?
Mauricio CASTRO
BITBOARD whitePawnAttacks[64];
BITBOARD blackPawnAttacks[64];
BITBOARD knightAttacks[64];
BITBOARD bishopAttacks[64];
and the "obstructed[64][64]" BITBOARD.
I know that some other chess engine uses rotated bitboards,
but I don't know how they use them?
Thank you.
Robert Hyatt
> Thank you.
How will you generate moves for sliding pieces. Rotated bitmaps allow you
to isolate the contents of each of the four ranks, files, and diagonals for
any given square. This gives you an 8-bit (or less for diagonals) "state"
of that diagonal, rank or file that can be used to index into an array to
give you a bitmap of the exact attacks that emanate from that square for
that state of the "rays"...
No looping or anything, just direct table lookups...
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Tord Kallqvist Romstad
> How will you generate moves for sliding pieces. Rotated bitmaps allow you
> to isolate the contents of each of the four ranks, files, and diagonals for
> any given square. This gives you an 8-bit (or less for diagonals) "state"
> of that diagonal, rank or file that can be used to index into an array to
> give you a bitmap of the exact attacks that emanate from that square for
> that state of the "rays"...
>
> No looping or anything, just direct table lookups...
I don't quite understand this, I'm afraid. How do you extract
information from bitmaps without any looping? For instance, given the
attack bitmap for a white rook, how do you create a list of the
pseudo-legal moves for the piece without using a loop?
--
Tord Romstad
Robert Hyatt
If you need a list of moves, then you have to loop to extract them fromt
the bitmap, which has _all_ the possible moves packed into one 64 bit
value. Or you can just extract a move from the "wad" when you need one
in the search (this is how chess 4.x and others did it).
> --
> Tord Romstad
SuneF
"Tord Kallqvist Romstad" <rom...@math.uio.no> wrote in message news:gqkzo72...@janus.uio.no...
Good question, I would very much like to know that too :)
I think they do loop through the bitboards to extract the moves.
And since extracting moves requires more 64 bit operations, I think the main performance
gain of rotated bitboards is almost lost, at least for the move generation part.
I switched back to regular "board-tracing", I think you need a bunch of highly tuned
assembler functions to make the rotated bitboards faster, I was unsuccesful.
-Sune
Robert Hyatt
> -Sune
One big savings is when you have to generate just captures. This is
_very_ efficient with bitmaps...
SuneF
"Robert Hyatt" <hy...@crafty.cis.uab.edu> wrote in message news:9pscdk$b66$1...@juniper.cis.uab.edu...
> Tord Kallqvist Romstad <rom...@math.uio.no> wrote:
> > Robert Hyatt <hy...@crafty.cis.uab.edu> writes:
>
> >> How will you generate moves for sliding pieces. Rotated bitmaps allow you
> >> to isolate the contents of each of the four ranks, files, and diagonals for
> >> any given square. This gives you an 8-bit (or less for diagonals) "state"
> >> of that diagonal, rank or file that can be used to index into an array to
> >> give you a bitmap of the exact attacks that emanate from that square for
> >> that state of the "rays"...
> >>
> >> No looping or anything, just direct table lookups...
>
> > I don't quite understand this, I'm afraid. How do you extract
> > information from bitmaps without any looping? For instance, given the
> > attack bitmap for a white rook, how do you create a list of the
> > pseudo-legal moves for the piece without using a loop?
>
> If you need a list of moves, then you have to loop to extract them fromt
> the bitmap, which has _all_ the possible moves packed into one 64 bit
> value. Or you can just extract a move from the "wad" when you need one
> in the search (this is how chess 4.x and others did it).
_All_ the moves or just all the moves for one piece?
I don't understand how you can do move ordering
without having all the moves on some sort of list?
I guess one could ask: does the hash have a killer move, if so try this first,
else if generate captures and try those..
But then what if there hasn't been a cutoff, how do you now search the remaining moves?
-S.
SuneF
"Robert Hyatt" <hy...@crafty.cis.uab.edu> wrote in message news:9ptl90$p01$1...@juniper.cis.uab.edu...
> SuneF <nol...@nowhere.dk> wrote:
>
> > "Tord Kallqvist Romstad" <rom...@math.uio.no> wrote in message news:gqkzo72...@janus.uio.no...
> >> Robert Hyatt <hy...@crafty.cis.uab.edu> writes:
> >>
> >> > How will you generate moves for sliding pieces. Rotated bitmaps allow you
> >> > to isolate the contents of each of the four ranks, files, and diagonals for
> >> > any given square. This gives you an 8-bit (or less for diagonals) "state"
> >> > of that diagonal, rank or file that can be used to index into an array to
> >> > give you a bitmap of the exact attacks that emanate from that square for
> >> > that state of the "rays"...
> >> >
> >> > No looping or anything, just direct table lookups...
> >>
> >> I don't quite understand this, I'm afraid. How do you extract
> >> information from bitmaps without any looping? For instance, given the
> >> attack bitmap for a white rook, how do you create a list of the
> >> pseudo-legal moves for the piece without using a loop?
>
> > Good question, I would very much like to know that too :)
>
> > I think they do loop through the bitboards to extract the moves.
> > And since extracting moves requires more 64 bit operations, I think the main performance
> > gain of rotated bitboards is almost lost, at least for the move generation part.
>
> > I switched back to regular "board-tracing", I think you need a bunch of highly tuned
> > assembler functions to make the rotated bitboards faster, I was unsuccesful.
>
> > -Sune
>
>
>
> One big savings is when you have to generate just captures. This is
> _very_ efficient with bitmaps...
For Q-search you mean?
BTW: how deep do you normally go in the full base tree?
And how much time does Crafty spend searching the tree extensions
relative to the base tree?
Regards,
-S.
Robert Hyatt
> For Q-search you mean?
Yes... Although this is useful in the normal search. I first generate
the captures only, then order them, and search the ones that appear to win
material or break even. I then generate the rest and use the normal ordering
ideas like killers, history, etc.
> BTW: how deep do you normally go in the full base tree?
> And how much time does Crafty spend searching the tree extensions
> relative to the base tree?
I am not sure about "extensions". The q-search is 50% of the work (or more)
depending on the position (less in endgames of course). As to "how deep"
if you mean the iteration depth, then typically 12-14 plies in the
middlegame at 1-2 minutes per move...
> Regards,
> -S.
Robert Hyatt
> "Robert Hyatt" <hy...@crafty.cis.uab.edu> wrote in message news:9pscdk$b66$1...@juniper.cis.uab.edu...
>> Tord Kallqvist Romstad <rom...@math.uio.no> wrote:
>> > Robert Hyatt <hy...@crafty.cis.uab.edu> writes:
>>
>> >> How will you generate moves for sliding pieces. Rotated bitmaps allow you
>> >> to isolate the contents of each of the four ranks, files, and diagonals for
>> >> any given square. This gives you an 8-bit (or less for diagonals) "state"
>> >> of that diagonal, rank or file that can be used to index into an array to
>> >> give you a bitmap of the exact attacks that emanate from that square for
>> >> that state of the "rays"...
>> >>
>> >> No looping or anything, just direct table lookups...
>>
>> > I don't quite understand this, I'm afraid. How do you extract
>> > information from bitmaps without any looping? For instance, given the
>> > attack bitmap for a white rook, how do you create a list of the
>> > pseudo-legal moves for the piece without using a loop?
>>
>> If you need a list of moves, then you have to loop to extract them fromt
>> the bitmap, which has _all_ the possible moves packed into one 64 bit
>> value. Or you can just extract a move from the "wad" when you need one
>> in the search (this is how chess 4.x and others did it).
> _All_ the moves or just all the moves for one piece?
> I don't understand how you can do move ordering
> without having all the moves on some sort of list?
It is complex. Best explanation is the "Chess skill in man and machine"
article on chess 4.x...
> I guess one could ask: does the hash have a killer move, if so try this first,
> else if generate captures and try those..
> But then what if there hasn't been a cutoff, how do you now search the remaining moves?
> -S.
Gian-Carlo Pascutto
news:9pv1u4$fpo$2...@juniper.cis.uab.edu...
> SuneF <nol...@nowhere.dk> wrote:
>
> I am not sure about "extensions". The q-search is 50% of the work (or
more)
50% ?
That sounds like a lot. Are you sure?
My qsearch is similar to yours, except that I do futility pruning on SEE
scores (you only toss losing captures), and I usually get 25-30%.
Don't forget to subtract leaf nodes from the number of q-nodes you search.
--
GCP
Robert Hyatt
> "Robert Hyatt" <hy...@crafty.cis.uab.edu> schreef in bericht
> news:9pv1u4$fpo$2...@juniper.cis.uab.edu...
>> SuneF <nol...@nowhere.dk> wrote:
>>
>> I am not sure about "extensions". The q-search is 50% of the work (or
> more)
> 50% ?
> That sounds like a lot. Are you sure?
Yes. For every leaf node in the full-width search, there is a call to
Quiesce() to generate captures and sort them. That is probably a 33%
effort in simple endings where there are _no_ captures to consider. Normally
there are more captures.
> My qsearch is similar to yours, except that I do futility pruning on SEE
> scores (you only toss losing captures), and I usually get 25-30%.
Are you counting the _first_ call to Quiesce() in this number? If so, I don't
see how you get to 25% in normal positions. IE the nodes at the final ply
number about the same as all the interior nodes combined. And for each
node in the final ply, quiesce() has to be called once. And it may produce
more recursive calls...
> Don't forget to subtract leaf nodes from the number of q-nodes you search.
Not for evaluating the efficiency of bitmaps. "leaf" nodes still do the
futility toss-out stuff and only generate captures. IE I _only_ generate
captures in leaf nodes.
> --
> GCP
Gian-Carlo Pascutto
> Gian-Carlo Pascutto <nat...@hotmail.com> wrote:
> > "Robert Hyatt" <hy...@crafty.cis.uab.edu> schreef in bericht
> > news:9pv1u4$fpo$2...@juniper.cis.uab.edu...
> >> SuneF <nol...@nowhere.dk> wrote:
> >>
> Are you counting the _first_ call to Quiesce() in this number?
No, I'm not. The reasoning behind that is that that call is unavoidable.
Basically I'm measuring qsearch overhead where you are measuring how
much time you spend there.
It depends on what you want to know of course. Since the first calls
are unavoidable, I'd rather measure how much extra work I do and try
to minimize that.
On a related note, I didn't measure that first call as a normal node
either. I 'corrected' this and now my NPS has doubled, which puts my
numbers much more in line with other people.
> > Don't forget to subtract leaf nodes from the number of q-nodes you
search.
>
> Not for evaluating the efficiency of bitmaps. "leaf" nodes still do the
> futility toss-out stuff and only generate captures. IE I _only_ generate
> captures in leaf nodes.
Do you have any kind of metric on how fast you can generate captures?
I know I beat you in plain movegeneration, but captures only is not so
much faster (600 000 vs 470 000 calls/s). I wonder how big the difference
is in crafty.
--
GCP
Robert Hyatt
> "Robert Hyatt" <hy...@crafty.cis.uab.edu> schreef in bericht
> news:9q1p6v$ct6$1...@juniper.cis.uab.edu...
>> Gian-Carlo Pascutto <nat...@hotmail.com> wrote:
>> > "Robert Hyatt" <hy...@crafty.cis.uab.edu> schreef in bericht
>> > news:9pv1u4$fpo$2...@juniper.cis.uab.edu...
>> >> SuneF <nol...@nowhere.dk> wrote:
>> >>
>> Are you counting the _first_ call to Quiesce() in this number?
> No, I'm not. The reasoning behind that is that that call is unavoidable.
> Basically I'm measuring qsearch overhead where you are measuring how
> much time you spend there.
> It depends on what you want to know of course. Since the first calls
> are unavoidable, I'd rather measure how much extra work I do and try
> to minimize that.
I agree with that. However, the original question was about bitmaps.
And the ability to generate only captures is a useful aspect of them
that is important in performance studies. And since that _first_
call to Quiesce() is both (a) technically an unavoidable leaf that you
can not get rid of; (b) a call to Quiesce() that _will_ use the unique
abilities of a bitmap move generator to generate only captures without
looping over empty squares; it fits _both_ conversations pretty well.
IE maybe even _moreso_ since it is efficient in generating only captures,
and I can't avoid the leaf calls to it anyway...
> On a related note, I didn't measure that first call as a normal node
> either. I 'corrected' this and now my NPS has doubled, which puts my
> numbers much more in line with other people.
I only count nodes as calls to Search() or Quiesce(). I don't differentiate
between them in my NPS calculations. Every node is "just a node" in Crafty's
NPS value.
>> > Don't forget to subtract leaf nodes from the number of q-nodes you
> search.
>>
>> Not for evaluating the efficiency of bitmaps. "leaf" nodes still do the
>> futility toss-out stuff and only generate captures. IE I _only_ generate
>> captures in leaf nodes.
> Do you have any kind of metric on how fast you can generate captures?
> I know I beat you in plain movegeneration, but captures only is not so
> much faster (600 000 vs 470 000 calls/s). I wonder how big the difference
> is in crafty.
In the trivial case of no possible captures, bitmaps is a _big_ winner.
No loops over all the pieces, over all the squares they attack. A quick
check for each piece to notice "no captures possible" and on to the
next piece. For normal captures of sliders, the typical piece has only
2 captures max. For bishops the best case would be attacking two opponent
pieces and 0, 1 or 2 of my own. I would get exactly two moves generated,
without having to loop up and down the rays discarding empty squares or
squares containing my pieces. I would think this is at least 4x more
efficient than the normal approach. Of course, part of that 4x goes away
due to the 2x extra work on bitmaps when using 32 bit machines. But I
get it back on 64 bit processors.
My own best guess is that bitmaps are probably close to a break-even on
32 bit machines. Significantly more efficient on 64 bit architectures.
I base this on some analysis I did with Bruce a few years ago. We both
ran on P6/200's, we both moved up to alphas for a tournament, Crafty
ran 3.5X faster on the alpha, Bruce ran something under 2.5X faster.
The bitmaps were the only thing that could explain that difference.
SuneF
"Robert Hyatt" <hy...@crafty.cis.uab.edu> wrote in message news:9q25fa$gql$1...@juniper.cis.uab.edu...
>
> In the trivial case of no possible captures, bitmaps is a _big_ winner.
> No loops over all the pieces, over all the squares they attack. A quick
> check for each piece to notice "no captures possible" and on to the
> next piece. For normal captures of sliders, the typical piece has only
> 2 captures max. For bishops the best case would be attacking two opponent
> pieces and 0, 1 or 2 of my own. I would get exactly two moves generated,
> without having to loop up and down the rays discarding empty squares or
> squares containing my pieces. I would think this is at least 4x more
> efficient than the normal approach. Of course, part of that 4x goes away
> due to the 2x extra work on bitmaps when using 32 bit machines. But I
> get it back on 64 bit processors.
If you _only_ want captures, and you _have_ the bitmaps ready - then yes,
it is only 2 moves which you can retrieve quickly.
But generating the bitmpas is very costly,
I think you need to update and keep track of these at every move?
If you use the other approach, you don't need bitmaps most of the time.
I only generate the bitmaps when checking for king moves, mate and in the eval().
But I don't call eval() at every node, some are hashed, some pruned etc. so
I save alot of bitmap-generating :)
> My own best guess is that bitmaps are probably close to a break-even on
> 32 bit machines. Significantly more efficient on 64 bit architectures.
> I base this on some analysis I did with Bruce a few years ago. We both
> ran on P6/200's, we both moved up to alphas for a tournament, Crafty
> ran 3.5X faster on the alpha, Bruce ran something under 2.5X faster.
> The bitmaps were the only thing that could explain that difference.
I don't really have enough empirical data to conclude that bitmaps are too
slow on 32 bit machines, but for me that seems to be the case.
Anyone else who has tried both ways and can compare them??
-S.
SuneF
"Robert Hyatt" <hy...@crafty.cis.uab.edu> wrote in message news:9q1p6v$ct6$1...@juniper.cis.uab.edu...
> Not for evaluating the efficiency of bitmaps. "leaf" nodes still do the
> futility toss-out stuff and only generate captures. IE I _only_ generate
> captures in leaf nodes.
Did I understand you correctly, that you _only_ generate captures in the q-search?
A non-capture move could be better than a capture, so I think there is a problem
with _only_ evaluating at "stable" positions, eg.
pawn takes pawn, queen takes pawn, knight takes queen!
How do you stop the q-search at the right place here?
-S.
Gian-Carlo Pascutto
"SuneF" <nol...@nowhere.dk> schreef in bericht
news:9q3u60$97r$1...@news.cybercity.dk...
>
> "Robert Hyatt" <hy...@crafty.cis.uab.edu> wrote in message
news:9q1p6v$ct6$1...@juniper.cis.uab.edu...
>
> > Not for evaluating the efficiency of bitmaps. "leaf" nodes still do the
> > futility toss-out stuff and only generate captures. IE I _only_
generate
> > captures in leaf nodes.
>
> Did I understand you correctly, that you _only_ generate captures in the
q-search?
For Robert that is correct. Some other people try checks too.
> A non-capture move could be better than a capture,
Yes, but thats up to the normal search to find. How
are you going to tell the noncapture move is better without
searching it? That is the job of the normal search.
The goal of the quiescent search is to make sure nothing
is left en prise or can be captured by a winning capture
sequence.
Good non-capture moves suddenly don't look so good
if they actually leave a queen en prise :)
> so I think there is a problem
> with _only_ evaluating at "stable" positions, eg.
> pawn takes pawn, queen takes pawn, knight takes queen!
> How do you stop the q-search at the right place here?
Why would that be a problem?
pawn takes pawn.
queen takes pawn.
knight takes queen.
no more captures (this always must happen at some point).
knight takes queen is good, so queen takes pawn must
be bad, so pawn takes pawn is good.
If the captures are all to the same square, most programs
won't even have to search this to know it's good.
--
GCP
Robert Hyatt
> "Robert Hyatt" <hy...@crafty.cis.uab.edu> wrote in message news:9q25fa$gql$1...@juniper.cis.uab.edu...
>>
>> In the trivial case of no possible captures, bitmaps is a _big_ winner.
>> No loops over all the pieces, over all the squares they attack. A quick
>> check for each piece to notice "no captures possible" and on to the
>> next piece. For normal captures of sliders, the typical piece has only
>> 2 captures max. For bishops the best case would be attacking two opponent
>> pieces and 0, 1 or 2 of my own. I would get exactly two moves generated,
>> without having to loop up and down the rays discarding empty squares or
>> squares containing my pieces. I would think this is at least 4x more
>> efficient than the normal approach. Of course, part of that 4x goes away
>> due to the 2x extra work on bitmaps when using 32 bit machines. But I
>> get it back on 64 bit processors.
> If you _only_ want captures, and you _have_ the bitmaps ready - then yes,
> it is only 2 moves which you can retrieve quickly.
> But generating the bitmpas is very costly,
> I think you need to update and keep track of these at every move?
The "occupied square" bitmaps, yes. But updating them for the typical
move requires two logical operations. If this were running on the Cray,
for example, the cost would be essentially zero. It has enough 64 bit
registers to hold _all_ the bitmaps, with another 50 or so left over
for normal programming stuff.
> If you use the other approach, you don't need bitmaps most of the time.
> I only generate the bitmaps when checking for king moves, mate and in the eval().
> But I don't call eval() at every node, some are hashed, some pruned etc. so
> I save alot of bitmap-generating :)
I call Evaluate() at _every_ position in the q-search. I often bail out
early, but the bitmap stuff does have advantages in evaluation as a single
And or Or can answer lots of questions in one cycle...
I've done both. Cray Blitz didn't use bitmaps. Then we did, but only to
detect king attacks by sliding pieces since that is very efficient. I
don't see any particular advantage or disadvantage for bitmaps overall. But
in the right places, they are very good. Generating only captures, which
is done in over 50% of all the nodes. Things like "square of the king/pawn"
pawn races are basically "free" where I had quite a bit of code for that in
Cray Blitz.
And on 64 bit machines, bitmaps have no disadvantages at all that I can see.
Data density is higher than for other approaches, which maximizes the work done
in every cycle on a machine that can do 64 bit operations in one instruction.
>
>> My own best guess is that bitmaps are probably close to a break-even on
>> 32 bit machines. Significantly more efficient on 64 bit architectures.
>> I base this on some analysis I did with Bruce a few years ago. We both
>> ran on P6/200's, we both moved up to alphas for a tournament, Crafty
>> ran 3.5X faster on the alpha, Bruce ran something under 2.5X faster.
>> The bitmaps were the only thing that could explain that difference.
> I don't really have enough empirical data to conclude that bitmaps are too
> slow on 32 bit machines, but for me that seems to be the case.
> Anyone else who has tried both ways and can compare them??
Probably not. The issue is that of "time". If you use bitmaps, then your
non-bitmap "test" will probably not be optimal. If you are not using
bitmaps, then your bitmap test will _definitely_ not be optimal. I think
the "learning" curve is high enough that if you don't make the commitment
I did when I started Crafty (I promised myself that I was going to do bitmaps
for at _least_ three years, and preferably five years, before I would consider
dumping them for another approach) then you give yourself enough time to get
"comfortable" with them. It requires a different way of thinking. And it
requires time to build the expertise necessary to make them work.
> -S.
Robert Hyatt
> "Robert Hyatt" <hy...@crafty.cis.uab.edu> wrote in message news:9q1p6v$ct6$1...@juniper.cis.uab.edu...
>> Not for evaluating the efficiency of bitmaps. "leaf" nodes still do the
>> futility toss-out stuff and only generate captures. IE I _only_ generate
>> captures in leaf nodes.
> Did I understand you correctly, that you _only_ generate captures in the q-search?
Yes.
> A non-capture move could be better than a capture, so I think there is a problem
> with _only_ evaluating at "stable" positions, eg.
> pawn takes pawn, queen takes pawn, knight takes queen!
> How do you stop the q-search at the right place here?
When I enter Quiesce(), I compute a static evaluation for the current
position. Then I use this as the "alpha" value. If any capture will
produce a score > alpha, I will accept that capture as "better". Otherwise,
I have the option to "stand pat" and not play any capture at all, which
stops this search path at this point.
> -S.
SuneF
"Gian-Carlo Pascutto" <nat...@hotmail.com> wrote in message news:nggx7.99039$6x5.21...@afrodite.telenet-ops.be...
> > so I think there is a problem
> > with _only_ evaluating at "stable" positions, eg.
> > pawn takes pawn, queen takes pawn, knight takes queen!
> > How do you stop the q-search at the right place here?
>
> Why would that be a problem?
>
> pawn takes pawn.
> queen takes pawn.
> knight takes queen.
> no more captures (this always must happen at some point).
>
> knight takes queen is good, so queen takes pawn must
> be bad, so pawn takes pawn is good.
The difference between winning a pawn and a queen is huge,
who knows maybe he could have won a rook by chosing a different variant,
instead he is fooled by this queen score.
You would have noise amplitude of 7-8 pawns in this case, that is very significant
but I don't know how often the score is this bad
or how much it matters when it's this deep.
I know q-search is not ideal and not meant to be, but if 50% of the time
is spent in q-search, it might be worth trying to reduce the noise on the evaluation.
If it was stopped at the right spot (with no overhead),
it would run faster _and_ have a more accurate score!!!
> If the captures are all to the same square, most programs
> won't even have to search this to know it's good.
Why?
What's the trick?
-S.
Robert Hyatt
> "Gian-Carlo Pascutto" <nat...@hotmail.com> wrote in message news:nggx7.99039$6x5.21...@afrodite.telenet-ops.be...
>> > so I think there is a problem
>> > with _only_ evaluating at "stable" positions, eg.
>> > pawn takes pawn, queen takes pawn, knight takes queen!
>> > How do you stop the q-search at the right place here?
>>
>> Why would that be a problem?
>>
>> pawn takes pawn.
>> queen takes pawn.
>> knight takes queen.
>> no more captures (this always must happen at some point).
>>
>> knight takes queen is good, so queen takes pawn must
>> be bad, so pawn takes pawn is good.
> The difference between winning a pawn and a queen is huge,
> who knows maybe he could have won a rook by chosing a different variant,
> instead he is fooled by this queen score.
> You would have noise amplitude of 7-8 pawns in this case, that is very significant
> but I don't know how often the score is this bad
> or how much it matters when it's this deep.
> I know q-search is not ideal and not meant to be, but if 50% of the time
> is spent in q-search, it might be worth trying to reduce the noise on the evaluation.
> If it was stopped at the right spot (with no overhead),
> it would run faster _and_ have a more accurate score!!!
I'm not sure what is actually being discussed here... However, the search
does this quite accurately. The static eval establishes "alpha" (the score
below which we will not accept anything at all). SEE is just used to order
the captures in the q-search and cull captures that look totally hopeless...
>> If the captures are all to the same square, most programs
>> won't even have to search this to know it's good.
> Why?
> What's the trick?
I agree. Overloaded pieces. Pinned pieces. Etc all make this very
difficult to accurately do in a "static" method...
> -S.
SuneF
"Robert Hyatt" <hy...@crafty.cis.uab.edu> wrote in message news:9q4api$dnh$4...@juniper.cis.uab.edu...
> SuneF <nol...@nowhere.dk> wrote:
>
> > "Robert Hyatt" <hy...@crafty.cis.uab.edu> wrote in message news:9q25fa$gql$1...@juniper.cis.uab.edu...
> >>
> >> In the trivial case of no possible captures, bitmaps is a _big_ winner.
> >> No loops over all the pieces, over all the squares they attack. A quick
> >> check for each piece to notice "no captures possible" and on to the
> >> next piece. For normal captures of sliders, the typical piece has only
> >> 2 captures max. For bishops the best case would be attacking two opponent
> >> pieces and 0, 1 or 2 of my own. I would get exactly two moves generated,
> >> without having to loop up and down the rays discarding empty squares or
> >> squares containing my pieces. I would think this is at least 4x more
> >> efficient than the normal approach. Of course, part of that 4x goes away
> >> due to the 2x extra work on bitmaps when using 32 bit machines. But I
> >> get it back on 64 bit processors.
>
> > If you _only_ want captures, and you _have_ the bitmaps ready - then yes,
> > it is only 2 moves which you can retrieve quickly.
> > But generating the bitmpas is very costly,
> > I think you need to update and keep track of these at every move?
>
> The "occupied square" bitmaps, yes. But updating them for the typical
> move requires two logical operations. If this were running on the Cray,
> for example, the cost would be essentially zero. It has enough 64 bit
> registers to hold _all_ the bitmaps, with another 50 or so left over
> for normal programming stuff.
However, Alphas are dream machines to the most of us,
you might as well be talking about Deep Blue;)
> > If you use the other approach, you don't need bitmaps most of the time.
> > I only generate the bitmaps when checking for king moves, mate and in the eval().
> > But I don't call eval() at every node, some are hashed, some pruned etc. so
> > I save alot of bitmap-generating :)
>
> I call Evaluate() at _every_ position in the q-search. I often bail out
> early, but the bitmap stuff does have advantages in evaluation as a single
> And or Or can answer lots of questions in one cycle...
>
> I've done both. Cray Blitz didn't use bitmaps. Then we did, but only to
> detect king attacks by sliding pieces since that is very efficient. I
> don't see any particular advantage or disadvantage for bitmaps overall. But
> in the right places, they are very good. Generating only captures, which
> is done in over 50% of all the nodes. Things like "square of the king/pawn"
> pawn races are basically "free" where I had quite a bit of code for that in
> Cray Blitz.
>
> And on 64 bit machines, bitmaps have no disadvantages at all that I can see.
> Data density is higher than for other approaches, which maximizes the work done
> in every cycle on a machine that can do 64 bit operations in one instruction.
Most people still use 32 bit machines.
Can Fritz, Shredder,Tiger,Junior,... even _run_ on alphas?
> >
> >> My own best guess is that bitmaps are probably close to a break-even on
> >> 32 bit machines. Significantly more efficient on 64 bit architectures.
> >> I base this on some analysis I did with Bruce a few years ago. We both
> >> ran on P6/200's, we both moved up to alphas for a tournament, Crafty
> >> ran 3.5X faster on the alpha, Bruce ran something under 2.5X faster.
> >> The bitmaps were the only thing that could explain that difference.
>
> > I don't really have enough empirical data to conclude that bitmaps are too
> > slow on 32 bit machines, but for me that seems to be the case.
>
> > Anyone else who has tried both ways and can compare them??
>
> Probably not. The issue is that of "time". If you use bitmaps, then your
> non-bitmap "test" will probably not be optimal. If you are not using
> bitmaps, then your bitmap test will _definitely_ not be optimal. I think
> the "learning" curve is high enough that if you don't make the commitment
> I did when I started Crafty (I promised myself that I was going to do bitmaps
> for at _least_ three years, and preferably five years, before I would consider
> dumping them for another approach) then you give yourself enough time to get
> "comfortable" with them. It requires a different way of thinking. And it
> requires time to build the expertise necessary to make them work.
Ah, so bitmaps _are_ faster if you spend 3-5 years tuning them ;)
I wonder, have you spent 3-5 years tuning non-bitmap programs?
Seems to me you need to spend same amount of time to do a fair comparison.
I heard somewhere that Junior doesn't use bitmaps,
if that's true, then there must be other ways.
But hay, I love bitmaps too,
thats why I find it so depressing I can't make them competitive.
-S.
Robert Hyatt
Not in 2-3 years. And by the time 5 years have passed, you will probably
only have access to 64 bit machines. 32 bitters will have gone the way
of the old '286.
>
>> > If you use the other approach, you don't need bitmaps most of the time.
>> > I only generate the bitmaps when checking for king moves, mate and in the eval().
>> > But I don't call eval() at every node, some are hashed, some pruned etc. so
>> > I save alot of bitmap-generating :)
>>
>> I call Evaluate() at _every_ position in the q-search. I often bail out
>> early, but the bitmap stuff does have advantages in evaluation as a single
>> And or Or can answer lots of questions in one cycle...
>>
>> I've done both. Cray Blitz didn't use bitmaps. Then we did, but only to
>> detect king attacks by sliding pieces since that is very efficient. I
>> don't see any particular advantage or disadvantage for bitmaps overall. But
>> in the right places, they are very good. Generating only captures, which
>> is done in over 50% of all the nodes. Things like "square of the king/pawn"
>> pawn races are basically "free" where I had quite a bit of code for that in
>> Cray Blitz.
>>
>> And on 64 bit machines, bitmaps have no disadvantages at all that I can see.
>> Data density is higher than for other approaches, which maximizes the work done
>> in every cycle on a machine that can do 64 bit operations in one instruction.
> Most people still use 32 bit machines.
> Can Fritz, Shredder,Tiger,Junior,... even _run_ on alphas?
They _could_ but using the x86 emulator which would hurt.
>> >
>> >> My own best guess is that bitmaps are probably close to a break-even on
>> >> 32 bit machines. Significantly more efficient on 64 bit architectures.
>> >> I base this on some analysis I did with Bruce a few years ago. We both
>> >> ran on P6/200's, we both moved up to alphas for a tournament, Crafty
>> >> ran 3.5X faster on the alpha, Bruce ran something under 2.5X faster.
>> >> The bitmaps were the only thing that could explain that difference.
>>
>> > I don't really have enough empirical data to conclude that bitmaps are too
>> > slow on 32 bit machines, but for me that seems to be the case.
>>
>> > Anyone else who has tried both ways and can compare them??
>>
>> Probably not. The issue is that of "time". If you use bitmaps, then your
>> non-bitmap "test" will probably not be optimal. If you are not using
>> bitmaps, then your bitmap test will _definitely_ not be optimal. I think
>> the "learning" curve is high enough that if you don't make the commitment
>> I did when I started Crafty (I promised myself that I was going to do bitmaps
>> for at _least_ three years, and preferably five years, before I would consider
>> dumping them for another approach) then you give yourself enough time to get
>> "comfortable" with them. It requires a different way of thinking. And it
>> requires time to build the expertise necessary to make them work.
> Ah, so bitmaps _are_ faster if you spend 3-5 years tuning them ;)
> I wonder, have you spent 3-5 years tuning non-bitmap programs?
> Seems to me you need to spend same amount of time to do a fair comparison.
> I heard somewhere that Junior doesn't use bitmaps,
> if that's true, then there must be other ways.
Yes I have. In fact, my first program played its first move in october
of 1968. I spent from then until 1995 working on "mailbox" type programs.
Crafty was my first bitmap program, which I started working on in 1995.
> But hay, I love bitmaps too,
> thats why I find it so depressing I can't make them competitive.
> -S.
Gian-Carlo Pascutto
>
> "Gian-Carlo Pascutto" <nat...@hotmail.com> wrote in message
news:nggx7.99039$6x5.21...@afrodite.telenet-ops.be...
>
> > > so I think there is a problem
> > > with _only_ evaluating at "stable" positions, eg.
> > > pawn takes pawn, queen takes pawn, knight takes queen!
> > > How do you stop the q-search at the right place here?
> >
> > Why would that be a problem?
> >
> > pawn takes pawn.
> > queen takes pawn.
> > knight takes queen.
> > no more captures (this always must happen at some point).
> >
> > knight takes queen is good, so queen takes pawn must
> > be bad, so pawn takes pawn is good.
>
> The difference between winning a pawn and a queen is huge,
> who knows maybe he could have won a rook by chosing a different variant,
> instead he is fooled by this queen score.
The quiescent search just works like alphabeta, and there's
no reason why it wouldn't know the difference between a pawn
and a queen.
But in this variant, nothing forces the queen to take, and
because she will be lost, there's no reason for her to take.
The outcome here would be +1 pawn.
If there's a different variant that wins a rook, then it
will pick that.
I dont see what the problem is here??
> I know q-search is not ideal and not meant to be, but if 50% of the time
> is spent in q-search, it might be worth trying to reduce the noise on the
evaluation.
> If it was stopped at the right spot (with no overhead),
> it would run faster _and_ have a more accurate score!!!
What are you talking about? What do you mean?
I feel like you are saying: 'because the evaluation is called for
all positions, it might be worth trying to make it perfect, so we
don't have to search at all, run infinitely fast _and_ have perfect
scores'
> > If the captures are all to the same square, most programs
> > won't even have to search this to know it's good.
>
> Why?
> What's the trick?
Calculate all attackers to the square you capture to
Sort them from low to high for both players
Start with the first capture (the one you're checking out)
Capture back with the piece worth least
If that doesn't bring the score negative, you bail out (winning capture for
you)
If it does, try to capture on that square again
Did that bring the score positive again?
If it doesn't, bail out, because this wins for your opponent
If it does, let your opponent capture with his next piece
[...]
Do this until there are no more pieces that can capture to this square.
It's not perfect because it only considers one square, but
it saves loads of work and works good enough to be a gain.
--
GCP
Gian-Carlo Pascutto
> SuneF <nol...@nowhere.dk> wrote:
>
> > "Gian-Carlo Pascutto" <nat...@hotmail.com> wrote in message
news:nggx7.99039$6x5.21...@afrodite.telenet-ops.be...
>
> >> won't even have to search this to know it's good.
>
> > Why?
> > What's the trick?
>
>
> I agree. Overloaded pieces. Pinned pieces. Etc all make this very
> difficult to accurately do in a "static" method...
Okay, I'm confused. You say 'I agree', but you use this trick
yourself. Did I miss something in this thread?
Are you contesting SEE pruning is accurate enough to be worthwhile?
If so, I'm sure you won't mind disabling it when you play me in Leiden ;)
--
GCP
Robert Hyatt
> "Robert Hyatt" <hy...@crafty.cis.uab.edu> schreef in bericht
> news:9q564u$nqm$1...@juniper.cis.uab.edu...
>> SuneF <nol...@nowhere.dk> wrote:
>>
>> > "Gian-Carlo Pascutto" <nat...@hotmail.com> wrote in message
> news:nggx7.99039$6x5.21...@afrodite.telenet-ops.be...
>>
>> >> If the captures are all to the same square, most programs
>> >> won't even have to search this to know it's good.
>>
>> > Why?
>> > What's the trick?
>>
>>
>> I agree. Overloaded pieces. Pinned pieces. Etc all make this very
>> difficult to accurately do in a "static" method...
> Okay, I'm confused. You say 'I agree', but you use this trick
> yourself. Did I miss something in this thread?
Two different subects. We (I) do _not_ use SEE in lieu of a tree
search. I use SEE to order captures in the normal search, and to
cull losers in the q-search. But I _never_ use SEE to _replace_ a
tree search as the poster was suggesting.
> Are you contesting SEE pruning is accurate enough to be worthwhile?
> If so, I'm sure you won't mind disabling it when you play me in Leiden ;)
Nope. I think you missed a key sentence in the post I replied to.
"using this sequence of captures _without_ using a tree search at all."
> --
> GCP
Gian-Carlo Pascutto
> Gian-Carlo Pascutto <nat...@hotmail.com> wrote:
>
> > "Robert Hyatt" <hy...@crafty.cis.uab.edu> schreef in bericht
> > news:9q564u$nqm$1...@juniper.cis.uab.edu...
> >> SuneF <nol...@nowhere.dk> wrote:
> >>
> >> > "Gian-Carlo Pascutto" <nat...@hotmail.com> wrote in message
> > news:nggx7.99039$6x5.21...@afrodite.telenet-ops.be...
> >>
> >> >> If the captures are all to the same square, most programs
> >> >> won't even have to search this to know it's good.
> >>
> >> > Why?
> >> > What's the trick?
> >>
> >>
> >> I agree. Overloaded pieces. Pinned pieces. Etc all make this very
> >> difficult to accurately do in a "static" method...
>
> > Okay, I'm confused. You say 'I agree', but you use this trick
> > yourself. Did I miss something in this thread?
>
> Two different subects. We (I) do _not_ use SEE in lieu of a tree
> search. I use SEE to order captures in the normal search, and to
> cull losers in the q-search. But I _never_ use SEE to _replace_ a
> tree search as the poster was suggesting.
>
> > Are you contesting SEE pruning is accurate enough to be worthwhile?
> > If so, I'm sure you won't mind disabling it when you play me in Leiden
;)
>
> Nope. I think you missed a key sentence in the post I replied to.
> "using this sequence of captures _without_ using a tree search at all."
I disagree here. If you prune a capture because your SEE score indicates
it is futile/losing, you _are_ replacing a tree search with SEE.
--
GCP
Robert Hyatt
Yes. But if you do _not_ reject the capture, SEE does not replace the
search. A real search is done, which _will_ notice overloaded pieces,
pins, and the like...
SuneF
"Gian-Carlo Pascutto" <nat...@hotmail.com> wrote in message news:eo_x7.103918$6x5.22...@afrodite.telenet-ops.be...
> "SuneF" <nol...@nowhere.dk> schreef in bericht
> news:9q53d4$2k6r$1...@news.cybercity.dk...
> >
> > "Gian-Carlo Pascutto" <nat...@hotmail.com> wrote in message
> news:nggx7.99039$6x5.21...@afrodite.telenet-ops.be...
> >
> > > > so I think there is a problem
> > > > with _only_ evaluating at "stable" positions, eg.
> > > > pawn takes pawn, queen takes pawn, knight takes queen!
> > > > How do you stop the q-search at the right place here?
> > >
> > > Why would that be a problem?
> > >
> > > pawn takes pawn.
> > > queen takes pawn.
> > > knight takes queen.
> > > no more captures (this always must happen at some point).
> > >
> > > knight takes queen is good, so queen takes pawn must
> > > be bad, so pawn takes pawn is good.
> >
> > The difference between winning a pawn and a queen is huge,
> > who knows maybe he could have won a rook by chosing a different variant,
> > instead he is fooled by this queen score.
>
> The quiescent search just works like alphabeta, and there's
> no reason why it wouldn't know the difference between a pawn
> and a queen.
Point is, if _all_ your evaluations are this bad, then all you have is noise.
> But in this variant, nothing forces the queen to take, and
> because she will be lost, there's no reason for her to take.
>
> The outcome here would be +1 pawn.
Not if you only evaluate at the leafs and you only generate captures.
You need the option of "standing pat", or else the queen must capture if it can.
> If there's a different variant that wins a rook, then it
> will pick that.
>
> I dont see what the problem is here??
>
> > I know q-search is not ideal and not meant to be, but if 50% of the time
> > is spent in q-search, it might be worth trying to reduce the noise on the
> evaluation.
> > If it was stopped at the right spot (with no overhead),
> > it would run faster _and_ have a more accurate score!!!
>
> What are you talking about? What do you mean?
>
> I feel like you are saying: 'because the evaluation is called for
> all positions, it might be worth trying to make it perfect, so we
> don't have to search at all, run infinitely fast _and_ have perfect
> scores'
Kinda the opposite actually:)
You want to bail out of the branches that loses quickly,
but if you _only_ generate captures and _only_ evaluate at so called
"stable positions" where no captures are possible,
then you have two problems.
First the score won't be very accurate
(because the queen has no choice but to capture the pawn),
and second, you'll spend too much time in worthless branches.
As I understand it, that is the basic idea in q-search,
obviously there is room for improvement.
But Haytt said he does evaluate at every node in the q-search
(however he does that?), so sounds like he did take care of those problems.
> > > If the captures are all to the same square, most programs
> > > won't even have to search this to know it's good.
> >
> > Why?
> > What's the trick?
>
> Calculate all attackers to the square you capture to
> Sort them from low to high for both players
> Start with the first capture (the one you're checking out)
> Capture back with the piece worth least
> If that doesn't bring the score negative, you bail out (winning capture for
> you)
> If it does, try to capture on that square again
> Did that bring the score positive again?
> If it doesn't, bail out, because this wins for your opponent
> If it does, let your opponent capture with his next piece
> [...]
> Do this until there are no more pieces that can capture to this square.
You use SSE that to "prune" the q-search?
> It's not perfect because it only considers one square, but
> it saves loads of work and works good enough to be a gain.
I think so too.
> --
> GCP
>
-S.
Gian-Carlo Pascutto
>
> > The quiescent search just works like alphabeta, and there's
> > no reason why it wouldn't know the difference between a pawn
> > and a queen.
>
> Point is, if _all_ your evaluations are this bad, then all you have is
noise.
What do you mean? -> ('this bad')
> > But in this variant, nothing forces the queen to take, and
> > because she will be lost, there's no reason for her to take.
> >
> > The outcome here would be +1 pawn.
>
> Not if you only evaluate at the leafs and you only generate captures.
> You need the option of "standing pat", or else the queen must capture if
it can.
I specifically said the queen did _not_ _have_ to capture.
> > I feel like you are saying: 'because the evaluation is called for
> > all positions, it might be worth trying to make it perfect, so we
> > don't have to search at all, run infinitely fast _and_ have perfect
> > scores'
>
> Kinda the opposite actually:)
> You want to bail out of the branches that loses quickly,
> but if you _only_ generate captures and _only_ evaluate at so called
> "stable positions" where no captures are possible,
> then you have two problems.
> First the score won't be very accurate
> (because the queen has no choice but to capture the pawn),
You don't have to capture with the queen.
> and second, you'll spend too much time in worthless branches.
This is very vague. Chessprograms spend 99% of their time in
worthless branches, so to speak.
> As I understand it, that is the basic idea in q-search,
> obviously there is room for improvement.
Feel free to make a suggestion (that will actually work).
> But Haytt said he does evaluate at every node in the q-search
> (however he does that?), so sounds like he did take care of those
problems.
So does everyone I guess, since you need to know your standpat
score.
> You use SSE that to "prune" the q-search?
(it's SEE, static exchange evaluation)
Yes. Robert uses it to cull out losing captures. I do that too
and additionally prune out everything that wont bring the score
near alpha again (more risk, more gain).
--
GCP
SuneF
"Gian-Carlo Pascutto" <nat...@hotmail.com> wrote in message news:Dxiy7.105190$6x5.22...@afrodite.telenet-ops.be...
>
> > > The quiescent search just works like alphabeta, and there's
> > > no reason why it wouldn't know the difference between a pawn
> > > and a queen.
> >
> > Point is, if _all_ your evaluations are this bad, then all you have is
> noise.
>
> What do you mean? -> ('this bad')
"this bad": I mean most of the q-search branches will run until
almost no pieces are left on the board because they all exchance,
I find that unrealistic and it must be a bad evaluation.
Bad eval => bad chess program.
> > > But in this variant, nothing forces the queen to take, and
> > > because she will be lost, there's no reason for her to take.
> > >
> > > The outcome here would be +1 pawn.
> >
> > Not if you only evaluate at the leafs and you only generate captures.
> > You need the option of "standing pat", or else the queen must capture if
> it can.
>
> I specifically said the queen did _not_ _have_ to capture.
If you have no way to standpat, why don't the queen capture????
You only have captures to choose from.
> > > I feel like you are saying: 'because the evaluation is called for
> > > all positions, it might be worth trying to make it perfect, so we
> > > don't have to search at all, run infinitely fast _and_ have perfect
> > > scores'
> >
> > Kinda the opposite actually:)
> > You want to bail out of the branches that loses quickly,
> > but if you _only_ generate captures and _only_ evaluate at so called
> > "stable positions" where no captures are possible,
> > then you have two problems.
> > First the score won't be very accurate
> > (because the queen has no choice but to capture the pawn),
>
> You don't have to capture with the queen.
Okay, maybe we misunderstand eachother.
> > and second, you'll spend too much time in worthless branches.
>
> This is very vague. Chessprograms spend 99% of their time in
> worthless branches, so to speak.
LOL, your right, it's probably 99.999% ;)
But these would indeed be meaningless because,
the same principle you use for SEE would also work here.
What sets out as a winning capture could easily turn into a losing one,
if you are not allowed to stop the capture sequence.
So you get a negative score eventhough the capture might actually be good.
I don't know how else to explain it,
but again it's hard to tell how bad this q-search will evaluate.
Maybe I just gave a freak example and most of the q-search evaluations are good,
or perhaps the minimax principle of alpha-beta will repair most of the damage?
> > As I understand it, that is the basic idea in q-search,
> > obviously there is room for improvement.
>
> Feel free to make a suggestion (that will actually work).
Haha, that is to be a closely guarded secret :)
(But Crafty probably already uses something like that)
> > But Haytt said he does evaluate at every node in the q-search
> > (however he does that?), so sounds like he did take care of those
> problems.
>
> So does everyone I guess, since you need to know your standpat
> score.
>
> > You use SSE that to "prune" the q-search?
>
> (it's SEE, static exchange evaluation)
Yep typo.
> Yes. Robert uses it to cull out losing captures. I do that too
> and additionally prune out everything that wont bring the score
> near alpha again (more risk, more gain).
I'm not sure what "cull out" means, but Robert doesn't use SEE for
cutting the tree. He uses SEE for move ordering only.
I guess one could experiment with replacing some parts of the
q-search with SEE, but if thats not how the good programs work,
then is probably not the way to go.
-S.
Gian-Carlo Pascutto
>
> "this bad": I mean most of the q-search branches will run until
> almost no pieces are left on the board because they all exchance,
Q-search can stop as soon as there is a beta cutoff,
or as soon as there is no capture that is better than
the static evaluation of the position.
> > I specifically said the queen did _not_ _have_ to capture.
>
> If you have no way to standpat, why don't the queen capture????
> You only have captures to choose from.
Why would there be no way to stand pat? Just don't capture.
> Okay, maybe we misunderstand eachother.
I think so :)
Only generating captures does _not_ mean you _have_ to capture.
> What sets out as a winning capture could easily turn into a losing one,
> if you are not allowed to stop the capture sequence.
> So you get a negative score eventhough the capture might actually be good.
> I don't know how else to explain it,
> but again it's hard to tell how bad this q-search will evaluate.
> Maybe I just gave a freak example and most of the q-search evaluations are
good,
> or perhaps the minimax principle of alpha-beta will repair most of the
damage?
But q-search simply doesn't work as you describe :)
> > Yes. Robert uses it to cull out losing captures. I do that too
> > and additionally prune out everything that wont bring the score
> > near alpha again (more risk, more gain).
>
> I'm not sure what "cull out" means, but Robert doesn't use SEE for
> cutting the tree.
He does. He prunes every capture the SEE says is losing in the
quiescent search. In the full-width search, it's used for ordering
moves only.
--
GCP