100-bit Move Generator for Draughts

Discussion about development of draughts in the time of computer and Internet.
Post Reply
64_bit_checkers_engine
Posts: 62
Joined: Mon Apr 20, 2009 01:10

100-bit Move Generator for Draughts

Post by 64_bit_checkers_engine »

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;\

#define IS_THERE_ANOTHER_WHITE_JUMP\
	another_jump = ((((individual_jumper_source >> 11) & red_pieces) >> 11) & empty_squares) | ((((individual_jumper_source >> 1) & red_pieces) >> 1) & empty_squares);\
	if(another_jump == 0)\
	{\
		if((individual_jumper_source & the_kings) == 0)\
		{\
		}\
		else\
		{\
			another_jump = ((((individual_jumper_source << 11) & red_pieces) << 11) & empty_squares) | ((((individual_jumper_source << 1) & red_pieces) << 1) & empty_squares);\
		}\
	}\

#define COMMON_JUMP_OVER_ROUTINE\
		(*pointer_to_positions)->red_pieces   = red_pieces;\
		(*pointer_to_positions)->white_pieces = white_pieces;\
		(*pointer_to_positions)->all_kings    = the_kings;\
		(*pointer_to_positions)++;\
		*count_of_jumps = 1 + (*count_of_jumps);\


#define COMMON_WHITE_CHECKER_OR_KING_JUMPS(s)\
	if((candidate_jumper_destination = ((((individual_jumper_source >> (s)) & red_pieces) >> (s)) & empty_squares)) > 0)\
	{\
		(*pointer_to_positions)->white_pieces  = (white_pieces & (~individual_jumper_source));\
		(*pointer_to_positions)->all_kings     = (the_kings & (~individual_jumper_source));\
		(*pointer_to_positions)->white_pieces |= candidate_jumper_destination;\
		(*pointer_to_positions)->red_pieces    = red_pieces & ~(individual_jumper_source >> (s));\
		(*pointer_to_positions)->all_kings    &= ~(individual_jumper_source >> (s));\
		if((individual_jumper_source & the_kings) == 0)\
		{\
			if((candidate_jumper_destination & g_white_crowning_squares) == 0)\
			{\
				generate_white_jumps((*pointer_to_positions)->white_pieces, (*pointer_to_positions)->red_pieces, (*pointer_to_positions)->all_kings, pointer_to_positions, candidate_jumper_destination, &(*count_of_jumps));\
			}\
			else\
			{\
				(*pointer_to_positions)->all_kings |= candidate_jumper_destination;\
				(*pointer_to_positions)++;\
				*count_of_jumps = 1 + (*count_of_jumps);\
			}\
		}\
		else\
		{\
			(*pointer_to_positions)->all_kings |= candidate_jumper_destination;\
			generate_white_jumps((*pointer_to_positions)->white_pieces, (*pointer_to_positions)->red_pieces, (*pointer_to_positions)->all_kings, pointer_to_positions, candidate_jumper_destination, &(*count_of_jumps));\
		}\
	}\

#define COMMON_WHITE_KING_JUMPS(s)\
		if((candidate_jumper_destination = ((((individual_jumper_source << (s)) & red_pieces) << (s)) & empty_squares)) > 0)\
		{\
			(*pointer_to_positions)->white_pieces  = (white_pieces & (~individual_jumper_source));\
			(*pointer_to_positions)->all_kings     = (the_kings & (~individual_jumper_source));\
			(*pointer_to_positions)->red_pieces    = red_pieces & ~(individual_jumper_source << (s));\
			(*pointer_to_positions)->all_kings    &= ~(individual_jumper_source << (s));\
			(*pointer_to_positions)->white_pieces |= candidate_jumper_destination;\
			(*pointer_to_positions)->all_kings    |= candidate_jumper_destination;\
			generate_white_jumps((*pointer_to_positions)->white_pieces, (*pointer_to_positions)->red_pieces, (*pointer_to_positions)->all_kings, pointer_to_positions, candidate_jumper_destination, &(*count_of_jumps));\
		}\

