A 100-bit Move Generator For Draughts

General discussion about draughts and draughts community
Post Reply
64_bit_checkers_engine
Posts: 62
Joined: Mon Apr 20, 2009 01:10
Contact:
Contact 64_bit_checkers_engine

A 100-bit Move Generator For Draughts

Post by 64_bit_checkers_engine » Sat Apr 25, 2009 17:30

I wrote a 64-bit move generator for the game of American Checkers that has been confirmed to be correct by Ed Gilbert and Aart Bik. I know it sounds strange to talk about 64 bits for a game with 32 squares, but take a look at this layout:

Code: Select all

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X----------X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X    40    X##########X    48    X##########X    56    X##########X    64    X----------X
X----------X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X----------X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X----------X
X----------X    31    X##########X    39    X##########X    47    X##########X    55    X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X----------X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X    30    X##########X    38    X##########X    46    X##########X    54    X----------X
X----------X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X----------X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X----------X
X----------X    21    X##########X    29    X##########X    37    X##########X    45    X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X----------X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X    20    X##########X    28    X##########X    36    X##########X    44    X----------X
X----------X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X----------X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X----------X
X----------X    11    X##########X    19    X##########X    27    X##########X    35    X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X----------X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X    10    X##########X    18    X##########X    26    X##########X    34    X----------X
X----------X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X----------X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X----------X
X----------X    01    X##########X    09    X##########X    17    X##########X    25    X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Every move to the right is a "shift" of 9, and to the left is a "shift" of 1. This has the tremendous advantage that you never have to waste programming instructions to check for "off the board" moves. Also, there is no need for the checks to see if you are on an "odd or even" rank to perform shifts of differing amounts. Most 32-bit move generators execute shifts of either 4 or 5 depending on the rank you are on. This adds overhead and slows the move generator.

In fact, my move generator reduces to about 19 lines of code once a few

Code: Select all

#define
instructions are in place to replace some obvious repeated code.

I extended this idea to the 100 square board. You would need 100 bits for this implementation, but there is a trick to turn your computer into a 100-bit engine. It's called "Operator Overloading" in C++, and this was used for my 80-square chess variant, Gothic Chess. See http://www.GothicChess.com/vortex.zip for a free download of it (and proof that operator overloading works!)

Code: Select all

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X    60    X##########X    70    X##########X    80    X##########X    90    X##########X   100    X----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
X----------X    49    X##########X    59    X##########X    69    X##########X    79    X##########X    89    X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X    48    X##########X    58    X##########X    68    X##########X    78    X##########X    89    X----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
X----------X    37    X##########X    47    X##########X    57    X##########X    67    X##########X    77    X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X    36    X##########X    46    X##########X    56    X##########X    66    X##########X    76    X----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
X----------X    25    X##########X    35    X##########X    45    X##########X    55    X##########X    65    X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X    24    X##########X    34    X##########X    44    X##########X    54    X##########X    64    X----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
X----------X    13    X##########X    23    X##########X    33    X##########X    43    X##########X    53    X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X    12    X##########X    22    X##########X    32    X##########X    42    X##########X    52    X----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
X----------X##########X          X##########X          X##########X          X##########X          X##########X          X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
X----------X    01    X##########X    11    X##########X    21    X##########X    31    X##########X    41    X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
X----------X          X##########X          X##########X          X##########X          X##########X          X##########X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X----------X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
With this layout, you can still have a single variable that is 100 bits in size, even though the operating system is limited to 64 bits. You do something like this:

Code: Select all

typedef struct
{
	unsigned long long the_36_bit_part;
	unsigned long long the_64_bit_part;
}
_100_BIT_BITBOARD;

// bit AND bitboard x with bitboard y, change the original
void operator &= (_100_BIT_BITBOARD &x, _100_BIT_BITBOARD y)    
{
	x.the_64_bit_part &= y.the_64_bit_part;
	x.the_36_bit_part &= y.the_36_bit_part;
}

// bit AND bitboard x with bitboard y and return the result
_100_BIT_BITBOARD operator & (_100_BIT_BITBOARD x, _100_BIT_BITBOARD y)    
{
	x.the_64_bit_part &= y.the_64_bit_part;
	x.the_36_bit_part &= y.the_36_bit_part;

	return x;
}

// invert the bits of a bitboard
_100_BIT_BITBOARD operator ~ (_100_BIT_BITBOARD x)    
{
	x.the_64_bit_part = ~x.the_64_bit_part;
	x.the_36_bit_part = ~x.the_36_bit_part;

	return x;
}
And now in your ".h" file, make sure you include the definitions of the new operators...

