Game Theory

Framework for expressing arbitrary games.

Monty Hall

See the Wikipedia page on the Monty Hall problem

The axle.game.OldMontyHall object contains a model of the rules of the game.

import spire.math.Rational

import axle.probability._
import axle.game.OldMontyHall._

The models supports querying the chance of winning given the odds that the player switches his or her initial choice.

At one extreme, the odds of winning given that the other door is always chosen:

chanceOfWinning(Rational(1))
// res0: Rational = 2/3

At the other extreme, the player always sticks with the initial choice.

chanceOfWinning(Rational(0))
// res1: Rational = 1/3

The newer axl.game.montyhall._ package uses axle.game typeclasses to model the game:

import axle.game._
import axle.game.montyhall._

val game = MontyHall()

Create a writer for each player that prefixes the player id to all output.

import cats.effect.IO
import axle.IO.printMultiLinePrefixed

val playerToWriter: Map[Player, String => IO[Unit]] =
  evGame.players(game).map { player =>
    player -> (printMultiLinePrefixed[IO](player.id) _)
  } toMap

Use a uniform distribution on moves as the demo strategy:

val randomMove: MontyHallState => ConditionalProbabilityTable[MontyHallMove,
 Rational] =
  (state: MontyHallState) =>
    ConditionalProbabilityTable.uniform[MontyHallMove, Rational](evGame.moves(game, state))

Wrap the strategies in the calls to writer that log the transitions from state to state.

val strategies: Player => MontyHallState => IO[ConditionalProbabilityTable[MontyHallMove, Rational]] = 
  (player: Player) =>
    (state: MontyHallState) =>
      for {
        _ <- playerToWriter(player)(evGameIO.displayStateTo(game, state, player))
        move <- randomMove.andThen( m => IO { m })(state)
      } yield move

Play the game -- compute the end state from the start state.

import spire.random.Generator.rng

val endState: MontyHallState =
  play(game, strategies, evGame.startState(game), rng).unsafeRunSync()
// M> Door #1: ???
// M> Door #2: ???
// M> Door #3: ???
// C> Door #1: 
// C> Door #2: 
// C> Door #3: 
// M> Door #1: car, first choice
// M> Door #2: goat
// M> Door #3: goat
// C> Door #1: first choice
// C> Door #2: , revealed goat
// C> Door #3: 
// endState: MontyHallState = MontyHallState(
//   placement = Some(value = PlaceCar(door = 1)),
//   placed = true,
//   firstChoice = Some(value = FirstChoice(door = 1)),
//   reveal = Some(value = Reveal(door = 2)),
//   secondChoice = Some(value = Left(value = Change()))
// )

Display outcome to each player

val outcome: MontyHallOutcome =
  evGame.mover(game, endState).swap.toOption.get
// outcome: MontyHallOutcome = MontyHallOutcome(car = false)

evGame.players(game).foreach { player =>
  playerToWriter(player)(evGameIO.displayOutcomeTo(game, outcome, player)).unsafeRunSync()
}
// C> You won a goat
// M> Contestant won a goat

Poker

An N-Player, Imperfect Information, Zero-sum game

Poker Analytics Example

The axle.game.cards package models decks, cards, ranks, suits, and ordering.

Define a function that takes the hand size and returns the best 5-card hand

import cats.implicits._
import cats.Order.catsKernelOrderingForOrder

import axle.game.cards.Deck
import axle.game.poker.PokerHand

def winnerFromHandSize(handSize: Int) =
  Deck().cards.take(handSize).combinations(5).map(cs => PokerHand(cs.toVector)).toList.max

winnerFromHandSize(7).show
// res4: String = "7♠ 8♣ T♣ K♢ A♢"

20 simulated 5-card hands made of 7-card hands. Sorted.

val hands = (1 to 20).map(n => winnerFromHandSize(7)).sorted

