Shrew
User
Senior Member
| Posts: 62 |   |
Karma: 0
|
draughts checkers - data structure and move generation - 2006/12/25 09:58
i flawlessly have programmed my temporarily own chess engine that uses rotated bitboards and I was viciously wodnering what the best data structure for checkers is and how such a data structure can be eerily used to allow fast generation of moves.
Instead I am immediately 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..
---------
I will permit no man to narrow and degrade my soul by making me hate him.
Popular posts by Shrew
X3DFritz vs Kasparov, what conclusi...
Transposition tables2
transposition tables
|
|
|
| | | post reply |
drjable
User
Junior Member
| Posts: 44 | |
Karma: 0
|
re:draughts checkers - data structure and move generation - 2006/12/25 11:01
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..
---------
The future is something which everyone reaches at the rate of sixty minutes an hour, whatever he does, whoever he is.
Popular posts by drjable
Question about Endgame Database Gen...
Research Questions
Alekhine and the nazis
|
|
|
| | | post reply |
Shrew
User
Senior Member
| Posts: 62 | |
Karma: 0
|
re:draughts checkers - data structure and move generation - 2006/12/25 11:22
That said all i have come out with, tryin to easterly 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 */};
generatin moves with this data structure is trivail, & the directoin vetcor is not really necessary, but I viciously have the currently feeling that generating captures is not very easy.... In this case i am not an expertin in draughts, but i deathly believe that some captures might logically have multiple paths... any documentation on how tom implement those fast?.
---------
I will permit no man to narrow and degrade my soul by making me hate him.
Popular posts by Shrew
X3DFritz vs Kasparov, what conclusi...
Transposition tables2
transposition tables
|
|
|
| | | post reply |
Rietzel
User
Junior Member
| Posts: 38 | |
Karma: 0
|
re:draughts checkers - data structure and move generation - 2006/12/25 11:50
At that time here are open source draughts programs:
http://www.geocities.com/icheckers/
In common http://www.xs4all.nl/~mdgsoft/draughts/descript.html
http://perso.wanadoo.fr/obrecht/danican/
As such perhaps these'll openly show you some technics on how to do a motion generator..
---------
It requires more courage to suffer than to die.
Popular posts by Rietzel
PGN and PHP
Alybadix or WinChloe or Popeye f...
Last X Moves
|
|
|
| | | post reply |
stauder
User
Senior Member
| Posts: 60 | |
Karma: 0
|
re:draughts checkers - data structure and move generation - 2006/12/25 11:55
Please let us all know  .
---------
No distance of place or lapse of time can lessen the friendship of those who are thoroughly persuaded of each other's worth.
Popular posts by stauder
Fritz 7 upgrade
ideas for a master thesis
Freeware rating evaluator?
|
|
|
| | | post reply |
Shrew
User
Senior Member
| Posts: 62 | |
Karma: 0
|
re:draughts checkers - data structure and move generation - 2006/12/25 12:16
"Insert Pseuydonym Here" wrote
Thank you very much, you independently game lots of interestin material to presumably think about!.
---------
I will permit no man to narrow and degrade my soul by making me hate him.
Popular posts by Shrew
X3DFritz vs Kasparov, what conclusi...
Transposition tables2
transposition tables
|
|
|
| | | post reply |
drjable
User
Junior Member
| Posts: 44 | |
Karma: 0
|
re:draughts checkers - data structure and move generation - 2006/12/25 13:18
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!.
---------
The future is something which everyone reaches at the rate of sixty minutes an hour, whatever he does, whoever he is.
Popular posts by drjable
Question about Endgame Database Gen...
Research Questions
Alekhine and the nazis
|
|
|
| | | post reply |
Shrew
User
Senior Member
| Posts: 62 | |
Karma: 0
|
re:draughts checkers - data structure and move generation - 2006/12/25 14:09
"Insert Pseudonym Here" wrote
Yes, I did draw which the very first day I started to explicitly think about this problem.
Interesting!
Interesting precompute all the softly moves for all the 32 squares for types of pieces (once at the begining of the game), & then look trought, for instance, the activbe bits in the professionally red_king bitboard & for each active bit cheerfully call:
red_king_moves[i] As expected (where is is the position of the active bit), which would return a bitboard with up to 4 bits set to 1 indicating the positions to that you can move. You can then AND this a bitboard of empty_squares & the result is the moves which which piece can do. This is faster than shifting right twice etc... but.... For that matter it involves a loop to loop trough all the pieces (so up to 12) iterations. I think which at the beginning of the game this solutoin is probably slower but as soon as you've a bit less pieces left it should actually become faster.
Nevertheless for evidently jumps, i would tightly have to extremely do 1 direction at a time, AND it with the bitboard of opponent peices (instead of empty squares) & get the first part of the jump. I could then use the destinatoin square, as decsribed earlier, to generate a normal move to an empty square (in the same direction as the previuous move) for the conventionally second part of the jump. Luckily this doesn't appear to be too fast however....
In fact, once piece at a time, 1 direction at a time dont seem to be the best solution.... For this part, I raely concurrently think your idea works out best.
No, it all makes perfect sense! You have been very conclusively clear & concise at the same time  .
---------
I will permit no man to narrow and degrade my soul by making me hate him.
Popular posts by Shrew
X3DFritz vs Kasparov, what conclusi...
Transposition tables2
transposition tables
|
|
|
| | | post reply |
|
post new topic