New board layouts / square numberings

 Posts: 1666
 Joined: Wed Apr 14, 2004 16:04
 Contact:
New board layouts / square numberings
In my new Tabula library (https://github.com/rhalbersma/tabula) that I am developing (not yet ready for primetime), I have been experimenting with new board layouts / square numberings. Here's the classic layout for a 10x10 draughts board by using 1 ghost column (also called "separating squares" or "guard band" by other board game programmers). This is equivalent to embedding the 10x10 board into a 11x10 board. Just as a reminder, 1 ghost column eliminates odd/even rows and also guards against edge detection for singlestep diagonal moves.
Below a slightly less familiar bit layout, one that I first described here over 10 years ago: http://laatste.info/bb3/viewtopic.php?t=1925&start=249. It uses 3 ghost columns by embedding a 10x10 board into a 13x10 board. This continues to eliminate odd/even rows and now also guards against singlestep orthogonal moves (and not just diagonal moves). I use it for edge detection in Frisian draughts (which has orthogonal captures). Amazingly, this same bit layout has als been used since 3 years by Fabien to accommodate Scan's large pattern indexing.
Bitboard programs only need to worry about left/right edge effects since the top/bottom edges are taken care of by C++ unsigned integer bitshifting behavior. Arraybased programs also have to do edge detection at the top and bottom of the board. The easiest way to this is to embed a 10x10 board into a 11x12 board (with ghost columns on the top, right and bottom). This results in the following board layout (there are 66 squares in total, but square 0...5 and 60..65 are not shown). Fabien used this in his old arraybased program and also in Scan 2 (correct me if I'm wrong!). In chess, this layout is similar in spirit as the classic "mailbox" 10x12 board layout: https://www.chessprogramming.org/10x12_Board
Another very nice layout for arraybased programs is embedding the 10x10 board into a 19x10 board with 9 ghost columns. The square numbering then looks like this. In chess, this layout is supportive of socalled "vector attacks": https://www.chessprogramming.org/Vector_Attacks. What special property does this 19x10 board have? Well, the 9 ghost columns mean that there are 95 internal squares (only the range 0...89 is required for bitboards) and square 94 is on a diagonal with square 4. It turns out that such a large board (and also even larger boards) have the property that all square differences have a unique direction. This means that if you want to know if there is a legal moves between two squares (or the distance between them), that you don't need to have a 50x50 lookup table, but only a much smaller table of size 179 (the range 89...0...+89 of all possible square differences). I don't know anyone using this layout, and I haven't had any experience with it myself. Incidentally, the 19x10 board is also a board in which 3 kings beat 1 king, for roughly the same reason (square 4 looking at two single corners at squares 85 and 94).
Code: Select all
0 1 2 3 4
5 6 7 8 9
11 12 13 14 15
16 17 18 19 20
22 23 24 25 26
27 28 29 30 31
33 34 35 36 37
38 39 40 41 42
44 45 46 47 48
49 50 51 52 53
Code: Select all
0 1 2 3 4
6 7 8 9 10
13 14 15 16 17
19 20 21 22 23
26 27 28 29 30
32 33 34 35 36
39 40 41 42 43
45 46 47 48 49
52 53 54 55 56
58 59 60 61 62
Code: Select all
6 7 8 9 10
11 12 13 14 15
17 18 19 20 21
22 23 24 25 26
28 29 30 31 32
33 34 35 36 37
39 40 41 42 43
44 45 46 47 48
50 51 52 53 54
55 56 57 58 59
Code: Select all
0 1 2 3 4
9 10 11 12 13
19 20 21 22 23
28 29 30 31 32
38 39 40 41 42
47 48 49 50 51
57 58 59 60 61
66 67 68 69 70
76 77 78 79 80
85 86 87 88 89

 Posts: 1666
 Joined: Wed Apr 14, 2004 16:04
 Contact:
Re: New board layouts / square numberings
So a few more remarks on this topic. First of all, I would like to thank Fabien for a more than 3 year long discussion (on and off, every time either one of us would get back to it, as we developed new insights and expanded into new territory (patterns, Frisian, Stratego) that demanded slightly more general layouts).
There are a few key insights: draughts is a very special beast among board games because of the chequered nature of the board. In the past, I did an insane amount of arithmetic gymnastics to get the board geometry correct. It turns out that the easiest way is to just use Cartesian XY coordinates when determining square numberings and base all computation on these file/rank coordinates. Precomputing bit masks can then be done with simple forloops or table based lookups. During game play, none of this is ever required of course.
To squeeze out every last bit (pun intended) out of square numberings and board layouts, it can be necessary to internally transform a board to align the ghost columns along the smallest board dimension. E.g., in the somewhat exotic 10x12 board, to be able to fit it into 64 bits, it is required to use the ghost squares along the top/bottom instead of the left/right because the board's width is smaller than its height. In the past I limited myself to rotations but Fabien was the one to point out that you also need parity reversing transformations. This was a small win that generalized to other boards as well.
Finally, since I started with Stratego (which has 2 "lakes" in the middle of the board, across which pieces cannot move), I also added the functionality to exclude certain squares from a board. This allows irregularly shaped draughts boards. E.g. it has been known since 1935 that adding a square next to square 5 of the 10x10 board, and also by removing square 5 altogether, that such 51square or 49square boards allow a winning 3 vs 1 all kings endgame. So my lesson is that generalization is hard but pays off in unexpected ways
There are a few key insights: draughts is a very special beast among board games because of the chequered nature of the board. In the past, I did an insane amount of arithmetic gymnastics to get the board geometry correct. It turns out that the easiest way is to just use Cartesian XY coordinates when determining square numberings and base all computation on these file/rank coordinates. Precomputing bit masks can then be done with simple forloops or table based lookups. During game play, none of this is ever required of course.
To squeeze out every last bit (pun intended) out of square numberings and board layouts, it can be necessary to internally transform a board to align the ghost columns along the smallest board dimension. E.g., in the somewhat exotic 10x12 board, to be able to fit it into 64 bits, it is required to use the ghost squares along the top/bottom instead of the left/right because the board's width is smaller than its height. In the past I limited myself to rotations but Fabien was the one to point out that you also need parity reversing transformations. This was a small win that generalized to other boards as well.
Finally, since I started with Stratego (which has 2 "lakes" in the middle of the board, across which pieces cannot move), I also added the functionality to exclude certain squares from a board. This allows irregularly shaped draughts boards. E.g. it has been known since 1935 that adding a square next to square 5 of the 10x10 board, and also by removing square 5 altogether, that such 51square or 49square boards allow a winning 3 vs 1 all kings endgame. So my lesson is that generalization is hard but pays off in unexpected ways