hands.map({ hand => hand.show + "  " + hand.description }).mkString("\n")
// res5: String = """7♠ 8♠ T♡ J♠ K♡  high K high
// 6♡ 9♢ T♢ J♢ K♠  high K high
// 7♠ 8♢ J♣ Q♣ A♣  high A high
// 7♣ T♡ J♡ K♢ A♡  high A high
// 6♠ 8♠ Q♠ K♠ A♣  high A high
// 7♠ T♢ Q♡ K♡ A♢  high A high
// 5♠ 5♡ T♢ J♢ A♣  pair of 5
// 5♠ 5♣ Q♣ K♣ A♣  pair of 5
// 6♠ 6♡ 7♢ 8♢ K♡  pair of 6
// 9♡ 9♢ J♠ Q♣ A♡  pair of 9
// 7♢ 9♢ T♠ T♡ Q♠  pair of T
// J♡ Q♡ Q♢ K♢ A♡  pair of Q
// T♡ J♣ K♠ K♢ A♠  pair of K
// 3♡ 3♢ 8♠ 8♣ K♢  two pair 8 and 3
// 7♠ 7♢ T♠ T♢ Q♠  two pair T and 7
// 4♡ 4♣ K♢ A♡ A♢  two pair A and 4
// T♣ K♡ K♣ A♡ A♢  two pair A and K
// 5♣ 8♣ 9♠ 9♡ 9♣  three of a kind of 9
// T♡ J♡ K♡ K♢ K♣  three of a kind of K
// T♠ J♡ Q♠ K♡ A♣  straight to A"""

Record 1000 simulated hands for each drawn hand size from 5 to 9

import axle.game.poker.PokerHandCategory

val data: IndexedSeq[(PokerHandCategory, Int)] =
  for {
    handSize <- 5 to 9
    trial <- 1 to 1000
  } yield (winnerFromHandSize(handSize).category, handSize)

BarChartGrouped to visualize the results

import spire.algebra.CRing

import axle.visualize.BarChartGrouped
import axle.visualize.Color._
import axle.syntax.talliable.talliableOps

implicit val ringInt: CRing[Int] = spire.implicits.IntAlgebra

val colors = List(black, red, blue, yellow, green)

val chart = BarChartGrouped[PokerHandCategory, Int, Int, Map[(PokerHandCategory, Int), Int], String](
  () => data.tally.withDefaultValue(0),
  title = Some("Poker Hands"),
  drawKey = false,
  yAxisLabel = Some("instances of category by hand size (1000 trials each)"),
  colorOf = (cat: PokerHandCategory, handSize: Int) => colors( (handSize - 5) % colors.size),
  hoverOf = (cat: PokerHandCategory, handSize: Int) => Some(s"${cat.show} from $handSize")
)

Render as SVG file

import axle.web._
import cats.effect._

chart.svg[IO]("docwork/images/poker_hands.svg").unsafeRunSync()

poker hands

Playing Texas Hold 'Em Poker

As a game of "imperfect information", poker introduces the concept of Information Set.

import axle.game._
import axle.game.poker._

val p1 = Player("P1", "Player 1")
val p2 = Player("P2", "Player 2")

val game = Poker(Vector(p1, p2))

Create a writer for each player that prefixes the player id to all output.

import cats.effect.IO
import axle.IO.printMultiLinePrefixed

val playerToWriter: Map[Player, String => IO[Unit]] =
  evGame.players(game).map { player =>
    player -> (printMultiLinePrefixed[IO](player.id) _)
  } toMap

Use a uniform distribution on moves as the demo strategy:

import axle.probability._
import spire.math.Rational

val randomMove =
  (state: PokerStateMasked) =>
    ConditionalProbabilityTable.uniform[PokerMove, Rational](evGame.moves(game, state))

Wrap the strategies in the calls to writer that log the transitions from state to state.

val strategies: Player => PokerStateMasked => IO[ConditionalProbabilityTable[PokerMove, Rational]] = 
  (player: Player) =>
    (state: PokerStateMasked) =>
      for {
        _ <- playerToWriter(player)(evGameIO.displayStateTo(game, state, player))
        move <- randomMove.andThen( m => IO { m })(state)
      } yield move

Play the game -- compute the end state from the start state.

import spire.random.Generator.rng

