Canonical Position Representation

[hgm]

The Bishop problem is nasty, as the total number of Bishop states is really 32*32 + 64 + 1, which overflows what 10 bits can do by a few percent. It would be a waste to use a full bit to cover such a small number of overflowing states. But it doesn't seem easy to hide this information in encodings for other traits, as the matter whether you have a Bishop pair or not seems mostly independent from the matter of whether you can have super-numerary Knights or Queens. If we do encode the Bishops constellation with 11 bits, the decoding will not be completely trivial. One bit could indicate whether the other 10 bits should be interpreted as 5 for the light plus 5 for the dark square, or as 10 bits for a single square (possibly equal to the King location if there are no Bishops at all). But it might be better to just assign each pair constellation a number, and decode the two actual locations from a LUT using the 11-bit code as index. For uniformity the Knights and Bishops could both use that same system, so you would now also save one bit on the exchange symmetry of the Knights. Unfortunately I did not see a way to describe Rook locations + castling rights in 11 bits. In the presence of Kings two Rooks can have 62*61/2 = 1891 constellations. In addition you have 62 for a single Rook, 1 for no Rooks, 1 for KQ castling, and 62 for K and Q castling each, in total 2078 > 2048. In theory it would still be possible if you involve the King, because any Rook having castling rights implies the King location. But it is not easy to cash on that if coinciding with a King is used to indicate whether there are castling rights in the first place.

It might work if we indicate capture by coinciding with the enemy King, so that coinciding with the own King can be used to indicate castling rights. Then the pair code for the Rook could be decoded through the LUT into two Rook locations (64*63/2 codes), or directly provide the information that there are no Rooks, or they can both castle (2 more codes). If only one of the Rooks can castle, the pair decoding will have resulted in that Rook being in a corner, and we can artificially put the King on top of it. This will then be detected as having castling rights for only that Rook, after which we correct the King to its true location on the e-file. After both Kings are corrected to their true location, we can use the coincidence test with the enmy King to determine if one of the Rooks is captured.

This is a bit awkward, especially since you have to decode opponent Rooks before you can determine where his King is, and thus know your own captured pieces. You could of course also adopt the convention that you indicate your own captured pieces by coincidence with the artificially displaced King, then you would not have to do that. (It is still an invalid square for your own pieces, as it must contain an enemy Rook.) Downside is that you would have to update the location of all your captured pieces when the opponent loses the castling right, so that the artificial displacement is undone. But this is a general problem withdrawback of this scheme: every time the King moves, all locations of the pieces that hide underneath it must be updated as well. (My EGT generator works this way...)

Anyway, we now save 1 bit on R, B, N each, so 6 in total. But decoding has become a bit more complex.

[hgm]

I suppose we could reserve indices 1 and 2 to the bishops, which would further limit our supernumerary options.

In any case, this is seemingly becoming less and less practical. Now, how about 208 bits? If we added just an extra octet per side, we'd get a much simpler and more practical encoding. How bad could that be (e.g. cache utilisation-wise)?

Well, I am still not sure why it would be any help at all to use a "dense" piece list, rather than a more structured one. Just leave extra entries for all super-numerary pieces you could have. In Joker the leaper section and slider section are stacks that grow towards each other, and initially there are 8 empty entries between them, so that super-numerary pieces can either grow one or the other. Perhaps compactness is an advantage if you plan to do a lot of copy-make on it, but even then it is only a minor cost, easily offset by need for complex decoding. (OTOH, if the complex decoding is only needed in the super-numerary case, who cares? This is all "never happens" stuff.)

There is a lot to discuss about what would make the fastest engine design, but details of the piece list like this would probably not contribute anything significant compared to other design choices one could make.

[leanchess]

This is a bit awkward, especially since you have to decode opponent Rooks before you can determine where his King is, and thus know your own captured pieces. You could of course also adopt the convention that you indicate your own captured pieces by coincidence with the artificially displaced King, then you would not have to do that. (It is still an invalid square for your own pieces, as it must contain an enemy Rook.) Downside is that you would have to update the location of all your captured pieces when the opponent loses the castling right, so that the artificial displacement is undone. But this is a general problem withdrawback of this scheme: every time the King moves, all locations of the pieces that hide underneath it must be updated as well. (My EGT generator works this way...)

Anyway, we now save 1 bit on R, B, N each, so 6 in total. But decoding has become a bit more complex.

Suppose we use 11 bits for every pair of bishops, knights and pawns. We encode castling rights within the rooks and e.p. within the pawns, as you had proposed originally. That frees up 12 bits.

Now, for the sake of simplicity, let's use 1 bit per side for color. This still leaves us 5 bits, which are more than enough to encode any reasonable combination of supernumerary pieces.

[leanchess]

Correction: not any combination, of course, since they must come in pairs. So we go back to two 6-bit locations for the first two pawns, which could be promoted to anything, and use the remaining 4 bits to encode whether and to what they are promoted.

[hgm]

Nice idea to also do the pawns in pairs. I guess you could even do a pair of adjacent pawns with 10 bits, because there are many squares of the 48 that they cannot reach, and at most one of them can carry e.p. rights. But then you would need different decoding tables for each pawn pair.

There still is one problem: the pair code assumes indistinguishable pieces. So you cannot use a pair code for encoding the location of a pawn and a queen; you get two squares, but you don't know which of the two contains the queen. I guess the super-numerary pieces only have to be indicated in pairs, though, as one you needed only one, you could just remove one of the normal pieces. So you could use one of the spare bits for each pair to indicate whether it is pawns or something else, where each pair has its own 'something else'. This has the disadvantage that you could not have the maximum number of pawns when you have super-numerary pieces, though.

An 11-bit pawn code could also either encode for no pawns (1), a single one (48) or a pair (48*47/2), without or with (8*45 + 8) e.p. rights (total 1545), or a single N, B, R or Q (4*64). That would still force you to delete an extra pawn for a super-numerary piece. But it wouldn't need any extra bits to indicate what super-numerary pieces you have. You could then try to use the spare bits for an additional pawn. That would work for one color, but not for both. The 11 spare bits are enough to encode another pair of pawns, though. But not if there are two of different color. The basic pairs still have a lot of codes left to provide some extra info, though. I would have to think if something can be done with that.

[edit] your last posting crossed mine. And yes, what you propose also seems a good solution.

[hgm]

This morning I had the following idea:

The 11 spare bits we have when we encode all Pawns, Knights and Bishops as pairs can be split in two fields of 6 and 5 bits, (spare1 and spare2) respectively. With the convention that last rank should be interpreted as e.p. rights and first rank as captured, the Pawn pairs can use the same decoding tables as the other pieces. But this leaves many codes unused: those where both Pawns carry e.p. rights (28), while we can limit the 'captured' code to a1, leaving 7*56 codes unused. And only a single code is needed to indicate 'no Pawns', leaving the other 27 codes with both on the back-rank unused.

These unused codes could be re-purposed as follows: 4 x 64 codes could be used to indicate we are dealing with a single super-numerary piece (N, B, R, or Q) instead of the Pawn pair. And 4 x 56 codes could describe only a single Pawn, but at the same time indicate that the location of a super-numerary piece is 'outsourced' to spare1 or spare2. Unfortunately spare2 is one bit short, so to use that the pair code would have to indicate which half of the board the super-numerary piece is on. We have four Pawn pairs, and the meaning could depend on the Pwn pair where the code occurs. E.g. for one it could mean N1, B1, R1 or Q1 (i.e. spare1 indicates location of the indicated piece), for the second N2L, N2R, B2L, B2L (spare 2 contains location of the indicated piece within the indicated board half), for the third R2L, R2R, Q2L, Q2R (idem), and for the fourth it could remain unused.

This makes it possible to always add two independent super-numerary pieces of any type and color without loss of pawns (other than those that must have promoted). In addition to that two other super-numerary pieces of any type can be added per player, but each such piece would go at the expense of a Pawn of the same color. So you can do 5 Queens vs 5 Queens, but only if both players do not have more than 2 Pawns.

[leanchess]

Nice idea. I'd suggest keeping it symmetrical, i.e. 1 bit for color on both sides, two 5-bit spares and 16 half-board codes.

I was thinking in a different direction - namely, making incremental updates less painful. Since supernumerary pieces seem more of a curiosity, two slots should suffice for all practical purposes. Instead, we could use some extra bits to encode NRBQ counts, so a king move would only require updating the rooks (and only once per side).

My idea was to replace the three pairs of pawns with two triplets. I don't have the numbers (my combinatoric skills are far inferior to yours), but those should be more than enough. Now, if we place the second disjoint pawn after the second triplet, sorting the pawns becomes easier. White pawns could be sorted in reverse order (as opposed to black ones) so the first pawn to promote would have a high probability to occupy slot 8, right next to the queen (or its empty slot, which it would then take).

P.S. Both triplets could also be re-purposed for supernumerary pieces (at least for queens).

[hgm]

Pawn triplets can be encoded in 15 bits. So that saves 2 x 2 = 4 more bits. I did not want to propose it, because I was afraid the decoding tables would become too large for comfort (96KB).

[leanchess]

Ordered pawns would require less codes (and, hopefully, even less bits). In the proposed arrangement the first triplet would never host the h-pawn and the second one would never host the a-pawn, so the first one in every triplet would only need 7 e.p. codes, for example. That way the tables get smaller, but the decoded values require adjustment for the second triplet (I believe a simple XOR would do the trick).

P.S. There is also the vertical symmetry, so only one table (and two XORs in the worst case) is needed.

[hgm]

It occurred to me that pairs can be encoded such that the individual locations are easy to derive by calculation rather than tabe lookup. You can encode them such that the 6 lowest bits are the square number of the first piece, while the second can be calculated from the other 5 bits as

sqr1 = pairCode & 63;
sqr2 = pairCode >> 5 & 62; // an even number
sqr2 += sqr1 & 1;
sqr2 += (sqr2 >= sqr1);

The idea here is that you can think of a pair constellation as a cell in a 64 x 64 matrix, and you want to assign a unique number to every cell in the triangle below the main diagonal. The constellations that contain a certain square can be traversed by first moving up along the corresponding column until you reach the main diagonal, and from there horizontally to the right. Such paths for different squares will always intersect each other in one cell, so each cell lies on two such paths. Now think of the matrix as checkered, and only take the dark cells on the leg moving up to the diagonal, and the light cells on the horizontal leg, and number them (in the 5 high-order bits) in that order. No cell will be counted double, as the 'dashed' vertical legs only visit dark cells, and the horizontal legs light cells. The light cells can be mirrored w.r.t. the diagonal to the upper triangle (such mirroring preserves shade), to straighten out the dashed paths. For a given sqr1, the 5 remaining bits then have to count in steps of 2 to stay on the dark shade, and start at 1 (rather than 0) for the odd columns (which is done by adding sqr1 & 1). As soon as you cross the diagonal (sqr2 >= sqr1) you have to skip to the light shade, by adding 1 more (and avoiding you ever count the cell on the diagonal itself).

I don't know if a similar trick exists for triples.