Chess Moves in a byte

[Kaisen2100]

Hello people i am wondering if it is posible to store a chess move with only a byte ... the are 64 squares (you can conut it from 0 to 63), so you can use a byte to store the starting square ... and ... what i can't see is how can include in that byte the finishing square. I think it is posible ... what you think?

i just want to store the starting square and the finish square, i dont want to store if it was a capture or a check, only store the moves.

[Kaeru Gaman]

if you want to store the fields, it's clearly NOT possible,
because you need 6bit to store a number of 0-63,
so you'll need 12bit to store two of them, not 8bit.

you could also store the moving unit.
you have 16 units on each side, so you would only need 4 bit to store the moving unit,
but the queen has more than 16 possibilities where it can move,
and the pawn has only 2 possibilities, so this will make the whole thing unconsistent.

take a word for each move, store the start in the lower and the aim in the higher byte,
and just forget about the lost 4 bit per date.

[Kaisen2100]

Yeah ... after thinking a bit more .. i think it is not posible using only a byte ... so i need at least 12 bits ... One and Half byte :p lo0ol ... and because i cant declare a variable like "Dim ChessMove as '1.5 Byte'" i need to use 2 bytes at least ... a word

Thanks any way !!!

[va!n]

Why should it not be possible handling data using a byte? What about following? A chess board has 64 possible fields... So each field can have its own ID (1-64), and you know everytime which field you are ^^

Code: Select all

+----+----+----+----+----+----+----+----+
|  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |
+----+----+----+----+----+----+----+----+
|  9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
+----+----+----+----+----+----+----+----+
| 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
+----+----+----+----+----+----+----+----+
| 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
+----+----+----+----+----+----+----+----+
| 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
+----+----+----+----+----+----+----+----+
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 |
+----+----+----+----+----+----+----+----+
| 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 |
+----+----+----+----+----+----+----+----+
| 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 |
+----+----+----+----+----+----+----+----+

Hope this hels... good luck... Btw, using LONG is better and faster isntead handling datas using BYTE... but for size optimizing you can use topic example...

[va!n]

Another idea is to handle each field as X and Y ... you have for each coorinate X and Y with a max value of 8....

A byte is max 255 or $FF.... so you can split the byte $FF into $0F and $F0 ... in the first $F0 you can store the X pos... in the second $0F you can save the Y pos... so you calculate the pos by X and Y or X * Y

Code: Select all

    X1   X2   X3   X4   X5   X6   X7   X8

   +----+----+----+----+----+----+----+----+
Y1 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |
   +----+----+----+----+----+----+----+----+
Y2 |  9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
   +----+----+----+----+----+----+----+----+
Y3 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
   +----+----+----+----+----+----+----+----+
Y4 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
   +----+----+----+----+----+----+----+----+
Y5 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
   +----+----+----+----+----+----+----+----+
Y6 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 |
   +----+----+----+----+----+----+----+----+
Y7 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 |
   +----+----+----+----+----+----+----+----+
Y8 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 |
   +----+----+----+----+----+----+----+----+

$24 will be field 26.. $24 = split into $2# = XPos2 And $#4 = YPos 4

You you understand what i mean

[va!n]

sorry i oversaw, you want to store start and endpos in one byte... after thinking a bit it could be possible. it was just a fast cross idea...

Code: Select all

    X1   X2   X3   X4   X5   X6   X7   X8

   +----+----+----+----+----+----+----+----+
Y1 |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 | = 0
   +----+----+----+----+----+----+----+----+ 
Y2 |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 | = 1
   +----+----+----+----+----+----+----+----+
Y3 |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 | = 2
   +----+----+----+----+----+----+----+----+
Y4 |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 | = 3
   +----+----+----+----+----+----+----+----+
Y5 |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 | = 4
   +----+----+----+----+----+----+----+----+
Y6 |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 | = 5
   +----+----+----+----+----+----+----+----+  
Y7 |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 | = 6 
   +----+----+----+----+----+----+----+----+
Y8 |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 | = 7
   +----+----+----+----+----+----+----+----+ 

One idea could be, that each row has a value from 0 to 7... each line you can do shifts or something and calculate a result to store in a byte (for start and endpos...) thats very tricky and you must think very carefull about it... as long as you work with values from 0-7 it should be possible... good luck ^^

[dracflamloc]

best i could think of was down to 11 bits

000000 0000 0
newpos piece# color

[edit]

Unless you encode every possible move in chess as a #.

[Kaisen2100]