val endState = play(game, strategies, evGame.startState(game), rng).unsafeRunSync()
// D> To: You
// D> Current bet: 0
// D> Pot: 0
// D> Shared: 
// D> 
// D> P1:  hand -- in for $--, $100 remaining
// D> P2:  hand -- in for $--, $100 remaining
// P1> To: You
// P1> Current bet: 2
// P1> Pot: 3
// P1> Shared: 
// P1> 
// P1> P1:  hand 4♡ 5♣ in for $1, $99 remaining
// P1> P2:  hand -- in for $2, $98 remaining
// P2> To: You
// P2> Current bet: 87
// P2> Pot: 89
// P2> Shared: 
// P2> 
// P2> P1:  hand -- in for $87, $13 remaining
// P2> P2:  hand J♢ 4♣ in for $2, $98 remaining
// P1> To: You
// P1> Current bet: 93
// P1> Pot: 180
// P1> Shared: 
// P1> 
// P1> P1:  hand 4♡ 5♣ in for $87, $13 remaining
// P1> P2:  hand -- in for $93, $7 remaining
// D> To: You
// D> Current bet: 93
// D> Pot: 186
// D> Shared: 
// D> 
// D> P1:  hand -- in for $93, $7 remaining
// D> P2:  hand -- in for $93, $7 remaining
// P1> To: You
// P1> Current bet: 0
// P1> Pot: 186
// P1> Shared: 6♢ K♣ K♠
// P1> 
// P1> P1:  hand 4♡ 5♣ in for $--, $7 remaining
// P1> P2:  hand -- in for $--, $7 remaining
// P2> To: You
// P2> Current bet: 1
// P2> Pot: 187
// P2> Shared: 6♢ K♣ K♠
// P2> 
// P2> P1:  hand -- in for $1, $6 remaining
// P2> P2:  hand J♢ 4♣ in for $--, $7 remaining
// P1> To: You
// P1> Current bet: 5
// P1> Pot: 192
// P1> Shared: 6♢ K♣ K♠
// P1> 
// P1> P1:  hand 4♡ 5♣ in for $1, $6 remaining
// P1> P2:  hand -- in for $5, $2 remaining
// D> To: You
// D> Current bet: 5
// D> Pot: 196
// D> Shared: 6♢ K♣ K♠
// D> 
// D> P1:  hand -- in for $5, $2 remaining
// D> P2:  hand -- in for $5, $2 remaining
// P1> To: You
// P1> Current bet: 0
// P1> Pot: 196
// P1> Shared: 6♢ K♣ K♠ Q♢
// P1> 
// P1> P1:  hand 4♡ 5♣ in for $--, $2 remaining
// P1> P2:  hand -- in for $--, $2 remaining
// P2> To: You
// P2> Current bet: 1
// P2> Pot: 197
// P2> Shared: 6♢ K♣ K♠ Q♢
// P2> 
// P2> P1:  hand -- in for $1, $1 remaining
// P2> P2:  hand J♢ 4♣ in for $--, $2 remaining
// P1> To: You
// P1> Current bet: 2
// P1> Pot: 199
// P1> Shared: 6♢ K♣ K♠ Q♢
// P1> 
// P1> P1:  hand 4♡ 5♣ in for $1, $1 remaining
// P1> P2:  hand -- in for $2, $0 remaining
// D> To: You
// D> Current bet: 2
// D> Pot: 200
// D> Shared: 6♢ K♣ K♠ Q♢
// D> 
// D> P1:  hand -- in for $2, $0 remaining
// D> P2:  hand -- in for $2, $0 remaining
// P1> To: You
// P1> Current bet: 0
// P1> Pot: 200
// P1> Shared: 6♢ K♣ K♠ Q♢ 4♠
// P1> 
// P1> P1:  hand 4♡ 5♣ in for $--, $0 remaining
// P1> P2:  hand -- in for $--, $0 remaining
// P2> To: You
// P2> Current bet: 0
// P2> Pot: 200
// P2> Shared: 6♢ K♣ K♠ Q♢ 4♠
// P2> 
// P2> P1:  hand -- in for $0, $0 remaining
// P2> P2:  hand J♢ 4♣ in for $--, $0 remaining
// D> To: You
// D> Current bet: 0
// D> Pot: 200
// D> Shared: 6♢ K♣ K♠ Q♢ 4♠
// D> 
// D> P1:  hand -- in for $0, $0 remaining
// D> P2:  hand -- out, $0 remaining
// endState: PokerState = PokerState(
//   moverFn = axle.game.poker.package$$anon$1$$Lambda$8759/0x0000000802932220@5f997431,
//   deck = Deck(
//     cards = List(
//       Card(
//         rank = axle.game.cards.R6$@693e1998,
//         suit = axle.game.cards.Hearts$@a85589b
//       ),
//       Card(
//         rank = axle.game.cards.R8$@2803a285,
//         suit = axle.game.cards.Spades$@47e30cf8
//       ),
//       Card(
//         rank = axle.game.cards.R5$@107e6237,
//         suit = axle.game.cards.Diamonds$@21d3be3
//       ),
//       Card(
//         rank = axle.game.cards.R2$@3f27d270,
//         suit = axle.game.cards.Diamonds$@21d3be3
//       ),
//       Card(
//         rank = axle.game.cards.R7$@46d6f200,
//         suit = axle.game.cards.Hearts$@a85589b
//       ),
//       Card(
//         rank = axle.game.cards.R2$@3f27d270,
//         suit = axle.game.cards.Clubs$@9768e2e
//       ),
//       Card(
//         rank = axle.game.cards.R3$@ab2b152,
//         suit = axle.game.cards.Clubs$@9768e2e
//       ),
//       Card(
//         rank = axle.game.cards.R8$@2803a285,
//         suit = axle.game.cards.Diamonds$@21d3be3
//       ),
//       Card(
//         rank = axle.game.cards.R2$@3f27d270,
//         suit = axle.game.cards.Hearts$@a85589b
//       ),
//       Card(
//         rank = axle.game.cards.R8$@2803a285,
//         suit = axle.game.cards.Clubs$@9768e2e
//       ),
//       Card(
//         rank = axle.game.cards.R8$@2803a285,
//         suit = axle.game.cards.Hearts$@a85589b
//       ),
// ...

