Chess Moves in a byte

[Topilno]

You theoretically could actually encode every single possible move into 8 bits. I'm pretty sure anyway. Though you may have a hard time if you encode moves that a pawn can make if it gets turned into a queen. You'd probably run over 0-255 limit in that case.

Example:

Pawn 1: Move 1 forward, Move 1 up-left, Move 1 up-right

3 moves. Each pawn would have 3 moves so thats a total of 24 moves. 0-23 would be for pawn moves.

Just analyze every move a piece can make. You'll probably be right on the border of the 8-byte limit.

This is the most popular method: it's used by practically all the modern chess databases like Chessbase and Chess Assistant.
They use a byte to store the index of the move in an array of the possible moves in the position.
In the past NICbase used bits, and not bytes: very efficient but more complicated.
The problem of > 255 moves is simply solved: it's a very rare condition, and when happens you can consume a second byte.
The overhead is not so big, and a little footprint of the moves becomes important when you store millions of games in a database.

[superadnim]

I didn't read all the posts, I stopped at the part where a structure of 3 byte fields is suggested: Please, do add an unused padding byte element at the end so your structure ends up being 32bits long instead of 24. You can benchmark if you want, but you'll always see it's faster this way.

Specially on chess, what you want is speed even if though you'll "sacrifice" some memory.

Going through the minimalistic approach is only going to get you that far if you're under a very limited system such as a mobile phone, etc. Even so, sticking to it's core specs is going to get you that much far than trying to play nice in RAM level.

Most compilers add padding (if optimizations are enabled) I doubt PB does this, so you have to do it by yourself. And quite frankly, it's not such a pain to do so.

[Demivec]

You theoretically could actually encode every single possible move into 8 bits. I'm pretty sure anyway. Though you may have a hard time if you encode moves that a pawn can make if it gets turned into a queen. You'd probably run over 0-255 limit in that case.

Example:

Pawn 1: Move 1 forward, Move 1 up-left, Move 1 up-right

3 moves. Each pawn would have 3 moves so thats a total of 24 moves. 0-23 would be for pawn moves.

Just analyze every move a piece can make. You'll probably be right on the border of the 8-byte limit.

This is the most popular method: it's used by practically all the modern chess databases like Chessbase and Chess Assistant.
They use a byte to store the index of the move in an array of the possible moves in the position.
In the past NICbase used bits, and not bytes: very efficient but more complicated.
The problem of > 255 moves is simply solved: it's a very rare condition, and when happens you can consume a second byte.
The overhead is not so big, and a little footprint of the moves becomes important when you store millions of games in a database.

To clarify and restate what you said, you wouldn't store the move information, you would store an index into the possible moves for a position.

For any board position there are at most 216 possible moves. It will never be above 256 and so it would fit easily in a byte. This would be carried out by requiring the board position, then computing and sorting the possible moves, then using the index to select the move that was made.

It is relatively easy to do this for playing back moves. On the other hand for move planning all the time is spent in determining which of the possible moves is the best one to make, but that's another story.

[Helle]

For fans: A little chess-programm in PB (comments are in German, sorry): http://www.mdcc-fun.de/k.helbing/Little-Timpetu
Have fun!

Gruss
Helle

[Kwai chang caine]

Great job HELLE
Thanks for sharing your code

[Road Runner]

Please, do add an unused padding byte element at the end so your structure ends up being 32bits long instead of 24. You can benchmark if you want, but you'll always see it's faster this way.

This is not always the case.
Using 4 bytes/structure instead of 3 requires 33% more memory reads which can often cause more of a performance hit than the misaligned 3 byte reads, especially if the data is in main memory and not in the CPU cache.

[Topilno]

To clarify and restate what you said, you wouldn't store the move information, you would store an index into the possible moves for a position.

For any board position there are at most 216 possible moves. It will never be above 256 and so it would fit easily in a byte. This would be carried out by requiring the board position, then computing and sorting the possible moves, then using the index to select the move that was made.

