Home 
Search 
Today's Posts 
#1




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




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




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




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 upright. Note that none of White's pieces at the very top and very right of the board can move upright. Further, note that when you compress the board from 8x8 to 32 bits, movement IN THE BITBOARD looks funnysome 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 upright moves in our example. Take one of your original bitboards and copy it (call this copy_a). Next, BITWISEAND copy_a by 0x0F0F0F0F, then RIGHTSHIFT it by 4. Now, take another copy of the original bitboard (call it copy_b), BITWISEAND copy_b by 0x00E0E0E0, and RIGHTSHIFT it by 3. Finally, BITWISEOR 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 upright 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 BITWISEAND and RIGHTSHIFT 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 upright 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 (upright, upleft, downright, down left) has different masks, shiftcounts, and shiftdirections. 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 reasonablelooking solution to the problem. This turned out to be a lot more fun than trying to implementing it. Tommy 
#5




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




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 funnysome 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 upright moves in our example. Take one of your original bitboards and copy it (call this copy_a). Next, BITWISEAND copy_a by 0x0F0F0F0F, then RIGHTSHIFT it by 4. Now, take another copy of the original bitboard (call it copy_b), BITWISEAND copy_b by 0x00E0E0E0, and RIGHTSHIFT it by 3. Finally, BITWISEOR 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 upright 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 BITWISEAND and RIGHTSHIFT 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 upright 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




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 funnysome 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 upright moves in our example. Take one of your original bitboards and copy it (call this copy_a). Next, BITWISEAND copy_a by 0x0F0F0F0F, then RIGHTSHIFT it by 4. Now, take another copy of the original bitboard (call it copy_b), BITWISEAND copy_b by 0x00E0E0E0, and RIGHTSHIFT it by 3. Finally, BITWISEOR 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 upright 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 BITWISEAND and RIGHTSHIFT 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 upright 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




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  


Similar Threads  
Thread  Forum  
How to handle bizarre moves during 'book' openings  rec.games.chess.analysis (Chess Analysis) 