Games & Game Theory

Games or Adversarial Search (Chapter 5)

class games.GameState(to_move, utility, board, moves)

Bases: tuple

board

Alias for field number 2

moves

Alias for field number 3

to_move

Alias for field number 0

utility

Alias for field number 1

class games.StochasticGameState(to_move, utility, board, moves, chance)

Bases: tuple

board

Alias for field number 2

chance

Alias for field number 4

moves

Alias for field number 3

to_move

Alias for field number 0

utility

Alias for field number 1

games.minmax_decision(state, game)

Given a state in a game, calculate the best move by searching forward all the way to the terminal states. [Figure 5.3]

games.expect_minmax(state, game)

[Figure 5.11] Return the best move for a player after dice are thrown. The game tree includes chance nodes along with min and max nodes.

games.alpha_beta_search(state, game)

Search game to determine best action; use alpha-beta pruning. As in [Figure 5.7], this version searches all the way to the leaves.

games.alpha_beta_cutoff_search(state, game, d=4, cutoff_test=None, eval_fn=None)

Search game to determine best action; use alpha-beta pruning. This version cuts off search and uses an evaluation function.

games.query_player(game, state)

Make a move by querying standard input.

games.random_player(game, state)

A player that chooses a legal move at random.

games.alpha_beta_player(game, state)

A player that picks a move using full alpha-beta search.

games.minmax_player(game, state)

A player that picks a move using full minimax search.

games.expect_minmax_player(game, state)

A player for stochastic games that picks a move using expectiminimax search.

class games.Game

Bases: object

A game is similar to a problem, but it has a utility for each state and a terminal test instead of a path cost and a goal test. To create a game, subclass this class and implement actions, result, utility, and terminal_test. You may override display and successors or you can inherit their default methods. You will also need to set the .initial attribute to the initial state; this can be done in the constructor.

actions(state)

Return a list of the allowable moves at this point.

result(state, move)

Return the state that results from making a move from a state.

utility(state, player)

Return the value of this final state to player.

terminal_test(state)

Return True if this is a final state for the game.

to_move(state)

Return the player whose move it is in this state.

display(state)

Print or otherwise display the state.

play_game(*players)

Play an n-person, move-alternating game.

class games.StochasticGame

Bases: Game

A stochastic game includes uncertain events which influence the moves of players at each state. To create a stochastic game, subclass this class and implement chances and outcome along with the other unimplemented game class methods.

chances(state)

Return a list of all possible uncertain events at a state.

outcome(state, chance)

Return the state which is the outcome of a chance trial.

probability(chance)

Return the probability of occurrence of a chance.

play_game(*players)

Play an n-person, move-alternating stochastic game.

class games.Fig52Game

Bases: Game

The game represented in [Figure 5.2]. Serves as a simple test case.

succs = {'A': {'a1': 'B', 'a2': 'C', 'a3': 'D'}, 'B': {'b1': 'B1', 'b2': 'B2', 'b3': 'B3'}, 'C': {'c1': 'C1', 'c2': 'C2', 'c3': 'C3'}, 'D': {'d1': 'D1', 'd2': 'D2', 'd3': 'D3'}}

utils = {'B1': 3, 'B2': 12, 'B3': 8, 'C1': 2, 'C2': 4, 'C3': 6, 'D1': 14, 'D2': 5, 'D3': 2}

initial = 'A'

actions(state)

Return the moves available from the given node of the game tree.

result(state, move)

Return the successor node reached by taking the given move.

utility(state, player)

Return the leaf value, negated for the MIN player.

terminal_test(state)

Return True for leaf nodes, i.e. anything other than A, B, C, D.

to_move(state)

Return ‘MIN’ for the second-ply nodes B, C, D, otherwise ‘MAX’.

class games.Fig52Extended

Bases: Game

Similar to Fig52Game but bigger. Useful for visualisation

