I know of two ways to come about the solution, the one is easy and elegant (and was how I solved it initially), while the other is a bit more roundabout and uses a bunch of game theory that I think is sort of cool. Anyway, I'm going to do the long game theory version first, if you want to just read the elegant quick solution, skip to the second last paragraph.
First of all, I'm going to set up a bit about game theory of impartial games, games where both players always have the same options available to them (other games are called partizan, chess and go are partizan games with one player playing black and the other white, I cannot move your pawn). I will also be focused exclusively on the type of game where the players alternate turns in the usual way. It is clear that for any impartial game, in any position either the active player has a winning strategy or the inactive player does. As is standard, we will call the former kind of position an "N-position" (for next player wins) and the latter a "P-position" (for previous player wins). It is clear that from any position you always want to move to P-positions, when possible.
At this point will be looking just at games that use the "normal play" rule that is, if you have no moves available on your turn you lose the game (as opposed to the "misère play" rule where having no legal moves is a win). So the game state with no legal moves is a P-position. Generally speaking, if from a game state you can move to a P-position, then that game state must be an N-position (since P-position moves are winning moves, having a P move available means that the active player has a winning strategy). On the other hand, if all the legal moves from a game state are N-positions (including the specific case of no legal moves), then that game state must be a P-position. So if a player has used this to completely map out the game space (first by labeling the end state P then moving outward labeling things P or N) that player will always try to move to a P-position, the opponent will have to choice to move to an N-positon, from which a new move to a P-position is available, and eventually the game must end with the winning player being the one who can move the game into P-positions (the end state also being a P-position).
Next we must figure out how game types combine when you add them together as we do in the breaking chocolate game. Suppose we start the breaking chocolate gmae from a 5x6 position and we move to the 5x2 + 5x4 position, what does that "+" mean? It means that we can make a move in either game. So, if G and H are both games, then G+H is the game where you can legally move in either G or in H, you must move in one of them, but not in both. Convince yourself that this addition is associative, that is (G+H)+J is the same as G+(H+J), it is also commutative but that is trivial.
Now we can prove something, I claim that if G is a P-position and if H is a P-position, then G+H is also a P-position (yay, a theorem), the proof is to simply show the strategy. If G is a P-position, then the inactive player has a response to any move the active player can make, and the inactive player can guarantee that it is the active player will run out of moves first (note how much more difficult it is if we used misère play instead, the fact is normal play is much easier to analyise in most cases). All this is true about H as well, so by simply always responding to the opponents moves in G with moves in G and respond to moves in H with moves in H you can always get to another position of the form P+P. So, we see that:
P+P=P
Good good.
Next, I claim that if G is an N-position and H is a P-position then G+H is an N-position. To prove this I simply need to show that there is a legal move in G+H to a state that is a P-position. We know that there is a legal move in G to a game state K with K being a P-position, but then K+H is a P-position by the previous theorem. So we see that there is a legal move in G+H to a P-position, specifically the move from G to K. So, we have:
N+P=N
Actually, we can quite generally show that if H is a P-position, then for any game G, G+H=G because you can just use your strategy in G and always respond to opponent moves in H with moves in H.
Alright, it is natural to wonder about N+N next, unfortunately you can come up with situations in actual games where N+N can be P and other games where N+N can be N. You can show that any game plus itself is a P-position, because in G+G you can always answer your opponents move in one with the same move in ther other, so they will run out of moves first, so G+G is a P-position, but if G and H are both N-positions, but not the same N-position, you can't prove much.
Alright, now for the chocolate game, I will prove the following statement for some arbitrary AxB position (I would have used NxM, but N is being used for something else here, and that notation is more standard):
AxB is a P-position if both A and B are odd and is an N-position if either A or B is even
The proof will be by induction, we can see this are true if AxB is 1x1, now to prove it by indution suppose we have want to prove this statement for a particular AxB and we are going to assume it is true for all ixB (with i less than A) and all Axj (with j less than B).
Now, I must show that AxB can reach a P-position if either A or B are even, this is easy, just move to (A/2)xB+(A/2)xB or Ax(B/2)+Ax(B/2), whichever exists. Then you mirror the opponent from there and cannot run out of moves first, so AxB can reach a P-position, it must be an N-position. Now if A and B are both odd, a generic legal move is to RxB+SxB with R even and S odd. But then RxB is an N-position and SxB is a P-position by the induction assumption and we know that N+P=N, so any legal move leads to an N-position meaning AxB must have been a P-position.
This completes the proof of the theorem, so we know from any start position if it is a P-position or an N-position so we can clearly say who wins and how (and the typical winning move is to break even sides directly in half), now I will show that that is totally unneeded and if you are in a winning position you can just make random moves and you won't ruin it.
Consider, at the start of the game we have a single block of chocolate on the table (of size NxM), each move causes one break in an existing piece of chocolate, increasing the number of blocks of chocolate on the table by exactly 1. The game ends when there are NxM blocks of chocolate on the table, so exactly NxM-1 moves have gone by, no matter what people chose as their moves there were exactly NxM-1 moves in all cases. The first player wins if NxM is even as there will be an odd number of moves, and the second player wins if NxM is odd as there will be an even number of moves.
Anyway, game theory is cool, but this game is really trivial. The P and N-position things come up alot in other games though, for example the game where you are removing sticks from a pile of N sticks but you cannot remove more than 4 (or K) at a time. You can also be a bit more general and use the Sprague–Grundy theorem to make any impartial game under the normal play condition into nim, but that takes more work (though not much more).
No comments:
Post a Comment