Storing Chessboard positions

Michael Vogel · Post by **Michael Vogel** » Thu Jan 22, 2009 7:50 am

Just found an article (Link) which contains the sentence, that Mychess "[...] represented the board in only 32 bytes [...]" and that the "program fixed the problem" which was given with some informations for the pawn. There was no explanation how to do it, but also a the following book reference: "David Welsh's book, Computer Chess, published in 1984"

Michael

Kaisen2100 · Post by **Kaisen2100** » Thu Jan 22, 2009 1:55 pm

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

Right now i am contrunting the chessboard, and the interface for moving and storing the moves, but since it is a chessvariant and it plays in 2 10 x 10 boards (lol

) it takes time, because there are new pieces and a lot of rules i have to define in my variant before continue making the interface.

I also want to make something like a "positional database" where you can search past games with a specific position and analise them.

It is a hard work.

The info you posted can work in 2 10 x 10 boards but will need work to adapt it from 64 to 200 cells

i am a little crazy

hehe

Michael Vogel · Post by **Michael Vogel** » Thu Jan 22, 2009 3:35 pm

I have spent some time now to think about a solution to use 32 bytes only and I have now a (hopefully) correct answer

I put two pieces together into a 16 bit value, 9 bits for a pawn and 7 bits for each other figures, makes 32 byte for all 32 pieces.

Each pair looks like that (Bits 1 to 16 = a...p):
[abcdef][ghi][j][klmnop]
Lets say its the pair for the white rook (a1) and pawn (a2):
[a...f] tells the position on the board (8x8=64, so 6 bits are needed)
[h..i] are for showing the one the following states (0:normal, 1:dead, 2:en passant possible, 3:is a queen, 4:rook, 5:bishop or 6:knight)
[j] says if the figure is on the board or off the bord, for the king it says, if castling is possible or not
[k...p] position on the board

The only missing information is, who is next, this could be done using the unused state 7 for a pawn, this is the only tricky part here...

Michael

Demivec · Post by **Demivec** » Thu Jan 22, 2009 5:20 pm

Kaisen2100 wrote:
If I may ask, what is the overall goal/purpose of what you are working on?
Right now i am contrunting the chessboard, and the interface for moving and storing the moves, but since it is a chessvariant and it plays in 2 10 x 10 boards (lol ) it takes time, because there are new pieces and a lot of rules i have to define in my variant before continue making the interface.

I also want to make something like a "positional database" where you can search past games with a specific position and analise them.

It is a hard work.

The info you posted can work in 2 10 x 10 boards but will need work to adapt it from 64 to 200 cells

i am a little crazy hehe

@Kaisen2100: do you have the number of piece types fixed yet ? For the method I posted you can have up to 7. That means you could add 1 more piece type of each color or 3 non-colored pieces (depending on your creative rule making). My method currently supports spacing of up to 255, so 200 wouldn't be a problem. This would change the #of bytes needed for a board to roughly 49 (with only 7 piece types). When you nail down the details of the representation it may be possible to optimize it further.

@Michael Vogel: with the layout you describe, how would you differentiate between being able to castle to either kingside or queenside but not both?

Kaisen2100 · Post by **Kaisen2100** » Thu Jan 22, 2009 10:16 pm

The total number of different pieces are 13 ... including the pieces from normal chess,and it has 2 boards hehehe

... in each board there are 30 black pieces and 30 white ... i dont know if it is so much ... but that is the idea i have in mind

Kaisen2100 · Post by **Kaisen2100** » Thu Jan 22, 2009 11:14 pm

Kaisen2100 wrote:The total number of different pieces are 13 ... including the pieces from normal chess,and it has 2 boards hehehe ... in each board there are 30 black pieces and 30 white ... i dont know if it is so much ... but that is the idea i have in mind

what you think about that ... with just that little description ... what you think?

Michael Vogel · Post by **Michael Vogel** » Fri Jan 23, 2009 11:10 am

Demivec wrote:@Michael Vogel: with the layout you describe, how would you differentiate between being able to castle to either kingside or queenside but not both?

