Classes of chess pieces for chess variants

[hgm]

Progress is a bit slow, because one day was lost shopping for furniture, and another on an out-of-town funeral. But I did make some progress now.

For one, I made a version of Fairy-Max that implements the 'highlight protocol'. Through this it can instruct the WinBoard GUI on what the legal moves of a 'picked up' piece are, overruling WinBoard's own notion of how the pieces move. On the CirSquare board this will be a necessity.

I think I succeeded in stipulating all possible orthogonal and diagonal slider trajectories, respecting the 'two-castle-walls rule. I then made a routine to derive Knight moves from the orthogonal table. Perhaps you can have a look at the following table, which for each square lists the (up to 8) possible squares a Knight could go to from there:

Code: Select all

   0:   1:   2:   3:   4:   5:   6:   7:   8:   9:  10:  11:
   36    0    0    0   22   23   26   74    0    0    0   73
   21    0    0    0   65   17   20   21    0    0    0   90
   66    0    0    0   37   38   39   41    0    0    0   39
   81    0    0    0   34   36   37   38    0    0    0   22
   51    0    0    0    0    0    0    0    0    0    0   56
    0    0    0    0    0    0    0    0    0    0    0    0
    0    0    0    0    0    0    0    0    0    0    0    0
    0    0    0    0    0    0    0    0    0    0    0    0

  16:  17:  18:  19:  20:  21:  22:  23:  24:  25:  26:  27:
    0   52    0    0   38   39   41   73    0    0   72    0
    0   37    0    0   66   34   36   37    0    0   91    0
    0    5    0    0   53   54   55   56    0    0   89    0
    0   67    0    0   51   52   53   54    0    0   55    0
    0   82    0    0    6    7   11   75    0    0   38    0
    0   80    0    0   64    0    4    5    0    0    6    0
    0    0    0    0    0    0    0    0    0    0    0    0
    0    0    0    0    0    0    0    0    0    0    0    0

  32:  33:  34:  35:  36:  37:  38:  39:  40:  41:  42:  43:
    0    0   68    0   54   55   56   53    0   75    0    0
    0    0    4    0   69   51   52   72    0   71    0    0
    0    0   53    0   67   70   71   70    0   90    0    0
    0    0   21    0   22   68   69   74    0   88    0    0
    0    0   64    0   65   23   26   21    0    7    0    0
    0    0   83    0    5   17   20   11    0   54    0    0
    0    0   81    0    0    6    7    6    0   22    0    0
    0    0    0    0    0    4    5    0    0    0    0    0

  48:  49:  50:  51:  52:  53:  54:  55:  56:  57:  58:  59:
    0    0    0   84   70   71   72   73   89    0    0    0
    0    0    0   20   66   67   68   69   38    0    0    0
    0    0    0   69   85   86   87   88   74    0    0    0
    0    0    0   37   83   84   85   86   23    0    0    0
    0    0    0   65   38   39   41   37   87    0    0    0
    0    0    0   82   21   34   36   26   70    0    0    0
    0    0    0    0   17   22   23   22    0    0    0    0
    0    0    0    0    0   20   21    0    0    0    0    0

  64:  65:  66:  67:  68:  69:  70:  71:  72:  73:  74:  75:
   97   98   99  100   86   87   88   89  105  106  107  106
   20   36   84   36   82   83   84   85   39   23    7   23
   82   83   52   85  101  102  103  104   90   91  105   89
   34   51   97   53   99  100  101  102   26   11   39   41
    0   96   20   98   54   55   56   53  103  104   88    0
    0    4   80   81   37   51   52   41   86   87   56    0
    0    0    0   17   34   38   39   38   54   55    0    0
    0    0    0    0    0   36   37    0    0    0    0    0

  80:  81:  82:  83:  84:  85:  86:  87:  88:  89:  90:  91:
  113  114  115  116  102  103  104  105  121  122  123  122
   17   34   51   52   98   99  100  101   41   26   11   26
   98   99  100  101  117  118  119  120  106  107  121  105
   66   67   68   69  115  116  117  118   74   75   41   73
    0  112  113  114   70   71   72   73  119  120  104    0
    0    0   17   34   66   67   68   69   55   56   72    0
    0    0   96   97   53   54   55   56  102  103    0    0
    0    0   64   65   51   52   53   54   70   71    0    0

  96:  97:  98:  99: 100: 101: 102: 103: 104: 105: 106: 107:
  161  146  131  132  118  119  120  121  153  170  187  170
   65   66   67   68  114  115  116  117   73   74   75   74
  114  115  116  117  133  134  135  136  122  123  153  121
   82   83   84   85  131  132  133  134   90   91   73   89
    0  176  161  146   86   87   88   89  135  136  120    0
    0   64   65   66   82   83   84   85   71   72   88    0
    0    0  112  113   69   70   71   72  118  119    0    0
    0    0   80   81   67   68   69   70   86   87    0    0

 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123:
  164  148   83  148  134  135  136  133  151  167  183  167
   81   82  132   84  149  131  132  153   89   90   91   90
  146  131  100  133  146  150  151  150  170  187  151  153
   98   99  164  101  102  148  149  105  106  107   89  105
    0  180   81   82   98  103  104  101   87   88  136    0
    0   80  176  161   85   99  100   88  134  135  104    0
    0    0   96   97   83   86   87   86  102  103    0    0
    0    0    0    0    0   84   85    0    0    0    0    0

 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139:
    0    0    0  164  150  151  153  121  105    0    0    0
    0    0    0  100  114  146  148  149  150    0    0    0
    0    0    0  149  165  166  167  170  122    0    0    0
    0    0    0  117  161  164  165  166  167    0    0    0
    0    0    0  113  118  119  120  117  103    0    0    0
    0    0    0   98  101  115  116  104  118    0    0    0
    0    0    0    0   99  102  103  102    0    0    0    0
    0    0    0    0    0  100  101    0    0    0    0    0

 144: 145: 146: 147: 148: 149: 150: 151: 152: 153: 154: 155:
    0    0  180    0  166  167  170  122    0  123    0    0
    0    0  116    0  113  161  164  165    0  119    0    0
    0    0  165    0  181  182  183  187    0  106    0    0
    0    0  133    0  176  180  181  182    0  104    0    0
    0    0  112    0  134  135  136  133    0  183    0    0
    0    0   99    0  117  131  132  120    0  166    0    0
    0    0   97    0  115  118  119  118    0  134    0    0
    0    0    0    0    0  116  117    0    0    0    0    0

 160: 161: 162: 163: 164: 165: 166: 167: 168: 169: 170: 171:
    0  132    0    0  182  183  187  123    0    0  120    0
    0  181    0    0  112  176  180  181    0    0  107    0
    0  149    0    0  150  151  153  121    0    0  105    0
    0  115    0    0  114  146  148  149    0    0  135    0
    0   98    0    0  133  134  135  136    0    0  182    0
    0   96    0    0  131  132  133  134    0    0  150    0
    0    0    0    0    0    0    0    0    0    0    0    0
    0    0    0    0    0    0    0    0    0    0    0    0

 176: 177: 178: 179: 180: 181: 182: 183: 184: 185: 186: 187:
  148    0    0    0  166  167  170  122    0    0    0  121
  165    0    0    0  113  161  164  165    0    0    0  106
  114    0    0    0  149  150  151  153    0    0    0  151
   97    0    0    0  146  148  149  150    0    0    0  166
  131    0    0    0    0    0    0    0    0    0    0  136
    0    0    0    0    0    0    0    0    0    0    0    0
    0    0    0    0    0    0    0    0    0    0    0    0
    0    0    0    0    0    0    0    0    0    0    0    0

