Let N be a number initialized to zero. Consider the moves of a go 囲碁 game in reverse order.
Multiply N by s, the number of empty spaces currently available. Add a number 0 through s-1 corresponding to which empty space was taken for the move. This is variable base representation.
Decode in forward order by quotient and remainder. Is there a way to do it without originally encoding the moves in reverse order? Arithmetic coding. Perhaps p-adic. The key point is the number of moves available is not known (because of potential captures) until all the previous moves have been played.
One can make this scheme more sophisticated by not just counting empty spaces but only moves not prohibited by ko or suicide. In theory, one must also encode passes.
The motivation was to very densely encode a go game as a printed QR code. Approximately 2000 bits or 300 bytes.
Any game, such as chess, can be encoded this way, assuming a canonical ordering of moves.
In reverse, any number can be steganographically encoded as a game. For chess, both sides could use identical deterministic engines to select only moves within a point of best playing at an agreed level. This results in games being not nonsensical.
In the original direction, use an engine to establish a prior probability of moves for even denser arithmetic coding (of real games). It suggests a game database compression contest.
No comments :
Post a Comment