A game theory question about tiles, part 2

179 Views Asked by At

A recent question asked about the following game:

There are six tiles, face down. Three are type A and three are type B.

Each player turns over three tiles, and wins if they match. Otherwise, they are put face down again, but both players now know what they are.

My change is this: Each player may turn over 3 or fewer than 3 tiles, but at least one tile that was not previously turned over. Now who has the advantage?

1

There are 1 best solutions below

4
On

The first player has the advantage. We can argue as follows... Suppose the first player chooses the strategy of only one tile to flip in the first turn. So this reveals exactly one tile.

Now suppose there is a winning strategy for the second player which includes flipping exactly $n$ tiles at the turn. If $n = 1$, then first player can replicate it by choosing instead to flip two tiles in the first turn. Similarly if $n = 2$, then the first player could have chosen to flip three tiles in the first turn. So the only possible winning strategy for the second player is to flip $n = 3$ times.

However, there are only two ways the second player can win in three tile flips (note if the turn goes back to the first player after four flips, that is a certain loss for the second player). Either the first two tiles picked must be identical to the one already known ($\frac{1}{10}$ probability) or by picking three identical tiles which are all different from the already known one ($\frac{3}{20}$ probability). Thus this strategy has a total chance of winning of $\frac{1}{4}$, leaving the first player the advantage.


Addendum - including freedom for players to dynamically decide number of flips per turn.

We add assumptions that each player uses all available information, is rational, play to win, know that the other is also similar, etc.

Let us denote the information on tiles available at any stage in the game by $I = (a, b)$, where $0 \le a \le 3, 0 \le b \le a$ represent the number of known tiles of each kind known after the last flip. As we are not interested in order, the larger known pile is $a$.

Now we have the following information states and transition probabilities possible during the game:

                              (2,2) ----> (3, 2)
                           2/3  |     1
                                |
                 (1, 1) ----> (2, 1) ----> (3, 1)
                   |     1      |    1/3 
              3/5  |        3/4 |          
   (0, 0) ----> (1, 0) ----> (2, 0) ----> (3, 0)
          1             2/5           1/4

Let us consider two players only (I assume), P and Q, with P going first. Let value of an information position $V(a, b)$ be the chances of win starting a turn with the information state $(a, b)$, using the best strategy.

Working backwards, suppose someone is left beginning a turn (with upto 3 flips to go) with information $(3, x)$. Clearly this person wins by selecting the 3 known identical tiles. Hence $V(3, x) = 1$.

Next let us assume that someone starts a turn with information $(2, 2)$. Again clearly this person wins as the first new tile opened can be followed by two known identical tiles. So $V(2, 2) = 1$.

If the person starts at $(2, 1)$, then stopping by choice after one turn means leaving the other player with $V(2, 2)$ or $V(3, x)$, i.e. a certain win. So it makes sense to try winning. In fact the only way to lose is to get to $(2, 2)$ and then $(3, 2)$, but with one tile of each kind open, so the loss probability is $\frac{1}{3}$. Hence $V(2, 1) = \frac{2}{3}$

Now if the person starts with information $(2, 0)$, then if the flip goes to $(3, 0)$, i.e. with probability $\frac{1}{4}$, there is a certain win. OTOH, if the flip goes to $(2, 1)$, then the only way to win is to get to $(2, 2)$ and then hope for the exactly right tile among two, which is with additional probability $\frac{1}{3}$. Leaving at this stage to the next player does not help / matter as $V(2, 1) = \frac{2}{3}$. Thus $V(2, 0) = \frac{1}{4} + \frac{3}{4}\cdot \frac{1}{3} = \frac{1}{2}$.

Now consider starting a turn from $(1, 1)$. The first flip invariably gets to $(2, 1)$. Now the only way to win in the next flip is to get to $(3, 1)$, so the chances of win are $\frac{1}{3}$. Stopping doesn't make a difference, as $V(2, 1) = \frac{2}{3}$. So $V(1, 1) = \frac{1}{3}$.

Suppose the turn starts at $(1, 0)$. Now with one flip, either you reach $(2, 0)$ or $(1, 1)$. As $V(2, 0) = \frac{1}{2}$ and $V(1, 1) = \frac{1}{3}$, this means stopping after one turn gives a chance of win of $\frac{2}{5}\cdot \frac{1}{2} + \frac{3}{4}\cdot \frac{2}{3} = \frac{7}{10}$. OTOH, playing two turns means reaching $(3, 0)$ with a win probability $\frac{2}{5} \cdot \frac{1}{4}=\frac{1}{10}$, or leaving the turn at $(2, 1)$, i.e. a win probability of $\frac{9}{10} \cdot (1-V(2, 1)) = \frac{3}{10}$. So the chances of winning flipping twice and then deciding to stop or continue is $\frac{1}{10} + \frac{3}{10} =\frac{4}{10}$, which is not as good as stopping after the first flip. Thus $V(1, 0) = 7/10$.

Finally, if one starts from $(0, 0)$ the first flip takes to $(1, 0)$, and then by the strategy of $V(1, 0)$, taking one more flip in fact places the first player in the same position. Hence stopping after two flips is the best strategy, doing this gives you $V(0, 0) = V(1, 0) = \frac{7}{10}$ chances of a win, so the first player has the advantage.