[RichV]

HGM, I made a long response to your last post, but when I hit Preview, the system made me log in again and I lost my entire response. It is 1 am and have to go to be bed now. I will recreate my entire response tomorrow. The only problems I initially saw was the Knight moves from spaces 0, 11, 176, and 187. The first 4 moves from each square are good, but the 5th move to a triangular space 51, 56, 131, and 136 appear to be illegal moves. On the my CirSquare board they would be move 3 spaces orthogonally in one direction, for instance from space 0 it move to 17, 34, 51 in a straight line.

I will check the rest of the moves tomorrow. The table appears to be only for a classic Knight, all capture moves. Do you want me to make the table for the 'extended Knight' additional non-capture moves that are one additional orthogonal space?

[hgm]

Ah OK, good catch. There is a spurious 5th move. I now understand why: in my table of trajectories the triangles occur not just as their square number, but get 2048 or 4096 added, to signal that the trajectory forks there. My algorithm for generating Knight moves was to travel 2 steps along one orthogonal trajectory, and then jump onto a perpendicular trajectory there for one more step (or the other way around). The tricky thing is to recognize which two of the four orthogonal trajectories passing through each square are the perpendicular ones, so I do that by trying all four, and rejecting those for which the first step leads to the square of the first trajectory where you just came from, or to the next square on that trajectory. The marking of the triangles as branch points apparently fools this comparison, so that the third step along the first orthogonal is mistakenly though to go in a perpendicular direction to the first two.