succs = {0: {'l': 1, 'm': 2, 'r': 3}, 1: {'l': 4, 'm': 5, 'r': 6}, 2: {'l': 7, 'm': 8, 'r': 9}, 3: {'l': 10, 'm': 11, 'r': 12}, 4: {'l': 13, 'm': 14, 'r': 15}, 5: {'l': 16, 'm': 17, 'r': 18}, 6: {'l': 19, 'm': 20, 'r': 21}, 7: {'l': 22, 'm': 23, 'r': 24}, 8: {'l': 25, 'm': 26, 'r': 27}, 9: {'l': 28, 'm': 29, 'r': 30}, 10: {'l': 31, 'm': 32, 'r': 33}, 11: {'l': 34, 'm': 35, 'r': 36}, 12: {'l': 37, 'm': 38, 'r': 39}}

utils = {}

actions(state)

Return the moves, sorted, available from the given node.

result(state, move)

Return the successor node reached by taking the given move.

utility(state, player)

Return the leaf value, negated for the MIN player.

terminal_test(state)

Return True once the state falls outside the 0-12 node range.

to_move(state)

Return ‘MIN’ for the second-ply nodes 1, 2, 3, otherwise ‘MAX’.

class games.TicTacToe(h=3, v=3, k=3)

Bases: Game

Play TicTacToe on an h x v board, with Max (first player) playing ‘X’. A state has the player to move, a cached utility, a list of moves in the form of a list of (x, y) positions, and a board, in the form of a dict of {(x, y): Player} entries, where Player is ‘X’ or ‘O’.

actions(state)

Legal moves are any square not yet taken.

result(state, move)

Place the current player’s mark at move and return the new state; an illegal move leaves the state unchanged.

utility(state, player)

Return the value to player; 1 for win, -1 for loss, 0 otherwise.

terminal_test(state)

A state is terminal if it is won or there are no empty squares.

display(state)

Print the board as a grid, with empty squares shown as dots.

compute_utility(board, move, player)

If ‘X’ wins with this move, return 1; if ‘O’ wins return -1; else return 0.

k_in_row(board, move, player, delta_x_y)

Return true if there is a line through move on board for player.

class games.ConnectFour(h=7, v=6, k=4)

Bases: TicTacToe

A TicTacToe-like game in which you can only make a move on the bottom row, or in a square directly above an occupied square. Traditionally played on a 7x6 board and requiring 4 in a row.

actions(state)

Return legal moves: bottom-row squares or squares directly above an occupied one.

class games.Gomoku(h=15, v=16, k=5)

Bases: TicTacToe

Also known as Five in a row.

class games.Backgammon

Bases: StochasticGame

A two player game where the goal of each player is to move all the checkers off the board. The moves for each state are determined by rolling a pair of dice.

actions(state)

Return a list of legal moves for a state.

result(state, move)

Apply the player’s checker move(s) for the current dice roll and return the resulting state, with the turn passed to the opponent.

utility(state, player)

Return the value to player; 1 for win, -1 for loss, 0 otherwise.

terminal_test(state)

A state is terminal if one player wins.

get_all_moves(board, player)

All possible moves for a player i.e. all possible ways of choosing two checkers of a player from the board for a move at a given state.

display(state)

Display state of the game.

compute_utility(board, move, player)

If ‘W’ wins with this move, return 1; if ‘B’ wins return -1; else return 0.

checkers_at_home(board, player)

Return the no. of checkers at home for a player.

is_legal_move(board, start, steps, player)

Move is a tuple which contains starting points of checkers to be moved during a player’s turn. An on-board move is legal if both the destinations are open. A bear-off move is the one where a checker is moved off-board. It is legal only after a player has moved all his checkers to his home.

move_checker(board, start, steps, player)

Move a checker from starting point by a given number of steps

is_point_open(player, point)

A point is open for a player if the no. of opponent’s checkers already present on it is 0 or 1. A player can move a checker to a point only if it is open.

chances(state)

Return a list of all possible dice rolls at a state.

outcome(state, chance)

Return the state which is the outcome of a dice roll.

probability(chance)

Return the probability of occurrence of a dice roll.

Games or Adversarial Search (Chapter 5)

class games4e.GameState(to_move, utility, board, moves)

Bases: tuple

board

Alias for field number 2

moves

Alias for field number 3

to_move

Alias for field number 0

utility

Alias for field number 1

class games4e.StochasticGameState(to_move, utility, board, moves, chance)

Bases: tuple

board

Alias for field number 2

chance

Alias for field number 4

moves

Alias for field number 3

to_move

Alias for field number 0

utility

Alias for field number 1

