Chess Moves in a byte

Rook Zimbabwe · Post by **Rook Zimbabwe** » Thu Mar 01, 2007 4:34 am

If I remember all the rules of chess the pawn can have 6 moves if you count capturing "en passant" that special move ( I count 6 because this can happen Right or Left)

http://www.conservativebookstore.com/chess/enpass.htm
http://www.chessvariants.org/d.chess/enpassant.html

I think no one ever programs in chess computer games because it is so unorthadox.

I like it. It throws the competition for a loop and you get a psych9ological advantage...

Kaeru Gaman · Post by **Kaeru Gaman** » Thu Mar 01, 2007 9:12 am

hm...
but coordinates it's the same move like a normal capture with a pawn,
only the position of the captured unit differs.
since non of the move-codes as stated so far encloses anything about
capturing or not, I count still 4 possible moves for a pawn.

on the other hand, I can't image atm how to code a rochade...
maybe it would be best to signalize it by an empty move of the opponent...

dioxin · Post by **dioxin** » Thu Mar 01, 2007 2:49 pm

Rook Zimbabwe,
can you list the 6 moves? If you mean the 6th one is the capture en passant in 2 ways then that's not true. En passent only applies for one move after the opposition has moved his piece into a position to be taken.
If 2 such pieces are moved into that position then only the last one can be taken so a single "take en passant" is enough to identify which move is made.

Demivec,
there are other corrections too!
As posted there are deficiencies in the method, the main one being pawn promotion to queen. But I explained the method the way I did to get an idea across.

In practice you wouldn't split the byte up into bit fields as I showed with the first 4 breing the piece and the last 4 being the move, you'd use a 256 byte look up table.