It is relatively easy to do this for playing back moves. On the other hand for move planning all the time is spent in determining which of the possible moves is the best one to make, but that's another story.

It's the method used by the main programs, not my opinion.
You can find docs about formats like cbf and cbh on sites like wotsit.
216 possible moves?
Please remove a lot of pawns, place 5-6 queens on the board and tell me how many legal moves are possible...

[PB]

> Why make things hard for yourself when you could of probably finished
> the program by now if you hadn't got bogged down with this.

+1

[Helle]

216 moves:
White: Kf1, Qa3, Qb6, Qc4, Qd2, Qd7, Qe5, Qf3, Qg6, Qh4, Ra8, Rh8, Bb1, Bg1, Nc1, Nd1
Black: Ka1, Pa2, Pb2
White on move.

Gruss
Helle

P.S.: In many books are published 218 moves, but my program say also 216.

[Demivec]

216 possible moves?
Please remove a lot of pawns, place 5-6 queens on the board and tell me how many legal moves are possible...

Here is the board setup as well as a list of all the moves possible:

Code: Select all

White:KQQQQQQQQQRRBBNN
Black:kp

 a b c d e f g h
8      Q
7  Q         Q	
6        Q
5    Q         R
4Q         Q
3      Q
2  Q         R p
1  K   B B N N k

The possible moves depend on whose turn it is, here is a list if you wish to tally them yourself:

;location of piece, Piece Name, possible moves for that piece
loc P list of possible moves
--- - -------------------------------------------------------------------------------
d8  Q a8  b3  c8  e8  f8  g8  h8  c7  d7  e7  b6  d6  f6  a5  d5  g5  d4  h4
b7  Q a8  b8  c8  a7  c7  d7  e7  f7  a6  b6  c6  b5  d5  b4  e4  b3  e3
g7  Q f8  g8  h8  c7  d7  e7  f7  h7  f6  g6  h6  e5  g5  d4  g4  c3  g3
e6  Q c8  e8  g8  d7  e7  f7  a6  b6  c6  d6  f6  g6  h6  d5  e5  f5  c4  e4  g4  b3  e3  h3  a2  e2
c5  Q c8  f8  a7  c7  e7  b6  c6  d6  a5  b5  d5  e5  f5  g5  b4  c4  d4  a3  c3  e3  c2  f2  c1
a4  Q a8  e8  a7  d7  a6  c6  a5  b5  b4  c4  d4  e4  a3  b3  a2  c2  a1
f4  Q b8  f8  c7  f7  d6  f6  e5  f5  b4  c4  d4  e4  g4  h4  e3  f3  g3  d2  f2  xh2 c1
d3  Q d7  h7  a6  d6  g6  b5  d5  f5  c4  d4  e4  a3  b3  c3  e3  f3  g3  h3  c2  d2  e2
b2  Q b6  f6  b5  e5  b4  d4  a3  b3  c3  a2  c2  d2  e2  f2  a1  c1
h5  R h8  h7  h6  d5  e5  f5  g5  h4  h3  xh2
g2  R g6  g5  g4  g3  c2  d2  e2  f2  xh2
b2  K a2  c2  a1  c1
d1  B g4  b3  f3  c2  e2
e1  B a5  b4  h4  c3  g3  b2  f2
f1  N e3  g3  d2  h2
g1  N f3  h3  e2
h1  k xg1
h2  p xg1

216 moves for White + 2 for Black = 218 total possible moves from this board position

[Topilno]

216 moves:
White: Kf1, Qa3, Qb6, Qc4, Qd2, Qd7, Qe5, Qf3, Qg6, Qh4, Ra8, Rh8, Bb1, Bg1, Nc1, Nd1
Black: Ka1, Pa2, Pb2
White on move.

Gruss
Helle

P.S.: In many books are published 218 moves, but my program say also 216.

You both are right.