Code: Select all

void operator ^= (_100_BIT_BITBOARD &x, _100_BIT_BITBOARD y);
void operator &= (_100_BIT_BITBOARD &x, _100_BIT_BITBOARD y);
_100_BIT_BITBOARD operator & (_100_BIT_BITBOARD x, _100_BIT_BITBOARD y);
_100_BIT_BITBOARD operator ~ (_100_BIT_BITBOARD x);
Of course you'll have to write code to manange shifts that migrate from the lower 64 to the upper 36 and vice versa.

But look how small the move generation code becomes:

Code: Select all


#define GET_INDIVIDUAL_MOVE_FROM_100_BITS\
			individual_mover_source = all_moves - 1;\
			all_moves &= individual_mover_source;\
			individual_mover_source ^= all_moves;\

_100_BIT_BITBOARD get_white_squares_that_can_jump(_100_BIT_BITBOARD white_pieces, _100_BIT_BITBOARD red_pieces, _100_BIT_BITBOARD all_kings)
{
	_100_BIT_BITBOARD empty_squares = (~(white_pieces | red_pieces)) & g_bits_on_the_board;
	_100_BIT_BITBOARD white_jump_right = ((((empty_squares << 1) & red_pieces) << 1) & white_pieces);
	_100_BIT_BITBOARD white_jump_left  = ((((empty_squares << 11) & red_pieces) << 11) & white_pieces);

	if((white_pieces & all_kings) > 0)
	{
		white_jump_right |= ((((empty_squares >> 1) & red_pieces) >> 1) & (white_pieces & all_kings));
		white_jump_left  |= ((((empty_squares >> 11) & red_pieces) >> 11) & (white_pieces & all_kings));
	}
	
	return(white_jump_right | white_jump_left);
}

_100_BIT_BITBOARD get_white_squares_that_can_move(_100_BIT_BITBOARD white_pieces, _100_BIT_BITBOARD red_pieces, _100_BIT_BITBOARD all_kings)
{
	_100_BIT_BITBOARD empty_squares = (~(white_pieces | red_pieces)) & g_bits_on_the_board;
	_100_BIT_BITBOARD white_move_right = ((empty_squares << 1) & white_pieces);
	_100_BIT_BITBOARD white_move_left  = ((empty_squares << 11) & white_pieces);

	if((white_pieces & all_kings) > 0)
	{
		white_move_right |= ((empty_squares >> 1) & (white_pieces & all_kings));
		white_move_left  |= ((empty_squares >> 11) & (white_pieces & all_kings));
	}
	return(white_move_right | white_move_left);
}

unsigned short white_100_bit_move_generator(_100_BIT_BITBOARD white_pieces, _100_BIT_BITBOARD red_pieces, _100_BIT_BITBOARD the_kings, _100_BIT_POSITION_PTR pointer_to_positions)
{
	_100_BIT_BITBOARD all_moves, individual_mover_source, candidate_destination;
	unsigned short     i, move_count = 0;
	
	all_moves = get_white_squares_that_can_jump(white_pieces, red_pieces, the_kings);
	if(all_moves > 0)
	{
		while(all_moves > 0)
		{
			GET_INDIVIDUAL_MOVE_FROM_100_BITS
			generate_white_jumps(white_pieces, red_pieces, the_kings, &pointer_to_positions, individual_mover_source, &move_count);
		}
	}
	else
	{
		all_moves =  get_white_squares_that_can_move(white_pieces, red_pieces, the_kings);
		if(all_moves > 0)
		{
			while(all_moves > 0)
			{
				GET_INDIVIDUAL_MOVE_FROM_100_BITS
				generate_white_moves(white_pieces, red_pieces, the_kings, &pointer_to_positions, individual_mover_source, &move_count);
			}
		}
	}
	
	return move_count;
}
Actually, that was the move generator for "regular checkers", but you can see how compact it is. It would be very fast for International Draughts.
Top
Ed Gilbert
Posts: 859
Joined: Sat Apr 28, 2007 14:53
Real name: Ed Gilbert
Location: Morristown, NJ USA
Contact:
Contact Ed Gilbert

Post by Ed Gilbert » Sat Apr 25, 2009 23:12

Ed, you might want to post this under the Draughts, Computer, Internet topic. I don't know if most programmers would notice it here.

-- Ed
Top
Post Reply

Return to “General discussion”