Paranoid algorithm
In combinatorial game theory, the paranoid algorithm is an algorithm that aims to improve the alpha-beta pruning capabilities of the maxn algorithm by making the player p chosen to maximize the score "paranoid" of the other players by assuming they are cooperating to minimize p's score, thus minimizing any n-player game to a two-player game by making the opposing player the sum of the other player's scores. This returns the game to a zero-sum game and makes it analyzable via any optimization techniques usually applied in pair with the minimax theorem.[1] It performs notably faster than the maxn algorithm because of those optimizations.[2]
See also
- Maxn algorithm
- Minimax algorithm
References
- ^ Sturtevant, Nathan; Korf, Richard (30 July 2000). "On Pruning Techniques for Multi-Player Games" (PDF). AAAI-00 Proceedings: 201–207.
- ^ Sturtevant, Nathan (2003). "A Comparison of Algorithms for Multi-player Games". Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 108–122. doi:10.1007/978-3-540-40031-8_8. ISBN 978-3-540-20545-6.
- v
- t
- e
- Congestion game
- Cooperative game
- Determinacy
- Escalation of commitment
- Extensive-form game
- First-player and second-player win
- Game complexity
- Graphical game
- Hierarchy of beliefs
- Information set
- Normal-form game
- Preference
- Sequential game
- Simultaneous game
- Simultaneous action selection
- Solved game
- Succinct game
- Mechanism design
concepts
- Bayes correlated equilibrium
- Bayesian Nash equilibrium
- Berge equilibrium
- Core
- Correlated equilibrium
- Coalition-proof Nash equilibrium
- Epsilon-equilibrium
- Evolutionarily stable strategy
- Gibbs equilibrium
- Mertens-stable equilibrium
- Markov perfect equilibrium
- Nash equilibrium
- Pareto efficiency
- Perfect Bayesian equilibrium
- Proper equilibrium
- Quantal response equilibrium
- Quasi-perfect equilibrium
- Risk dominance
- Satisfaction equilibrium
- Self-confirming equilibrium
- Sequential equilibrium
- Shapley value
- Strong Nash equilibrium
- Subgame perfection
- Trembling hand equilibrium
of games
- Go
- Chess
- Infinite chess
- Checkers
- All-pay auction
- Prisoner's dilemma
- Gift-exchange game
- Optional prisoner's dilemma
- Traveler's dilemma
- Coordination game
- Chicken
- Centipede game
- Lewis signaling game
- Volunteer's dilemma
- Dollar auction
- Battle of the sexes
- Stag hunt
- Matching pennies
- Ultimatum game
- Electronic mail game
- Rock paper scissors
- Pirate game
- Dictator game
- Public goods game
- Blotto game
- War of attrition
- El Farol Bar problem
- Fair division
- Fair cake-cutting
- Bertrand competition
- Cournot competition
- Stackelberg competition
- Deadlock
- Diner's dilemma
- Guess 2/3 of the average
- Kuhn poker
- Nash bargaining game
- Induction puzzles
- Trust game
- Princess and monster game
- Rendezvous problem
- Aumann's agreement theorem
- Folk theorem
- Minimax theorem
- Nash's theorem
- Negamax theorem
- Purification theorem
- Revelation principle
- Sprague–Grundy theorem
- Zermelo's theorem
figures
- Albert W. Tucker
- Amos Tversky
- Antoine Augustin Cournot
- Ariel Rubinstein
- Claude Shannon
- Daniel Kahneman
- David K. Levine
- David M. Kreps
- Donald B. Gillies
- Drew Fudenberg
- Eric Maskin
- Harold W. Kuhn
- Herbert Simon
- Hervé Moulin
- John Conway
- Jean Tirole
- Jean-François Mertens
- Jennifer Tour Chayes
- John Harsanyi
- John Maynard Smith
- John Nash
- John von Neumann
- Kenneth Arrow
- Kenneth Binmore
- Leonid Hurwicz
- Lloyd Shapley
- Melvin Dresher
- Merrill M. Flood
- Olga Bondareva
- Oskar Morgenstern
- Paul Milgrom
- Peyton Young
- Reinhard Selten
- Robert Axelrod
- Robert Aumann
- Robert B. Wilson
- Roger Myerson
- Samuel Bowles
- Suzanne Scotchmer
- Thomas Schelling
- William Vickrey
- Alpha–beta pruning
- Aspiration window
- Principal variation search
- max^n algorithm
- Paranoid algorithm
- Lazy SMP
This mathematical analysis–related article is a stub. You can help Wikipedia by expanding it. |
- v
- t
- e
This game theory article is a stub. You can help Wikipedia by expanding it. |
- v
- t
- e