The Centipede game has two players who alternate in making decisions. At each turn, a player can choose between going "down" and ending the game or going "across" and continuing it (except at the last node where going "across" also ends the game). The longer the game goes on, the higher the total utility. A player who ends the game early will get a larger share of what utility there is. Consider a centipede game of three actions per player:

While the game-theoretic best solution is the pessimistic first choice, note that random players have a similar expected payoff. Compare the expected output of random and perfect players:

The tree game of Matching Pennies is a game where each of two people chooses either Head or Tail. If the choices differ, person 1 pays person 2 a dollar; if they are the same, person 2 pays person 1 a dollar. Generate a tree game of Matching Pennies:

Visualize the game:

Clearly, this game gives an advantage to player 2, making it impossible to get a better payoff against a perfect player. Imagine being player 1. Try several strategies to attempt to beat a perfect player (to have a payoff of 1):

An entry game is a game where an entrant decides whether to enter a market or not, and the incumbent decides whether to fight or accommodate the entrant if he enters. Generate an entry game:

Show the decision tree:

Suppose that you are the incumbent player, and your strategy is to always fight (first choice). Find the expected payoff against a random player:

Perfect players assume perfect subgame equilibrium. Since that strategy is suboptimal, it turns out that the perfect player may have a worse payoff than the random player. Find the expected payoff against a perfect player:

Rock Paper Scissors is a zero-sum game, where either one player wins and the other loses, or there is a tie. Generate the tree version of this game, where the second player can choose an action considering the action of the first player:

Visualize the game:

Clearly, in the case of the tree game of Rock Paper Scissors, the second player can always choose the best action, and thus the first player is at a disadvantage by playing first. Write the perfect strategy in this version of Rock Paper Scissors:

Consider the game of tic-tac-toe. Design a function to generate the partial tic-tac-toe game between players A and B:

Consider a partially completed game of tic-tac-toe:

Form a TreeGame based on it:

If both players play perfectly, Player B wins:

If both players play randomly, player 2 is more likely to win only by a small margin: