Canonical Position Representation

[hgm]

Well, it seems obvious that sqr2 will always be an odd number this way. So you would never be able to encode a position where both pieces are on even squares. Not just n and n+2.

BTW, even without ADC there can exist tricks, because you can often deduce the carry from the result itself, if the magnitude is limited. E.g. (a > b) can be calculated as (b - a & 0x80) >> 7 when a and b are known to not exceed 64.

And yes, piece counts would be a way to encode the Rooks + castling rights as a pair. And pair encoding does have the advantage of being unique, unlike two singles. But it does require extra bits. And those could also be spent in a different way. You would not require complete piece count; just 1 bit to indicate whether the 11-bit code represents a pair or a single/none. But that overloads the pair, and hardly uses the code space in the single/none case.

It could be better to just use a 12-bit code 'uniformly', i.e. without requiring a specific meaning for one of the bits. You could augment the 64 board squares with three 'pseudo-squares', indicating K or Q castling rights and absence, so you don't need to refer to the King squares. This would need 67*66/2 = 2211 codes (and you would still need 1 more for indicating both are absent, as for normal / castling squares you would not allow both squares of the pair to be the same). That is rather inefficient use of the code-space, though.

[Edit] Our last messages crossed, but it seems what you got now is indeed an even better way to do it.

[leanchess]

You would not require complete piece count; just 1 bit to indicate whether the 11-bit code represents a pair or a single/none. But that overloads the pair, and hardly uses the code space in the single/none case.

I love this idea. Let's see what we ended up with.

There are 96 bits per side, each divided into 2 48-bit words. The side to move comes first.

First word:

Code: Select all

  Bits | Contents
-------|----------
   00  | color
   01  | Q-flag
 02-05 | S-code
 06-11 | K
 12-17 | R0
   18  | R-flag
 19-23 | R1
 24-29 | B0
   30  | B-flag
 31-35 | B1
 36-41 | N0
   42  | N-flag
 43-47 | N1

Second word:

Code: Select all

  Bits | Contents
-------|----------
 00-05 | S0
 06-11 | S1
 12-26 | PPP0
 27-41 | PPP1
 42-47 | S2

• Q-flag indicates whether S0 encodes a queen
• S-code indicates the supernumerary piece arrangement
• K-castling rook is placed at own king
• Q-castling rook is placed at opponent's king
• S0 initially encodes the queen, and may encode any NRBQ piece
• S1 initially encodes the a-pawn, and may encode any NRBQ piece
• S2 initially encodes the h-pawn, and may encode any NRBQ piece
• PPP0 initially encodes the b-d-pawns
• PPP1 initially encodes the e-g-pawns
• Pieces take precedence over pawns in S1 and S2
• Pieces are ordered by castling rights, then type, then rank, then file
• Pawns are ordered (S1-PPP0-PPP1-S2) by file, then rank
• Captured pawns in S1 and in PPP0 are placed at h1/h8 for whites/blacks respectively
• Captured pawns in S2 and in PPP1 are placed at a1/h1 for whites/blacks respectively
• En passant is encoded as a1-h1/a8-h8 for whites/blacks respectively

Edit: Placing a pair's flag between the two pieces allows to calculate all three sqr2's in parallel with a single ADD.

[leanchess]

On a second thought, placing the pair's flag there wouldn't help; let's keep it as the MSB.

Parallel computation of RBN coordinates:

Code: Select all

s1 = w1 >> 12 & 0x3F03F03F;
s2 = w1 >> 18 & 0x1F01F01F;
s2 += s1 + 0x01001001;
s2 &= 0x3F03F03F;

[leanchess]

I'm having trouble finding the formula for the third in a triplet. I thought it would be as simple as it was for pairs, but I was gravely mistaken.

Any ideas? Perhaps some combination of your method with mine?

[Pio]

Gentlemen (regrettably, I am afraid there are no ladies present),

Recently I have been experimenting with move generation from dense piece lists, and noticed that an arbitrary position (assuming no RB-promotions) may be stored in 256 bits (128 per side) as a whole (STM, castling and e.p. included). This means 4 64-bit registers (or 2 128-bit registers, if we are really down to the metal).

The next logical step seems to be canonicalisation, which may come in handy for preventing hash collisions. However, maintaining a canonical list requires many conditionals and selective updates (16 octets in the worst case), so it might be more sensible to defer canonicalisation to the endgame.

In any case, something similar has been requested some time ago:

https://stackoverflow.com/questions/213 ... s-position

I haven't come across an existing solution thus far, so I am wondering whether this is worth pursuing.

As I am new to the field, I would greatly appreciate your feedback.

Thanks in advance!