games4e.minmax_decision(state, game)

Given a state in a game, calculate the best move by searching forward all the way to the terminal states. [Figure 5.3]

games4e.expect_minmax(state, game)

[Figure 5.11] Return the best move for a player after dice are thrown. The game tree includes chance nodes along with min and max nodes.

games4e.alpha_beta_search(state, game)

Search game to determine best action; use alpha-beta pruning. As in [Figure 5.7], this version searches all the way to the leaves.

games4e.alpha_beta_cutoff_search(state, game, d=4, cutoff_test=None, eval_fn=None)

Search game to determine best action; use alpha-beta pruning. This version cuts off search and uses an evaluation function.

games4e.monte_carlo_tree_search(state, game, N=1000)

Choose a move by running N iterations of Monte Carlo tree search from the given state, repeatedly selecting a leaf via UCB, expanding it, simulating a random playout, and backing the result up; return the most-visited child move.

games4e.query_player(game, state)

Make a move by querying standard input.

games4e.random_player(game, state)

A player that chooses a legal move at random.

games4e.alpha_beta_player(game, state)

A player that picks a move using full alpha-beta search.

games4e.expect_min_max_player(game, state)

A player for stochastic games that picks a move using expectiminimax search.

games4e.mcts_player(game, state)

A player that picks a move using Monte Carlo tree search.

class games4e.Game

Bases: object

A game is similar to a problem, but it has a utility for each state and a terminal test instead of a path cost and a goal test. To create a game, subclass this class and implement actions, result, utility, and terminal_test. You may override display and successors or you can inherit their default methods. You will also need to set the .initial attribute to the initial state; this can be done in the constructor.

actions(state)

Return a list of the allowable moves at this point.

result(state, move)

Return the state that results from making a move from a state.

utility(state, player)

Return the value of this final state to player.

terminal_test(state)

Return True if this is a final state for the game.

to_move(state)

Return the player whose move it is in this state.

display(state)

Print or otherwise display the state.

play_game(*players)

Play an n-person, move-alternating game.

class games4e.StochasticGame

Bases: Game

A stochastic game includes uncertain events which influence the moves of players at each state. To create a stochastic game, subclass this class and implement chances and outcome along with the other unimplemented game class methods.

chances(state)

Return a list of all possible uncertain events at a state.

outcome(state, chance)

Return the state which is the outcome of a chance trial.

probability(chance)

Return the probability of occurrence of a chance.

play_game(*players)

Play an n-person, move-alternating stochastic game.

class games4e.Fig52Game

Bases: Game

The game represented in [Figure 5.2]. Serves as a simple test case.

succs = {'A': {'a1': 'B', 'a2': 'C', 'a3': 'D'}, 'B': {'b1': 'B1', 'b2': 'B2', 'b3': 'B3'}, 'C': {'c1': 'C1', 'c2': 'C2', 'c3': 'C3'}, 'D': {'d1': 'D1', 'd2': 'D2', 'd3': 'D3'}}

utils = {'B1': 3, 'B2': 12, 'B3': 8, 'C1': 2, 'C2': 4, 'C3': 6, 'D1': 14, 'D2': 5, 'D3': 2}

initial = 'A'

actions(state)

Return the moves available from the given node of the game tree.

result(state, move)

Return the successor node reached by taking the given move.

utility(state, player)

Return the leaf value, negated for the MIN player.

terminal_test(state)

Return True for leaf nodes, i.e. anything other than A, B, C, D.

to_move(state)

Return ‘MIN’ for the second-ply nodes B, C, D, otherwise ‘MAX’.

class games4e.Fig52Extended

Bases: Game

Similar to Fig52Game but bigger. Useful for visualisation

succs = {0: {'l': 1, 'm': 2, 'r': 3}, 1: {'l': 4, 'm': 5, 'r': 6}, 2: {'l': 7, 'm': 8, 'r': 9}, 3: {'l': 10, 'm': 11, 'r': 12}, 4: {'l': 13, 'm': 14, 'r': 15}, 5: {'l': 16, 'm': 17, 'r': 18}, 6: {'l': 19, 'm': 20, 'r': 21}, 7: {'l': 22, 'm': 23, 'r': 24}, 8: {'l': 25, 'm': 26, 'r': 27}, 9: {'l': 28, 'm': 29, 'r': 30}, 10: {'l': 31, 'm': 32, 'r': 33}, 11: {'l': 34, 'm': 35, 'r': 36}, 12: {'l': 37, 'm': 38, 'r': 39}}

