Board Game Theory

May 11, 2022May 11, 2022 Nekst-Online 397 Views

It is Friday afternoon, and the weekly game night with the family is about to begin. A set of games – battleship, rock paper scissors, and guess who- are laid out on a table, and the one who wins the most games will be declared the big winner of the night. Your eight year old cousin proclaims proudly that he is going to beat everyone. Fury and fire boil within: rather death than losing to that brat! Maybe there are some optimal strategies to wield when playing these games, where you will always win more games than your direct opponent. Ultimately, this will lead to becoming the big winner of the night – and thereby achieving eternal fame and the undying respect of the entire family. Time to do some research in this pursuit of glory.

Written by Matthijs Kroesen en Sara Darwinkel

Battleship

First, you move to the game of battleship, where your father is impatiently waiting for you. In this game, you imitate a battle at sea with your direct opponent. Each player has to place five ships of different sizes on a 10 by 10 grid. They can be vertically or horizontally placed, however, it is not allowed to place the ships diagonally. These ships can not overlap, but two different ships can be on neighboring coordinates. The respective lengths of the ships are:

5 for the carrier
4 for the battleship
3 for the cruiser and the submarine
2 for the destroyer

After choosing a location for these ships, each player is going to guess alternately at which coordinate their competitor has placed a ship and sends a torpedo to said coordinate. If you guessed correctly, you hit the ship; if you were wrong, you shot an unnecessary torpedo. To remember where you have sent your missiles, you place a red torpedo on your own grid in case of a hit, and a white torpedo otherwise. After hitting all the coordinates of a certain ship, then this ship sinks to the bottom of the ocean. If you sink the entire fleet of your foe before he sinks your fleet, you have won the battle, and one point is added to your resume of the night.

At first, this game seems to be based purely on luck. After all, every choice of coordinate is completely random; since you can not know where your rival has placed his ships. Furthermore, your father always plays without a strategy, thus it is also not possible to predict his behavior, unless by cheating by looking at a reflective surface to see his grid (which is unfortunately not allowed). Maybe, applying some game theory will help here. What are the optimal plays that will help you win the most games?

Firstly, let’s discuss the strategy that seems to always be the case: to choose every coordinate at random. This means that you have no strategy whatsoever; every turn, you ignore the results of the previous turn (even if you had hit a ship) and you randomly pick a new coordinate. Let’s assume that the random variable $X = 1$ if a ship is hit, and $X = 0$ otherwise. In the first move, you have $P(X=1) = \frac{(2+3+3+4+5)}{100} = \frac{17}{100}$ . Afterward, you pick new coordinates without replacement, thus $X \sim HYP(n,17,100)$ , where $n$ is the number of plays necessary to end the game. After running 100 million simulations of games, it becomes clear that an approximate 99% confidence interval for $n$ is $CI=[78, ∞)$ , and the median for $n$ is 96 shots (DataGenetics, 2011). Obviously, this is not the desired outcome, and you need fewer plays to win consistently. Let’s consider some different strategies.

When hitting a vessel of your enemy, it seems evident that another piece of that vessel must be near. After all, each ship is located on two or more coordinates. Hence we arrive at the ‘hunt and target’ strategy: first ‘hunt’ coordinates (shoot torpedoes at random coordinates), and when hitting a ship, start ‘targeting’ adjacent (up, right, left, or down; unless you have hit a ship that is located on the border of the grid) coordinates. Now, stay in this ‘target’ mode until you have sunk the ship entirely, and then you go back to the ‘hunt’ mode. This reduces the mean amount of plays to end a game of battleship significantly: the median for n is now approximately 65 shots when playing 100 million games of battleship (DataGenetics, 2011). It is evident that this is a big improvement of the random strategy, however, wielding this strategy alone is not optimal yet.

To understand the next strategy fully, we first need to introduce some terminology. If we consider the index of the rows $i=1,2,...,10$ and the index of the columns $j=1,2,..,10$ (in the game itself, the column indexes are $j=A,B,...,J$ , let’s assume for simplicity that the columns have a numerical index), then the coordinate that we bomb is $(i,j)$ . Furthermore, we know that a ship has a length of at least two units. This means that if we would ‘hunt’ in only 50 of the coordinates, namely the coordinates where $i+j=2n$ where $n \in \mathbb{N}$ (the white squares in the picture), we would still hit all the desired targets eventually in the ‘hunt’ strategy. With the help of the ‘target’ strategy, all ships will be sunk. This means that the set of coordinates that can be targeted randomly is reduced by 50 squares. We call this the parity strategy. This strategy, when wielded in combination with the ‘hunt and target’ strategy, again leads to a small improvement: when playing 100 million games, the approximate median for $n$ is 63 shots (as opposed to the 96 shots we found before) (DataGenetics, 2011). Note that if you get lucky and sink the smallest ship of two units, you can ‘hunt’ for the coordinates where $i+j=3n$ where $n\in\mathbb{N}$ , furthermore improving the required amount of plays to find a different ship. Obviously, this tactic is applicable as well if you have sunken all the ships with length three or fewer units, etcetera. This improved parity strategy is a special case of the next tactic.

