Chess Move Compression • Hacker News Board

Re: Chess Move Compression

#31

Post by level3 » Thu, Nov 12, 2015, 3:49 PM UTC

Very interesting! But I don't quite see why you need to bother with tracking pieces and swapping them. Can't you just go by the convention that pawn 0 is the first pawn you find when scanning across from a1 to h8, pawn 1 is the second pawn, etc.? Similarly for the knights, bishops, and rooks? (obviously still using the fallback when necessary)

That would eliminate the need for computing swaps while still producing the same move code for a given move in a given position.

Re: Chess Move Compression

#32

Post by billforsternz » Thu, Nov 12, 2015, 10:38 PM UTC

slm_HN wrote: post #17

Chess move compression was an interesting topic back when the games were stored on 360k floppy disks. Nowadays every master chess game ever played in the history of chess fits easily on one DVD, uncompressed. So it's not clear what the point of compressing the moves, especially since at some points the article is concerned about size and sometimes about speed. If it's just an intellectual exercise then consider the f…

Too late to edit my earlier reply, so I'll reply again instead. I've subsequently learned more, mainly from a discussion with "mxtppy" in the programming subreddit. I've updated my blog post with a new section "One Move in 2 Bits, Maybe?" to reflect my improved understanding.

Re: Chess Move Compression

#33

Post by billforsternz » Fri, Nov 13, 2015, 11:02 PM UTC

level3 wrote: post #31

Very interesting! But I don't quite see why you need to bother with tracking pieces and swapping them. Can't you just go by the convention that pawn 0 is the first pawn you find when scanning across from a1 to h8, pawn 1 is the second pawn, etc.? Similarly for the knights, bishops, and rooks? (obviously still using the fallback when necessary) That would eliminate the need for computing swaps while still producing th…

This would work but it requires a scan of the whole board for pawn (and knight and rook) moves. I wanted (and eventually got - after a lot of mistakes along the way) a system which would use negligible CPU cycles for almost all moves.

Re: Chess Move Compression

#34

Post by billforsternz » Fri, Nov 13, 2015, 11:05 PM UTC

meta_AU wrote: post #21

I'd suggest a slight change. Code all the pawns into 2 'pieces' and have a special piece for promoting. The 16 moves for the special piece can be an index from a list of possible promotions which is easier to generate and canonicalise than the total move list. This frees up 5 pieces for promoted queens. You could special case the king into the spare entropy in the rooks and bishops to save one more piece.

I don't think that would work (but possibly I misunderstand!). The system cannot cope with (up to, if all 8 pawns stood on the 7th rank) 8 more pieces! The fact that the queen needs 1 more 'piece' already requires a certain amount of ingenuity to work around.

Re: Chess Move Compression

#35

Post by level3 » Sun, Nov 15, 2015, 3:27 AM UTC

billforsternz wrote: post #33

level3 wrote: post #31

Very interesting! But I don't quite see why you need to bother with tracking pieces and swapping them. Can't you just go by the convention that pawn 0 is the first pawn you find when scanning across from a1 to h8, pawn 1 is the second pawn, etc.? Similarly for the knights, bishops, and rooks? (obviously still using the fallback when necessary) That would eliminate the need for computing swaps while still producing th…

This would work but it requires a scan of the whole board for pawn (and knight and rook) moves. I wanted (and eventually got - after a lot of mistakes along the way) a system which would use negligible CPU cycles for almost all moves.

That makes sense. I'm probably underestimating the amount of cycles saved by your swap method.