utils = {}

actions(state)

Return the moves, sorted, available from the given node.

result(state, move)

Return the successor node reached by taking the given move.

utility(state, player)

Return the leaf value, negated for the MIN player.

terminal_test(state)

Return True once the state falls outside the 0-12 node range.

to_move(state)

Return ‘MIN’ for the second-ply nodes 1, 2, 3, otherwise ‘MAX’.

class games4e.TicTacToe(h=3, v=3, k=3)

Bases: Game

Play TicTacToe on an h x v board, with Max (first player) playing ‘X’. A state has the player to move, a cached utility, a list of moves in the form of a list of (x, y) positions, and a board, in the form of a dict of {(x, y): Player} entries, where Player is ‘X’ or ‘O’.

actions(state)

Legal moves are any square not yet taken.

result(state, move)

Place the current player’s mark at move and return the new state; an illegal move leaves the state unchanged.

utility(state, player)

Return the value to player; 1 for win, -1 for loss, 0 otherwise.

terminal_test(state)

A state is terminal if it is won or there are no empty squares.

display(state)

Print the board as a grid, with empty squares shown as dots.

compute_utility(board, move, player)

If ‘X’ wins with this move, return 1; if ‘O’ wins return -1; else return 0.

k_in_row(board, move, player, delta_x_y)

Return true if there is a line through move on board for player.

class games4e.ConnectFour(h=7, v=6, k=4)

Bases: TicTacToe

A TicTacToe-like game in which you can only make a move on the bottom row, or in a square directly above an occupied square. Traditionally played on a 7x6 board and requiring 4 in a row.

actions(state)

Return legal moves: bottom-row squares or squares directly above an occupied one.

class games4e.Backgammon

Bases: StochasticGame

A two player game where the goal of each player is to move all the checkers off the board. The moves for each state are determined by rolling a pair of dice.

actions(state)

Return a list of legal moves for a state.

result(state, move)

Apply the player’s checker move(s) for the current dice roll and return the resulting state, with the turn passed to the opponent.

utility(state, player)

Return the value to player; 1 for win, -1 for loss, 0 otherwise.

terminal_test(state)

A state is terminal if one player wins.

get_all_moves(board, player)

All possible moves for a player i.e. all possible ways of choosing two checkers of a player from the board for a move at a given state.

display(state)

Display state of the game.

compute_utility(board, move, player)

If ‘W’ wins with this move, return 1; if ‘B’ wins return -1; else return 0.

checkers_at_home(board, player)

Return the no. of checkers at home for a player.

is_legal_move(board, start, steps, player)

Move is a tuple which contains starting points of checkers to be moved during a player’s turn. An on-board move is legal if both the destinations are open. A bear-off move is the one where a checker is moved off-board. It is legal only after a player has moved all his checkers to his home.

move_checker(board, start, steps, player)

Move a checker from starting point by a given number of steps

is_point_open(player, point)

A point is open for a player if the no. of opponent’s checkers already present on it is 0 or 1. A player can move a checker to a point only if it is open.

chances(state)

Return a list of all possible dice rolls at a state.

outcome(state, chance)

Return the state which is the outcome of a dice roll.

probability(chance)

Return the probability of occurrence of a dice roll.

Multiagent decision making: game theory and social choice (Chapter 18).

game_theory4e.dominates(payoff, s, t, strongly=True)

[Section 18.2] True if, for the player whose payoff matrix is ‘payoff’ (rows = that player’s own strategies, columns = the opponents’ joint strategies), strategy s dominates strategy t. Strong domination requires s to be strictly better than t against every opponent strategy; weak domination requires s to be no worse everywhere and strictly better in at least one column.

game_theory4e.dominant_strategy(payoff, strongly=True)

[Section 18.2] Return the strategy (row index) that dominates all of the player’s other strategies, or None if the player has no such dominant strategy. To analyze the column player of a game, pass the transpose of their payoff matrix so that their strategies become the rows.

game_theory4e.iterated_dominance(payoff1, payoff2, strongly=True)

