Hacker News new | ask | show | jobs
by mcherm 263 days ago
That's a fine upper bound, but it doesn't minimize but usage since it also can represent illegal positions.
2 comments

While this is an upper bound for a "board position", it should be noted that it is not an upper bound for a "game state". That includes the (unbounded) whole board position history because of the threefold repetition rule. If you ignore that (and the fifty-move rule which can alternatively be kept using a six-bit counter), you also need the castling state and the en passant state. Plus one bit of the player on move, obviously :-)
The vast majority of the positions are illegal. There is only 1 black king on the board; practically all of the represented positions have more than one. And there are over a dozen kinds of pieces to repeat that for. A better upper bound is almost 100 orders of magnitude smaller.