You're right, it's no problem to put this information into the available sequence of the pawn bits (I believe 4 bits are available because only one color will use en passant, so when all pawns of the other color are still "alive" their [ghi] bits can be used for this information. If the first pawn will get off the board, there is even more space using its [abcdef] bits.
But when changing to this scheme, encoding and decoding will get difficult and that means, you can start with an even more complex (and compact) coding sceme using huffman coding (a quick check leads to 23 bytes for the initial position)...

Michael

Found a new document: Download

Kaisen2100 · Post by **Kaisen2100** » Fri Jan 23, 2009 9:47 pm

Michael Vogel wrote: Found a new document: Download

that document is great. The idea is good and can reduce the size

we store a mask or 64 bit array telling what cells are occupied and which ones are free

something like this:

11001110 ... 1110 64 bits = 8 bytes

after thar we store what piece is in each of the cells, using 4 bits for each type of piece.

0000= King
0001 = Queen
...
0110 = Pawn

that is a good Method for storing.

I searched in google but i didnt found documents like that

Michael Vogel · Post by **Michael Vogel** » Sat Jan 24, 2009 9:00 am

Kaisen2100 wrote:[...] that document is great. The idea is good and can reduce the size [...]

That's why I love this forum - there are so many cool people here, and together we find a lot of useful things

Michael

Demivec · Post by **Demivec** » Sun Jan 25, 2009 12:00 am

Kaisen2100 wrote:
Kaisen2100 wrote:The total number of different pieces are 13 ... including the pieces from normal chess,and it has 2 boards hehehe ... in each board there are 30 black pieces and 30 white ... i dont know if it is so much ... but that is the idea i have in mind
what you think about that ... with just that little description ... what you think?

@Kaisen2100: It looks like you have the makings of a war.

It will depend on a lot on the moves allowed for the pieces. Do I understand you correctly that there are 120 pieces when the game starts?

Kaisen2100 wrote:
Michael Vogel wrote: Found a new document: Download
that document is great. The idea is good and can reduce the size

we store a mask or 64 bit array telling what cells are occupied and which ones are free

something like this:

11001110 ... 1110 64 bits = 8 bytes

after thar we store what piece is in each of the cells, using 4 bits for each type of piece.

0000= King
0001 = Queen
...
0110 = Pawn

that is a good Method for storing.

I adapted my method according to what you described (pieces & board size) and came up with a solution that takes between 5 and 131 bytes to store a board (without further compression). It varies only slightly from what I described previously. I record the placement of all Black pieces, followed by a unique piece type, followed by the placement of all White pieces.

I was also intrigued by the method Michael linked to and made some comparisons between that method and my own for size differences.

Wouldn't you need 5 bits for each piece because you have to indicate color as well as type (i.e. 13 types x 2 colors) ?

I tested the method by using 8 bits for each piece. The results were between 27 and 145. It can be calculated easily as 200 bits (board) + 8 bits * numberOfPieces. So for a full board it would be 200 + 8 * 120 = 1160 bits = 145 bytes. If you used 5 bits for each piece it would be 200 + 5 * 120 = 800 bits = 100 bytes

If you used 8 bits per piece my method came in between 14 and 23 bytes shorter on average. If you used 5 bits per piece my method took more storage (between 1 and 31 bytes more) on average for positions with greater than 47 pieces, all others took less space.

It depends on the gameplay as to which method is better at the moment. For instance, whether you store more positions with either less than 48 pieces or more than 47 pieces. At the moment I would favor the method michael found. If you are interested in compressing the storage further (if time isn't that critical) the advantages between the two methods may change.

I'm going to investigate this further and keep you abreast of any significant findings.

Kaisen2100 · Post by **Kaisen2100** » Sun Jan 25, 2009 10:21 pm

Demivec wrote: @Kaisen2100: It looks like you have the makings of a war. It will depend on a lot on the moves allowed for the pieces. Do I understand you correctly that there are 120 pieces when the game starts?

Yes you are right

And i am looking for people for playtesting

... can you be one the playtesters? do you know someone interested?

thanks for your help

Demivec · Post by **Demivec** » Mon Jan 26, 2009 1:38 am

Kaisen2100 wrote:
Demivec wrote: @Kaisen2100: It looks like you have the makings of a war. It will depend on a lot on the moves allowed for the pieces. Do I understand you correctly that there are 120 pieces when the game starts?
Yes you are right

And i am looking for people for playtesting ... can you be one the playtesters? do you know someone interested?

thanks for your help

Your welcome for the help.

I would be able to help with playtesting. It depends a little on what would be involved. I can let you know more as I learn more. I unfortunately don't know of anyone else who also would be interested.

Kaisen2100 · Post by **Kaisen2100** » Mon Jan 26, 2009 1:50 am

the playtesting wil be just 1 or 2 games against me to test the rules ... but first i need to write all the rules

... define the rules very well is not easy ... too many things to think about ... but i think it can be a good chesvariant

thanks

alokdube · Post by **alokdube** » Mon Feb 23, 2009 12:26 pm

I wrote a brute force peg solitaire solver (kiddy stuff , I just wanted to see how good thread processing and tree traversal goes)
i was wondering if the same logic works for chess, brute force tree traversal for an opening upto some x depths and storing results in a database and proceeding.... ofcourse the memory reqmnts are huge but in general is every tree traversed?

astonflamsCaf · Post by **astonflamsCaf** » Wed Jun 03, 2009 9:42 pm

I am looking for a portable device such as a Blackberry to store all of my recipes in a Word or text format. I would like to be able to access them on the line or anywhere else. Is there anyone using such a device? Is there one that you think is more/less suitable for the task?