nvidia-AI.summerschool17-no.../teaching-ncso/95-game-theory.ipynb
2017-09-22 19:38:09 +02:00

659 lines
No EOL
25 KiB
Text

{
"metadata": {
"name": "95-game-theory"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Games, Agents, Decisions\n",
"================\n",
"\n",
"We view the world as divided into:\n",
"\n",
"- nature\n",
"- agents\n",
"\n",
"What are agents?\n",
"\n",
"- autonomous\n",
"- interactive (with environment and each other)\n",
"- frequently\n",
" - intelligent\n",
" - goal-directed\n",
" - rational\n",
"\n",
"Examples of agents:\n",
"\n",
"- humans\n",
"- computer programs\n",
"- nations\n",
"- animals\n",
"- cells\n",
"\n",
"Fields of study:\n",
"\n",
"- **Decision Theory** - decision making by rational, intelligent agent against nature\n",
"- **Game Theory** - decision making by rational, intelligent agents against other rational, intelligent agents\n",
"\n",
"Other related fiels:\n",
"\n",
"- economics\n",
"- psychology\n",
"- evolutionary biology\n",
"- artificial intelligence\n",
"- computer security\n",
"\n",
"We're not going to formalize _agent theory_ any more in this lecture.\n",
"\n",
"We are going to focus on _game theory_, that is, mathematical theories\n",
"of how rational, intelligent agents can interact in order to achieve goals.\n",
"\n",
"What are the goals of game theory?\n",
"\n",
"- understand and model the behavior of existing multiagent systems\n",
"- design strategies to succeed against opponents\n",
"- design systems consisting of multiple agents that achieve a common goal"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Formalization of Games\n",
"======================\n",
"\n",
"_Games_ consist of a sequence of _turns_ that the _players_ (agents) take.\n",
"\n",
"At each turn, a player has a choice among a number of _moves_.\n",
"\n",
"At the end of the game, there is a _payoff_.\n",
"\n",
"Many games in game theory have only very few moves.\n",
"\n",
"Games like chess or Go can also be analyzed in this kind of framework.\n",
"However, for chess or Go, computational challenges are dominant over the mathematical challenges;\n",
"if computation were free, chess or Go would be trivial games from the point of game theory.\n",
"\n",
"The rules each agent has for making choices are called his _strategy_.\n",
"\n",
"Strategies may be deterministic (_pure strategies_) or randomized (_mixed strategies_).\n",
"\n",
"Extensive Form Games\n",
"------------------------\n",
"\n",
"Moves in game theory can be represented in a form similar to a decision tree:\n",
"\n",
"<img src=\"http://upload.wikimedia.org/wikipedia/commons/thumb/b/be/Ultimatum_Game_Extensive_Form.svg/800px-Ultimatum_Game_Extensive_Form.svg.png\" width=500px>\n",
"\n",
"This is called an _extensive form game_ representation:\n",
"\n",
"- in the first move, the first player chooses either F/U\n",
"- in the second move, the second player chooses either A/R\n",
"- the moves available to the second player are independent of the first move, but that is not necessarily so\n",
"- after each player has made his choice, the payoff can be found at the leaves:\n",
" - for the sequence of moves 1:F 2:A, the firs tplayer receives a payoff of 5, and the second player receives a payoff of 5 as well\n",
"- each player sees all the preceding moves\n",
"\n",
"What can you say around this game?\n",
"\n",
"What is the best choice for player 1 if he wants to maximize his payoff?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Normal Form Games\n",
"-------------------\n",
"\n",
"_Normal form games_ are usually represented as a matrix:\n",
"\n",
"![normal form game](https://lh5.googleusercontent.com/-Lu0DxnhHtuc/UAR15xvBuDI/AAAAAAAAJh0/Wpc5nv8FHUY/s357/1342469610018.png)\n",
"\n",
"For these games, each player makes their choice simultaneously, without knowing the other player's move.\n",
"\n",
"So, the essential question is: \n",
"\n",
"- you make a move in order to achieve your goals\n",
"- your opponent makes moves in order to achieve their goals\n",
"- both of you know the payoff matrix\n",
"- you don't know what your opponent is going to do\n",
"\n",
"This differs very much from decision making in Bayesian decision theory\n",
"\n",
"- Bayesian decision theory: uncertainty due to randomness\n",
"- game theory: uncertainty due to opponent's choice\n",
"\n",
"So, in that normal form game above, what move should you make if you are Player 1?\n",
"\n",
"Bounded Rationality\n",
"--------------------\n",
"\n",
"Players have...\n",
"\n",
"- _limited information_ (uncertainty)\n",
"- _limited time to make a decision_ (computational limitation)\n",
"\n",
"Frequent constraints in AI:\n",
"\n",
"- real time control with small processors\n",
"- pattern recognition / object recognition with limited training data\n",
"- exponential complexity of some algorithms\n",
"\n",
"Research Questions for AI/CS\n",
"----------------------------\n",
"\n",
"- efficient algorithms for finding game theoretic solutions\n",
"- algorithmic constraints, limits\n",
"- design of multi-agent based algorithms, distributed computations\n",
"- applications to computer security\n",
"- ..."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Prisoner's Dilemma\n",
"===================\n",
"\n",
"Consider the following game:\n",
"\n",
"![prisoner's dilemma](https://lh5.googleusercontent.com/-R_JrTc92cbY/UASARD58ezI/AAAAAAAAJiI/cGmvFCZRJK8/s576/1342472256.png)\n",
"\n",
"\"Defect\" means tell the police what they want to know, \"cooperate\" means cooperate with the other prisoner.\n",
"\n",
"Assume that A and B are each only motivated by self-interest. \n",
"\n",
"(When would this not be the case? Repeated games or cooperation in other areas.)\n",
"\n",
"Individual View\n",
"------------------\n",
"\n",
"For both A and B, defecting is a _dominant strategy_:\n",
"\n",
"- if A defects, then:\n",
" - if B has defected, the sentence is reduced from 1 year to 3 months\n",
" - if B has cooperated, then the sentence is reduced from 1 month to nothing\n",
"- (analogous for B)\n",
"\n",
"There are two forms of domination:\n",
"\n",
"- _strong domination_: all outcomes are better for this strategy than other strategies\n",
"- _weak domination_: no outcome is worse for this strategy than other strategies\n",
"\n",
"Quality of Global Outcome\n",
"------------\n",
"\n",
"Domination is related to individual decision making.\n",
"\n",
"In economics, we are also interested in the question: is this the best outcome for all?\n",
"\n",
"- an outcome is _Pareto optimal_ if there is no outcome that _all_ players would prefer\n",
"- an outcome is _Pareto dominated_ if there is some outcome that _all_ players would prefer\n",
"\n",
"Actual Global Outcome\n",
"---------------------\n",
"\n",
"So, the question is now: if people act according to their individual interests, what is\n",
"the global outcome? This is the question of the _equilibrium_ that is reached in the game.\n",
"\n",
"Every game like the prisoner dilemma has an equilibrium, the _Nash equilibrium_:\n",
"\n",
"- in this case, we have a _dominant strategy equilibrium_\n",
"- other games have equilibria but not based on dominant strategies\n",
"\n",
"In this case:\n",
"\n",
"- the Nash equilibrium is for both players to \"defect\"\n",
"- the Pareto optimal outcome would be for both players to \"cooperate\"\n",
"\n",
"Therefore:\n",
"\n",
"**Even though each player acts rationally, they do not achieve the globally optimal outcome.**\n",
"\n",
"Where might you apply this?\n",
"\n",
"Note that this outcome depends on making the decisions independently.\n",
"Information, communication, and coordination are important in game theory."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"More Games\n",
"===========\n",
"\n",
"Zero Sum Games\n",
"--------------\n",
"\n",
"One player's win is another player's loss.\n",
"\n",
"Economic transactions sometimes are often of this form, but often are not (zero sum fallacy).\n",
"\n",
"<img width=300 src=\"https://lh6.googleusercontent.com/-Kef5w7yo1fs/UAUk34a1lUI/AAAAAAAAJi0/n0VkiOAbLvs/s179/1342514394.png\">\n",
"\n",
"Observe about this:\n",
"\n",
"- pure strategies don't work\n",
"- the solution is to _randomize_ choices\n",
"- players 1 and 2 choose each move with some probability\n",
"- each player minimizes the maximum expected loss\n",
"- can be transformed into a linear programming problem\n",
"\n",
"Revelation Game\n",
"---------------\n",
"\n",
"The Relevation Game (a version of Pascal's wager), played between human (H) and a superior being (SB)\n",
"\n",
"SB preferences:\n",
"\n",
"- (1) wants belief\n",
"- (2) prefers not to reveal\n",
"\n",
"H preferences:\n",
"\n",
"- (1) wants confirmation\n",
"- (2) benefits from faith over disbelief\n",
"\n",
"Questions\n",
"\n",
"- What is the payoff matrix? \n",
"- What is the dominant strategy for each player?\n",
"- Are the assumptions/costs reasonable? What are the different regimes?\n",
"\n",
"General Classification of Games\n",
"------------------------------\n",
"\n",
"There are many such simple two person games, depending on the relative payoffs players receive.\n",
"\n",
"<img src=\"https://lh3.googleusercontent.com/-52U7uOatIpg/UAUeo0yS3ZI/AAAAAAAAJiY/c4uYEEgAlYU/s512/1342512794.png\">\n",
"\n",
"<img src=\"https://lh5.googleusercontent.com/-Mf3sY-aR_X8/UAUev0gUyrI/AAAAAAAAJig/fpxXhZ6Sovk/s512/1342512826.png\">"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Games Humans Play\n",
"=========\n",
"\n",
"- sequential games with perfect information - combinatorial game theory\n",
" - chess\n",
" - Go\n",
" - ...\n",
"- games of chance\n",
" - roulette\n",
" - poker\n",
" - ...\n",
"\n",
"Video games?\n",
"\n",
"Behavioral Game Design\n",
"=======================\n",
"\n",
"Goal of commercial computer games: _sales_ and _revenue_\n",
"\n",
"Approach to design is based on behavioral psychology:\n",
"\n",
"- 1950's: rats pressing a lever and randomly rewarded will keep pressing\n",
"- psychological reinforcment part of game mechanics (accidentally or deliberately)\n",
"- reinforcement schedule can be optimized in order to maximize player engagement\n",
"\n",
"Gamification\n",
"=============\n",
"\n",
"Use the motivation and engagement of gaming to get people to solve other\n",
"tasks that they might ordinarily consider too tedious.\n",
"\n",
"Question: Is success in various fields (mathematics, physics, literature, etc.)\n",
"just the ability to gamify that field?\n",
"\n",
"Applications\n",
"\n",
"- reCAPTCHA: OCR by human labeling\n",
"- ESP game: image labeling for getting object recognition training data\n",
"- Phylo: multiple sequence alignment\n",
"- Foldit, EteRNA: protein/RNA folding as game\n",
"- EyeWire: neural fiber tracing\n",
"\n",
"Techniques of gamification:\n",
"\n",
"- achievements, levels, badges\n",
"- progress bars and measures\n",
"- selection of challenges tailored to player abilities\n",
"- competition, leader boards\n",
"- delivery on platforms users can use (including casual games)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Combinatorial Game Theory\n",
"===========================\n",
"\n",
"Tic Tac Toe\n",
"-----------\n",
"\n",
"<img width=300 src=\"http://upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Tic-tac-toe-game-1.svg/462px-Tic-tac-toe-game-1.svg.png\">\n",
"\n",
"Properties of game:\n",
"\n",
"- perfect information\n",
"- completely deterministic\n",
"- outcomes (1,0), (0,0), (0,1)\n",
"\n",
"Complexity:\n",
"\n",
"- 9 cells\n",
"- $3^9$ possible board layouts, $9!$ games, but many aren't possible games\n",
"- final boards: 91 wins by X, 44 wins by O, 3 draws\n",
"- 131184 games won by X, 77904 games won by O, 46080 games end in draw\n",
"- total number of games _with symmetries removed_ is 26830 (Schaeffer, 2002)\n",
"- average game length is 9 moves\n",
"- computational complexity of _generalized game_ is PSPACE-complete\n",
"\n",
"Game Tree for Tic Tac Toe\n",
"\n",
"<img width=300 src=\"http://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Tic-tac-toe-game-tree.svg/220px-Tic-tac-toe-game-tree.svg.png\">\n",
"\n",
"General solution: the _minimax algorithm_\n",
"\n",
"- each position is assigned a value by an evaluation function\n",
" - positive if win for first player\n",
" - negative if win for second player\n",
"- choosing a move\n",
" - maximize attainable value assuming...\n",
" - opponent minimizes attanable value on his moves\n",
"- with infinite lookahead, evaluation becomes win/loss\n",
" - the game is solved\n",
"- with finite lookahead, the evaluation is a _heuristic_\n",
" - optimizing the evaluation function does not guarantee a win\n",
"\n",
"Solving a Game\n",
"\n",
"<img width=300 src=\"http://upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Arbitrary-gametree-solved.svg/400px-Arbitrary-gametree-solved.svg.png\">\n",
"\n",
"Perfect Algorithm for Tic Tac Toe\n",
"\n",
"Use the first move that is applicable:\n",
"\n",
"- take win\n",
"- block opponent's win\n",
"- create a fork\n",
"- block opponent's fork\n",
"- play the center\n",
"- play opposite corner\n",
"- play empty corner\n",
"- play empty side\n",
"\n",
"Note that these rules are much simpler than knowledge of the entire game tree.\n",
"\n",
"They also represent a kind of preference or evaluation of moves."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"Checkers\n",
"-----------\n",
"\n",
"<img width=200 src=\"http://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Draughts.svg/220px-Draughts.svg.png\">\n",
"\n",
"Properties of checkers:\n",
"\n",
"- perfect information\n",
"- completely deterministic\n",
"- outcomes: (1,0), (0,0), (0,1)\n",
"\n",
"Theoretically optimal algorithm:\n",
"\n",
"- write down a complete game tree, each move and countermove\n",
"- determine the minimax payoff:\n",
" - what is the maximum payoff I can receive...\n",
" - under the assumption that my opponent is rational and maximizes his payoff\n",
"- there is a first move that maximizes the payoff for the first player\n",
"\n",
"Complexity:\n",
"\n",
"- 32 cells on board\n",
"- state space complexity: $10^{20}$\n",
"- game tree complexity: $10^{31}$\n",
"- complexity of _generalized game_: EXPTIME-complete\n",
"\n",
"Progress:\n",
"\n",
"- first computer opponents in the 1950's\n",
"- Samuel's checkers (1956): adaptive, learning, self-modifying; not very good\n",
"- Chinook (1996): first implementation to beat a champion\n",
"- Chinook (2007): Checkers has been _solved_ (it's a draw)\n",
"- **solution has nothing to do with artificial or human intelligence**\n",
"\n",
"Chess\n",
"-------\n",
"\n",
"Complexity:\n",
"\n",
"- 32 cells on board\n",
"- state space complexity: $10^{47}$\n",
"- game tree complexity: $10^{123}$\n",
"- complexity of _generalized game_: EXPTIME-complete\n",
"\n",
"Progress:\n",
"\n",
"- Deep Thought (1989): master level computer chess\n",
"- Deep Blue (1997): champion level computer chess\n",
"- Fritz (2002): top level chess software on PC hardware\n",
"- Pocket Fritz (2009): grandmaster level mobile chess\n",
"\n",
"Approaches:\n",
"\n",
"- special data structures for fast evaluation\n",
"- high performance search algorithms, pruning techniques for the game tree\n",
"- evaluation functions\n",
"- no machine learning, neural networks, etc.\n",
"- no apparent relationship to human chess playing\n",
"\n",
"Go\n",
"-----\n",
"\n",
"Complexity:\n",
"\n",
"- most complex widely played game\n",
"- 361 cells (but only one piece)\n",
"- state space complexity: $10^{171}$\n",
"- game tree complexity: $10^{360}$\n",
"\n",
"Differences to chess:\n",
"\n",
"- chess restricts moves, go allows almost any move\n",
"- the board is much larger, much larger # of possible moves\n",
"- bad moves hurt you, but often much later\n",
"- win is by overall score, not achieving a single goal\n",
"- players need to make tradeoffs between different regions\n",
"\n",
"Progress:\n",
"\n",
"- MoGo (2008): one win in 9x9 game against 5th dan pro (halfway up the pro ladder, regular game is 19x19)\n",
"- Zen (2010): 4th dan on KGS Go server\n",
"- Zen (2012): 6th dan on KGS Go server\n",
"\n",
"Techniques\n",
"\n",
"Chess and checkers can be won largely by brute force search and hardwiring once hardware was fast enough.\n",
"This does not work for Go.\n",
"\n",
"Go is a much richer ground for AI research. Techniques include:\n",
"\n",
"- knowledge-based systems\n",
"- machine learning and neural networks\n",
"- Monte Carlo methods\n",
"\n",
"These are combined with traditional game tools (minimax, heuristic evaluation, etc.)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Rock Paper Scissors\n",
"=======================\n",
"\n",
"The Game\n",
"------------\n",
"\n",
"<img width=300 src=\"http://upload.wikimedia.org/wikipedia/commons/thumb/e/e6/Rock_paper_scissors.jpg/300px-Rock_paper_scissors.jpg\">\n",
"\n",
"Real-Life Relevance\n",
"-------------------\n",
"\n",
"- model of mating strategies (in lizards and elsewhere)\n",
"- antibiotics production, resistance, sensitivity in bacteria\n",
"- as a counterexample to simplistic applications of game theory\n",
"\n",
"The Payoff Matrix\n",
"---------------\n",
"\n",
"<img width=400 src=\"https://lh5.googleusercontent.com/-MogcvzlGEZQ/UAU5t63sZ9I/AAAAAAAAJjI/3amA7wxN7VU/s398/1342519732.png\">\n",
"\n",
"Game Theoretic Analysis\n",
"-----------------------\n",
"\n",
"The Nash equilibrium is simple:\n",
"\n",
"- use a _mixed strategy_\n",
"- choose moves randomly, each with a probability of 1/3\n",
"- for the repeated game, continue choosing randomly\n",
"- can't do any better... according to theory\n",
"\n",
"Rock-Paper-Scissors (RoShamBo) is usually _iterated_, that is, played many times.\n",
"\n",
"Theory vs Reality\n",
"-----------------\n",
"\n",
"RoShamBo computer tournament results:\n",
"\n",
"- 64 entries\n",
"- points\n",
" - Greenberg: 9268\n",
" - Iocaine Powder: 6960\n",
" - random: -7\n",
" - Rock'em Sock'em: -52074\n",
"\n",
"What is going on?\n",
"--------------------\n",
"\n",
"- two rational opponents playing against each other might use the random strategy\n",
"- if you use a non-random strategy, a rational opponent can exploit you and gain\n",
"- but by exploiting your non-random strategy, the opponent's strategy itself becomes non-random and exploitable\n",
"\n",
"Iocaine Powder Approach\n",
"-------------------------\n",
"\n",
"- P meta-strategies\n",
" - P.0 (naive application) predict opponent's move, play to beat it\n",
" - P.1 (defeat second guessing) assume opponent thinks you use P.0, anticipate and counteract\n",
" - P.2 (defeat triple guessing) assume opponent thinks you use P.1, anticipate and counteract\n",
" - P.3 is just like P.0 by game design\n",
"- P' meta-strategies\n",
" - assume opponent is also using P\n",
" - counteract each\n",
"- apply all the meta-strategies with a number of different predictive algorithms\n",
" - random guess\n",
" - frequency analysis (multiple time horizons)\n",
" - history matching (multiple versions with different amounts)\n",
"- meta-meta strategy\n",
" - apply meta-strategies over different time horizons\n",
"\n",
"Actual computation:\n",
"\n",
"- predict with all 6 meta-strategies for each of the predictors\n",
"- see which one would have given the best performance in the past\n",
"- use that...\n",
"\n",
"General Message for Game Theory (and Economics, Biology, etc)\n",
"-----------------------------------------------\n",
"\n",
"- games are repeated\n",
"- other players have bounded rationality\n",
"- players repeat mistakes consistently\n",
"- mistakes can be exploited\n",
"- exploits can themselves be exploited\n",
"- good strategy depends on modeling the psychology of the other participants (and their designers)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Nomic\n",
"========\n",
"\n",
"Game designed by philosopher Peter Suber: \"The Paradox of Self-Amendment, A Study in Law, Logic, Omnipotence, and Change\"\n",
"\n",
"http://www.earlham.edu/~peters/writing/psa/\n",
"\n",
"The game starts with an initial ruleset consisting of _mutable_ and _immutable_ rules.\n",
"\n",
"Permitted changes (initially):\n",
"\n",
"- addition of a new mutable rule\n",
"- amendment to a mutable rule\n",
"- repeal of a mutable rule\n",
"- transmutation of a rule from mutable to immutable\n",
"- transmutation of a rule from immutable to mutable\n",
"\n",
"Game play (initially):\n",
"\n",
"- changes are voted on democratically\n",
"- all players begin with 0 points\n",
"- players propose rule changes\n",
" - if adopted, the proposer gets points based on number of votes\n",
" - if rejected, the proposer loses 10 points\n",
" - (actually, a bit more complicated)\n",
"- adjudication of different interpretations by previous player\n",
"- if play cannot continue, the first player unable to complete a turn wins"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"General Message\n",
"================\n",
"\n",
"- game theory models fundamental questions in biology, economics, security, AI, evolution, etc.\n",
"- gamification increasingly important for real-world applications\n",
"- challenging and fundamental questions in AI, psychology remain\n",
"- computer science has a lot to contribute\n",
" - computability and complexity - bounded rationality\n",
" - theory and modeling of multi-agent systems\n",
" - theory and modeling of communications, information\n",
" - large scale simulations and evaluation\n",
"- will cover more of this in Foundations of Artificial Intelligence next semester"
]
},
{
"cell_type": "code",
"collapsed": true,
"input": [],
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}