Represent the game state as a feature vector

[keithgw]

As part of the summarization and table transpositon strategies of #50 , the state of the game should be able to represented as a feature vector.

1. Decide the format of the feature vector
2. Implement a method that takes the current game state, and translates it into this feature vector.
3. Implement a method that takes a feature vector and translates it back to a valid game state. Inherently, information about hidden information will not be perfectly translated back to the game state, but this will still be useful for simualting playouts from the current state.

This is a dependency for #45

[keithgw]

Leveraging a combination of dictionary, frozenset, tuple, and base data types, the state can be represented in a way that is useful for a transposition table, for node representation, still human readable, is compact, and can be translated back to a valid and possible game state.

• phase: phase: str
• Bird: tuple(vp: int, cost: int)
• deck and player hand: frozenset({(bird: tuple(int, int), count: int)})
• tray: frozenset({bird: tuple(int, int), bird, bird)}) the tuple (0, 0) will stand for the empty slot
• gameboard: frozenset({bird: tuple(int, int), bird, ..., bird}) of size 5 and the tuple (0, 0) will stand for the empty slot
• food supply: count: int
• discard pile: count: int
• opponent: frozenset({('food_supply', count: int), ('cards_in_hand', count: int), ('game_board': frozenset({bird: tuple(int, int), bird, ..., bird}, ('turns_remaining', count: int)})

Some things to note:

• the order of the deck, hand, tray, or game boards doesn't matter. That is, different orderings should yield equivalent game states, since the order of play has no bearing on their cost or total victory points.
• This state representation allows a representation of partial information. For example, cards that have been seen and discarded can be removed from the deck, but the order of the deck is still unkown.
• This compacts the state space quite a bit by thinking of birds with the same vp and cost as equivalent.

Other options considered:

• embedding a hand/deck/tray. Using one hot encoding, and embedding of a hand can solve the variable length problem, and make adding and removing cost simple vector math. This wasn't preferred, as the chosen state representation is more human-readable. While a vector representation of the state will be required for training a value network, this representation need not be equivalent to the representation used for transposition tables and compactness.
• hashing. A FEN-like system from chess, or representing the state as a JSON object and then using the hash algorithm would have also worked. The chosen strategy uses the same premise: by keeping the data types to hashable types, the total state can be hashed, and then easily translated back to a dictionary for fast key lookup.

[keithgw]

Having a deck return its representation exactly is inappropriate, since some of this information is hidden to the player. The player can only know with certainty:

• the number of cards in the deck
• cards the player has seen - in hand or in the tray - cannot be in the deck

This suggests the deck and player hand should be represented differently. The same format frozenset({(bird: tuple(int, int), count: int)}) can still be used, but this should instead represent cards known to be missing from the deck, and in addition, it should have a count for cards in deck.

[keithgw]

Here is an outline for the conversion back and forth between representations and game states:

def to_representation(self):
    """Returns a representation of the game state."""
    state_dict = {
        'num_turns': self.num_turns,
        'num_players': self.num_players,
        'game_turn': self.game_turn,
        'phase': self.phase,
        'bird_deck': self.bird_deck.to_representation(),
        'discard_pile': self.discard_pile.to_representation(),
        'tray': self.tray.to_representation(),
        'bird_feeder': self.bird_feeder.to_representation(),
        'players': [player.to_representation() for player in self.players]
    }
    return frozenset(state_dict.items())

@classmethod
def from_representation(cls, representation):
    """Reconstructs the game state from a representation."""
    state_dict = dict(representation)
    bird_deck = BirdDeck.from_representation(state_dict['bird_deck'])
    discard_pile = DiscardPile.from_representation(state_dict['discard_pile'])
    tray = Tray.from_representation(state_dict['tray'])
    bird_feeder = BirdFeeder.from_representation(state_dict['bird_feeder'])
    players = [Player.from_representation(player_repr) for player_repr in state_dict['players']]
    return cls(state_dict['num_turns'], state_dict['num_players'], state_dict['game_turn'], state_dict['phase'], bird_deck, discard_pile, tray, bird_feeder, players)

[keithgw]

For the simplest representation, represent the deck as a count. Updating for known missing cards #58 #55 can be handled as an enhancement later.

[keithgw]

Having a game state specific to MCTS that can construct a valid game state is creating a circular import loop. It probably makes sense to create an MCTSGameState that inherits from GameState and adds the methods necessary to translate between representation. This also begs the question if all other classes that have a to_representation method should be a subclass with the additional representation method.

[keithgw]

64