Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old May 7th 04, 11:15 AM
Tommy
 
Posts: n/a
Default draughts checkers - data structure and move generation

Hello,

i have programmed my own chess engine that uses rotated bitboards and I was
wondering what the best data structure for checkers is and how such a data
structure can be used to allow fast generation of moves.
I am looking for a document like the one on rotated bitboards by Dr. Hyatt,
only, this time for checkers. I woke up with this question and... looked on
google, but did not find much.
Thanks in advance,

Tommy

  #2   Report Post  
Old May 7th 04, 05:02 PM
Tommy
 
Posts: n/a
Default draughts checkers - data structure and move generation


"Tommy" wrote

i have programmed my own chess engine that uses rotated bitboards and I

was
wondering what the best data structure for checkers is and how such a data
structure can be used to allow fast generation of moves.
I am looking for a document like the one on rotated bitboards by Dr.

Hyatt,
only, this time for checkers. I woke up with this question and... looked

on
google, but did not find much.


All i have come out with, trying to work it out by myself is:

enum Square {EMPTY = 0, RED = +1, REDKING = +2, YELLOW = -1, YELLOWKING
= -2};
Square board[32] = {EMPTY};
int direction[4] = {+5 /* NE */, +4 /* NW */, -4 /* SW */, -3 /* SE */};

generating moves with this data structure is trivial, and the direction
vector is not really necessary, but I have the feeling that generating
captures is not very easy.... i am not an expertin in draughts, but i
believe that some captures might have multiple paths... any documentation on
how tom implement those fast?

Thanks,

Tommy

  #3   Report Post  
Old May 7th 04, 06:32 PM
Joost de Heer
 
Posts: n/a
Default draughts checkers - data structure and move generation

i have programmed my own chess engine that uses rotated bitboards and I was
wondering what the best data structure for checkers is and how such a data
structure can be used to allow fast generation of moves.
I am looking for a document like the one on rotated bitboards by Dr. Hyatt,
only, this time for checkers. I woke up with this question and... looked on
google, but did not find much.
Thanks in advance,


Here are open source draughts programs:
http://www.geocities.com/icheckers/
http://www.xs4all.nl/~mdgsoft/draughts/descript.html
http://perso.wanadoo.fr/obrecht/danican/

Perhaps these'll show you some techniques on how to do a move generator.