Hi, I store my board in 192 (3*64) bits (see my post http://www.talkchess.com/forum3/viewto ... 93&t=49575 how I do it). The nice thing with my representation is that it is simple, compact, can represent all possible chess positions (and all impossible ones as long as there is at most 16 pieces/pawns each). Two other nice properties that are really nice is that my representation can 1) be made colour agnostic (is very nice if used in opening database) branchless and 2) my representation contains an occupancy bitboard of 64 bits so you can use that as one of your primary keys (but you will have to do a composite primary key with the rest of the board data) and thus immediately find all positions having the same squares occupied.

/Pio

[leanchess]

Hi, I store my board in 192 (3*64) bits (see my post http://www.talkchess.com/forum3/viewto ... 93&t=49575 how I do it). The nice thing with my representation is that it is simple, compact, can represent all possible chess positions (and all impossible ones as long as there is at most 16 pieces/pawns each). Two other nice properties that are really nice is that my representation can 1) be made colour agnostic (is very nice if used in opening database) branchless and 2) my representation contains an occupancy bitboard of 64 bits so you can use that as one of your primary keys (but you will have to do a composite primary key with the rest of the board data) and thus immediately find all positions having the same squares occupied.

/Pio

I'm assuming you store the whites first and clear the unused bits. Then you have the perfect globally unique position representation.

Unfortunately, I see two problems with this method:

1. You have to generate everything but the occupancy bits from a board on every make.
2. You cannot use it for move generation.

That leaves collision detection the only valid use case, as I understand it.

[Pio]

Hi, I store my board in 192 (3*64) bits (see my post http://www.talkchess.com/forum3/viewto ... 93&t=49575 how I do it). The nice thing with my representation is that it is simple, compact, can represent all possible chess positions (and all impossible ones as long as there is at most 16 pieces/pawns each). Two other nice properties that are really nice is that my representation can 1) be made colour agnostic (is very nice if used in opening database) branchless and 2) my representation contains an occupancy bitboard of 64 bits so you can use that as one of your primary keys (but you will have to do a composite primary key with the rest of the board data) and thus immediately find all positions having the same squares occupied.

/Pio

I'm assuming you store the whites first and clear the unused bits. Then you have the perfect globally unique position representation.

Unfortunately, I see two problems with this method:

1. You have to generate everything but the occupancy bits from a board on every make.
2. You cannot use it for move generation.

That leaves collision detection the only valid use case, as I understand it.

I use my dense representation for everything. I do not have any other structures except a static 10x8 board helping move generation and for seeing if a piece moves out of bounds. I only do copy make so no unmake is needed. I do not have white and black. I have side to move and not side to move. The make move is complicated because I have to shift a lot. The rotation of board is simple. I do not say my representation is good but it is possible to make a chess engine with it.

[leanchess]

I use my dense representation for everything. I do not have any other structures except a static 10x8 board helping move generation and for seeing if a piece moves out of bounds. I only do copy make so no unmake is needed. I do not have white and black. I have side to move and not side to move. The make move is complicated because I have to shift a lot. The rotation of board is simple. I do not say my representation is good but it is possible to make a chess engine with it.

Sounds like a fun programming exercise; remove the board for extra credit. But what about your engine's performance? I'm not sure how practical the behemoth we have birthed here would be, but your perfect representation, as much as I admire its elegance, seems to be perfectly impractical IMHO.

[Pio]

I use my dense representation for everything. I do not have any other structures except a static 10x8 board helping move generation and for seeing if a piece moves out of bounds. I only do copy make so no unmake is needed. I do not have white and black. I have side to move and not side to move. The make move is complicated because I have to shift a lot. The rotation of board is simple. I do not say my representation is good but it is possible to make a chess engine with it.

Sounds like a fun programming exercise; remove the board for extra credit. But what about your engine's performance? I'm not sure how practical the behemoth we have birthed here would be, but your perfect representation, as much as I admire its elegance, seems to be perfectly impractical IMHO.

You are right my board representation is perfectly impractical . And it is really slow at least the way I have implemented it in c# without profiling and without hardware instrinsics (that are available in .net core I think). I think I evaluate 300-400 knps (just interpolated piece square tables, quiescence search, hash table and draw detection) on a 10 year old laptop.

/Pio

[leanchess]

You are right my board representation is perfectly impractical . And it is really slow at least the way I have implemented it in c# without profiling and without hardware instrinsics (that are available in .net core I think). I think I evaluate 300-400 knps (just interpolated piece square tables, quiescence search, hash table and draw detection) on a 10 year old laptop.

Ah, you wrote it in C#. That's cheating

In all seriousness, I don't think you would be able to compete with the mainstream even if you had it optimised down to the instruction, due to the nature of your data structure (which IS beautiful, without a doubt).