New board layouts / square numberings

[Rein Halbersma]

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 single-step diagonal moves.

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    

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 single-step 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.

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    

Bitboard programs only need to worry about left/right edge effects since the top/bottom edges are taken care of by C++ unsigned integer bit-shifting behavior. Array-based 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 array-based 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

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    

Another very nice layout for array-based 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 so-called "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
   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    

[Rein Halbersma]

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. Pre-computing bit masks can then be done with simple for-loops 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 51-square or 49-square boards allow a winning 3 vs 1 all kings endgame. So my lesson is that generalization is hard but pays off in unexpected ways

[Rein Halbersma]

Another exotic board layout! Here's the 10x10 board embedded into a 29x10 grid:

Code: Select all

       5       6       7       8       9
  19      20      21      22      23    
      34      35      36      37      38
  48      49      50      51      52    
      63      64      65      66      67
  77      78      79      80      81    
      92      93      94      95      96
 106     107     108     109     110    
     121     122     123     124     125
 135     136     137     138     139    

Why on earth would this be useful? Well, it allows for a cylinder geometry. On the left there is a 9x10 hidden board and on the right there is a hidden 10x10 board. Instead of ghost squares, you can put 2 copies of the 9 left-most and right-most columns of the actual board into these extra squares. This way, you can move from square 46 (bit 135 in the above diagram) left-upward to square 45 (bit 125). Similarly, you can move from square 5 (bit 9) right-downward to square 6 (bit 19). You can check for yourself that all other square connections are also enabled by this enlarged board.

With these two hidden board copies, you can detect moves that wrap around the board. There are two performance drawbacks: the board is 145 bits (29x10 divided by 2) which requires three 64-bit words and when making a move, one has to update the board also in the hidden copies (or copy them back after updating the visible board squares).

For a general WxH board, (W even), you can make a (3W-1) x H bitboard layout, and put the (W-1) right-most columns on the left, and the entire board on the right (or vice versa). This ensures that you can play draughts on a cylinder geometry.