Games & Game Theory

Games or Adversarial Search (Chapter 5)

class 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 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

minmax_decision(state, game)[source]

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

expect_minmax(state, game)[source]

[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.

alpha_beta_search(state, game)[source]

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

alpha_beta_cutoff_search(state, game, d=4, cutoff_test=None, eval_fn=None)[source]

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

monte_carlo_tree_search(state, game, N=1000)[source]

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.

query_player(game, state)[source]

Make a move by querying standard input.

random_player(game, state)[source]

A player that chooses a legal move at random.

alpha_beta_player(game, state)[source]

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

minmax_player(game, state)[source]

A player that picks a move using full minimax search.

expect_minmax_player(game, state)[source]

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

mcts_player(game, state)[source]

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

class Game[source]

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)[source]

Return a list of the allowable moves at this point.

result(state, move)[source]

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

utility(state, player)[source]

Return the value of this final state to player.

terminal_test(state)[source]

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

to_move(state)[source]

Return the player whose move it is in this state.

display(state)[source]

Print or otherwise display the state.

play_game(*players)[source]

Play an n-person, move-alternating game.

class StochasticGame[source]

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)[source]

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

outcome(state, chance)[source]

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

probability(chance)[source]

Return the probability of occurrence of a chance.

play_game(*players)[source]

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

class Fig52Game[source]

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)[source]

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

result(state, move)[source]

Return the successor node reached by taking the given move.

utility(state, player)[source]

Return the leaf value, negated for the MIN player.

terminal_test(state)[source]

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

to_move(state)[source]

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

class Fig52Extended[source]

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)[source]

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

result(state, move)[source]

Return the successor node reached by taking the given move.

utility(state, player)[source]

Return the leaf value, negated for the MIN player.

terminal_test(state)[source]

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

to_move(state)[source]

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

class TicTacToe(h=3, v=3, k=3)[source]

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)[source]

Legal moves are any square not yet taken.

result(state, move)[source]

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

utility(state, player)[source]

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

terminal_test(state)[source]

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

display(state)[source]

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

compute_utility(board, move, player)[source]

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)[source]

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

class ConnectFour(h=7, v=6, k=4)[source]

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)[source]

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

class Gomoku(h=15, v=16, k=5)[source]

Bases: TicTacToe

Also known as Five in a row.

class Backgammon[source]

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)[source]

Return a list of legal moves for a state.

result(state, move)[source]

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)[source]

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

terminal_test(state)[source]

A state is terminal if one player wins.

get_all_moves(board, player)[source]

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)[source]

Display state of the game.

compute_utility(board, move, player)[source]

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

checkers_at_home(board, player)[source]

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

is_legal_move(board, start, steps, player)[source]

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)[source]

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

is_point_open(player, point)[source]

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)[source]

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

outcome(state, chance)[source]

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

probability(chance)[source]

Return the probability of occurrence of a dice roll.

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

dominates(payoff, s, t, strongly=True)[source]

[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.

dominant_strategy(payoff, strongly=True)[source]

[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.

iterated_dominance(payoff1, payoff2, strongly=True)[source]

[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.

pure_nash_equilibria(payoff1, payoff2)[source]

[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).

solve_zero_sum_game(payoff)[source]

[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).

shapley_value(players, characteristic_function)[source]

[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.

is_in_core(players, characteristic_function, payoff)[source]

[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.

plurality_winner(preferences)[source]

[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.

borda_winner(preferences)[source]

[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.

condorcet_winner(preferences)[source]

[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.

vickrey_auction(bids)[source]

[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).

contract_net(tasks, agents, bid, select=<built-in function min>)[source]

[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.

alternating_offers_bargaining(discount_a, discount_b)[source]

[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.