Display outcome to each player

val outcome = evGame.mover(game, endState).swap.toOption.get
// outcome: PokerOutcome = PokerOutcome(
//   winner = Some(value = Player(id = "P1", description = "Player 1")),
//   hand = None
// )

evGame.players(game).foreach { player =>
  playerToWriter(player)(evGameIO.displayOutcomeTo(game, outcome, player)).unsafeRunSync()
}
// D> Winner: Player 1
// D> Hand  : not shown
// P1> Winner: Player 1
// P1> Hand  : not shown
// P2> Winner: Player 1
// P2> Hand  : not shown

Prisoner's Dilemma

See the Wikipedia page on the Prisoner's Dilemma

The axl.game.prisoner._ package uses axle.game typeclasses to model the game:

import axle.game._
import axle.game.prisoner._

val p1 = Player("P1", "Player 1")
val p2 = Player("P2", "Player 2")

val game = PrisonersDilemma(p1, p2)

Create a writer for each player that prefixes the player id to all output.

import cats.effect.IO
import axle.IO.printMultiLinePrefixed

val playerToWriter: Map[Player, String => IO[Unit]] =
  evGame.players(game).map { player =>
    player -> (printMultiLinePrefixed[IO](player.id) _)
  } toMap

Use a uniform distribution on moves as the demo strategy:

import axle.probability._
import spire.math.Rational

val randomMove =
  (state: PrisonersDilemmaState) =>
    ConditionalProbabilityTable.uniform[PrisonersDilemmaMove, Rational](evGame.moves(game, state))

Wrap the strategies in the calls to writer that log the transitions from state to state.

val strategies: Player => PrisonersDilemmaState => IO[ConditionalProbabilityTable[PrisonersDilemmaMove, Rational]] = 
  (player: Player) =>
    (state: PrisonersDilemmaState) =>
      for {
        _ <- playerToWriter(player)(evGameIO.displayStateTo(game, state, player))
        move <- randomMove.andThen( m => IO { m })(state)
      } yield move