#define COMMON_WHITE_CHECKER_OR_KING_MOVES(s)\
	if((candidate_move = ((individual_move >> (s)) & empty_squares)) > 0)\
	{\
		(*pointer_to_positions)->white_pieces = (white_pieces & ~individual_move) | candidate_move;\
		(*pointer_to_positions)->red_pieces   = red_pieces;\
		if((individual_move & the_kings) > 0)\
			(*pointer_to_positions)->all_kings = (the_kings & ~individual_move) | candidate_move;\
		else\
		{\
			if((candidate_move & g_white_crowning_squares) > 0)\
				(*pointer_to_positions)->all_kings = (the_kings | candidate_move);\
			else\
				(*pointer_to_positions)->all_kings = the_kings;\
		}\
		(*pointer_to_positions)++;\
		*count_of_moves = 1 + (*count_of_moves);\
	}\

#define COMMON_WHITE_KING_MOVES(s)\
		if((candidate_move = ((individual_move << (s)) & empty_squares)) > 0)\
		{\
			(*pointer_to_positions)->white_pieces = (white_pieces & ~individual_move) | candidate_move;\
			(*pointer_to_positions)->all_kings    = (the_kings & ~individual_move)    | candidate_move;\
			(*pointer_to_positions)->red_pieces   = red_pieces;\
			(*pointer_to_positions)++;\
			*count_of_moves = 1 + (*count_of_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);
}

void generate_white_jumps(_100_BIT_BITBOARD white_pieces, _100_BIT_BITBOARD red_pieces, _100_BIT_BITBOARD the_kings, _100_BIT_POSITION_PTR_PTR pointer_to_positions, _100_BIT_BITBOARD individual_jumper_source,  unsigned short *count_of_jumps)
{
	_100_BIT_BITBOARD all_jumps, individual_jump, another_jump, candidate_jumper_destination, empty_squares = (~(white_pieces | red_pieces)) & g_bits_on_the_board;
	unsigned short     i;
	
	IS_THERE_ANOTHER_WHITE_JUMP
		
	if(another_jump == 0)
	{
		COMMON_JUMP_OVER_ROUTINE
		return;
	}
	
	COMMON_WHITE_CHECKER_OR_KING_JUMPS(11)
	COMMON_WHITE_CHECKER_OR_KING_JUMPS(1)
	
	if((individual_jumper_source & the_kings) > 0)
	{
		COMMON_WHITE_KING_JUMPS(11)
		COMMON_WHITE_KING_JUMPS(1)
	}
}


void generate_white_moves(_100_BIT_BITBOARD white_pieces, _100_BIT_BITBOARD red_pieces, _100_BIT_BITBOARD the_kings, _100_BIT_POSITION_PTR_PTR pointer_to_positions, _100_BIT_BITBOARD individual_move, unsigned short *count_of_moves)
{
	_100_BIT_BITBOARD all_moves, candidate_move, empty_squares = (~(white_pieces | red_pieces)) & g_bits_on_the_board;
	unsigned short     i, local_move_count;
			
	COMMON_WHITE_CHECKER_OR_KING_MOVES(11)
	COMMON_WHITE_CHECKER_OR_KING_MOVES(1)
		
	if((individual_move & the_kings) > 0)
	{
		COMMON_WHITE_KING_MOVES(11)
		COMMON_WHITE_KING_MOVES(1)
	}
}

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" just ported to a 100 square layout, but you can see how compact it is. It would be very fast for International Draughts.
Top
BertTuyt
Posts: 1592
Joined: Wed Sep 01, 2004 19:42

Post by BertTuyt »

Thanks sharing this with all.
To my knowledge several of the program which uses bitboards (like Damage, which uses 64Bitboards), have implemented the concept of ghost fields.

This also has the advantage that moves to the left or right always have the same shiftcount independent of rank.
With these ghostfields one can limit the bitboard to 64bit, which with nowadays 64bit processors and registers in an advantage.

Bert
Top
Post Reply

Return to “Draughts, Computer, Internet”