Limits of Poker AI and State Space 00:00
- Research on AI in games like poker has been advanced due to manageable state spaces with limited hidden information.
- In heads-up no-limit Texas Holdem, there are 1,326 possible states due to two hidden cards per player.
- When playing six-handed poker, the number of possible hidden states increases linearly with more players, but remains computationally tractable.
- AI for poker works by enumerating all possible states, assigning probabilities, and using neural nets for action selection.
- As the number of hidden cards increases (as in Omaha poker), or in games with exponentially more possible states (like Stratego with 40 factorial states), these poker-based approaches become unworkable.
Challenges for AI in Complex Games Like Magic the Gathering 01:36
- Existing poker AI techniques do not work "out of the box" for games with vast state spaces such as Magic the Gathering or Stratego.
- There is ongoing research on coping with high-complexity hidden-information games, as enumerative approaches break down at large scales.
- Model-free reinforcement learning (RL) does not suffer from the same state space explosion and may be adaptable for superhuman play in Magic the Gathering.
- The more promising avenue is developing general reasoning AI approaches that are not restricted by the limitations of poker-style search techniques.
- With progress in general reasoning and RL, an AI capable of superhuman Magic the Gathering gameplay is expected to emerge eventually.