Tic Tac Toe with Bidding

In order to spice up classical combinatorial games, mathematicians have explored what happens if, instead of alternating turns, players bid each turn for the opportunity to make a move. Here we'll look at Tic Tac Toe with such a bidding scheme.

Setup

Here is an option for manipulatives:

Tic Tac Toe boards (12 for $12 or 30 for $19)
Plastic poker chips (600 for $14)
Dry erase cards (180 for $8)
Dry erase markers (72 for $10)

You will want nine X's and O's per board, since it's no longer guaranteed that you need no more than five of each. If using the boards above, which come with five X's and five O's, you'll need roughly twice the number of boards as concurrent games, since you'll need to pool the X and O pieces from two boards for one game.

To start, students will each have $4$ chips of one color (e.g., blue) and one of the players will start with a special chip (e.g., red). Who starts the game with the special chip can be decided with a coin flip or paper-rock-scissors each game or can trade back and forth. The special chip is the tie-breaker chip. One player plays only X's and the other player plays only O's.

Each turn, players will start by making a bid. They will choose some number of their chips to bid and write it on their bidding card, keeping it hidden. When both players have their bids written down, they compare them. The player with the highest bid gives that number of chips to the other player and then makes a move wherever they like. The turn is then over and the next turn begins with a new round of bidding. It is always acceptable to bid $0$ chips.

If there is ever a tie bid, the player with the tie-breaker chip has a choice:

Win the bid: Make a move at the cost of giving the other player the bid number of chips along with the tie-breaker chip
Lose the bid: Let the other player make a move, keep the tie-breaker chip, and receive the bid number of chips from the other player

Note: The tie-breaker chip does not count as a chip for bidding. It is only used as above to settle ties.

As in standard Tic Tac Toe rules, the winner is the first player to get three of their letters in a row, column, or diagonal. If the game ends with no three-in-a-rows, the player who did not start with the tie-breaker chip is the winner.

Depending on the age of the students and the number of chips you want to use, a nice substitute for bidding cards could simply be having the students secretly put some number of their chips (the bid amount) in one hand and the rest in their other hand, placing their bid hands in the center of the table and revealing their bids at the same time.

Example

Players X and O play a game each starting with $4$ chips, with Player X starting with the tie-breaker chip.

In the first round, X bids $2$ and O bids $1$. X wins the bid and plays in the upper left corner:
Next round, X and O both bid $1$ chip. X has the tie-breaker chip and chooses to win the bid, playing in the center square. O now has the tie-breaker chip:
Next, X bids $1$ and O bids $2$. O wins the bid and plays in the lower right corner, blocking X:
In the fourth round, X and O both bid $2$. O has the tie-breaker chip and chooses to lose the bid, allowing X to play in the upper right corner:
Next X bids $1$ chips and O bids $2$. O plays in the lower left square.
Next X bids $3$ chips and O bids $4$. O plays in the lower center square, winning the game.

Challenges

While this game is tricky to analyze and the main strategizing will likely be local (i.e., comparing chip pools and anticipating the next one or two moves), it can be instructive to start with different amounts of chips and even unequal amounts. In general, players should play each other and discuss strategies, trying to identify whether one player or another has an advantage, what a good strategy might look like, and so on.

Notes

Whatever the state of the game board, all other things being equal, it is better for a player to have a larger proportion of the chip pool going into bidding. If $n$ is $n$ chips and $n^*$ is $n$ chips plus the tie-breaker chip, then the pecking order is
\[ 0 < 0^* < 1 < 1^* < 2 < 2^* < 3 < 3^* < 4 < 4^* < ... \]
We can think of the tie-breaker chip acting as a sort of fractional or infinitesimally positive chip for the purpose of a bidding advantage.

If it is worth bidding enough chips to tie and then not use the tie-breaker, it would instead be better to bid one chip fewer and lose the bid outright, since the net effect on the game board is the same and you end the turn with more chips.
There will be certain times where a player will have to bid all or a majority of their chips in order to secure the next move. This will sometimes be at odds with their long-term interest, however. For example, if X bids all $4$ chips in the first round, they will have earned the right to play wherever they like. However, O would then control $8$ chips to X's $0$. By bidding $1$ chip, then $2$ chips, and then $4$ chips for three consecutive rounds, O could ensure getting to move the next three turns in a row and easily win the game. So, while getting the first move is pretty advantageous, getting it at the expense of too many of one's chips is clearly not. We see an example of this in the end of the example game, where having a clear runway for two moves in a row is what enabled O to win, despite X's early advantage.
Develin and Payne have analyzed the game based on the available pool of chips (the combined total of what X and O start with, not counting the tie-breaker, so our standard game has $4+4=8$ chips, total) and found that as long as the total number of chips is not $5$, it is optimal for the first player who moves to play in the center square. In the case of $5$ chips, the optimal first move is to play in a corner. (There are cases where playing in a corner is just as optimal as playing in the center, but the hinging a strategy around $5$ is easier to remember.)
Richman calculus provides a nice framework for analyzing the game states. The basic idea is that for any state of the board $G$, you can assign a threshold number $R(G) \in [0,1]$ such that $X$ has a winning strategy on board $G$ if their proportion of the chips is greater than $R(G)$. Develin and Payne discuss this in their paper for games like ours. For something more in the vein of Richman's original version, check out Lazarus, Loeb, Propp, and Ullman and their paper with Stromquist.

Extra Challenges

I adapted the idea of a tie-breaker chip from Develin and Payne, but students might enjoy thinking about how other tie-breakers change the game. For example, what if the player with the tie-breaker chip never gives it up and always wins tie bids? Is that a huge advantage, even if tied games count as wins for the other player? What other tie-breaker conditions can students think of?
The $3 \times 3$ game is challenging enough, but students might like playing on a $4 \times 4$ board, trying to get $4$ in a row. Scaling down to getting $2$ in a row on a $2 \times 2$ board makes for extremely quick games, but students might be able to articulate a full strategy.
This bidding condition can be added to other games to add a new flavor. How does it impact a Nim-like game? What about something like Connect Four, checkers, or chess?

This post was sponsored by the Julia Robinson Mathematics Festival

Search This Blog

math them