Chomp is a game in which you have a chocolate bar made of blocks arranged in a m x n matrix, where m is the number of rows and n the number of columns. For example, a 4 x 6 bar would look like
n 0 1 2 3 4 5 m ._____._____._____._____._____._____. | | | | | | | 0 |death| | | | | | |_____|_____|_____|_____|_____|_____| | | | | | | | 1 | | | | | | | |_____|_____|_____|_____|_____|_____| | | | | | | | 2 | | | | | | | |_____|_____|_____|_____|_____|_____| | | | | | | | 3 | | | | | | | |_____|_____|_____|_____|_____|_____|
Notice how the (0,0) block is poisoned, so you want to avoid eating it. The rules are very simple: player A begins the game by choosing a block, and must eat all the blocks that are to the right and to the bottom of the selected block. So if A chooses the block (1,4) our chocolate bar will look like
n 0 1 2 3 4 5 m ._____._____._____._____._____._____. | | | | | | | 0 |death| | | | | | |_____|_____|_____|_____|_____|_____| | | | | | 1 | | | | | |_____|_____|_____|_____| | | | | | 2 | | | | | |_____|_____|_____|_____| | | | | | 3 | | | | | |_____|_____|_____|_____|
Now it is B's turn, and it decided to take the (0,2) block, so B has to eat all the blocks to the right and to the bottom of it. The bar will look like:
n 0 1 m ._____._____. | | | 0 |death| | |_____|_____| | | | 1 | | | |_____|_____| | | | 2 | | | |_____|_____| | | | 3 | | | |_____|_____|
Now it is A's turn again, and it decided to choose (2,0), so we obtain
n 0 1 m ._____._____. | | | 0 |death| | |_____|_____| | | | 1 | | | |_____|_____|
B now plays (1,1), obtaining
n 0 1 m ._____._____. | | | 0 |death| | |_____|_____| | | 1 | | |_____|
A decides to eat (1,0), so
n 0 1 m ._____._____. | | | 0 |death| | |_____|_____|
B eats (0,1), leaving
n 0 m ._____. | | 0 |death| |_____|
which means A must eat the poisoned block and dies, or simply loses. B has won. We could have depicted the whole match as
n 0 1 2 3 4 5 m ._____._____._____._____._____._____. | | | | | | | 0 |death| 6 | 2 | 2 | 2 | 2 | |_____|_____|_____|_____|_____|_____| | | | | | | | 1 | 5 | 4 | 2 | 2 | 1 | 1 | |_____|_____|_____|_____|_____|_____| | | | | | | | 2 | 3 | 3 | 2 | 2 | 1 | 1 | |_____|_____|_____|_____|_____|_____| | | | | | | | 3 | 3 | 3 | 2 | 2 | 1 | 1 | |_____|_____|_____|_____|_____|_____|
where odd numbers are A's moves and even numbers are B's moves. This way of displaying the game allows a single drawing of the block with all the moves in it. It could be even more simple as
n 0 1 2 3 4 5 m ._____._____._____._____._____._____. | | | | | | | 0 |death| 6 | 2 | | | | |_____|_____|_____|_____|_____|_____| | | | | | | | 1 | 5 | 4 | | | 1 | | |_____|_____|_____|_____|_____|_____| | | | | | | | 2 | 3 | | | | | | |_____|_____|_____|_____|_____|_____| | | | | | | | 3 | | | | | | | |_____|_____|_____|_____|_____|_____|
but I prefer the previous one.
Why writing about this game here? Because there is an awesome proof that shows that there exists a strategy for player A to always win the game, but such strategy is not known: it is an open problem of mathematics (at least it is today 22/11/20). I find this fascinating: the proof that there exists a winning strategy is there, but does not provide you with such strategy. This is called a non-constructive proof. But I would call it a mystery-constructive proof instead! It builds mystery and awe. It tells you it is there but does not tell you what it is. Like treasure map: before you have the map you don't know that there is a treasure there. If you were presented by the treasure, directly, you would probably not pay much attention to it. But the map makes the magic, being the proof of the existence and seducing you into going for it.
The actual proof is also a riveting miracle: it uses a strategy-stealing argument, invented by John Nash, the mathematician whose life was portrayed in the movie *A Beautiful Mind*. He invented it to show that the game of *hex* can also be won by player A (the first to play) if it plays a perfect strategy.
Let's see an simple example of a strategy-stealing argument:
strategy-stealing argumentIn tic-tac-toe, we suppose the second player, B, is using a strategy S which guarantees winning. Then, first is the turn of A, who places an X somewhere, let's call it the block 1, and then it is B's turn, who using winning strategy S, will place a O somewhere else, let's call it block 2. At this point we can ask: why can't A play following the same strategy as B? A can move according to such winning book as well. But no, you may say, because while for player B the block 1 was already occupied, for A such block is still unused!
Let's draw this in order to understand it better:
1|_|_ _|2|_ | |
This is the first situation we described, in which A plays 1 and B plays 2. So we then ask whether A could have played B's location, i.e.
i|_|_ _|1|_ | |
where we have placed an "i" at what we will call the ignored position.
But what if, later in the game, the strategy tells A to place an X at the top-left block, the ignored position? Imagine we are at
i|2|_ _|1|_ | |
and that the winning book says it is time to play at i. This is the point where the argument becomes really interesting. Player A simply plays another random position,
i|2|_ _|1|3 | |
and then swaps 3 and i so that we get
3|2|_ _|1|i | |
Notice how this is still a valid situation. It is not the situation we were before but it is still a valid one! Why? Because in the first described scenario A could have played the right-middle block instead of the left-top one, and the book S would still player B how to win. This would mean this:
4|3|_ _|2|1 | |
Notice here how A starts the game (1) without having the book, so then B uses the book to move (2), to which A can reply (3) again without the book. The book must surely contemplate this situation! So that it recommends B to play 4.
We can continue the game (in which A has the book) as
3|2|6 _|1|i 5| |4
which is equivalent to
x|o|o _|x|i x| |o
We clearly see that A can now win. Is this inevitable? Yes, because no matter what B responds, A can answer by following the winning book S. The book can either recommend an empty block, so that the game continues, or recommend the i block, so that we swap again and we obtain a different but still valid scenario. But notice that our hypothesis was that B has a book that ensures victory, while we have seen how A, by having the same book, can always win. So we have found a contradiction in our hypothesis. We must conclude, then, that there is no book that guarantees victory for player B!
But this can mean two things: either A is able to force a win or it is able to force a tie. In this game, further analysis shows that the optimal playing by both players leads to a tie. But what if the game cannot end in a tie, like hex? Then it means that A can force a victory!
Notice how in Chomp there can't be ties either! One of the players must eat the poisoned block, which means that the first player can always force a victory. Isn't this a fascinating thing to discover? Most of all because we don't know which strategy this is!
Talking with Tim, a mathematician and an XMPP colleague, he posed the following question: "does that proof guarantee that the winning moves can be found without considering all the possibilities?" In other words, can the brute force approach be the only way to find such strategy? My first reaction was to say no, since I find that we cannot call brute force a "strategy", but I really don't know. Subjectively, if we need to know all the moves in order to force a win, I resist calling it a strategy. For small boards that could be feasible, but for huge boards only a very strong computer or even a God's mind could know how to force a win.
To me, a strategy would be a set of rules that you follow to try to achieve a goal, these rules being based on the current state of the game and without having to consider all the possible futures. Then, the strategy can be successful or not. But if we calculate all possible futures stemming from a state, what we have is not a strategy, but a certainty. However, this is just a semantic discussion, and what it is interesting is whether there is a local rule to achieve victory that does not involve total knowledge. Otherwise I don't find the problem interesting.
Some time ago, exploring Brilliant.org, I learned about an interesting approach to this chocolate game: imagine you just have 5 blocks of chocolate, all of them yummy but one of them marked as being full of poison. Instead of worrying about the space configuration of the blocks, you just need to say how many blocks you eat in each turn, choosing between 1 or 2 blocks. So if player A says 2, there are 3 blocks left. Then B says 2 and A will have to eat the poison. This game can be written as AABBA.
Another run of the game: now A starts eating 1, and B eats also 1. Then A can win in such game by eating 2: ABAAB.
The idea is to eat the 4th block, so that you force the other to eat the 5th.
Notice how there are no ties here, so each position is either a winning or a losing position. Notice this table:
|------------+-------------------| | blocks left| winning or losing | |------------+-------------------| | 1 | losing | |------------+-------------------| | 2 | winning | |------------+-------------------| | 3 | winning | |------------+-------------------| | 4 | losing | |------------+-------------------| | 5 | winning | |------------+-------------------|
So one needs to avoid losing positions! What if we have 10 blocks to begin with? We can build the table:
|------------+-----| | blocks left| w/l | |------------+-----| | 1 | l | |------------+-----| | 2 | w | |------------+-----| | 3 | w | |------------+-----| | 4 | l | |------------+-----| | 5 | w | |------------+-----| | 6 | w | |------------+-----| | 7 | l | |------------+-----| | 8 | w | |------------+-----| | 9 | w | |------------+-----| | 10 | l | |------------+-----|
The pattern is very clear: lww. Knowing this, if you are given a number of initial blocks, you can know whether to be player A or B in order to force a win. If there are 4,7,10,etc blocks then you don't want to be player A because this would mean you begin in a losing position!
Once you know you are in a winning position the strategy is very clear: just jump to a next winning strategy. If you are at state 6, which is a w position, you must eat two blocks, so you leave the bar in state 4, which is a losing position for B. Here the concept of strategy does not need to have a God knowledge, since there is a clear pattern. Could we define strategy as something equivalent to following a pattern?
Again inspired by the problems found in a Brilliant.org course, we can analyze a slightly more involved chocolate game. Now we have a bar of two poisoned blocks, and on top of some of them we have some chocolate blocks that are not poisoned, marked as choc:
+--------+
| choc |
+--------+
| choc |
+--------+
| choc |
+--------+--------+
| choc | choc |
+--------+--------|
| poison | poison |
+--------+--------+
In each turn, a player can eat as many chocs as it wants, but choosing from one block or the other. It is not allowed to take chocs from different blocks in a single move.
The player losing is the one facing no chocs anywhere. So if you are the first player, what should you do? We can build a table here as well, where "chocs left" means "not poisoned chocs left" and (o,x) means that there are chocs in the left pile but none in the right one. Try to see why each position is marked l or w:
|------------+-----| | chocs left | w/l | |------------+-----| | (x,x) | l | |------------+-----| | (o,x) | w | |------------+-----| | (x,o) | w | |------------+-----| | (1,1) | l | |------------+-----| | (2,1) | w | |------------+-----| | (3,1) | w | |------------+-----| | (4,1) | w | |------------+-----|
It is clear that, since the first state is (4,1) we just eat 3 chocs from the left pile so that we leave player B in the losing position (1,1).
These tables are really useful, but in this case we could build a chart to analyze the game even better:
|---+---+---+---+---+---+---| | | 0 | 1 | 2 | 3 | 4 | 5 | |---+---+---+---+---+---+---| | 0 | L | W | W | W | W | W | |---+---+---+---+---+---+---| | 1 | W | L | | | | | |---+---+---+---+---+---+---| | 2 | W | | | | | | |---+---+---+---+---+---+---| | 3 | W | | | | | | |---+---+---+---+---+---+---| | 4 | W | | | | | | |---+---+---+---+---+---+---| | 5 | W | | | | | | |---+---+---+---+---+---+---|
First of all, each state is given by (row,column), where row indicates the number of chocs on the left pile and the column the number of chocs on the right pile. And each element of the matrix tells you whether, if you are faced with this state in your turn, you can force victory (W) or not (L).
Try to see why I have marked L or W each of these cells. Can you complete the whole chart? It is a nice exercise. This is my solution:
stack 1
|---+---+---+---+---+---+---|
| | 0 | 1 | 2 | 3 | 4 | 5 |
|---+---+---+---+---+---+---|
| 0 | L | W | W | W | W | W |
s|---+---+---+---+---+---+---|
t| 1 | W | L | W | W | W | W |
a|---+---+---+---+---+---+---|
c| 2 | W | W | L | W | W | W |
k|---+---+---+---+---+---+---|
| 3 | W | W | W | L | W | W |
2|---+---+---+---+---+---+---|
| 4 | W | W | W | W | L | W |
|---+---+---+---+---+---+---|
| 5 | W | W | W | W | W | L |
|---+---+---+---+---+---+---|
A clear pattern emerges! If you are faced with a diagonal cell state, like (3,3) or (5,5) then your opponent can force victory upon you. However, if you are at any other cell, you can win by bringing your opponent to move in a diagonal cell. For example, if you are at (5,3) you just eat two chocs from the left pile so that your opponent faces the state (3,3), which is a losing position.
Having seen these previous examples, we can ask whether we could find a pattern in actual Chomps, but the answer to this question is, as already said before, currently an open problem.
There are simple situations where we can extract a good winning strategy, however. For example, when faced with a 2 x 2 bar, what is the best we can do?
i ii
._____._____. ._____._____.
| | | | | |
| | X | | | . |
|_____|_____| |_____|_____|
| | | | | |
|death| | |death| X |
|_____|_____| |_____|_____|
Should we play like in i) or ii)? Clearly i), since this forces the B player to eat only one of the remaining chocs (not poisoned blocks), while if you play ii), then player B can easily eat the other two chocs in a single move and leaving you facing the poisoned block. So for a 2 x 2 bar there is a known winning "strategy", but it requires to have a whole (God) knowledge of all the possible futures after each move.
At this point it should be clear that there are symmetric positions that are equivalent and not worth mentioning twice. So, for example, we can consider a 1 x n bar and use the conclusions to know what can happen for a n x 1 bar.
Imagine we have a 2 x 3 game:
._____._____._____. | | | | |death| | | |_____|_____|_____| | | | | | | | | |_____|_____|_____|
We have 5 different choices for our first move as A players, here marked with numbers:
._____._____._____. | | | | |death| 4 | 5 | |_____|_____|_____| | | | | | 1 | 2 | 3 | |_____|_____|_____|
The choice marked as 1 is L (losing), and so is 2. Choice 3 is W (winning). Finally, 4 and 5 are both L.
Knowing this, what about a 2 x 4 game?
._____._____._____._____. | | | | | |death| | | | |_____|_____|_____|_____| | | | | | | | | | 1 | |_____|_____|_____|_____|
Is this move by A W or L? We can see that, after this, B can play (2,1), (1,4), (1,3) or (1,2) and then we can easily win. What if B plays (2,2)?
._____._____._____._____. | | | | | |death| | | | |_____|_____|_____|_____| | | | | | | | 2 | 2 | 1 | |_____|_____|_____|_____|
Notice how we can win by playing (1,3). What about B playing (2,3) instead?
._____._____._____._____. | | | | | |death| | | | |_____|_____|_____|_____| | | | | | | | | 2 | 1 | |_____|_____|_____|_____|
We cannot play (2,1) or (2,2). We cannot play (1,2) either. If we play (1,3) we also lose. Our only hope lies in (1,4)!
._____._____._____._____. | | | | | |death| | | 3 | |_____|_____|_____|_____| | | | | | | | | 2 | 1 | |_____|_____|_____|_____|
Then B cannot play (1,3) or (2,1). Neither (1,2). If B plays (2,2):
._____._____._____._____. | | | | | |death| | | 3 | |_____|_____|_____|_____| | | | | | | | 4 | 2 | 1 | |_____|_____|_____|_____|
then we cannot play (2,1) or (1,2). But (1,3)?
._____._____._____._____. | | | | | |death| | 5 | 3 | |_____|_____|_____|_____| | | | | | | | 4 | 2 | 1 | |_____|_____|_____|_____|
We win! Conclusion: the move
._____._____._____._____. | | | | | |death| | | | |_____|_____|_____|_____| | | | | | | | | | 1 | |_____|_____|_____|_____|
is a winning one for A.
Can this be generalized to a 2 x n bar?
._____._____._____. ._____._____._____. | | | | | | | | |death| | | ... | | | | |_____|_____|_____| |_____|_____|_____| | | | | | | | | | | | | ... | | | | |_____|_____|_____| |_____|_____|_____|
We could like
._____._____._____. ._____._____._____. | | | | | | | | |death| | | ... | | | | |_____|_____|_____| |_____|_____|_____| | | | | | | | | | | | | ... | | | 1 | |_____|_____|_____| |_____|_____|_____|
so B cannot eat (2,1) or (2,2). If B plays (1,j) for whatever j the game is reduced to a new game of a 2 x m bar with m smaller than n and we can begin again. So B could eat (2,i) for i greater than 2:
._____._____._____. ._____._____._____. | | | | | | | | |death| | | ... | | | | |_____|_____|_____| |_____|_____|_____| | | | | | | | | | | | | ... | 2 | 2 | 1 | |_____|_____|_____| |_____|_____|_____|
So we answer by eating (1,i+1)
._____._____._____. ._____._____._____. | | | | | | | | |death| | | ... | | 3 | 3 | |_____|_____|_____| |_____|_____|_____| | | | | | | | | | | | | ... | 2 | 2 | 1 | |_____|_____|_____| |_____|_____|_____|
Then B cannot play (1,j) or (2,1) or (2,2), so B is restricted to play (2,i) again, but now with an i smaller than before, and we (A) will respond with (1,i+1) again. This inevitably leads to
._____._____._____. ._____._____._____. | | | | | | | | |death| | 7 | ... | 5 | 3 | 3 | |_____|_____|_____| |_____|_____|_____| | | | | | | | | | | 6 | 4 | ... | 2 | 2 | 1 | |_____|_____|_____| |_____|_____|_____|
which is a W for A. We have shown what is the strategy for playing a 2 x n bar and force winning. However, we don't know how to generalize the strategy for a generic bar! Can you solve this problem?