[Section 18.2] Iterated elimination of dominated strategies: since a rational player never plays a dominated strategy, we can repeatedly delete, for either player, any strategy that is dominated among the strategies still in play, until none remains. ‘payoff1’/’payoff2’ are the row and column player’s payoff matrices. Returns the surviving (rows, cols) strategy indices of the original game.

game_theory4e.pure_nash_equilibria(payoff1, payoff2)

[Section 18.2] All pure-strategy Nash equilibria of a two-player game, given the payoff matrices payoff1[i][j] and payoff2[i][j] for the row and column player when the row player plays i and the column player plays j. A profile (i, j) is a Nash equilibrium when each player is playing a best response to the other, so neither can gain by deviating unilaterally. Returns a list of (i, j) profiles (possibly empty, e.g. for matching pennies).

game_theory4e.solve_zero_sum_game(payoff)

[Section 18.2] Solve a two-player zero-sum game by linear programming. ‘payoff’ is the payoff to the row (maximizing) player; the column (minimizing) player receives its negation. By von Neumann’s minimax theorem the game has a value v and optimal mixed strategies x, y such that x maximizes the row player’s guaranteed payoff (for every column j, sum_i x_i payoff[i][j] >= v) and y minimizes the column player’s guaranteed loss. Returns (value, row_strategy, col_strategy).

game_theory4e.shapley_value(players, characteristic_function)

[Section 18.3] The Shapley value of a cooperative game (players, v): a fair division of the grand coalition’s value v(N) that pays each player the average, over all n! orderings of the players, of the marginal contribution mc_i(C) = v(C and {i}) - v(C) they make to the players preceding them. The ‘characteristic_function’ is a callable mapping a frozenset of players to its value. Returns a dict mapping each player to their Shapley value.

game_theory4e.is_in_core(players, characteristic_function, payoff)

[Section 18.3] True if ‘payoff’ (a dict mapping each player to their share) lies in the core of the cooperative game (players, v): it must distribute exactly the grand coalition’s value (sum of shares = v(N)) and be immune to defection, i.e. for every coalition C the players in C receive at least v(C) (otherwise C would be better off on its own). An empty core means the grand coalition cannot form.

game_theory4e.plurality_winner(preferences)

[Section 18.4] Winner under plurality voting: the candidate ranked first by the most voters. ‘preferences’ is a list of ballots, each a list of candidates ordered from most to least preferred.

game_theory4e.borda_winner(preferences)

[Section 18.4] Winner under the Borda count: with k candidates each voter awards k points to their top choice, k-1 to the next, down to 1 for the last; the candidate with the highest total score wins.

game_theory4e.condorcet_winner(preferences)

[Section 18.4] The Condorcet winner: the candidate that beats every other candidate in a pairwise majority comparison. Returns None when no such candidate exists (Condorcet’s paradox), in which case majority preference is cyclic.

game_theory4e.vickrey_auction(bids)

[Section 18.4] Sealed-bid second-price (Vickrey) auction: the highest bidder wins but pays only the second-highest bid. ‘bids’ maps each bidder to their bid. Returns the (winner, price) pair. Because the winner does not pay their own bid, bidding one’s true value is a dominant strategy (the mechanism is truth-revealing).

game_theory4e.contract_net(tasks, agents, bid, select=<built-in function min>)

[Section 18.4.1] The contract net protocol for task allocation. For each task the manager broadcasts a task announcement; every agent submits a bid through the callable bid(agent, task), which returns a numeric bid or None when the agent cannot or will not perform the task. The manager then awards the task to the agent with the best bid (‘select’ = min for costs, max for values). Returns a dict mapping each task to an (agent, bid) award, or to None if nobody bid.

game_theory4e.alternating_offers_bargaining(discount_a, discount_b)

[Section 18.4.4] Rubinstein’s alternating-offers bargaining over how to split a pie of size 1 between two impatient agents with discount factors discount_a and discount_b in [0, 1). In the unique subgame-perfect equilibrium the agent who makes the first offer (A) keeps a share (1 - discount_b) / (1 - discount_a * discount_b) and B receives the rest; the more patient an agent is (larger discount factor) the larger the share it secures. Returns the (share_a, share_b) pair.