How constructive are strategy stealing proofs?
David Gale was a famous mathematician and economist, who passed away just over five years ago. I had the honor of meeting him while I was on the faculty at Berkeley years ago; Gale spent most of his career at Berkeley, ending it as a professor emeritus.
Today I want to talk about his famous proof that there is a winning strategy for the game Chomp.
The proof is based on the brilliant idea of strategy stealing, which is due to John Nash. It is usually considered a nonconstructive proof method, but we will argue that there are some situations where it is quite constructive. At least it is constructive in the spirit of complexity theory.
Gale invented many games, but the coolest is, in my opinion, called Chomp. It is based on eating chocolate. Chocolate is the most important food group—this is not a opinion, but a fact.
Chomp is a two-player strategy game played on a rectangular chocolate bar made up of smaller square blocks (cells). The players take it in turns to choose one block and “eat it” (remove from the board), together with those that are below it and to its right. The top left block is “poisoned” and the player who eats this loses. Poisoned is pretty serious and does not make one play the game lightly, nor be able to play it repeatedly. I prefer to say that the corner is make of chocolate that is very bitter and the rest is milk chocolate. Since I do not like bitter dark chocolate, having to eat this corner would be not very much fun.
Gale invented, named, and analyzed the game of Chomp. Earlier an equivalent game had been published by Frederik Schuh in his book called “The Master Book of Mathematical Recreations.” He did this in 1943, and although this was 70 years ago, the book is now a Dover book and is available.
Math is like this, as we have pointed out many times: fame often goes to the last person to discover something, rather than the first one. We could call this Gauss’ Law: but he is the exception, since he often gets credit even thought he discovered something first and yet did not publish it at all. This is a topic for another day.
Here is a game played on a bar as shown by Wikipedia. As usual we will name the players Alice (A) and Bob (B). I should add that Schuh in his book did use names for players: his were John and Peter.
Note at the end Alice must eat the last bar and so she loses. Since we know, thanks to Gale, that the game is winnable by Alice, she must have made some error in her play.
There is a wonderful site where you can play the game on-line. Try it. I played randomly in the start and then switched to thinking at the end and won as the first player. So I am 1-0, and will not play the machine again.
Gale’s argument is this:
It turns out that for any rectangular starting position other than the first player can win. This can be shown using a strategy-stealing argument: assume that the second player has a winning strategy against any initial first-player move. Suppose then, that the first player takes only the bottom right hand square. By our assumption, the second player has a response to this which will force victory. But if such a winning response exists, the first player could have played it as his first move and thus forced victory. The second player therefore cannot have a winning strategy.
The idea of strategy stealing is due to Nash in 1949. He applied it to a different game called called Hex. Gale’s argument is clearly based on Nash’s idea, but is slightly different.
How To Steal Some Algorithm
Assume that Bob has a winning strategy for Chomp that is based on a polynomial time algorithm. We do not care if it is fast or slow, but his strategy that Alice plans to steal is based on an algorithm. Then Alice can beat Bob as they play a series of larger and larger games, for all but a finite number of games. Moreover, Alice takes time that is order the same as Bob’s algorithm—that is, her running time is up to a constant slower than Bob’s.
Let’s look and see how she does this.
Alice’s Basic Strategy
Here is an obvious method for Alice that almost works. We know that Bob has a strategy that runs in polynomial time. Let be a listing of all the TM’s that run in polynomial time. Alice selects and begin to play against Bob. As long as she wins, she keeps using . If she ever loses, she then switches to . Recall that they keep playing on larger and larger boards.
We claim that this strategy for Alice will win all but a finite number of games and will run in polynomial time. The latter is direct from the definition of the machine list. To prove the first note that when Bob plays first he uses some for his winning strategy. So in the worst case Alice moves from to to until she selects .
Thus she can only lose at most a finite number of games, since she changes her program only after a finite number of games. The argument is similar to that in our recent post about how satisfiability becomes easier if the world lacks randomness.
Can Alice Steal Bob’s Algorithm?
The above strategy for Alice insures that she loses at most a finite number of games. But it does not guarantee that she will eventually be playing as fast as Bob’s algorithm . She might stop earlier with some that is a winning strategy but is very slow. Bob’s strategy may run in time, but Alice may settle on an algorithm that runs in . This clearly is not satisfying the claim that Alice will eventually runs about as fast as Bob’s best first player strategy.
So how does Alice fix this? I have an idea that may work, but have not been able to carry it out completely. Perhaps you can help. My conjecture is that Alice should be able to create a slightly more clever strategy so that she wins most games, but also eventually runs essentially as fast as Bob’s best strategy.
I asked Ken—who is at his anti-cheating meetings in Paris—to try without telling him my idea, and he came up with this: It is important that the games are played with larger and larger box sizes . At any time Alice maintains a list of machines that have not yet lost a game, where is unbounded but grows slowly with . She simulates each machine, and waits for the first one to finish. Note that will always be one of the machines. If a faster machine loses she rubs it off the list. The idea is that eventually she plays faster and faster correct machines.
The one hitch is that as Alice slowly adds new machines to her list, she must risk the possibility that a new machine is faster—so she plays its move—but it is erroneous. Thus she might lose an occasional game infinitely often. However, if Bob’s algorithm is the fastest one asymptotically, for large enough it is the fastest concretely and it always gets played. The problem comes in if the Chomp game has no well-defined best algorithm, but instead an infinite succession of faster ones. In this we don’t know what is the best we can prove—and we are not sure either how Alice can avoid both losing infinitely many games and getting stuck with a definitely sub-optimal running time.
Does this strategy work? Any ideas on how to make this into a full proof? That is: Can Alice steal Bob’s algorithm, or one with almost as good running time?