Limited-Information Game
(Redirected from Imperfect Information Game)
A Limited-Information Game is a game in which some player information is private information (to game opponents).
- AKA: Imperfect Information Game.
- Context:
- It can typically involve Information Hiding through limited-information game private state.
- It can typically require Probabilistic Reasoning about limited-information game hidden elements.
- It can typically enable Strategic Deception through limited-information game information asymmetry.
- It can typically feature Belief Formation about limited-information game opponent knowledge.
- It can typically support Mixed Strategy development for limited-information game optimal play.
- It can typically create Decision Uncertainty due to limited-information game incomplete knowledge.
- ...
- It can often include Bluffing Mechanics through limited-information game strategic misrepresentation.
- It can often involve Psychological Elements like limited-information game opponent modeling.
- It can often feature Information Revelation through limited-information game sequential play.
- It can often require Risk Management of limited-information game probabilistic outcomes.
- It can often incorporate Social Interaction through limited-information game player communication.
- It can often utilize Bayesian Updating of limited-information game belief states.
- ...
- It can range from being a Deterministic Limited-Information Game to being a Stochastic Limited-Information Game, depending on its limited-information game chance element.
- It can range from being a Partial-Information Limited-Information Game to being a Mostly-Hidden Limited-Information Game, depending on its limited-information game information visibility level.
- It can range from being a Strict Limited-Information Game to being a Fuzzy Limited-Information Game, depending on its limited-information game information certainty.
- It can range from being a Two-Player Limited-Information Game to being a Multi-Player Limited-Information Game, depending on its limited-information game participant count.
- It can range from being a Zero-Sum Limited-Information Game to being a Non-Zero-Sum Limited-Information Game, depending on its limited-information game outcome distribution.
- It can range from being a Sequential Limited-Information Game to being a Simultaneous Limited-Information Game, depending on its limited-information game turn structure.
- ...
- It can be studied by Games Research to advance limited-information game theoretical understanding.
- It can serve as AI Development Challenge for limited-information game playing algorithms.
- It can model Real-World Decision Making under limited-information game uncertainty conditions.
- It can represent Economic Scenarios with limited-information game asymmetric information.
- It can facilitate Strategic Thinking development through limited-information game probabilistic reasoning.
- ...
- Examples:
- Card-Based Limited-Information Games, such as:
- Poker Limited-Information Games, such as:
- Trick-Taking Limited-Information Games, such as:
- Set Collection Limited-Information Games, such as:
- Board-Based Limited-Information Games, such as:
- Hidden Unit Limited-Information Games, such as:
- Deduction Limited-Information Games, such as:
- Clue (Cluedo) requiring limited-information game logical elimination.
- Mastermind featuring limited-information game pattern discovery.
- Computer-Based Limited-Information Games, such as:
- Strategy Limited-Information Games, such as:
- Electronic Card Limited-Information Games, such as:
- Single-Player Limited-Information Games, such as:
- Economic Limited-Information Games, such as:
- ...
- Card-Based Limited-Information Games, such as:
- Counter-Examples:
- Perfect Information Games, such as:
- Chess Game where all game pieces and game positions are visible to both players.
- Go Game where the entire game board state is observable throughout play.
- Checkers Game where all game moves are visible and no information is hidden.
- Trivial Information Games, such as:
- Tic-Tac-Toe with extremely limited game state space and fully visible game position.
- Connect Four where all game pieces and game moves are completely transparent.
- Pure Chance Games, such as:
- Dice Games like Craps that depend entirely on random outcome rather than strategic information use.
- Lottery Games that have no hidden information but rather complete randomness.
- Perfect Information Games, such as:
- See: Prisoners Dilemma, Game Theory, Nash Equilibrium, Information Asymmetry, Bayesian Game, Mixed Strategy, Decision Under Uncertainty.
References
2017
- (Silver, 2017) ⇒ David Silver. (2017). “Technical Perspective: Solving Imperfect Information Games.” In: Communications of the ACM Journal, 60(11). doi:10.1145/3131286
- QUOTE: Most of this research focused on perfect information games, in which all events are observed by all players, … However, many applications in the real world have imperfect information: each agent observes different events. This leads to the possibility of deception and a wealth of social strategies. Imperfect information games provide a microcosm of these social interactions, while abstracting away the messiness of the real world.
Among imperfect information games, Poker is the most widely studied — the latest drosophila—due to its enormous popularity and strategic depth. The smallest competitively played variant by humans, and the most widely played by computers, is the two-player game known as Heads-Up Limit Hold'Em (HULHE), in which each player holds two private cards in addition to five public cards. Two decades of research in this game has led to powerful methods, such as counterfactual regret minimization (CFR), for approximating a Nash equilibrium. Several years ago, a program called Polaris — created by many of the authors of the following paper —defeated for the first time a human professional poker player in HULHE.
- QUOTE: Most of this research focused on perfect information games, in which all events are observed by all players, … However, many applications in the real world have imperfect information: each agent observes different events. This leads to the possibility of deception and a wealth of social strategies. Imperfect information games provide a microcosm of these social interactions, while abstracting away the messiness of the real world.
2016
- (Heinrich & Silver, 2016) ⇒ Johannes Heinrich, and David Silver. (2016). “Deep Reinforcement Learning from Self-play in Imperfect-information Games.” In: Proceedings of NIPS Deep Reinforcement Learning Workshop.
- QUOTE: Many real-world applications can be described as large-scale games of imperfect information. To deal with these challenging domains, prior work has focused on computing Nash equilibria in a handcrafted abstraction of the domain. In this paper we introduce the first scalable end-to-end approach to learning approximate Nash equilibria without prior domain knowledge. Our method combines fictitious self-play with deep reinforcement learning. When applied to Leduc poker, Neural Fictitious Self-Play (NFSP) approached a Nash equilibrium, whereas common reinforcement learning methods diverged. In Limit Texas Holdem, a poker game of real-world scale, NFSP learnt a strategy that approached the performance of state-of-the-art, superhuman algorithms based on significant domain expertise.
2014
- http://en.wikipedia.org/wiki/Game_theory#Perfect_information_and_imperfect_information
- … Many card games are games of imperfect information, such as poker or contract bridge.
Perfect information is often confused with complete information, which is a similar concept. Complete information requires that every player know the strategies and payoffs available to the other players but not necessarily the actions taken. Games of incomplete information can be reduced, however, to games of imperfect information by introducing “moves by nature” Template:Leyton-Brown.
- … Many card games are games of imperfect information, such as poker or contract bridge.