This last strategy is called probability assessment, which basically means that you assess whether a certain ship has a high or low probability of being on a certain coordinate. When starting a new game, this strategy is hardly useable yet, since thus far you have not acquired any information about where a vessel could be (the vessels could be everywhere). But as the game progresses, you can use this strategy more often. Let’s assume you have sunk all ships of two and three units, and you have a space of three units between two already fired torpedoes. Now there is a probability of zero that a leftover ship is in this space since their lengths are larger than the length of the space. Also, if you have an area where no torpedoes are fired and a different area where a lot of torpedoes are fired, then there is a higher probability that there is a battleship in the area with little torpedoes than the area with lots of torpedoes. Wielding this probability assessment strategy in addition to wielding all the previously mentioned strategies, the approximate median for the number of shots fired $n$ is 43, a serious improvement. When applying these strategies correctly, it is very difficult for your direct opponent to beat you in one game, let alone when using an overall score of multiple games, which is the case this game night.

After playing multiple games of battleship, you have utterly destroyed your father, leaving him with mixed feelings about whether he should have left you at an orphanage all those years ago. You move to the Nekst (pun intended) game.

Rock, Paper, Scissors

The next game is rock, paper, scissors. Unfortunately, your sister is sitting at that game. Although she is not that bright, even she can understand this game: the players count down using the verse ‘rock, paper, scissors’, and at ‘scissors’, they have to choose between one element in the set {rock, paper, scissors}, showing the corresponding hand-signs. Scissors beat rock, rock beats scissors, and paper beats rock. If there is a draw, the game is played again, until some player wins.

Maybe some game theory will help us when dealing with the problem of finding an optimal strategy. You are player 1 and your sister is player 2. We denote $\pi_i(x) = 1$ if player $i$ wins, $\pi_i(x) = 0$ if there is a draw, and $\pi_i(x) = -1$ if player $i$ loses, $\forall i \in {1,2}$ . The payoff matrix of a game of rock, paper, scissors is:

You \\\\ your sister	Rock	Paper	Scissors
Rock	(0,0)	(-1,1)	(1,-1)
Paper	(1,-1)	(0,0)	(-1,1)
Scissors	(-1,1)	(1,-1)	(0,0)

Notice that there is not a Nash equilibrium in pure strategies. If (Rock, Paper) is played, then you have an incentive to play scissors, but then your sister has an incentive to play rock, ad infinitum. Maybe there is a Nash equilibrium in mixed strategies.

Let $p=(p_1 , p_2 , p_3)$ be the probability vector that you choose rock, paper, and scissors respectively, and let $q=(q_1 , q_2 , q_3)$ be the probability vector such that your sister chooses rock, paper, and scissors respectively. Now your payoff is $\pi_1 (p,q) = p^t A q$ , where $A$ is the payoff matrix of player 1. When optimizing this $\pi_1 (p,q)$ with respect to the choice op player 2, one will end up with the probability vectors $p=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$ and $q=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$ . Now the strategy profile $(p,q)$ is the Nash equilibrium in mixed strategies of rock, paper, scissors (Cornell University, 2014).

This means that according to game theory when playing a finite game, the best you can do is play rock, paper, or scissors each with a probability of ⅓. However, there is one issue: we can not assume our game is finite. A round of game night continues and continues until all games are played multiple times, and a few games of battleship take a whole lot longer than a game of rock, paper, scissors: it is unclear when the game will end, hence we will assume that this game will be repeated infinitely.

Now an entirely different game unfolds. Since players play the game multiple times, the players have the opportunity to react to the actions of their opponent. It has been shown that when playing an infinitely repeated game of rock, paper, scissors, winners tend to repeat winning strategies, and losers tend to switch strategies when they lose a game (Wang et al., 2014). This chosen strategy has the largest probability of being the strategy that would have beaten the strategy their competitor played in the previous game. This is called a conditional response in game theory terminology. For example, player 1 wins a game playing rock, while player 2 played scissors. It is statistically most likely that now player 1 will play rock again, while player 2 will switch strategy to paper.

Hence we arrive at our final strategy you will use to destroy your sister: the so-called conditional strategy. The first game has to be played at random since we have no information yet of previously played games. It’s a $\fraq{1}{3}$ probability that you either draw, win or lose. When losing, it is statistically most likely that your opponent plays the previously played strategy again. Your optimal tactic will now be to play the strategy that will beat the strategy that player 1 plays. Conversely, if you win the game, player 2 will most likely play the strategy that would have beaten your strategy next game. This means that you should play the strategy that will beat player 2’s future strategy – thus playing the strategy that player 2 played in the previous game will be optimal. When wielding this conditional strategy, your chances of winning rock paper scissors will increase by 10% (Wang et al., 2014), a significant amount.

