Efficient encoding of game notation - IGN

46 views
Skip to first unread message

Will Entriken

unread,
May 25, 2008, 11:27:30 PM5/25/08
to
IGN - Integer game notation

Integer game notation is a maching-readible way to store a game state
by encoding each move sequentially.

This done very efficiently because at each point in the game there is
a limited (and different) number of possible moves. Each of these
moves is encoded as efficiently as possible.

The algorithm to encode is (IGN starts at 0, product starts at 1, the
game starts in the original state):

1. Enumerate and sort the possible moves in this game state
2. IGN += the index of the current move of all possible moves (zero-
indexed)
3. product *= the number of possible moves in this game state
4. Commit the move in the game
5. repeat...

... and to decode

1. Enumerate and sort the possible moves in this game state
2. IGN % the number of all possible moves is the current move
3. IGN /= the number of possible moves in this game state (round
down)

---------

More text: http://debug.phor.net/PUB/chess/ign
Proof of concept (encoding): http://debug.phor.net/PUB/chess/pgnign
Proof of concept (decoding): http://debug.phor.net/PUB/chess/ignpgn

----------

David Richerby

unread,
May 26, 2008, 9:47:50 AM5/26/08
to
Will Entriken <fulld...@gmail.com> wrote:
> IGN - Integer game notation
>
> Integer game notation is a maching-readible way to store a game
> state by encoding each move sequentially.

Why bother? Discs are huge and you're sacrificing the human
readability of PGN for a saving of at most a factor of ten or so. If
your disc is small, just compress the PGN file -- PGN compresses like
a dream because it's so repetitive.

> The algorithm to encode is (IGN starts at 0, product starts at 1, the
> game starts in the original state):
>
> 1. Enumerate and sort the possible moves in this game state
> 2. IGN += the index of the current move of all possible moves (zero-
> indexed)
> 3. product *= the number of possible moves in this game state
> 4. Commit the move in the game
> 5. repeat...

Huh? Are the two numbers "IGN" and "product" supposed to somehow
uniquely represent the game? They don't. There are twenty legal
moves for white at the start of the game and twenty legal replies to
black for each of them. Let's assume that the enumeration of the
legal white moves is a3, a4, b3, b4, ... and the enumeration of the
black replies is a6, a5, b6, b5, ... . Then the games 1.a3 a5 and
1.a4 a6 both set IGN to 3 and product to 400.


Dave.

--
David Richerby Strange Electronic Atom Bomb (TM):
www.chiark.greenend.org.uk/~davidr/ it's like a weapon of mass destruction
but it uses electricity and it's
totally weird!

Reply all
Reply to author
Forward
0 new messages