move generators in computer chess
Joel Rivat
I have been testing them for 2 years
It is true that they can express a lot of geometric properties
very easily, but the wrong thing is about attack bitboards...
you say that the main advantage of the bitboard approach
is to have fast the capture list and the mobility
(which are effectively very important things)
But in most cases the hash table or the killer table give
a legal move (or capture)
that produces a cut off and with a not bitboard_attack
approach you don't spend time in building the move list nor in make_move
(this is a very big saving especially in endgame)
with the bitboard approach you never save this time...
(the make_move call always takes a long time...)
mobility can be computed while
computing the capture list (for the other side one can use some approx.)
another remark: all the or'ing xor'ing and'ing you do
to find the first occupied square in a direction
probably takes more time than a simple loop...
When I started with bitboards I was very enthousiastic like you,
but now I regret this nice idea didn't work (in my case) for attacks
It remains nice for pawn structure and all geometric things...
Hope this helps
Joel Rivat
Robert Hyatt
Joel Rivat <ri...@caissa.univ-lyon1.fr> wrote:
>I regret I disagree with you about bitboards
>I have been testing them for 2 years
>It is true that they can express a lot of geometric properties
>very easily, but the wrong thing is about attack bitboards...
>you say that the main advantage of the bitboard approach
>is to have fast the capture list and the mobility
>(which are effectively very important things)
>
>But in most cases the hash table or the killer table give
>a legal move (or capture)
> that produces a cut off and with a not bitboard_attack
>approach you don't spend time in building the move list nor in make_move
>(this is a very big saving especially in endgame)
right. however, the transposition table/killer moves don't prevent
move generation in at least 50% of the positions since every type-1
and type-3 node (Knuth/Moore terminology here) must have every
branch examined, requiring a full move generation.
Other special cases are handled easier, such as check evasion: if there
is one checker, try to capture it; if there are two checkers, only try
king moves; etc.
>
>with the bitboard approach you never save this time...
>(the make_move call always takes a long time...)
Long is relative. the current version of Cray Blitz is over 4x faster than
the old version, and will get faster. I've done instruction counts and found
that the new approach contains far fewer instructions than the old, if it's
done well.
>
>mobility can be computed while
>computing the capture list (for the other side one can use some approx.)
NO! If you do this, you are burning cpu time. with bit-boards, we avoid
this "scanning" operation completely. since the capture search is the majority
of the total search, the savings become huge.
>
>another remark: all the or'ing xor'ing and'ing you do
>to find the first occupied square in a direction
>probably takes more time than a simple loop...
>
Again, no. On a Cray, one memory reference takes 24 clock cycles. To fetch
the entire diagonal (which might be 7 squares with a bishop in a corner)
7x24 clock cycles. ands, ors, etc take 2 clock cycles. I can do *all* the
anding stuff before I can read the first square from memory.
>When I started with bitboards I was very enthousiastic like you,
>but now I regret this nice idea didn't work (in my case) for attacks
I don't see how you can improve on the attack stuff. In the old Cray Blitz,
our "attack" routine (which was used to determine if the king was in check
primarily) consumed about 20-25% of the total search time, and went even
higher in tactical positions. This is now "0" since from.attacks answers this
question with one and operation to eliminate your own pieces. Since make_move()
is still faster than our old move generation, this 25% is totally gone....
>
>It remains nice for pawn structure and all geometric things...
>
>Hope this helps
>
> Joel Rivat
>
>
Bob
--
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
Peter Gillgasch
|> I regret I disagree with you about bitboards
<snip>
|> But in most cases the hash table or the killer table give
|> a legal move (or capture)
|> that produces a cut off and with a not bitboard_attack
|> approach you don't spend time in building the move list nor in make_move
|> (this is a very big saving especially in endgame)
This works only if you allow capture moves in your killer list. Doesn't
seem reasonable to me, since then you rarely have non capturing
killers... In the endgame the bitboard approach is *free* since you
don't have to update many things... Endgames are handled by the
trans/ref table anyway...
|> with the bitboard approach you never save this time...
|> (the make_move call always takes a long time...)
Not true. My DoMove()/TestLegality/UNDO_MOVE cycle has a frequency of
33 KHz on a 25 MHz 68030 ('C' with leadz() and leadzClr() in assembly),
which is significantly faster than modifiying a 64 bytes board
representation, maintaining a move stack *plus* the cost of re-modifying
it with an UndoMove() routine. And the code is still suboptimal coded...
|> mobility can be computed while
|> computing the capture list (for the other side one can use some approx.)
I thought you don't have a capture list? Approx'ing the mobility
of the other side and using something else for the side to move
seems quite unreliable to me...
|> another remark: all the or'ing xor'ing and'ing you do
|> to find the first occupied square in a direction
|> probably takes more time than a simple loop...
Currently my DoMove() does a loop over the occupied squares on the ray.
I will check Bob's bit manipulation wizadry soon... I am convinced that
at least on a 64 bit machine his approach is the faster one...
|> When I started with bitboards I was very enthousiastic like you,
|> but now I regret this nice idea didn't work (in my case) for attacks
I am convinced that the bitboard approach is the fastest way for move
generation. I am currently rewriting my chess program. As soon as I get
everything working & debugged and did some optimizations, I will post
some benchmarks (table driven program vs. bitboard approach). Give me
another week...
Peter
--
+-------------------------------//-------------------//---------\\
| Peter W. Gillgasch //the way is clear // Gothic \\
| Klosterweg 28/I-113 //The road is closed // computer \\
| 76131 Karlsruhe/Germany //the damage done // award for the \\
| Phone ++49/(0)721/6904255 //and the course // Macintosh SE: \\
| email gil...@ira.uka.de //imposed you //Dead and monochrome\\
+-------------------------//-------------------//---------------------\\
Peter Gillgasch
In article <384kd9...@life.ai.mit.edu>, de...@great-grain.ai.mit.edu (Deniz Yuret) writes:
|> Recently, there has been some discussion on my question about optimal move
|> generation for computer chess.
<...>
|>
|> To this end, Bob Hyatt <hy...@willis.cis.uab.edu> and Steven J. Edwards
|> <s...@mv.mv.com> defend the advantages of the bitboard approach, even on
|> hardware that does not support 64 bit words. Peter Gillgasch
|> <gil...@i41s19.ira.uka.de>, seems to favor the table based approach.
|>
Well, actually I am implementing a 64 bit move generator currently. I
will report on that on r.g.c. Bob has offered the tricky part of his
implementation to all who are interested. Thanks Bob! I am of course
interested in your MakeMove() routine to compare mine with yours and to
look for bugs and suboptimal execution paths in my code.
I am in no way dissatisfied with the table driven approach, I just want
to test another idea... If the 64 bit move generator doesn't slow down
my program I will keep it for better evaluation, if it is slower, I have
learned something... If it will be faster... We'll see!
|> They point out the importance of the fact that move generation is not an
|> isolated part of the program, and the data structures you use there will effect
|> the performance of the other routines such as evaluation. Furthermore, in most
|> chess programs, move generation takes on the order of 10% of the whole
|> computation, so maybe it is not worth optimizing it.
Where have you gathered this data? In every publication I read the cost
of move generation was said to be in the order of 30-50% cpu time (pure
software programs of course). That was one of the reasons why I believe
that my (table driven) implementation is very efficient. I haven't seen
any statements of other programmers revealing the cost of their move
generation algorithms... Have I missed something?
|> These are true, however if one thinks about only move generation efficiency,
|> both sides are missing an important point. The trick is to avoid redundant
|> computation. As pointed out in previous messages, most of the move list is
|> uneffected between successive positions, and it is important to take advantage
|> of that. If a piece moves from s1 to s2, only the pieces that were attacking
|> s1 or s2 need be updated. There are on the average 2.5 pieces attacking every
|> square, which would mean on the average 5 pieces need be updated instead of 32.
|> Furthermore, only the piece that moves requires a complete update. Other
|> pieces usually have part of their moves deleted, or some new moves added. On
|> the average 1/4th of the moves of effected pieces need be regenerated, so an
|> intelligent program could do the equivalent of move generation for 2 pieces
|> instead of 32. This is a 16 fold increase. It will be less because of the
|> need to update certain data structures, but it might still be a significant
|> gain. (The statistics are for typical middle game positions).
|>
I think you overlooked something. You don't need a complete list of
moves. Most of the time you don't need the move generator at all or you
need only *one* move. In at least 50% of the cases you are only
interested in captures and you can do some clever forward pruning to
skip captures that don't matter anyway. And it is not necessary to have
the move list of the player who is not to move if you are only
interested in growing the game tree. If you have good move ordering
heuristics, you need only a fraction of the moves - and probably you
already know what move you need, so you don't need to generate it,
just check if it is legal in the current position. Then you get the
problem how you "mask" this move(s) from further move generation if you
really have to create a complete move list, but this is another story...
|> Bob Hyatt says:
|> >> 1. when you make a move, you update the attack tables so you in essence
|> >> re-generate just the part of the move list affected by the move...
|> However, when the program needs to actually read these moves into a list, it
|> has to get them one by one using leadz() instructions. So this still uses an
|> instruction per move. In the table based approach, instead of reading from a
|> bitboard, one reads from the table, which also uses aprox the equivalent of
|> this one instruction. One could average less than one instruction per move by
|> recycling the move list, instead of generating it (or reading it in from a
|> table or bitboard) completely.
The idea of recycling the move list is not new, and I think that it
cannot be done in an efficient way. The cost of "building" move
descriptors that you feed to your MakeMove() routine is *very* limited
(if you have the "from" and "to" square and maybe other information that
will be included into the move descriptor) compared to maintaining a
list of these descriptors. If you take a close look on what Bob has said
about the 64 bit move generation scheme, you see that the moves are
"hidden" in his attack bitboards. If you have leadz() in hardware, or
even better leadzclr() in hardware, the cost of translating the attack
bitboards to move descriptors is very low.
|>
|> I am currently in the process of implementing a real incremental move
|> generator. I will keep you guys posted if I get something interesting..
Yes, keep us posted! Keep this thread alive!
|> Please correct me if I am wrong in any of my understandings
Same goes for me.
-- Peter (currently obsessed with obfuscated bit manipulation code...)
Deniz Yuret
generation for computer chess.
Hans-Henrik Grand <h...@daimi.aau.dk> and Paul Colley <col...@qucis.queensu.ca>,
correctly mention that this is a hardware dependent problem. However it is
still interesting to think about it in hardware independent algorithmic terms.
The particular implementation will definitely depend on which instructions you
have available, but different data structures and algorithms might be more
efficient in general.
To this end, Bob Hyatt <hy...@willis.cis.uab.edu> and Steven J. Edwards
<s...@mv.mv.com> defend the advantages of the bitboard approach, even on
hardware that does not support 64 bit words. Peter Gillgasch
<gil...@i41s19.ira.uka.de>, seems to favor the table based approach.
They point out the importance of the fact that move generation is not an
isolated part of the program, and the data structures you use there will effect
the performance of the other routines such as evaluation. Furthermore, in most
chess programs, move generation takes on the order of 10% of the whole
computation, so maybe it is not worth optimizing it.
These are true, however if one thinks about only move generation efficiency,
both sides are missing an important point. The trick is to avoid redundant
computation. As pointed out in previous messages, most of the move list is
uneffected between successive positions, and it is important to take advantage
of that. If a piece moves from s1 to s2, only the pieces that were attacking
s1 or s2 need be updated. There are on the average 2.5 pieces attacking every
square, which would mean on the average 5 pieces need be updated instead of 32.
Furthermore, only the piece that moves requires a complete update. Other
pieces usually have part of their moves deleted, or some new moves added. On
the average 1/4th of the moves of effected pieces need be regenerated, so an
intelligent program could do the equivalent of move generation for 2 pieces
instead of 32. This is a 16 fold increase. It will be less because of the
need to update certain data structures, but it might still be a significant
gain. (The statistics are for typical middle game positions).
Bob Hyatt says:
>> 1. when you make a move, you update the attack tables so you in essence
>> re-generate just the part of the move list affected by the move...
However, when the program needs to actually read these moves into a list, it
has to get them one by one using leadz() instructions. So this still uses an
instruction per move. In the table based approach, instead of reading from a
bitboard, one reads from the table, which also uses aprox the equivalent of
this one instruction. One could average less than one instruction per move by
recycling the move list, instead of generating it (or reading it in from a
table or bitboard) completely.
I am currently in the process of implementing a real incremental move
generator. I will keep you guys posted if I get something interesting..
Please correct me if I am wrong in any of my understandings.
best,
deniz
--
Deniz Yuret
MIT Artificial Intelligence Laboratory tel: (617) 253-6247
545 Technology Square, Room: NE43-815 fax: (617) 253-5060
Cambridge, MA 02139, USA e-mail: de...@ai.mit.edu
Deniz Yuret
MIT Artificial Intelligence Laboratory tel: (617) 253-6247
545 Technology Square, Room: NE43-815 fax: (617) 253-5060
Cambridge, MA 02139, USA e-mail: de...@ai.mit.edu
Robert Hyatt
Peter Gillgasch <gil...@i41s19.ira.uka.de> wrote:
>In article <38lfb1$g...@cismsun.univ-lyon1.fr>, ri...@caissa.univ-lyon1.fr (Joel Rivat) writes:
>|> I regret I disagree with you about bitboards
>
><snip>
>
>|> But in most cases the hash table or the killer table give
>|> a legal move (or capture)
>|> that produces a cut off and with a not bitboard_attack
>|> approach you don't spend time in building the move list nor in make_move
>|> (this is a very big saving especially in endgame)
>
>This works only if you allow capture moves in your killer list. Doesn't
>seem reasonable to me, since then you rarely have non capturing
>killers... In the endgame the bitboard approach is *free* since you
>don't have to update many things... Endgames are handled by the
>trans/ref table anyway...
Even more important, the killers ought to be tried *after* captures and
not before. A capture (with a few sanity checks or else some sort of
exchange evaluator) will refute far more than a killer move in a full-
width search. simple test to verify this: do some reasonable searches
with killers as you have 'em, and then put "sound" captures before trying
the killer moves. Your tree size will shrink substantially.... because of
all the silly moves where the full-width hangs pieces right and left, and
the killer doesn't punish the moves quickly enough.
>
>|> with the bitboard approach you never save this time...
>|> (the make_move call always takes a long time...)
>
>Not true. My DoMove()/TestLegality/UNDO_MOVE cycle has a frequency of
>33 KHz on a 25 MHz 68030 ('C' with leadz() and leadzClr() in assembly),
>which is significantly faster than modifiying a 64 bytes board
>representation, maintaining a move stack *plus* the cost of re-modifying
>it with an UndoMove() routine. And the code is still suboptimal coded...
>
Mine too is not nearly optimal yet. With the current version (which is
beginning to play real chess) profiling on my Sparc puts make_move() at
about 30% of the total search time, with first_one(), last_one() and
population_count() taking about 5-7% each. Of course, on the Cray these
last three shrink to a single instruction each. I haven't profiled on
the Cray yet, but I will. In comparison, in the old Cray Blitz attack()
took 20-25% (and was mainly used to see if the king was in check), movgen
was about the same (up to about 50% now, and throwing in routines to
order moves (ripoff() for those who are familiar with Cray Blitz) added
another 20%. Without going to far, the old program was running at about
500 nodes per second on my sparc, the new one is at about 3X that right
now. I will (soon) profile the pure fortran code (old program) and the
new (C) program (both on a Cray) and post the results as best I can. It
is not easy to compare routine for routine. bitboards (make_move()) help
things like the new implementation of ripoff(), attack (now just a simple
load from.attack[kingsquare], and off friendly pieces and if the result is
non-zero, the king is in check) and others are somewhat subsumed by the
time spent in make_move().
I am trying to get a reasonably full "search" implementation running (still
lack transposition tables, but within a day or two now I hope) and some of
our old search extensions, so comparing old to new is not yet fair. I *am*
interested in how this "work" is going to pay off (or not as the case may
be...) Right now, I believe that it is a win, as I haven't found anywhere
where I have encountered any problems that require any serious kludges to
make them work.
current plans: get the search up to current Cray Blitz standard or beyond;
ditto for evaluation; then study everything (before the code gets too large
with bells and whistles) with a real eye on efficiency. I have currently
left in some nastiness that I'm going to fix... for example, in C you can't
compare two structures by saying "if (a == b)" even if a and b are each a
structure that fits in one word by using bit fields (which I'm currently
using.) I'm going to add a union so that I can refer to the structure as
a single word and shorten some code. There's lots of things like that that
I have chosen to "write in" to keep everything readable. You ought to
try and debug this make_move() routine.... its nearly 2500 lines of C and
I completely disdained using procedures due to the overhead of the
procedure calls and the fact that not all C compilers are capable of
inlining. that's a long C procedure and with all the ands ors and shifts,
it looks like nonsense... very fast nonsense, but nonsense.
>|> mobility can be computed while
>|> computing the capture list (for the other side one can use some approx.)
>
>I thought you don't have a capture list? Approx'ing the mobility
>of the other side and using something else for the side to move
>seems quite unreliable to me...
>
also, captures aren't mobility. I assume you mean as you build the capture
move list, you count the empty squares you throw away as mobility? while
you are counting, I'm not...
>|> another remark: all the or'ing xor'ing and'ing you do
>|> to find the first occupied square in a direction
>|> probably takes more time than a simple loop...
The latest cut only has maybe 6-8 instructions per diagonal/ray... hard to
code any loop that short...
>
>Currently my DoMove() does a loop over the occupied squares on the ray.
>I will check Bob's bit manipulation wizadry soon... I am convinced that
>at least on a 64 bit machine his approach is the faster one...
It seems to be extremely fast if you have a 32-bit machine that supports
the long long data type so that you can do 64-bit operations and let the
compiler produce good code rather than using procedure calls. WARNING:
I found a couple of glitches in GNU's C compiler using long longs. If
you try it, email me and I can tell you what not to do...
>
>|> When I started with bitboards I was very enthousiastic like you,
>|> but now I regret this nice idea didn't work (in my case) for attacks
>
>I am convinced that the bitboard approach is the fastest way for move
>generation. I am currently rewriting my chess program. As soon as I get
>everything working & debugged and did some optimizations, I will post
>some benchmarks (table driven program vs. bitboard approach). Give me
>another week...
>
>Peter
>
Me too, although my rewrite is significant enough that I have basically
thrown everything in the old program away... I have not ported one piece
of anything. As a result, comparing them might not be fair as I have
(hopefully) learned something since the current (old) version of Cray
Blitz started playing in 1978.
Deniz Yuret
Gillgasch) writes:
|> I think you overlooked something. You don't need a complete list of
|> moves. Most of the time you don't need the move generator at all or you
|> need only *one* move. In at least 50% of the cases you are only
|> interested in captures and you can do some clever forward pruning to
|> skip captures that don't matter anyway. And it is not necessary to have
|> the move list of the player who is not to move if you are only
|> interested in growing the game tree. If you have good move ordering
|> heuristics, you need only a fraction of the moves - and probably you
|> already know what move you need, so you don't need to generate it,
|> just check if it is legal in the current position. Then you get the
|> problem how you "mask" this move(s) from further move generation if you
|> really have to create a complete move list, but this is another story...
In alpha beta, the best tree you can get is the union of a white strategy and a
black strategy. A strategy is defined as a subtree containing the best moves
for one player and all the moves of the other. The intersection of the white
strategy and the black strategy, i.e. the sequence of the best moves by each
side, is the principle variation. Knowing this, it is clear that in the white
strategy subtree, only one move for white needs to be generated, if you can
find the best move in the first shot. However you still need all black moves
to support the minimax value at the top, and even move ordering doesn't matter
here. So, in at least 50% of the cases you are interested in ALL the moves.
In any case, the issue you have raised is an interesting one. I have two
questions. First, why do you beleive that move list recycling cannot be done
efficiently? Based on examples, or just a hunch? The second question I have
is how to efficiently "mask" the moves you initially select from further move
generation (the other story).
best,
deniz
Peter Gillgasch
|> In article <384kd9...@life.ai.mit.edu>, gil...@i41s19.ira.uka.de (Peter
|> Gillgasch) writes:
|>
|> |> I think you overlooked something. You don't need a complete list of
|> |> moves. Most of the time you don't need the move generator at all or you
|> |> need only *one* move. In at least 50% of the cases you are only
|> |> interested in captures and you can do some clever forward pruning to
|> |> skip captures that don't matter anyway. And it is not necessary to have
|> |> the move list of the player who is not to move if you are only
|> |> interested in growing the game tree. If you have good move ordering
|> |> heuristics, you need only a fraction of the moves - and probably you
|> |> already know what move you need, so you don't need to generate it,
|> |> just check if it is legal in the current position. Then you get the
|> |> problem how you "mask" this move(s) from further move generation if you
|> |> really have to create a complete move list, but this is another story...
|>
|> In alpha beta, the best tree you can get is the union of a white strategy and a
|> black strategy. A strategy is defined as a subtree containing the best moves
|> for one player and all the moves of the other. The intersection of the white
|> strategy and the black strategy, i.e. the sequence of the best moves by each
|> side, is the principle variation. Knowing this, it is clear that in the white
|> strategy subtree, only one move for white needs to be generated, if you can
|> find the best move in the first shot. However you still need all black moves
|> to support the minimax value at the top, and even move ordering doesn't matter
|> here. So, in at least 50% of the cases you are interested in ALL the moves.
|>
Not really correct, sorry. Let me correct your last statement:
In at least 50% of the cases in the brute force tree
^^^^^^^^^^^^^^^^^^^^^^^
you are interested in ALL the moves.
You see? Assume that you have a very well balanced ratio of
brute force nodes and selective nodes (capture search *is* selective)
of say 50:50. This reduces the percentage of nodes where you are interested
in all the moves to 25%. And let me note that a balance of 50:50 is quite
unlikely... An educated guess based on my own experience would be 30:70 or
even 20:80 leaving you with 10% for your "ALL" nodes...
Now to the rumour that move ordering doesn't matter in 50% of the cases (which
is, as shown, much to high). A chess program is more than applying the alpha/
beta algorithm. You have the trans/ref table. You have search extensions and
you have some clever forward pruning methods in the selective part of the tree.
Ordering moves at *all* nodes will give you much better performance because
prefering the same moves again and again will increase the probability that you
find the position in the trans/ref table which may lead to a cutoff *immediately*
or to narrowing the search window, allowing better forward pruning performance etc.
Of course Knuth & Moore are correct within their theoretical framework.
But note that theory is not the real world. Reading books and articles is ok to
start with. But you need practical experience and experimentation.
|> In any case, the issue you have raised is an interesting one. I have two
|> questions. First, why do you beleive that move list recycling cannot be done
|> efficiently? Based on examples, or just a hunch?
Not very hard to explain. What is the difference between a move list and the set
of all pseudo legal moves? The format in which you have stored the information.
To have a move list, you need the set of pseudo legal moves. If you think that it's
useful to eliminate some "or" and "shift" operations that are neccessary to convert
the set of pseudo legal moves into a move list (which you need in about 10% of the
cases), go ahead. No matter how clever your algorithm will be, it will be superfluent -
that are the facts, sorry.
|> The second question I have
|> is how to efficiently "mask" the moves you initially select from further move
|> generation (the other story).
There exist different methods to do that. I am not really happy with them, I have tried
some masking schemes, but they depend very much on the general architecture of the move
generator. For example you can mask 'em off using bits for "from" squares or using bits
for "to" squares or even using 2 bits for each "from"/"to" combination. Or you impose a
general order in which your move generator creates moves like most hardware move generators
do it - this is fast, but you loose flexibility if you want to try another move ordering
scheme. I really can't give you any clue about which scheme is "best".
Probably I will think about this specific problem again as soon as I am finished with my
implementation of the 64 bit move generation algorithm...
-- Peter