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: goat
// M> Door #2: goat, first choice
// M> Door #3: car
// C> Door #1: , revealed goat
// C> Door #2: first choice
// C> Door #3: 
// endState: MontyHallState = MontyHallState(
//   placement = Some(value = PlaceCar(door = 3)),
//   placed = true,
//   firstChoice = Some(value = FirstChoice(door = 2)),
//   reveal = Some(value = Reveal(door = 1)),
//   secondChoice = Some(value = Right(value = Stay()))
// )

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 = "2♣ 7♣ 9♣ T♣ K♣"

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 = """5♡ 6♢ 9♣ T♠ K♡  high K high
// 7♡ 8♠ 9♢ J♠ A♠  high A high
// 4♡ 6♠ 7♠ K♢ A♣  high A high
// 2♢ 2♣ 9♠ T♢ K♢  pair of 2
// 2♢ 2♣ T♡ J♢ A♡  pair of 2
// 3♡ 3♢ 8♢ J♢ A♣  pair of 3
// 4♡ 4♣ 6♣ 7♣ T♠  pair of 4
// 5♠ 5♣ 8♣ 9♡ Q♡  pair of 5
// 5♠ 5♣ T♠ J♣ Q♢  pair of 5
// 6♠ 6♡ J♣ K♣ A♡  pair of 6
// 7♡ 7♢ T♡ J♣ K♡  pair of 7
// 9♢ T♢ T♣ K♡ A♡  pair of T
// 5♢ 5♣ 8♠ 8♡ A♣  two pair 8 and 5
// J♢ J♣ Q♡ Q♣ A♢  two pair Q and J
// 2♠ 2♡ K♡ K♣ A♡  two pair K and 2
// 5♠ 5♢ J♠ K♠ K♣  two pair K and 5
// 8♡ Q♠ Q♡ K♡ K♣  two pair K and Q
// 7♣ 8♢ 9♠ T♠ J♠  straight to J
// 2♣ 5♣ 6♣ 7♣ K♣  flush in ♣
// K♡ K♢ K♣ A♢ A♣  full house K over 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 5♠ 2♠ in for $1, $99 remaining
// P1> P2:  hand -- in for $2, $98 remaining
// P2> To: You
// P2> Current bet: 74
// P2> Pot: 76
// P2> Shared: 
// P2> 
// P2> P1:  hand -- in for $74, $26 remaining
// P2> P2:  hand J♡ 5♢ in for $2, $98 remaining
// P1> To: You
// P1> Current bet: 87
// P1> Pot: 161
// P1> Shared: 
// P1> 
// P1> P1:  hand 5♠ 2♠ in for $74, $26 remaining
// P1> P2:  hand -- in for $87, $13 remaining
// P2> To: You
// P2> Current bet: 100
// P2> Pot: 187
// P2> Shared: 
// P2> 
// P2> P1:  hand -- in for $100, $0 remaining
// P2> P2:  hand J♡ 5♢ in for $87, $13 remaining
// D> To: You
// D> Current bet: 100
// D> Pot: 200
// D> Shared: 
// D> 
// D> P1:  hand -- in for $100, $0 remaining
// D> P2:  hand -- in for $100, $0 remaining
// P1> To: You
// P1> Current bet: 0
// P1> Pot: 200
// P1> Shared: 9♡ A♣ 4♣
// P1> 
// P1> P1:  hand 5♠ 2♠ in for $--, $0 remaining
// P1> P2:  hand -- in for $--, $0 remaining
// P2> To: You
// P2> Current bet: 0
// P2> Pot: 200
// P2> Shared: 9♡ A♣ 4♣
// P2> 
// P2> P1:  hand -- in for $0, $0 remaining
// P2> P2:  hand J♡ 5♢ in for $--, $0 remaining
// D> To: You
// D> Current bet: 0
// D> Pot: 200
// D> Shared: 9♡ A♣ 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$10673/0x000000080277aa78@1727e458,
//   deck = Deck(
//     cards = List(
//       Card(
//         rank = axle.game.cards.R8$@24825c76,
//         suit = axle.game.cards.Hearts$@3918498c
//       ),
//       Card(
//         rank = axle.game.cards.Queen$@7d6ba9f3,
//         suit = axle.game.cards.Hearts$@3918498c
//       ),
//       Card(
//         rank = axle.game.cards.King$@7bbcbb06,
//         suit = axle.game.cards.Clubs$@149349c
//       ),
//       Card(
//         rank = axle.game.cards.R5$@4cfd92fd,
//         suit = axle.game.cards.Clubs$@149349c
//       ),
//       Card(
//         rank = axle.game.cards.R4$@9fe0aa2,
//         suit = axle.game.cards.Diamonds$@4486f5f8
//       ),
//       Card(
//         rank = axle.game.cards.R8$@24825c76,
//         suit = axle.game.cards.Diamonds$@4486f5f8
//       ),
//       Card(
//         rank = axle.game.cards.Jack$@3fa990cd,
//         suit = axle.game.cards.Clubs$@149349c
//       ),
//       Card(
//         rank = axle.game.cards.King$@7bbcbb06,
//         suit = axle.game.cards.Hearts$@3918498c
//       ),
//       Card(
//         rank = axle.game.cards.R10$@66e1cec3,
//         suit = axle.game.cards.Hearts$@3918498c
//       ),
//       Card(
//         rank = axle.game.cards.R3$@4864d24,
//         suit = axle.game.cards.Diamonds$@4486f5f8
//       ),
//       Card(
//         rank = axle.game.cards.R9$@33198d39,
//         suit = axle.game.cards.Clubs$@149349c
//       ),
// ...

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 = Silence()),
//   p1Moved = true,
//   p2Move = Some(value = Betrayal())
// )

Display outcome to each player

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

evGame.players(game).foreach { player =>
  playerToWriter(player)(evGameIO.displayOutcomeTo(game, outcome, player)).unsafeRunSync()
}
// P1> You is imprisoned for 3 years
// P1> Player 2 is imprisoned for 0 years
// P2> Player 1 is imprisoned for 3 years
// P2> You is imprisoned for 0 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>  | |           4|5|6
// O>  | |X          7|8|9
// X> Board:         Movement Key:
// X>  | |O          1|2|3
// X>  | |           4|5|6
// X>  | |X          7|8|9
// O> Board:         Movement Key:
// O>  | |O          1|2|3
// O> X| |           4|5|6
// O>  | |X          7|8|9
// X> Board:         Movement Key:
// X>  | |O          1|2|3
// X> X| |           4|5|6
// X>  |O|X          7|8|9
// O> Board:         Movement Key:
// O>  | |O          1|2|3
// O> X|X|           4|5|6
// O>  |O|X          7|8|9
// X> Board:         Movement Key:
// X>  |O|O          1|2|3
// X> X|X|           4|5|6
// X>  |O|X          7|8|9
// endState: TicTacToeState = TicTacToeState(
//   moverOpt = None,
//   board = Array(
//     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 = "X", description = "Player X")),
//     Some(value = Player(id = "X", description = "Player X")),
//     None,
//     None,
//     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 = Some(value = Player(id = "X", description = "Player X"))
// )

evGame.players(game).foreach { player =>
  playerToWriter(player)(evGameIO.displayOutcomeTo(game, outcome, player)).unsafeRunSync()
}
// X> You beat Player O!
// O> Player X beat You!

Future Work

Missing functionality

Motivating Examples

Deeper changes to axle.game

Hygeine

Game Theory and Examples