Building game trees

Theodore L. Turocy
University of East Anglia

EC'16 Workshop 24 July 2016

In [1]:
import gambit

One can build up extensive games from scratch and manipulate them. This example shows one way to do that for the simple one-card poker game.

The primitives for doing this remain rather low-level, as I have never settled on a good way to write higher-level ones that apply broadly. It has always seemed to me that different games have different "natural" ways to build them out. It is nevertheless likely that having some more powerful idioms could be useful - suggestions are welcomed.

In [2]:
g = gambit.Game.new_tree()
g.title = "A simple poker example"

Define the players; save them as variables for convenience laster.

In [3]:
alice = g.players.add("Alice")
In [4]:
bob = g.players.add("Bob")

The root node is a chance move, between Ace and King. Chance moves default to uniform randomisation, but I set the probabilities here anyway just for explicitness.

In [5]:
move = g.root.append_move(g.players.chance, 2)
In [6]:
move.actions[0].label = "A"
move.actions[0].prob = gambit.Rational(1, 2)
move.actions[1].label = "K"
move.actions[1].prob = gambit.Rational(1, 2)

After an Ace, Alice can Raise or Fold.

In [7]:
move = g.root.children[0].append_move(alice, 2)
move.label = 'a'
move.actions[0].label = "R"
move.actions[1].label = "F"

She can also Raise or Fold after the King. Calling append_move with the player, rather than the previously created move, creates a new information set for Alice.

In [8]:
move = g.root.children[1].append_move(alice, 2)
move.label = 'k'
move.actions[0].label = "R"
move.actions[1].label = "F"

After Alice raises with the Ace, Bob can Meet or Pass.

In [9]:
move = g.root.children[0].children[0].append_move(bob, 2)
move.label = 'b'
move.actions[0].label = "M"
move.actions[1].label = "P"

Likewise after Alice raises with the King. Using the same move here adds the move to the same information set for Bob.

In [10]:
g.root.children[1].children[0].append_move(move)
Out[10]:
<Infoset [0] 'b' for player 'Bob' in game 'A simple poker example'>

The game so far, as an .efg file. We see the tree structure is in place; now to deal with payoffs.

In [11]:
g
Out[11]:
EFG 2 R "A simple poker example" { "Alice" "Bob" }
""

c "" 1 "" { "A" 1/2 "K" 1/2 } 0
p "" 1 1 "a" { "R" "F" } 0
p "" 2 1 "b" { "M" "P" } 0
t "" 0
t "" 0
t "" 0
p "" 1 2 "k" { "R" "F" } 0
p "" 2 1 "b" { "M" "P" } 0
t "" 0
t "" 0
t "" 0
In [12]:
alice_big = g.outcomes.add("Alice wins big")
alice_big[0] = 2
alice_big[1] = -2
In [13]:
alice_small = g.outcomes.add("Alice wins")
alice_small[0] = 1
alice_small[1] = -1
In [14]:
bob_small = g.outcomes.add("Bob wins")
bob_small[0] = -1
bob_small[1] = 1
In [15]:
bob_big = g.outcomes.add("Bob wins big")
bob_big[0] = -2
bob_big[1] = 2

Attach the outcomes to the corresponding terminal nodes. Notice how we can re-use the outcomes to denote that different terminal nodes may correspond to the same logical outcome.

In [16]:
g.root.children[0].children[0].children[0].outcome = alice_big
g.root.children[0].children[0].children[1].outcome = alice_small
g.root.children[0].children[1].outcome = bob_small
In [17]:
g.root.children[1].children[0].children[0].outcome = bob_big
g.root.children[1].children[0].children[1].outcome = alice_small
g.root.children[1].children[1].outcome = bob_small

Here's the game we've just built

In [18]:
g
Out[18]:
EFG 2 R "A simple poker example" { "Alice" "Bob" }
""

c "" 1 "" { "A" 1/2 "K" 1/2 } 0
p "" 1 1 "a" { "R" "F" } 0
p "" 2 1 "b" { "M" "P" } 0
t "" 1 "Alice wins big" { 2, -2 }
t "" 2 "Alice wins" { 1, -1 }
t "" 3 "Bob wins" { -1, 1 }
p "" 1 2 "k" { "R" "F" } 0
p "" 2 1 "b" { "M" "P" } 0
t "" 4 "Bob wins big" { -2, 2 }
t "" 2 "Alice wins" { 1, -1 }
t "" 3 "Bob wins" { -1, 1 }

For comparison, here's the game we started with for the Poker example.

In [19]:
gambit.Game.read_game("poker.efg")
Out[19]:
EFG 2 R "A simple poker example" { "Alice" "Bob" }
""

c "" 1 "" { "A" 1/2 "K" 1/2 } 0
p "" 1 1 "a" { "R" "F" } 0
p "" 2 1 "b" { "M" "P" } 0
t "" 1 "Alice wins big" { 2, -2 }
t "" 2 "Alice wins" { 1, -1 }
t "" 3 "Bob wins" { -1, 1 }
p "" 1 2 "k" { "R" "F" } 0
p "" 2 1 "b" { "M" "P" } 0
t "" 4 "Bob wins big" { -2, 2 }
t "" 2 "Alice wins" { 1, -1 }
t "" 3 "Bob wins" { -1, 1 }

We can confirm they're the same:

In [20]:
g.write() == gambit.Game.read_game("poker.efg").write()
Out[20]:
True