MCTS Transposition Table

• Transposition table
  • Identify two identical game states
  • Merge them to only one tree node
• Notes
  • Hidden information is present
    • Typical approach on Go cannot be applied
  • The path of the tree node actually matters
    • Need to carefully chosen which two nodes can be merged
    • For example:
      • One tree node T1:
        • Player A plays A1
        • Player B plays a secret B (hidden information: B1)
          • This is a tactical strategy, since player A played A1
        • Player A plays A2
      • Another tree node T2:
        • Player A plays A2
        • Player B plays a secret B (hidden information: B2)
          • This is a tactical strategy, since player A played A2
        • Player A plays A1
      • Now, the game states are THE SAME to player A
        • But these two nodes should NOT be combined
        • Since player B's action depends on the game states at that time
• Definition of identical states
  • Learn something from the example above:
    • The current game state by itself is not enough
    • The parent nodes are informative
  • Key idea:
    • We can detect identical states as long as they are ALL performed by the same player
      • The opponent does not perform any action
• Implementation
  • A transposition table is shared among the subtree ST1
    • The actions in subtree ST1 are ALL performed by the same player
    • Create another transposition table when switched to another player
  • Implemented by a tree node addon
• Discussions
  • Does this help?
    • The order of minion playing can be detected
    • Many actions can be re-ordered without any difference. Those can all be detected
  • Test game state equality with careful
    • Game states contains minions' attack/hp/max-hp
    • if an enchantment attached to a minion, but not modify its attack/hp/max-hp
      • Maybe a event-hooked enchantment like 'draw a card when attacking'
      • Or, deathrattles
    • the equality test should be able to detect this
    • Quick solution
      • An enchantment count
      • A deathrattle count