This is indeed only for a classical Knight. Once this works I will copy and modify it to generate Camel moves (doing 3+1 and 1+3 steps instead of 2+1 and 1+2). My strategy now is to first create tables for each 'pure' move, i.e. the Rook and Bishop Slides, and the oblique Knight and Camel leaps. These will then be used as basis for creating tables for the actual pieces, which in general will be 'compounds', combining the move lists of several tables. (E.g. Queen = Rook + Bishop, Chancellor = Rook + Knight.) For creating the Pawn tables there must be a separate routine, which must somehow decide which of the orthogonal and diagonal trajectories go 'forward'.

I finally came to the following scheme:

1) There will be a table that contains all trajectories written behind each other, where each trajectory is a -1 terminated list of square numbers. For leapers only the first square along a trajectory would be used, and when there is no 'rider' equivalent of this move in the game, the trajectories degenerate to a single square, and the -1 terminator can be omitted. The first 187 elements of the trajectory table will thus just contain the numbers 0-187 in increasing order, to act as single-step trajectories. The longer orthogonal and diagonal trajectories will be packed behind that.

2) Squares where trajectories fork will be indicated in the trajectory table by adding 2048 or 4096 (i.e. setting a single bit in their binary representation, which can be easily tested for by an engine trying to step along the trajectory). Two different cases were needed: in most cases (indicated by the 2048 bit) the main trajectory continues fo 4 more steps to one of the four 'corners' (0, 11, 176, 187) after which a terminating -1 is encountered (if they are not blocked earlier), after which the other leg of the fork commences. Orthogonal trajectories that start at a corner towards a triangle are more complex, though: the two legs from the first triangle are both much longer than 4 steps, and both visit more triangles where they fork again. So they are considered higher-order forks, which must get different treatment in the move generator, and are indicated by the 4096 bit.

3) There will be a table containing 'move lists'. A move list will be a 0-terminated list of numbers, where each number is an index in the trajectory table, indicating where in the latter table the first destination along the trajectory for that move can be found. Roughly speaking each element in a move list will correspond with a certain direction (starting from a given square) in which a piece can move, sliding or leaping. There must be a separate move list for every piece type on every square, and they will all be stored behind each other in the move-list table.

4) The higher-order bits of the numbers in the move lists will not be needed to record the start of the corresponding trajectory, as the trajectory table will only contain a few thousand elements. So they will be used to store the 'move rights' flags that Fairy-Max uses for indicating what the move can do (capture, non-capture, slide/leap, hop, range). Each direction thus has its own set of move rights, so that compounds of various move types can be easily made. (E.g. Chancellor slides in orthogonal directions, but leaps in hippogonal ones).

5) A two-dimensional table indexed by piece type and square number will indicate where the (first element of the) move list for that piece starting from the given square can be found in the move-list table. This would be the first thing looked up during move generation, once a piece of the side-to-move is found on a square.

[RichV]