Note that this strategy is only valid if your opponent does not know that you are using this strategy: he could then play his moves such that he would always respond optimally to the conditional choices. Fortunately, since your sister is not that smart, we can assume that she will not figure out your tactic.

After what felt like an eternity, this round of the game night ends. With a very positive win-loss ratio, you leave, quite satisfied. This round has not been as fun for everyone; your sister has started to scroll her Instagram timeline out of pure frustration. Let’s move on to the last game of the night.

Guess Who

It is time for Guess Who, and your mother is waiting for you. She is a real master in this game – you know that, even without her having a strategy – she always wins. Your only chance to win is to find the ultimate strategy in order to beat her random skills.

You both flip your cardboards to get all the characters standing and draw your mystery persons. When all is settled, the battle begins. Since you are the youngest (you play with your mother, so I hope you are), you may begin. Alternately you ask closed questions to each other about physical characteristics of the characters such that, when getting the answer, you can eliminate characters and end up with a final question which will be “Is [enter name] your mystery person?”. If your guess is right you win, if it is wrong you lose.

As you closely look at your cardboard, you rapidly see that in this 3×8 grid with 24 characters (yes, I am giving you the math), each character is different and has his own characteristics. And what is remarkable is that, as each characteristic applies to around five characters, this game is made for narrow questions . We can thus assume that your mother will, without thinking about it, play the narrow question strategy. This strategy is also called the naive or optimistic strategy, your mother is hoping that you have a character that is most convenient to her. According to Mark Rober, who thanks to an algorithm played 625 games of guess who, your mother will have to ask around seven questions in order to determine your mystery character. But you are smart enough and know that you can use math in order to win in less turns.

It is already obvious for you that the most important thing is to ask questions that will optimize the amount of people left on your board, which will hopefully each time result in the elimination of half of the characters. The expected number of people left on the board can be easily computed, let’s take an example. The expected number of people left when you ask “does your character wear earrings?” is the following:

So if the first question you ask is about the earring, the expected number of people left will be a bit more than 20 compared to a bit more than 12 if you ask about a big mouth.

Your question choice is therefore really important. When you halve the amount of characters left each time you go from 24, to 12, to 6, to 3, to 2 or 1, to finally only one character left on your board. Hence you will win one third of the time in five guesses, two thirds of the time in six guesses. But what questions are best to ask? This matter is all about decision theory.

Even though this seems like cheating, you can ask compound questions. For example, you can ask if the mystery person of your mother has ginger or white hair or if they wear glasses. This way, you eliminate exactly twelve characters. In the instructions it is only written you must ask yes/no questions. This is just like cheating within the rules ;).

Another strategy would be to begin with the question “Does your mystery person’s name begin with the letter A-G?”. This way you again eliminate half of the characters.

The problem with these two methods would be that they are really obvious. Your mother may not be the smartest, but your intelligence does not come from nobody. If she plays the game with the same strategy, you are back to winning with a chance of 50 percent. So what would be the best question to begin with? Well – according to Rafael Prieto Curiel – you need to take the question which has an expected outcome of characters left as close as possible to half of your characters remaining on your board. For the first question, half of the characters would be twelve. This question would be “Does your mystery person have a big mouth?”. This way you concretely ask something about a characteristic without giving your mother doubts about a special strategy.

Looking at the table it seems a logical step to then ask about “facial hair”. Yet the problem is that all characteristics are correlated and hence you can use the table only for the first question and must then compute it all again. Playing this game asking broad questions but without thinking about the correlation would be better than using the naive strategy but is far from optimal. It is important to think a few steps ahead because some questions may halve your characters but leave you only with terrible follow up questions.

To wrap this up, the best way to play this game is to ask questions that lead to an expected number of people left as close as possible to half of the characters remaining on your board. By doing this you will win around 80 percent of the time if your mother does not play the same optimal strategy. And to make this better, if you play multiple times, your chances of winning increase according to the law of large numbers and you will, if you play indefinitely, win with 96 percent confidence.

You made it! You are the big winner, the game master of the night, the overlord of the house. But while you are calling all your nerd friends to share your victory, your family is plotting against you. This is the end of the board game nights, it is no fun like this. Nekst time you will have a different game night, namely ‘just dance’ this way. Your math brain will not get in the way… or will it?

Battleship

Rock, Paper, Scissors

Guess Who

You May Also Like

Epidemics, Vaccines and Mathematics

Many Thanks to our Professor, Colleague and Friend

Column: Bipartite Graphs