Play the game -- compute the end state from the start state.

import spire.random.Generator.rng

val endState = play(game, strategies, evGame.startState(game), rng).unsafeRunSync()
// P1> You have been caught
// P2> You have been caught
// endState: PrisonersDilemmaState = PrisonersDilemmaState(
//   p1Move = Some(value = Betrayal()),
//   p1Moved = true,
//   p2Move = Some(value = Betrayal())
// )

Display outcome to each player

val outcome = evGame.mover(game, endState).swap.toOption.get
// outcome: PrisonersDilemmaOutcome = PrisonersDilemmaOutcome(
//   p1YearsInPrison = 2,
//   p2YearsInPrison = 2
// )

evGame.players(game).foreach { player =>
  playerToWriter(player)(evGameIO.displayOutcomeTo(game, outcome, player)).unsafeRunSync()
}
// P1> You is imprisoned for 2 years
// P1> Player 2 is imprisoned for 2 years
// P2> Player 1 is imprisoned for 2 years
// P2> You is imprisoned for 2 years

Tic-Tac-Toe

A Perfect Information, Zero-sum game

Playing Tic-Tac-Toe

import axle.game._
import axle.game.ttt._

val x = Player("X", "Player X")
val o = Player("O", "Player O")

val game = TicTacToe(3, x, o)

Create a writer for each player that prefixes the player id to all output.

import cats.effect.IO
import axle.IO.printMultiLinePrefixed

val playerToWriter: Map[Player, String => IO[Unit]] =
  evGame.players(game).map { player =>
    player -> (printMultiLinePrefixed[IO](player.id) _)
  } toMap

Use a uniform distribution on moves as the demo strategy:

import axle.probability._
import spire.math.Rational

val randomMove =
  (state: TicTacToeState) =>
    ConditionalProbabilityTable.uniform[TicTacToeMove, Rational](evGame.moves(game, state))

Wrap the strategies in the calls to writer that log the transitions from state to state.

val strategies: Player => TicTacToeState => IO[ConditionalProbabilityTable[TicTacToeMove, Rational]] = 
  (player: Player) =>
    (state: TicTacToeState) =>
      for {
        _ <- playerToWriter(player)(evGameIO.displayStateTo(game, state, player))
        move <- randomMove.andThen( m => IO { m })(state)
      } yield move

Play the game -- compute the end state from the start state.

import spire.random.Generator.rng

val endState = play(game, strategies, evGame.startState(game), rng).unsafeRunSync()
// X> Board:         Movement Key:
// X>  | |           1|2|3
// X>  | |           4|5|6
// X>  | |           7|8|9
// O> Board:         Movement Key:
// O>  | |           1|2|3
// O>  | |X          4|5|6
// O>  | |           7|8|9
// X> Board:         Movement Key:
// X>  | |           1|2|3
// X>  |O|X          4|5|6
// X>  | |           7|8|9
// O> Board:         Movement Key:
// O>  | |           1|2|3
// O>  |O|X          4|5|6
// O> X| |           7|8|9
// X> Board:         Movement Key:
// X>  | |           1|2|3
// X> O|O|X          4|5|6
// X> X| |           7|8|9
// O> Board:         Movement Key:
// O>  |X|           1|2|3
// O> O|O|X          4|5|6
// O> X| |           7|8|9
// X> Board:         Movement Key:
// X>  |X|           1|2|3
// X> O|O|X          4|5|6
// X> X|O|           7|8|9
// O> Board:         Movement Key:
// O> X|X|           1|2|3
// O> O|O|X          4|5|6
// O> X|O|           7|8|9
// X> Board:         Movement Key:
// X> X|X|O          1|2|3
// X> O|O|X          4|5|6
// X> X|O|           7|8|9
// endState: TicTacToeState = TicTacToeState(
//   moverOpt = Some(value = Player(id = "O", description = "Player O")),
//   board = Array(
//     Some(value = Player(id = "X", description = "Player X")),
//     Some(value = Player(id = "X", description = "Player X")),
//     Some(value = Player(id = "O", description = "Player O")),
//     Some(value = Player(id = "O", description = "Player O")),
//     Some(value = Player(id = "O", description = "Player O")),
//     Some(value = Player(id = "X", description = "Player X")),
//     Some(value = Player(id = "X", description = "Player X")),
//     Some(value = Player(id = "O", description = "Player O")),
//     Some(value = Player(id = "X", description = "Player X"))
//   ),
//   boardSize = 3
// )