HGM, Being very much a visual learner, I created a graphic of the 12x12 portion of the 16x16 for Fairy-Max with all the squares annotated. Then I transferred the square numbers to my CirSquare 96 board, which helps see the actual moves on my board relative to the 12x12. I just posted the new page on my CastleStrife.com website. The link to the specific page is:

http://castlestrife.com/08_csg_story_08_23_p23.html

For some reason the images are not displaying yet, but the links to open the images do work. Please verify that I have the numbering scheme correctly positioned on the 12xx12.

I have spent so much time creating and printing the drawings that I am just now starting to verify the rest of the Knight moves. This is exciting and fun.

Thank you so much for taking on the Thrones Chess II programming challenge.

[RichV]

HGM, In your table, it is difficult to know when a 0 means square 0 or a non-move. Should the non-move zeros actually be blank--no number at all?
How will Fairy-Max tell the difference between a 0 move and a non--move?

I am just over half way checking the Knight moves, and they all check out good so far, except for those noted earlier that you are fixing. I will continue checking after supper.

This time I was smart enough to copy my post content before clicking Preview. It again made me log back in and erased my message. Is there any warning that I need to log back in before clicking Preview or Submit?

[Ovyron]

When you Log In there's a checkbox that says "Remember me", ticking it is supposed to avoid being logged out.

Also, after logging in, it's possible clicking back in your Browser a few times will recover your message.

[RichV]

HGM, I finished checking all the rest of the Knight moves by using the CirSquare board numbered with 12x12 numbers. They all checked out good. So the only 4 that needed attention were the 4 that referenced a triangular space as a move.

The CirSquare board with the 121x12 numbers makes it very easy for me to follow the moves. I think it will be the best for you to reference when following moves through the triangles and across the castle walls and a King in check next to a castle wall.

The rule for moving through a triangle is: A piece that enters a triangular space across a corner can exit the triangle across either of the other two corners; and, a piece that enters a triangular space across a side can exit the triangle across either of the other two sides. This is true as long as the piece abides by the castle wall crossings rule--on a single move, a piece can have a maximum of two castle wall crossings.

An example of a Bishop move that goes through a triangular space(s) is from space 36. It has 5 possible move paths (use the numbered CirSquare board to follow the moves):

1) 21, 6
2) 17, 64 (1 castle wall crossing)
3) 53, 70, 87, 104, 121, 170, 183 (2 castle wall crossings)
4) 51, 66, 81, 96 (1 castle wall crossing)
5) 51, 68, 85, 102, 119, 136, 151, 166, 181 (2 castle wall crossings)
6) is not legal due to 3 castle wall crossings: 51, 68, 85, 102, 119, 136, 121, 106, 91. So an opponent's piece can hide from a Bishop that is on space 36, 21, or 6 by hiding on space 121, 106, or 91.

If the Bishop was starting from space 68, 85, 102, or 119 (or 71, 86, 101, or 116), it would have 6 possible move paths and there would not be any spaces behind a wall for an opponent's piece to hide from the Bishop.

A Rook sitting on space 176 would have 7 possible paths for a move:

1) 180, 181, 182, 183, 187, 123, 107, 91, 75, 11, 7, 6, 5, 4, 0 (it cannot continue to space 64 because that would be a 3rd castle wall crossing).
2) 112, 96, 80, 64, 0, 4, 5, 6, 7, 11 (it cannot continue to space 75 because that would be a 3rd wall crossing).
3) 161, 146, 131, 132, 133, 134, 135, 136, 153, 170, 187 (no wall crossings)
4) 161, 146, 131, 132, 133, 134, 135, 136, 120, 104, 88, 72, 56 41 26 11 (2 castle wall crossings)
5) 161, 146, 131, 132, 133, 134, 135, 136, 120, 104, 88, 72, 56 55, 54, 53, 52, 51, (cannot cross the wall to 67--3rd crossing) 34, 17, 0 (2 wall crossings)
6) 161, 146, 131, 115, 99, 83, 67, 51, 34, 17, 0 (2 castle wall crossings)
7) 161, 146, 131, 115, 99, 83, 67, 51, 52, 53, 54, 55, 56, (cannot cross the wall to 72--3rd wall crossing) 41, 26, 11 (2 wall crossings)

