mirror of
https://github.com/saymrwulf/nvidia-AI.summerschool17-notebooks.git
synced 2026-11-18 09:41:49 +00:00
659 lines
No EOL
25 KiB
Text
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",
|
|
"\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",
|
|
"\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": {}
|
|
}
|
|
]
|
|
} |