Integer Game Notation (IGN) William Entriken / 2008 / ws@phor.net

Integer Game Notation is a way to represent the full state of any perfect information game. This method maps all nodes in the game tree to an integer. An example is shown for chess and could be useful in opening book or database applications.


Encode algorithm

  1. Set IGN=0, PRODUCT=1 and the game to its opening position
  2. Let MOVES equal an ordered list of possible moves from this position
  3. IGN += PRODUCT * the ordinal of the chosen move in MOVES (one-indexed)
  4. PRODUCT *= the cardinality of MOVES
  5. If there are more moves, goto 2
implementation in PHP

Decode algorithm

  1. Set game to its opening position, IGN is given
  2. Let MOVES equal an ordered list of possible moves from this position
  3. If IGN = 0 and the cardinality of MOVES is greater than 1, then this algorithm ends
  4. IGN % the cardinality of MOVES is the current move (zero wraps around to the last element of MOVES)
  5. IGN /= the cardinality of MOVES (round down)
  6. Goto 2
implementation in PHP

Implementation for chess

To encode and decode, moves must be ordered. For chess, I have chosen this way to order moves:

  1. Origin rank
  2. Origin file
  3. Destination rank
  4. Destination file
  5. Promotion piece: B, N, Q, R

convert PGN to IGN, convert IGN to PGN

Example:

[Event "F/S Return Match"]
[Site "Belgrade, Serbia JUG"]
[Date "1992.11.04"]
[Round "29"]
[White "Fischer, Robert J."]
[Black "Spassky, Boris V."]
[Result "1/2-1/2"]
 
1.e4 e5 2.Nf3 Nc6 3.Bb5 {This opening is called the Ruy Lopez.} 3...a6
4.Ba4 Nf6 5.O-O Be7 6.Re1 b5 7.Bb3 d6 8.c3 O-O 9.h3 Nb8  10.d4 Nbd7
11.c4 c6 12.cxb5 axb5 13.Nc3 Bb7 14.Bg5 b4 15.Nb1 h6 16.Bh4 c5 17.dxe5
Nxe4 18.Bxe7 Qxe7 19.exd6 Qf6 20.Nbd2 Nxd6 21.Nc4 Nxc4 22.Bxc4 Nb6
23.Ne5 Rae8 24.Bxf7+ Rxf7 25.Nxf7 Rxe1+ 26.Qxe1 Kxf7 27.Qe3 Qg5 28.Qxg5
hxg5 29.b3 Ke6 30.a3 Kd6 31.axb4 cxb4 32.Ra5 Nd5 33.f3 Bc8 34.Kf2 Bf5
35.Ra7 g6 36.Ra6+ Kc5 37.Ke1 Nf4 38.g3 Nxh3 39.Kd2 Kb5 40.Rd6 Kc5 41.Ra6
Nf2 42.g4 Bd3 43.Re6 1/2-1/2
Result: 7194381939026059815816432728404500838835011451049668943765896734611284670867176530570061223664286778997380554654077775346194 (412 bits)
1.f3 e5 2.g4 Qh4#
Result: 143395 (18 bits)

Benefits

Caveats