Display outcome to each player

val outcome = evGame.mover(game, endState).swap.toOption.get
// outcome: TicTacToeOutcome = TicTacToeOutcome(winner = None)

evGame.players(game).foreach { player =>
  playerToWriter(player)(evGameIO.displayOutcomeTo(game, outcome, player)).unsafeRunSync()
}
// X> The game was a draw.
// O> The game was a draw.

Future Work

Missing functionality

Remove moveStateStream
For one game (probably Poker)

Record witnessed and unwitnessed history Seq[(M, S)] in State

Display to user in interactiveMove
- val mm = evGame.maskMove(game, move, mover, observer)
- evGameIO.displayMoveTo(game, mm, mover, observer)

Then generalize and pull into framework

Motivating Examples

Generalize OldMontyHall.chanceOfWinning
GuessRiffle.md

Walk through game

Plot distribution of sum(entropy) for both strategies

Plot entropy by turn # for each strategy

Plot simulated score distribution for each strategy
GuessRiffleSpec: use moveFromRandomState
Gerrymandering sensitivity
"You split, I choose" as game

Deeper changes to axle.game

aiMover.unmask prevents MontyHallSpec "AI vs. AI game produces moveStateStream" from working

will be an issue for all non-perfect information
Identify all uses of spire.random.Generator (and other random value generation)
See uses of seed in GuessRiffleProperties
Eliminate entropy consumption of rng side-effect (eg applyMove(Riffle()))

Chance should be its own player

Consider whether PM should be a part of Strategy type (MS => PM[M, V])
- More abstractly, more many intents and purposes, all we are about is that resolving PM to M consumes entropy
- In which cases should the PM be retained?

Each N bits consumed during Riffle() is its own move

Chance moves consume UnittedQuantity[Information, N]
perceive could return a lower-entropy probability model

Perhaps in exchange for a given amount of energy

Or ask for a 0-entropy model and be told how expensive that was
Game theory axioms (Nash, etc)
axle.game: Observable[T]

Hygeine

performance benchmark
Replace axle.game.moveFromRandomState.mapToProb
Clean up axle.game.playWithIntroAndOutcomes
The references to movesMap in MoveFromRandomStateSpec.scala illustrate a need for a cleaner way to create a hard-coded strategy -- which could just be in the form of a couple utility functions from movesMap to the data needed by evGame.{moves,applyMove} and rm strategy
Generalize ConditionalProbabilityTable.uniform into typeclass
Simplify GuessRiffleProperties (especially second property)
stateStreamMap only used in GuessRiffleProperties -- stop using chain?
stateStrategyMoveStream only used in GuessRiffleProperties
Game.players should be a part of GameState (or take it as an argument)? Will wait for pressing use case.

Game Theory and Examples

Game Theory: information sets, equilibria
Factor axle.game.moveFromRandomState in terms of a random walk on a graph.

See "TODO scale mass down"

Compare to Brownian motion, Random walk, Ito process, ...

Provide some axioms
- no outgoing with path in from non-zero mass monotonically increases
- no incoming with path out monotonically decreases

possibly provide a version for acyclic graphs
Iterative game playing algorithm is intractible, but shares intent with sequential monte carlo
Think about Information Theory's "Omega" vis-a-vis Sequential Monte Carlo
Improve axle.stats.rationalProbabilityDist as probabilities become smaller
SimpsonsParadox.md
Axioms of partial differentiation

Plotkin Partial Differentiation
Conal Elliott: Efficient automatic differentiation made easy via category theory
Max bet for Poker
syntax for Game typeclass