One idea could be, that each row has a value from 0 to 7... each line you can do shifts or something and calculate a result to store in a byte (for start and endpos...) thats very tricky and you must think very carefull about it... as long as you work with values from 0-7 it should be possible... good luck ^^

I dont understand you ...

[Kaeru Gaman]

@dracflamloc
good idea.
10bit will do, because the color is determined by the counter of the moves:
white is odd, black is even (or vice versa, if you start with move 0)
but sparing this 2 bits makes it just a bit more complicated.

I think about a struct to handle the nibbles of the first, 12bit example.

Code: Select all

Structure Moves
  Lo.b
  Mid.b
  Hi.b
EndStructure

this is a three byte struct wich can hold 2 moves = 1 round.

if you access it like a LONG for reading, you can access the four included positions by bitwise-and:

Code: Select all

Structure Moves
  Lo.b
  Mid.b
  Hi.b
EndStructure

Define Move.moves
Define *LongPointer.l
Define ActRound.l

*LongPointer = @Move
ActRound = PeekL(*LongPointer)

WhiteStart  = ( ActRound & %000000000000000000111111 )
WhiteFinish = ( ActRound & %000000000000111111000000 ) >> 6
BlackStart  = ( ActRound & %000000111111000000000000 ) >> 12
BlackFinish = ( ActRound & %111111000000000000000000 ) >> 18

I wrote the Bitmask in binary, to make obvious wich bits are accessed...

so you could set up an structures array, wich holds all moves and makes full use of this method to spare mem.
note that it is less performant than using a 4byte struct with 1 byte per position,
also because of the way memory is accessed, but it only needs 75% memory in total,
so if you want to store millions of moves it's the better choice, but only then.

also be aware that you have to be careful with writing:
if you write a complete long to the structured array, the Lo-byte of the following element is affected.
if you want to set up an exchange-struct to get data safely in and out of the array,
better use an aditional struct that makes sure the following, fourth byte is also correctly allocated.

[va!n]

Why do you want use 24 bit (3 bytes) to store x,y(start) and x,y(end) or a movement? Why not just only in 16 bit (2 bytes?) or just 8 bit (1 byte to handling x + y pos?)

This is one way i tried to explain in one my postings before... following example is just an idea and has potential to optimize!

Code: Select all

StartPosX = Byte1 %00001111   ; 0 to 15
StartPosY = Byte1 %11110000
EndPosX   = Byte2 %00001111
EndPosY   = Byte2 %11110000

or just...

StartPosX = %0000000000001111   ; 0 to 15
StartPosY = %0000000011110000
EndPosX   = %0000111100000000
EndPosY   = %1111000000000000

[dracflamloc]

Yea you are right, color isn't really needed depending on how you handle king's castling.

[Kaeru Gaman]

@Va!n
you don't get it.
you don't spare any room needed for information, if you split a position into coordinates.

Code: Select all

WhiteStartX  = %000000000000000000000111
WhiteStartY  = %000000000000000000111000
WhiteFinishX = %000000000000000111000000
WhiteFinishY = %000000000000111000000000
BlackStartX  = %000000000111000000000000
BlackStartY  = %000000111000000000000000
BlackFinishX = %000111000000000000000000
BlackFinishY = %111000000000000000000000

it's still 24bit for 1 round = 2 moves = 4 positions = 8 coordinates
this is the most compressed way the information can be strored, there is nothing beyond.

except a different concept like dracflamloc suggested,
to store not the starting position but the moving unit,
which will spare 2bit per move = 4bit per round.
but that method makes it even more complicated,
because you'll need a bit more cryptic struct,
4 moves (= 2rounds) equal 5 bytes.

PS:
for purposes like this I miss the Structure-possibilities like in C,
where I could name/access single Bits in a Union...

[dracflamloc]

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.

[Derek]

Why not just use two bytes, it's not like your average pc comes with the memory capacity of a zx81 for crying out loud.

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.

[Kaeru Gaman]

I already thought about this "possible moves" thing,
but I think it will take much more space than assumed.

take in account an empty board with only one unit on it,
to mesure the maxmoves of each unit.

e.g. the higher units can make 7 moves in each possible direction,
wich are 4 for the queen, 2 for bishop and tower.
knight has 8 moves, king 8, 4 each pawn...

....hmmmmm.... maybe it fits in 255

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

so it just fits into it, but if a pawn turns into a queen the whole system is smashed,
because that means a former 4-poss-unit turns into a 28-poss-unit....

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...

[edit]
that's right derek. it's more a "theory tea talk" here....
like I said above:
> so if you want to store millions of moves it's the better choice, but only then.