International checkers bitboard representation

[Pemrograman]

I don't know if this is already known, but I found that using this bit layout has some nice properties.

Code: Select all

		49		36		23		10		61
	48		35		22		9		60	
		34		21		8		59		46
	33		20		7		58		45	
		19		6		57		44		31
	18		5		56		43		30	
		4		55		42		29		16
	3		54		41		28		15	
		53		40		27		14		1
	52		39		26		13		0	

With 64 bit, it is always rotate 1 or rotate 14 bits.

Furthermore, all the unused bits lay arround the board

Code: Select all

		63		50		37		24		11		62
	62		49		36		23		10		61	
		48		35		22		9		60		47
	47		34		21		8		59		46	
		33		20		7		58		45		32
	32		19		6		57		44		31	
		18		5		56		43		30		17
	17		4		55		42		29		16	
		3		54		41		28		15		2
	2		53		40		27		14		1	
		52		39		26		13		0		51
	51		38		25		12		63		50	

So shifting up right is now possible from every row as it wont overflow to the next row.

[Rein Halbersma]

I don't know if this is already known, but I found that using this bit layout has some nice properties.

Code: Select all

		49		36		23		10		61
	48		35		22		9		60	
		34		21		8		59		46
	33		20		7		58		45	
		19		6		57		44		31
	18		5		56		43		30	
		4		55		42		29		16
	3		54		41		28		15	
		53		40		27		14		1
	52		39		26		13		0	

With 64 bit, it is always rotate 1 or rotate 14 bits.

Furthermore, all the unused bits lay arround the board

Code: Select all

		63		50		37		24		11		62
	62		49		36		23		10		61	
		48		35		22		9		60		47
	47		34		21		8		59		46	
		33		20		7		58		45		32
	32		19		6		57		44		31	
		18		5		56		43		30		17
	17		4		55		42		29		16	
		3		54		41		28		15		2
	2		53		40		27		14		1	
		52		39		26		13		0		51
	51		38		25		12		63		50	

So shifting up right is now possible from every row as it wont overflow to the next row.

Very interesting! It reminds me of http://www.3dkingdoms.com/checkers/bitboards.htm#A1
We have been discussing bitboards for quite a bit on this forum, see. e.g. http://www.laatste.info/bb3/viewtopic.p ... &start=180, but your design never came up.
The overflow property is nice to have, because it means that you can always shift back after you slide of the board. However, the rotate instruction is a bit more expensive than the shift instruction, or do you have access to machines with native rotate instructions?
Are you the author of an international draughts engine by any chance?

[Pemrograman]

This design was inspired by that bitboard tutorial. In a spreadsheet I tried different values for left and right rotating, and found that 1 and 14 worked very nice. I had not read about the ghost square bitboard, and I probably would not have tried this approach if I had known about it. I'm not completely sure if this design offers any advantage? Also, the mscv compiler listed the rotr as an intrinsic and the tutorial mentioned that rotating was nice, so I never even though about a possible speed penalty. It sure is better dan odd and even row, left and right control flow statements.

ALso, after writing just 1000 sloc and not even implementing the king moves, I would not call myself an author of any program just yet. After writing a simple connect-four engine I wanted to experiment with more alpha beta search enhancements. Chess would probably deny me any creativity in designing a move generator. Most of the generators use magic bitboards, but that would just lead to blindly copying what others invented.

So dammen seemed a good alternative to start experimenting on. I thought I could mannage to come up with a acceptable move generator on my own. A bit stuck on a nice king move generator though.

TLDR: I would like to try and build an checkers engine and in the process I found this bitboard representation because I did not know of the ghost squares but did find this alternative.

Ow, and I dont even play checkers. (I had to google for the registration anwer. )

[Rein Halbersma]

This design was inspired by that bitboard tutorial. In a spreadsheet I tried different values for left and right rotating, and found that 1 and 14 worked very nice. I had not read about the ghost square bitboard, and I probably would not have tried this approach if I had known about it. I'm not completely sure if this design offers any advantage? Also, the mscv compiler listed the rotr as an intrinsic and the tutorial mentioned that rotating was nice, so I never even though about a possible speed penalty. It sure is better dan odd and even row, left and right control flow statements.

ALso, after writing just 1000 sloc and not even implementing the king moves, I would not call myself an author of any program just yet. After writing a simple connect-four engine I wanted to experiment with more alpha beta search enhancements. Chess would probably deny me any creativity in designing a move generator. Most of the generators use magic bitboards, but that would just lead to blindly copying what others invented.

So dammen seemed a good alternative to start experimenting on. I thought I could mannage to come up with a acceptable move generator on my own. A bit stuck on a nice king move generator though.

