Storing Chessboard positions

Kaisen2100 · Post by **Kaisen2100** » Tue Jan 20, 2009 12:02 am

More chess talk lol

Do you know any other way, different from FEN and EPD, of storing chessboard positions (in a text or ASCII file) ?

i was thinkg in something like: 32 bytes, 1 for each piece (16 black + 16 white) and for each of those 32 bytes we store the position of the piece (or captured, etc) that can be a value from 0 to 63 for the 64 board cells.

that will give us 32 bytes, per position.

Any other ideas with less size?

Thanks

rsts · Post by **rsts** » Tue Jan 20, 2009 1:00 am

I had remembered a few posts dealing with chessboard positions but it seems most of them were yours

e.g.
http://www.purebasic.fr/english/viewtop ... ight=chess

cheers

Kaisen2100 · Post by **Kaisen2100** » Tue Jan 20, 2009 1:23 am

in that thread we talk about storing a move from posA to posB (ex: e4-e5)

in this thread i talk about storing a position ... the location of all the pieces after a move

netmaestro · Post by **netmaestro** » Tue Jan 20, 2009 2:12 am

Raw location of pieces is not sufficient for practical purposes unfortunately. Whether castling is still allowed for black and for white is necessary, as is the possibility of en passant captures, all of which depend upon what has gone before in previous moves. To save a position for analysis purposes, you must save this information as well.

akj · Post by **akj** » Tue Jan 20, 2009 2:26 am

If your main goal is to minimise the number of bytes of storage, then, rather than recording the board position, it may be more efficient to record the moves that produced that board position [from the previous position of interest].

As (according to www.purebasic.fr/english/viewtopic.php?t=26034) fewer than 256 legal movements are possible at any given turn, each move can therefore be recorded in just one binary byte (which is no more than two text bytes).

This could be an efficient storage method and would overcome the shortcomings highlighted by netmaestro in his earlier post, as all information relating to castling etc. is deducible from the list of moves.

Rook Zimbabwe · Post by **Rook Zimbabwe** » Tue Jan 20, 2009 4:38 am

I still say a 2D array!

pbster · Post by **pbster** » Tue Jan 20, 2009 8:10 pm

32 pieces, 1 byte each (0-63) gives 32 bytes total to store an entire board I would think (?).

I'm just starting with pb, and not sure how I would store it into a file, but as a string of hex numbers, 00-40, doing it that way for simplicity sake would make it 64 bytes in a straight text format. (or just 32 in m/c format). You'd need to standardize the piece sequence represented by the string.

File contents could look like: (if it were text),
3C303A3438......

WhiteRookLeft=byte position 1
WhiteKnightLeft=byte position 2
WhiteBishopLeft=byte position 3
etc...
WhitePawn1=byte position 9
WhitePawn2=byte position 10

In this text example, each set of two characters represent the hex position of the piece, so that would give 64 bytes total.

I'm a perl/java guy so I feel like I'm a bit out of my realm here - still learning.

Kaeru Gaman · Post by **Kaeru Gaman** » Tue Jan 20, 2009 8:18 pm

André Beer wrote an essey about Strategy Games.
it was shipped with the German PB3.30 Boxed Version.

I remember he described a way to encode boardgames with single bits per position,
wich made it easy to calculate moves with simple bitoperations And/Or/XOr.

I don't know if this essey was translated to English....

Kaisen2100 · Post by **Kaisen2100** » Tue Jan 20, 2009 10:37 pm

pbster wrote:32 pieces, 1 byte each (0-63) gives 32 bytes total to store an entire board I would think (?).

I'm just starting with pb, and not sure how I would store it into a file, but as a string of hex numbers, 00-40, doing it that way for simplicity sake would make it 64 bytes in a straight text format. (or just 32 in m/c format). You'd need to standardize the piece sequence represented by the string.

File contents could look like: (if it were text),
3C303A3438......

WhiteRookLeft=byte position 1
WhiteKnightLeft=byte position 2
WhiteBishopLeft=byte position 3
etc...
WhitePawn1=byte position 9
WhitePawn2=byte position 10

In this text example, each set of two characters represent the hex position of the piece, so that would give 64 bytes total.

I'm a perl/java guy so I feel like I'm a bit out of my realm here - still learning.

i think it will give only 32 bytes per position, because in each byte we store the position of the piece following the sequence you say:

