[Discussion] Alternative State Encodings

[dglmoore]

This is an open discussion. Please comment with your thoughts on the matter.

Overview

As @EnricoBorriello has pointed out, the network state encoding we use is somewhat unorthodox: given an array of node states, lower indexed states have a lower bit value, call it the Lowest Index - Lowest Bit encoding (LILB). For example, in a three-dimensional binary state space, states are encoding/decoded using the following map:

0 ↔ [0,0,0]
1 ↔ [1,0,0]
2 ↔ [0,1,0]
3 ↔ [1,1,0]
4 ↔ [0,0,1]
5 ↔ [1,0,1]
6 ↔ [0,1,1]
7 ↔ [1,1,1].

Some people find this surprising as they would expect the decoded states to be reversed:

0 ↔ [0,0,0]
1 ↔ [0,0,1]
2 ↔ [0,1,0]
3 ↔ [0,1,1]
4 ↔ [1,0,0]
5 ↔ [1,0,1]
6 ↔ [1,1,0]
7 ↔ [1,1,1].

Call this the Lowest Index - Highest Bit encoding (LIHB).

The choice of which encoding to use no technical impact on the results, but it could be unintuitive to users. The decision to use LILB encoding stems from our implementation of the StateSpace.__iter__ method. This method allows the user to iterate over the decoded states of the state space. The states are produced in the LILB ordering to so that the follow holds:

>>> space = StateSpace(10)
>>> list(space) === list(map(space.decode, range(0, space.volume)))
True

The StateSpace.__iter__ algorithm is easier to implement in this ordering, but could be implemented using any alternative ordering. Regardless of which encoding we chose, the StateSpace.__iter__, StateSpace.encode and StateSpace.decode methods should be implemented so to satisfy the above condition.

Possible Encodings

1. Lowest Index - Lowest Bit (current implementation)
2. Lowest Index - Highest Bit (@EnricoBorriello's preferred encoding)
3. Gray Code (Maybe @Zhangyanbo would like this?)
4. Allow the user to choose the encoding. (My preferred option)