TLDR: I would like to try and build an checkers engine and in the process I found this bitboard representation because I did not know of the ghost squares but did find this alternative.

Ow, and I dont even play checkers. (I had to google for the registration anwer. )

The "ghost" squares that most people here use also eliminate the Left/Rigth special code, as well as edge-detection. As I said, your complete extra ghost "ring" also around the bottom and top of the board is very nice. I remember that I had once a bug in my capture generation where after landing after the final piece I let it slide until it dropped of the board, and then tried to slide it backwards to find the destination square. With your layout that would actually work.

Now that I think of it, "our" ghost layout here is using the board as a cylinder, so that you can share the ghost column on the left and right edge, whereas your layout uses the board as a torus so that also the bottom and top edges are connected.

Well you certainly made one orginal contribution already! Once you finish the move generator, also make sure to verify it with perft() counts. There are a large number of threads on this topic here, both for correctness and for speed comparisons.

[Pemrograman]

But if you offset the cylinder with a row of ghosts, wouldn't that lead to a donut with wrangled seams and achieving the same goal? It would require the rotate instruction though.

Code: Select all

[57][58][59][60][61][62]
[63]  00, 01, 02, 03, 04,
    05, 06, 07, 08, 09, [10]
[10]  11, 12, 13, 14, 15,
    16, 17, 18, 19, 20, [21]
[21]  22, 23, 24, 25, 26,
    27, 28, 29, 30, 31, [32]
[32]  33, 34, 35, 36, 37,
    38, 39, 40, 41, 42, [43]
[43]  44, 45, 46, 47, 48,
    49, 50, 51, 52, 53, [54] 
[55][56][57][58][59][60]

I shift my empty squares towards my targets however, so that I don't need to calculate the from position.

[Rein Halbersma]

But if you offset the cylinder with a row of ghosts, wouldn't that lead to a donut with wrangled seams and achieving the same goal? It would require the rotate instruction though.

Code: Select all

[57][58][59][60][61][62]
[63]  00, 01, 02, 03, 04,
    05, 06, 07, 08, 09, [10]
[10]  11, 12, 13, 14, 15,
    16, 17, 18, 19, 20, [21]
[21]  22, 23, 24, 25, 26,
    27, 28, 29, 30, 31, [32]
[32]  33, 34, 35, 36, 37,
    38, 39, 40, 41, 42, [43]
[43]  44, 45, 46, 47, 48,
    49, 50, 51, 52, 53, [54] 
[55][56][57][58][59][60]

I shift my empty squares towards my targets however, so that I don't need to calculate the from position.

We never thought of bitwise rotate, only bitwise shift, and then 64 bits are not enough to wrap all 4 edges
Main reason why bitwise rotate is not so much used is that C++ does not have a builtin operator for it. Do you perhaps program in Java?

[Pemrograman]

[...]

We never thought of bitwise rotate, only bitwise shift, and then 64 bits are not enough to wrap all 4 edges
Main reason why bitwise rotate is not so much used is that C++ does not have a builtin operator for it. Do you perhaps program in Java?

C++, I use the vs2012 compiler intrinsics for those functions. I believed it to be already common practice for bitscan and popcount, so I also use it to rotate.

[TAILLE]

Code: Select all

		49		36		23		10		61
	48		35		22		9		60	
		34		21		8		59		46
	33		20		7		58		45	
		19		6		57		44		31
	18		5		56		43		30	
		4		55		42		29		16
	3		54		41		28		15	
		53		40		27		14		1
	52		39		26		13		0	

Hi,
This coding is interesting for a move generator, but I can see some difficulties for the egdb generation: do you have a "magic" function in order to find the most advanced man (for white and for black) ?

[Rein Halbersma]

But if you offset the cylinder with a row of ghosts, wouldn't that lead to a donut with wrangled seams and achieving the same goal? It would require the rotate instruction though.

Code: Select all

   [58][59][60][61][62][63]
 [63] 00, 01, 02, 03, 04,
    05, 06, 07, 08, 09,[10]
 [10] 11, 12, 13, 14, 15,
    16, 17, 18, 19, 20,[21]
 [21] 22, 23, 24, 25, 26,
    27, 28, 29, 30, 31,[32]
 [32] 33, 34, 35, 36, 37,
    38, 39, 40, 41, 42,[43]
 [43] 44, 45, 46, 47, 48,
    49, 50, 51, 52, 53,[54] 
 [54][55][56][57][58][59]

I shift my empty squares towards my targets however, so that I don't need to calculate the from position.

Small correction in square numbers for future reference.