WhiteRookLeft=byte position 1
WhiteKnightLeft=byte position 2
WhiteBishopLeft=byte position 3
etc...
WhitePawn1=byte position 9
WhitePawn2=byte position 10

I think in storing the position in a byte, like:
Colum 0 and Row 0 = 00, we write the value "0" (with function "WriteByte) in that byte and so on ...

May be we can use a few more bytes to save the castling status, en passant, etc.

It can be more than 32 bytes but not 64 ... may be 40 or 48 bytes?

Kaisen2100 · Post by **Kaisen2100** » Tue Jan 20, 2009 10:49 pm

akj wrote: ...

As (according to www.purebasic.fr/english/viewtopic.php?t=26034) fewer than 256 legal movements are possible at any given turn, each move can therefore be recorded in just one binary byte (which is no more than two text bytes).

...

that will need a move generator to select from all the legals moves ... that i dont know if i want to create for my game lol

Demivec · Post by **Demivec** » Wed Jan 21, 2009 1:22 am

Kaisen2100 wrote:i think it will give only 32 bytes per position, because in each byte we store the position of the piece following the sequence you say:

WhiteRookLeft=byte position 1
WhiteKnightLeft=byte position 2
WhiteBishopLeft=byte position 3
etc...
WhitePawn1=byte position 9
WhitePawn2=byte position 10

I think in storing the position in a byte, like:
Colum 0 and Row 0 = 00, we write the value "0" (with function "WriteByte) in that byte and so on ...

May be we can use a few more bytes to save the castling status, en passant, etc.

It can be more than 32 bytes but not 64 ... may be 40 or 48 bytes?

Since you are open to using binary. here is my format to deal with it. It is based on the FEN format but much shorter. It would take at most only 37 bytes to store a board position, including information for castling, en passant, and turn indicator.

Here's how it would work:

Code: Select all

The first two bytes would contain the board status as bits.

[11eKQkqm] [rrrrffff]

where in the first byte the 2 high bits are set and each additional bit in the first byte would be set if a condition exists:

   e = en passant is possible (this bit is redundant because if en passant is possible the second byte <> $F0 (a "$" precedes hexadecimal digits).
  KQ = castling available for White Kingside or Queenside
  kq = castling available for Black Kingside or Queenside
   m = cleared if White's move (w), or set if Black's move (b)

  If en passant is possible the second byte indicates the square where en passant is possible.  It has it's upper nibble (4 bits) set to the rank (always 3, 6, or $F) and it's lower nibble set to the file #(1 - 8).
  If en passant is not possible this byte will equal $F0.

Now the piece information follows.  Moving across the board from the starting position for the Black Queen's Rook down to the starting position for the White King's Rook (moving across files first, then by rank) you would store the position of each piece.

This would be done with a single byte for each remaining piece.  The type of piece would be represented in the upper 4 bits (values 1 - 6 for white pieces {P,N,B,R,Q,K}, 10 - 16 for black pieces {p,n,b,r,q,k}).  The lower 4 bits would represent how many open spaces on the board until the next piece appears.  This would allow a range of 0 - 14 spaces to be represented.  If more than 14 are needed (and this would only be needed at the most 3 times on any given board), a value of 15 would be used and the byte that follows would instead contain the total amount of spacing needed, (1 - 61).
  To represent space before the first piece it would be coded with a piece type of zero.

So for example:
   3 spaces before the first piece would be represented by     $03 
   a black king followed by 60 spaces would be represented by  $AF $3C
   a white night followed by no spaces would be represented by $20.


The byte for the last piece always has the spacing information set to zero.



To show the whole board representation of a starting position with bytes within brackets (where piece types are represented by letters instead of numerals):

[%110KQkqw] [$F0]
[r0][n0][b0][q0][k0][b0][n0][r0][p0][p0][p0][p0][p0][p0][p0][p15][32][P0][P0][P0][P0][P0][P0][P0][P0][R0][N0][B0][Q0][K0][B0][N0][R0]

for a total of 35 bytes.  The representation would range between 6 - 37 bytes.  If you wanted to keep track of move counts you can use 4 more bytes to cover that range nicely and still be at or below  41 bytes (all status bytes would come first so that everything that remains would follow the piece placement format.

Here's a game in progress:
[1100000b] [$F0]
[r1][b2][r3][p1][n0][q1][b2][n0][p1][p1][k0][p0][p10][P0][N4][P2][B5][Q1][B0][P0][P0][P2][R0][R2][K0]

and the same game in hexadecimal bytes:
[C1][F0]
[D1][C2][D3][A1][B0][E1][C2][B0][A1][A1][F0][A0][AA][10][24][12][35][51][30][10][10][12][40][42][60]


and one involving en passant:
[11eKQkqb] [$34]
[r0][n0][b0][q0][k0][b0][n0][r0][p0][p0][p2][p0][p0][p3][p15][15][P0][p3][P0][P8][P1][P0][P0][P0][P0][R0][N0][B0][Q0][K0][B0][N0][R0]

and in hexadecimal bytes:
[FF][34]
[D0][B0][C0][E0][F0][C0][B0][D0][A0][A0][A2][A0][A0][A3][AE][E][10][A3][10][18][11][10][10][10][10][40][20][30][50][60][30][20][10]

With the way the values were chosen here each byte will have a non-zero value.  This means they can be read into and manipulated in strings (as buffers) if desired.

@edit: adjusted some values and added hexadecimal examples.

pbster · Post by **pbster** » Wed Jan 21, 2009 7:00 am

Wow, what an amazing train of thought to come up with this coding strategy. Interesting and definitely worth the price of admission!

Michael Vogel · Post by **Michael Vogel** » Wed Jan 21, 2009 7:41 am

One question is also, how easy such a representation should be able to read without a lot of calculations. I'd say, that the FEN format is relatively compact and can be understood just with one fast look. Some enhancements would help to decrease the size of the string, but makes the reading more difficult:
* using two different letters for the king (e.g. K if castling is still allowed, C if not)
* using two different letters for the pawn (e.g. P for normal, A if en passant would be possible)
* using the letters 1..9, 0 (and eventually more available characters) to indicate the space between the figures...

This would reduce the size to around 45 to 50 chars for normal, but could be theoretically 64 bytes long at the worst case as well.

Michael

Kaisen2100 · Post by **Kaisen2100** » Thu Jan 22, 2009 1:23 am

Demivec YOU ARE THE MASTER!

that is a good way to store the info and it is like the FEN but in binary lol ...

thanks for your help.

Thinking for several days and i can find ways to it in less size

I've found a way ... but is not so good. The way is

1. We write the initial position + castling status, e.p. status, etc
2. We write 1 byte to tell what piece was moved
3. We write 1 byte to store the new position of that piece
4. We write 1 byte for the new castling and ep status

that way we will have 32 bytes for the first position + 1 byte for castling status + just 3 bytes for each move that is made in the board. we only need 35 bytes for the 1st position and 3 for each next position

the problem with that is that you cant search inside the file for a specific position if you dont have all the preceding moves and the starting position

i want a way to store in a file all the positions in a file and can be able to search a specific position ... so the way you say is the best, i think

thanks

Demivec · Post by **Demivec** » Thu Jan 22, 2009 2:19 am

Kaisen2100 wrote:Demivec YOU ARE THE MASTER!

that is a good way to store the info and it is like the FEN but in binary lol ...

thanks for your help.

Thinking for several days and i can find ways to it in less size

I've found a way ... but is not so good. The way is

1. We write the initial position + castling status, e.p. status, etc
2. We write 1 byte to tell what piece was moved
3. We write 1 byte to store the new position of that piece
4. We write 1 byte for the new castling and ep status

that way we will have 32 bytes for the first position + 1 byte for castling status + just 3 bytes for each move that is made in the board. we only need 35 bytes for the 1st position and 3 for each next position

the problem with that is that you cant search inside the file for a specific position if you dont have all the preceding moves and the starting position

i want a way to store in a file all the positions in a file and can be able to search a specific position ... so the way you say is the best, i think

thanks

Thanks for the compliment. I wanted the format to be condensed and yet still be readable (in hex) by a person without straining too much.

Since the format I proposed never uses a zero byte a zero can be used to mark the start/end of individual positions to store unindexed positions in a file. That would make it so it wouldn't be necesarry to parse the entire file to find what the last position was. The program would just go to the end-of-file and search backwards for the next zero.

If I may ask, what is the overall goal/purpose of what you are working on?