From the information above (let's assume for now that I counted the moves for each piece correctly) the total number of valid moves is:
Pawns 8 x 5
Castles 2 x 14
Knights 2 x 8
Bishops 2 x 14
King 1 x 8 + 2 castling moves
Queen 1 x 28
Total= 150 moves

We know a byte can hold 256 moves in a byte so we have 106 moves spare to handle the case of pawn promotion. That's nearly 4 Queens worth since 4 x 28 = 112.
So it's clearly possible to compress all the possible moves into 1 byte as long as one side gets no more than 3 queen promotions in a single game. That would never happen in a real game.

Paul.

Derek · Post by **Derek** » Thu Mar 01, 2007 2:57 pm

I think your figures are wrong, a rook has 28 possible moves, a bishop 28, a queen 56. You have to take into account where the piece is on the board.

If you allow 14 moves for the rook starting on the left of the board then you are only allowing it to go up or right, you still need to allow it to go left and back.

Derek · Post by **Derek** » Thu Mar 01, 2007 3:01 pm

Incidently, why are you all saying 28 moves for a queen, a queen can move in 8 directions and upto 7 squares so that is 56 possible moves.

dioxin · Post by **dioxin** » Thu Mar 01, 2007 3:02 pm

Derek,
not true. As I stated, if the piece would move off the edge of the board then let it wrap around, i.e. reappear on the other side of the board. so if a rook is on square 3 and I move it right 7 places then it goes to square 10. Wrap that around MOD8 and it ends up on square 2. i.e the same as moving 1 place the other direction.

So, for a rook, there are 7 file squares in reach and 7 rank squares in reach so 14 moves will cover them all.

Paul.

Derek · Post by **Derek** » Thu Mar 01, 2007 3:08 pm

Ah yes, the penny drops. I stand corrected.

Demivec · Post by **Demivec** » Thu Mar 01, 2007 9:50 pm

@dioxin: What do you mean with regards to Queen promotions in this quote?

So it's clearly possible to compress all the possible moves into 1 byte as long as one side gets no more than 3 queen promotions in a single game. That would never happen in a real game.

I don't follow the thinking on that, I would handle a Pawn promotion by referring to the original piece as a Pawn# + Queen Move#. That seems like it would accomadate 8 promotions.

As an aside, what is a rochade move? I thought I was familiar with chess until that was mentioned.

einander · Post by **einander** » Thu Mar 01, 2007 10:42 pm

Lange Rochade = German for long castling ; Kurze Rochade = German for short castling.

dioxin · Post by **dioxin** » Thu Mar 01, 2007 10:44 pm

Demivec,
the way I envisaged it, the 256byte table would only allow for 5 moves for each pawn as explained earlier so there would be no room for a "Queen's move" in the space allocated to a pawn.
Instead, I'd use the remaining 106 unused moves to cover the promoted queens. You could consider that there are 3 extra pieces on the board called Queen2, Queen3, Queen4 which don't come into play until a pawn is promoted.

I'm not saying this method is necessarily the best but it's one simple way to squeeze all the information into 1 byte and will hopefully give Kaisen2100 ideas on how to do it.

More complex schemes could be used where the 256 byte lookup table changes according to the state of the game but that's a lot more complicated. That way, when a pawn is promoted its 5 moves in the table could be reused. Then, 6 pawn promotions would free up 6x5=30 moves. Added to the 106 spares we have anyway would give 136 which is enough to track 4 promoted pawn-queens and 4 promoted pawn-knights. Of course, any real chess program will never get this far. 2 queens on a side is very unusual in a real game,

Paul.

Derek · Post by **Derek** » Thu Mar 01, 2007 10:48 pm

Don't forget that pawns can actually promote to rooks, bishops or knights!

Demivec · Post by **Demivec** » Thu Mar 01, 2007 10:51 pm

einander wrote:Lange Rochade = German for long castling ; Kurze Rochade = German for short castling.

Thanks. Castiling was my best guess as to its interpretation. In this case Lange Rochade = Castling Queen Side; Kurze Rochade = Castling King Side.

Kaeru Gaman wrote:on the other hand, I can't image atm how to code a rochade...
maybe it would be best to signalize it by an empty move of the opponent...

This can be handled with 2 additional move options for the King. These moves would be as listed above.

dioxin · Post by **dioxin** » Thu Mar 01, 2007 10:54 pm

Derek,
I didn't forget but you can treat that as a special case. You could restrict the promotions to 2 of each piece which would all then fit in the 136 moves available.

I suppose there are circumstances when you wouldn't want a Queen or a Knight which would make sense.. such as if promoting to a Queen could cause the opponents King to be trapped and stalemated so a Bishop or Knight would be needed to allow the game to continue to checkmate.

Paul.

Kaisen2100 · Post by **Kaisen2100** » Fri Mar 02, 2007 2:16 am

dioxin

Thanks for your ideas ... i see what you mean. It is a way to do it and it is a good one.

But in theory there are some problems: you can have a max of 9 Queens or 10 bishops or 10 Knights or 10 Rooks (just one of that options, not all) ... lo0ol ... i know that it is something anormal but sometimes can happens things very close to that. You can see some Chess Records here:

http://www.xs4all.nl/~timkr/records/records.htm

You never will have 10 Rooks but ... if i have a game with 5 Queens it will be very hard to "compress" every move using just 1 byte. May be it's a dream to (in an easy, good and fast way) store every possible chess move with only 1 byte.

The less confusing way is using 12 bits to store starpos (6 bits) and endpos (6 bits), or using 10 bits: 4 bits for the piece # (each color has 16 pieces) and 6 to the endpos (6 bits).

May be the best way to do it is using 3 Bytes for store a full black's and white's move, it will give me 24 bits ... or i can use a Long with 4 bytes to store the 24 bits info + 8 bits of another info like check, etc.

Anyway i cant sleep trying to realize that dream of use only to store only 1 byte to store every possible move in a chess board

...

Demivec · Post by **Demivec** » Sat Mar 03, 2007 4:05 am

@Kiasen2100:

The link you provided to Chess Records includes at least several examples of "invented" games and ones that had moves made which were illegal (i.e. Castling 3 times).

Irregardless, I still don't see a difficulty in accomplishing your task after the discussion and suggestions which have been given.

You never will have 10 Rooks but ... if i have a game with 5 Queens it will be very hard to "compress" every move using just 1 byte. May be it's a dream to (in an easy, good and fast way) store every possible chess move with only 1 byte.

Just for curiosity, why don't you provide a sample (demonstration) game consisting of all the moves possible that are legal and you would need to code. The moves don't have to be sensible, just possible. Provide more than one set of moves (for different games) if necessary to cover all the possibilities. Until you do this, you won't really find out if your ideas would fail, or work.