Chess Moves in a byte

[Derek]

additionally, there will be a really, really large overhead of calculation using this system.
you can read the value "white queen is making possible move #13"
it will be quite a calculation to determine wich move it actually is...

You would simply have an array of vectors, look up vector 13 which might give an x of +6 and a y of +6 so the queen moves up 6 and right 6, not much overhead at all and probably very quick with only 248 vectors to store.

[Kaeru Gaman]

additionally, there will be a really, really large overhead of calculation using this system.
you can read the value "white queen is making possible move #13"
it will be quite a calculation to determine wich move it actually is...

You would simply have an array of vectors, look up vector 13 which might give an x of +6 and a y of +6 so the queen moves up 6 and right 6, not much overhead at all and probably very quick with only 248 vectors to store.

not exacly, because the 28 possible moves are not really vectors for the queen.
note that the 7 moves along the x axis mean different movements depending on the actual x-position.

but at the end, how many possible moves allover are there in chess?
wouldn't it be sufficent to use 2byte per move?
(the leftover nibble you can use to stote the additional redundant info wich unit it is that is moving)

[dracflamloc]

In practicality though the overhead of calculating that isn't very high at all. Even ancient computers can handle that with ease.

I think the key of getting a chess move into 8-bits is reduced storage space for a TON of moves. Say you wanted to automatically compute guaranteed ways to win for tons of different scenarios. With 8-bits per move instead of 16 you'd cut the storage required in half.

[va!n]

@Kaeru Gaman:
sorry, now i got the point and understand what he wanted

[Kaisen2100]

I think that its not possible to store it in a byte. If i use this:

Code: Select all

each queen  28 (*2)     =   56
each bishop 14 (*4)     =   56
each tower  14 (*4)     =   56
each knight  8 (*4)     =   32
each king    8 (*2)     =   16
each pawn    4 (*16)    =   32
                        ------
                           248

i will need to calculate every possible move for the piece and it will take so much time to "translate" the move.

I think that the way to store it is using 16 bits: 8 bit store the startpos and 8 bit store endpos.

But thinking a little bit more it can be stored with 12 bits: 6 bits to store starpos (0 .. 63 takes 6 bits) and 6 bits to store endpos (0 .. 63 takes 6 bits)

So ... here is a feature request ... i need a new datatype ... the nibble or the "One and Half Byte" :D:D:D

I cant see how can i use just a byte to store the startpos and endpos ... but i read somewhere (and i dont remember where ) that it is posible.

In practicality though the overhead of calculating that isn't very high at all. Even ancient computers can handle that with ease.

I think the key of getting a chess move into 8-bits is reduced storage space for a TON of moves. Say you wanted to automatically compute guaranteed ways to win for tons of different scenarios. With 8-bits per move instead of 16 you'd cut the storage required in half.

Well ... i want to store Chess moves in the minimum space possible ... in a binary file and not in a text file (like PGN chess files) ... i cant sleep thinking how can i use only a byte .

It would be great to use just one byte for each move (for each half move in real chess, because a full move in chess includes Black's and White's pieces moves), and then for a full chess move we need at least 24 bits or 3 bytes. The closets thing i have to 24 bits is a Long with 32 bits (4 bytes) ... but using a Long number there wil be an unused byte and i dont want to waste space.

[Kaisen2100]

but at the end, how many possible moves allover are there in chess?
wouldn't it be sufficent to use 2byte per move?
(the leftover nibble you can use to stote the additional redundant info wich unit it is that is moving)

I dont remember where i saw this ... but the max known number of moves posible in a chess board in a given position is 243. I dont want to calculate and analyse each move. I just want to store moves the simplest way i can do ... and after that read and "translate" it easily.

Well, using 2 bytes for each startpos-endpos pair (half moves) i will need 4 bytes to store the full black's and white's moves. I think that i need at least 12 bits to store the starpos-endpos pair and if i use 16 bits i can use the last 4 bits to store info like if the move is a check, a promotion or whatever. It will justify using 4 bytes to store the full black and white move.

The thing is that i dont care if the moves gives a check or if the pawn is promoting ... i read the move and calculate later the consequences of the move.

[Kaisen2100]

May be i can use a structure os 3 bytes like this:

Code: Select all

Structure ChessMove
Byte1.b
Byte2.b
Byte3.b
EndStructure

That is 24 bits.

What is the faster and better data type to work? Bytes, words, longs? (1 byte, 2 bytes, 4 bytes)

[Kaeru Gaman]

seems you didn't read all postings carefully...
http://www.purebasic.fr/english/viewtop ... 998#183998

[Rook Zimbabwe]

Longs... IMO longs...

aand this has got me thinking about several other ways to apply the byte/board idea to games I have already written... Maybe recode in style!

[Michael Vogel]

Hi,
nice discussion, I don't believe that 1 byte will be enough for that amount of data...