Joost
--
Du hast mein Herz zerrissen, meine Seele geraubt
Das es so enden würde hätt` ich nie geglaubt [Aus der Ruinen -]
Ohne Rücksicht auf Verluste, hast Du meine Welt zerstört [L'Âme Immortelle]
Eine Welt, die vor kurzem nur uns beiden hat gehört
  #4   Report Post  
Old May 9th 04, 07:16 PM
Insert Pseudonym Here
 
Posts: n/a
Default draughts checkers - data structure and move generation

"Tommy" wrote in
:

Hello,

i have programmed my own chess engine that uses rotated bitboards and
I was wondering what the best data structure for checkers is and how
such a data structure can be used to allow fast generation of moves.
I am looking for a document like the one on rotated bitboards by Dr.
Hyatt, only, this time for checkers. I woke up with this question
and... looked on google, but did not find much.
Thanks in advance,


Hey Tommy,

You don't really need to rotate bitboards in checkers. There are only
two kinds of moves any checkers piece can make: a move, and a jump. The
former always moves the piece one square diagonally, the latter two
squares diagonally.

We can leverage this regularity to determine, IN PARALLEL, what all
pieces can move. (First, note that checkers bitboards need only be 32
bits, since the dark squares are never used. Also, there needs to be
separate bitboards for each player's men, and each player's kings.)

For instance, say we're analyzing pieces for the player (say, White)
oriented toward the bottom of the board, and want to see which pieces can
move up-right. Note that none of White's pieces at the very top and very
right of the board can move up-right. Further, note that when you
compress the board from 8x8 to 32 bits, movement IN THE BITBOARD looks
funny--some moves appear to move straight up, and others appear to move
diagonally. (It will help you a lot to draw this out, probably on graph
paper.)

Anyway, here's how to generate up-right moves in our example. Take one
of your original bitboards and copy it (call this copy_a). Next,
BITWISE-AND copy_a by 0x0F0F0F0F, then RIGHT-SHIFT it by 4. Now, take
another copy of the original bitboard (call it copy_b), BITWISE-AND
copy_b by 0x00E0E0E0, and RIGHT-SHIFT it by 3. Finally, BITWISE-OR
copy_a and copy_b together into, say, copy_c. At this point, copy_c is a
bitboard representing the destination squares of all White's pieces from
the original bitboard, moved up and to the right.

But there's a problem, right? Not all of those squares are legal moves!
True; copy_c still needs some work. First, you need to mask out your own
pieces from copy_c, no matter what.

Now, here's the cool thing. If you mask out the opponent's pieces from
copy_c, you're left with all the valid up-right moves your pieces from
the original bitboard can make. However, if you mask out everything
that's NOT an opponent piece from copy_c, you can perform the above
BITWISE-AND and RIGHT-SHIFT again to get, say, copy_d. Mask out your and
your opponent's pieces, and copy_d is the bitboard representing the
destination of all up-right jump moves for your pieces (from the original
bitboard)!

If this doesn't make much sense, break out the graph paper and draw it
all out. Note that each direction (up-right, up-left, down-right, down-
left) has different masks, shift-counts, and shift-directions. You can
find this out on your own. Since you've written a chess engine using
bitboards, I assume you can fill in the blanks pretty easily.

Note that I haven't actually implemented this within a full checkers
program. I was mainly interested in coming up with a reasonable-looking
solution to the problem. This turned out to be a lot more fun than
trying to implementing it.


Tommy


  #5   Report Post  
Old May 10th 04, 02:20 AM
Tommy
 
Posts: n/a
Default draughts checkers - data structure and move generation


"Insert Pseudonym Here" wrote

Thank you very much, you game lots of interestin material to think about!

Tommy



  #6   Report Post  
Old May 10th 04, 11:00 AM
Tommy
 
Posts: n/a
Default draughts checkers - data structure and move generation


"Insert Pseudonym Here" wrote

(First, note that checkers bitboards need only be 32
bits, since the dark squares are never used.


yeah, i noticed that!

Further, note that when you
compress the board from 8x8 to 32 bits, movement IN THE BITBOARD looks
funny--some moves appear to move straight up, and others appear to move
diagonally. (It will help you a lot to draw this out, probably on graph
paper.)


Yes, I did draw that the very first day I started to think about this
problem.

Anyway, here's how to generate up-right moves in our example. Take one
of your original bitboards and copy it (call this copy_a). Next,
BITWISE-AND copy_a by 0x0F0F0F0F, then RIGHT-SHIFT it by 4. Now, take
another copy of the original bitboard (call it copy_b), BITWISE-AND
copy_b by 0x00E0E0E0, and RIGHT-SHIFT it by 3. Finally, BITWISE-OR
copy_a and copy_b together into, say, copy_c. At this point, copy_c is a
bitboard representing the destination squares of all White's pieces from
the original bitboard, moved up and to the right.
But there's a problem, right? Not all of those squares are legal moves!
True; copy_c still needs some work. First, you need to mask out your own
pieces from copy_c, no matter what.
Now, here's the cool thing. If you mask out the opponent's pieces from
copy_c, you're left with all the valid up-right moves your pieces from
the original bitboard can make. However, if you mask out everything
that's NOT an opponent piece from copy_c, you can perform the above
BITWISE-AND and RIGHT-SHIFT again to get, say, copy_d. Mask out your and
your opponent's pieces, and copy_d is the bitboard representing the
destination of all up-right jump moves for your pieces (from the original
bitboard)!


Interesting!
I am going to try out if this is the fastest approach or if it is faster to:
precompute all the moves for all the 32 squares for types of pieces (once at
the begining of the game),
and then look trought, for instance, the active bits in the red_king
bitboard and for each active bit call:
red_king_moves[i] (where is is the position of the active bit), that would
return a bitboard with up to four bits set to one indicating the positions
to which you can move. You can then AND this a bitboard of empty_squares and
the result is the moves that that piece can do. This is faster than shifting
right twice etc... but.... it involves a loop to loop trough all the pieces
(so up to 12) iterations. I think that at the beginning of the game this
solution is probably slower but as soon as you have less pieces left it
should actually become faster.

For jumps, i would have to do one direction at a time, AND it with the
bitboard of opponent pieces (instead of empty squares) and get the first
part of the jump. I could then use the destination square, as described
earlier, to generate a normal move to an empty square (in the same direction
as the previous move) for the second part of the jump. This does not appear
to be too fast however....
In fact, once piece at a time, one direction at a time does not seem to be
the best solution.... For this part, I really think your idea works out
best.

If this doesn't make much sense


No, it all makes perfect sense! You have been very clear and concise at the
same time ;-)

Now, I'll write a few different versions and see which one performs the
best....
Thanks a lot!

Tommy




  #7   Report Post  
Old May 10th 04, 11:50 AM
Terry
 
Posts: n/a
Default draughts checkers - data structure and move generation


"Tommy" wrote in message
...

"Insert Pseudonym Here" wrote

(First, note that checkers bitboards need only be 32
bits, since the dark squares are never used.


yeah, i noticed that!

Further, note that when you
compress the board from 8x8 to 32 bits, movement IN THE BITBOARD looks
funny--some moves appear to move straight up, and others appear to move
diagonally. (It will help you a lot to draw this out, probably on graph
paper.)


Yes, I did draw that the very first day I started to think about this
problem.

Anyway, here's how to generate up-right moves in our example. Take one
of your original bitboards and copy it (call this copy_a). Next,
BITWISE-AND copy_a by 0x0F0F0F0F, then RIGHT-SHIFT it by 4. Now, take
another copy of the original bitboard (call it copy_b), BITWISE-AND
copy_b by 0x00E0E0E0, and RIGHT-SHIFT it by 3. Finally, BITWISE-OR
copy_a and copy_b together into, say, copy_c. At this point, copy_c is

a
bitboard representing the destination squares of all White's pieces from
the original bitboard, moved up and to the right.
But there's a problem, right? Not all of those squares are legal moves!
True; copy_c still needs some work. First, you need to mask out your

own
pieces from copy_c, no matter what.
Now, here's the cool thing. If you mask out the opponent's pieces from
copy_c, you're left with all the valid up-right moves your pieces from
the original bitboard can make. However, if you mask out everything
that's NOT an opponent piece from copy_c, you can perform the above
BITWISE-AND and RIGHT-SHIFT again to get, say, copy_d. Mask out your

and
your opponent's pieces, and copy_d is the bitboard representing the
destination of all up-right jump moves for your pieces (from the

original
bitboard)!


Interesting!
I am going to try out if this is the fastest approach or if it is faster

to:
precompute all the moves for all the 32 squares for types of pieces (once

at[i]
the begining of the game),
and then look trought, for instance, the active bits in the red_king
bitboard and for each active bit call:
red_king_moves (where is is the position of the active bit), that would
return a bitboard with up to four bits set to one indicating the positions
to which you can move. You can then AND this a bitboard of empty_squares

and
the result is the moves that that piece can do. This is faster than

shifting
right twice etc... but.... it involves a loop to loop trough all the

pieces
(so up to 12) iterations. I think that at the beginning of the game this
solution is probably slower but as soon as you have less pieces left it
should actually become faster.

For jumps, i would have to do one direction at a time, AND it with the
bitboard of opponent pieces (instead of empty squares) and get the first
part of the jump. I could then use the destination square, as described
earlier, to generate a normal move to an empty square (in the same

direction
as the previous move) for the second part of the jump. This does not

appear
to be too fast however....
In fact, once piece at a time, one direction at a time does not seem to be
the best solution.... For this part, I really think your idea works out
best.

If this doesn't make much sense


No, it all makes perfect sense! You have been very clear and concise at

the
same time ;-)

Now, I'll write a few different versions and see which one performs the
best....
Thanks a lot!

Tommy


Please let us all know

Regards

Terry


  #8   Report Post  
Old May 11th 04, 03:16 AM
Insert Pseudonym Here
 
Posts: n/a
Default draughts checkers - data structure and move generation

"Tommy" wrote in
:

Now, I'll write a few different versions and see which one performs
the best....
Thanks a lot!


I agree that cycling through pieces one at a time and using a lookup table
would probably be faster with only a few pieces on the (bit)board. In
particular, it would probably be the method of choice for kings.

Be sure to report back your findings!

Tommy

Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to handle bizarre moves during 'book' openings Patrick Hoerter rec.games.chess.analysis (Chess Analysis) 13 December 7th 03 05:19 AM


All times are GMT +1. The time now is 03:16 AM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright ©2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017