Fall 2004, David Matuszek
Here's the game. One of us chooses "odd," the other is "even." Let's say that you are odd, I am even. We both start out with some money (say, a dollar).
At each turn, you choose a number between one and ten, and I choose a number between one and ten. If the sum of our two numbers is odd, you collect that many cents from me; if even, I collect that many cents from you.
For example, if I choose 3 and you choose 7, then the sum is 10. Since 10 is even, I get 10 cents from you. But if I choose 4 and you choose 7, you win 11 cents from me.
The "best" prediction function would be:
next bet = f(previous bet, win/lose)
This would be based on a table that, for each of 10 previous bets, for each two outcomes (win or lose), kept track of the number of times the opponent made each of the 10 possible next bets -- that's a table with 200 entries! It would be even worse if we tried to keep track of how much was won or lost.
We can greatly simplify this. Let's consider just "win" or "lose." This depends on whether your opponent bet even or odd. So our prediction function becomes:
next even/odd = f(previous even/odd, win/lose)
This gives us a 2x2x2 table, which we can fill reasonably quickly and start using before our money runs out. We can use this to decide whether to bet even or odd.
Now, how much should we bet? In a way, this doesn't matter, if we can just keep winning. However, it also makes sense to bet high when we are more confident of winning, and low when are less confident.Computer is playing