Don't forget that a lot of special moves ar allowed, rochade and a lot of pawn moves (en passant, change of a pawn)...

Anyway, what about using 4 bits for a figure number, the target field (6 more bits) and 2 more bits for special "comments" (change from a pawn to a queen, etc.)?

In principal this would work, but it's just nice for save memory, it's a lot of work to do the "decompression"...

[Kaisen2100]

In principal this would work, but it's just nice for save memory, it's a lot of work to do the "decompression"...

I Know that i need a few of work "decompress" the move ... but i want to store something like a million games in the less space i could, in a binary file. I will "decompress" a game only when it is necessary, i dont need to decompress the whole million games.

My conclusion is that we can't use less than 10 bits to store the halfmove and 20 bits to store the full black's-white's move.

[/code]

[dracflamloc]

By the way... Since you don't care about run-time memory use only HD, why not use the 10-bit method and write 10 bits at a time to the HD (Yes I know you can't technically do that but you can fake it using pokes and writebytes). You'd just end up with an extra byte at the end in most cases and would have to handle that.

[dioxin]

There are only 16 pieces maximum on each team so you can number the pieces 0-15 and fit that in 4 bits.

Code: Select all

Piece  #0  Pawn      Piece #8  King's Castle
Piece  #1  Pawn      Piece #9  King's Knight
Piece  #2  Pawn      Piece #10 King's Bishop
Piece  #3  Pawn      Piece #11 King
Piece  #4  Pawn      Piece #12 Queen
Piece  #5  Pawn      Piece #13 Queen's Bishop
Piece  #6  Pawn      Piece #14 Queen's Knight
Piece  #7  Pawn      Piece #15 Queen's Castle

You don't need to determine Black or White since odd moves are always White and even moves are always Black, you just need to count the moves so far to resolve which colour moves next.

From any given position
Pawn has only 5 possible moves only 3 bits needs
Castle has only 14 possible moves only 4 bits needs
Bishop has only 14 possible moves only 4 bits needs
Knight has only 8 possible moves only 3 bits needs
King has only 8 possible moves only 3 bits needs
Queen has only 28 possible moves only 5 bits needs

So all moves except the Queen's can be fully specified in one byte with room to spare.
To fit the Queen's move in you can include 4 bits worth (16) of moves in the byte and use the spare space from the 3-bit pieces (Pawns, Knights and King to fill in for the remaining 12 moves.

You need to choose which move number corresponds with which movement of the piece.
e.g. for Pawn
Move 0 move forward 1 place
Move 1 move forward 2 places
Move 2 Take En Passant
Move 3 Take to front left
Move 4 Take to front right

Similarly a Castle could be specified as:
Move 0 move forward 1 square
Move 1 move forward 2 squares
..
Move 6 move forward 7 squares (wrap around if it's beyond the board)
Move 7 CASTLE-QUEEN
Move 8 move right 1 square
Move 9 move right 2 squares
..
Move 14 move right 7 squares (wrap around if it's beyond the board)
Move 15 CASTLE-KING


e.gs:
Hex
Byte Move
03 Pawn #0 does move 3
11 Pawn #1 does move 1
84 Castle 1 ( piece 8 ) does move 4.

etc.
For the queen you can use a special case like this
C9 Queen (piece #12 = C in hex) makes move 9
09 Pawn 0 makes move 9
07 Pawn 0 makes move 7
0F Pawn 0 makes move 15 ( = F in hex)
etc.

Now move 9 for a Pawn doesn't exist as a Pawn only has moves 0-4 so this is invalid for a Pawn. Since this situation can never exist, simply interpret an invalid move like move 9 as really being a move for the Queen so the Queen's move 0-14 are coded in the Queens move bits and the Queen's move 15-27 are coded in the invalid Pawn moves.

I'm sure you get the idea.

Paul.

[Helle]

In big Data-Bases is this a way: A simple move-generator makes the moves (with reproduce) and in the list is stored the number of this move (one byte). "Decompression" is the same way with the move-generator.

Gruss
Helle

[Demivec]

@dioxin: there's a small correction needed to the format you suggested.

Now move 9 for a Pawn doesn't exist as a Pawn only has moves 0-4 so this is invalid for a Pawn. Since this situation can never exist, simply interpret an invalid move like move 9 as really being a move for the Queen so the Queen's move 0-14 are coded in the Queens move bits and the Queen's move 15-27 are coded in the invalid Pawn moves.

A Pawn doesn't have any extra moves because it can be a Queen also. You would have to split the additional moves up between several pieces, such as King and Knight. The 28 moves possible for a Queen could be stored under the piece types like this: Queen(0-15), Knight(16-23), King(24-27).

In other words you could store 8 moves in the Knight's table(along with the 8 it uses) and 4 in the King's table of moves (along with the 8 it uses).
Which reminds me, it would make a little more sense to store castling moves with the King's moves (bringing its total to 10+1 to include Resigning), not the Rooks.