Notice that the Rook can get to many squares from multiple directions, which is not possible in classic chess.

If the King is on either side of either wall and is placed in check, the King cannot cross the wall to get out of check, with one exception--to capture the attacking piece if that piece is not protected. (Two chess Masters talked me into the exception.) I don't know if you can do an 'if statement' in your coding of the moves for a King in check. Zillions was not able to do it--at least I could not figure out if it was possible and I could not get any help from Zillions staff. If you can't do it, do not worry about it. Can a piece be deleted from the board during play and dropped in a different position? If so, we can use a note to tell the players to delete the attacking piece and then move the King to the space the attacker was on. That the solution in ZoG. I had to handle castling the same way.

Also, remember that Pawns promote as soon as they cross the opponent's castle wall, which is one rank sooner than classic chess.

Castling is allowed only if the King and Rooks are in the classic chess positions and abide by classic chess rules for castling:
White K on 38 and white Rs on 4 and 7; Black K on 150 and black Rs on 180 and 183.
King side castling is K 39, 23 and R to 39; Queen side castling is K 37, 36 and R to 37.

When not playing with pieces in spaces 5,6, 21,22 and 181, 182, 165, 166, castling is not very useful because the King's backside is open to attack. When playing with extra pieces filling those spaces, the King's backside is more easily protected and castling becomes more useful.

It is getting late again, so I have to go for now. Have a good one.

[RichV]

HGM, Thanks for the logging in tips!

[hgm]

You have to thank Ovyron for that!

The slider moves nearly work, except that when I place a black Rook on one particular triangle (136) the engine crashes as soon as I pick up a white Rook on 0 or 17 for the next move, and I have not figured out yet why. I suspect it has something to do with capturing something that is on a triangle.

I still have to put in Pawn moves, and haven't done any fairy pieces yet.

I hadn't noticed this special rule for King in check. I suppose you added that to make it easier to checkmate a bare King? I will have to write some extra code for that; the only way Fairy-Max can make move legality dependent on check is for castling, where it imagines 'ghost Kings' on the square the King came from and the one it passed through in the reply move. This mechanism will not work here.

The old castling code is still completely broken in the new design, as it expects the Rooks in the wrong locations and calculates the squares passed through instead of looking them up in the table. I guess this can be fixed eventually by adding two bent trajectories to the King moves especially for castling.

The new (table-driven) way the move generator works breaks the old method Fairy-Max used to implement bent trajectories, which was done by changing direction of the step at some point. The concept that replaces that would be to jump from one tabulated trajectory onto another, but 'direction' is not a well-defined concept on the cirsquare board, and I couldn't think of a general way to determine which of the four (say) diagonal trajectories you would have to switch to when you want to bend 45 degrees from an orthogonal trajectory. On the upside, in the initialization phase you could tabulate completely arbitrary trajectories (such as the Rose or the Crooked Bishop). So it only hurts when you would have trajectories that bend in an unpredictable place (e.g. when hopping over an obstacle).

[RichV]

HGM, I did not like my original rendition of your Fairy-Max 12x12 board because of my use of red squares to indicate squares that are not used by the CirSquare board. I went back to the idea of your original drawing of the 12x12. So I switched to using 'X's over the numbers for the unused squares and making their backgrounds match the squares that are used. Now mine looks a lot better than it did. I replaced it on my website (the images still do not display on the page, but the links will display them):

http://castlestrife.com/08_csg_story_08_23_p23.html

Trying to make my circular board work in most chess engines has to be something like trying to force a round peg into a smaller size square hole. I would be totally lost in doing what you are doing in Fairy-Max. But it sounds like you are making good progress.

In a game, can pieces be deleted and others dropped on the board? If yes, then castling can be explained as a manual maneuver., and so can the idea of a King in check next to a castle wall capturing an unprotected attacker that is on a square on the other side of the castle wall that the King can normally move to. If no, then those 2 rules will not apply when playing the game with Fairy-Max.