Wikipedia:Reference desk/Archives/Mathematics/2011 October 4
| Mathematics desk | ||
|---|---|---|
| < October 3 | << Sep | October | Nov >> | October 5 > |
| Welcome to the Wikipedia Mathematics Reference Desk Archives |
|---|
| The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
October 4
[edit]Sprague-Grundy theory
[edit]I am not a game theorist, so I'm having a bit of difficulty interpreting the statement of the Sprague-Grundy theorem. Is this translation into lay-speak correct? Every finite, impartial game is 'equivalent' (in terms of disjunctive sum of games) to some Nim-heap of size n (say) -- fine. In particular, this means that our game G has the same winning strategy as the actual Nim-heap. Is the winning strategy for the first player in G therefore to carry out the move which corresponds to taking the entire Nim-heap, and thus winning that Nim-heap? Player two then acts, and player one is then left with a slightly different game position...which will be also be equivalent to some (perhaps different) Nim-heap. This continues until player one wins. Does that sound about right? Does that also imply that the second player can only win if G starts off as being equivalent to the zero Nim-heap? (Assuming optimal play?) Thanks, Icthyos (talk) 15:09, 4 October 2011 (UTC)
- The theorem doesn't say anything about the strategy, first that would be some sort of correspondence between moves G and moves in a nim-heap and there usually isn't one, and second I believe the proof is non-constructive so it doesn't actually tell you what the size of the nim-heap is but just tells you there must be one. One way to think of it is that in most impartial games the first player has a winning strategy, those for which this is not the case have nim-value 0. For a game G and integer n, define a new game Gn in which a heap of size n is combined with G. A move in Gn consists of either making a move in G or taking away some number of part of the heap. In this definition G0 is the same as G and G1 is G with a one time only skip a move option. The theorem says for any impartial game G there is some n where there is no winning strategy for Gn. The n for which this is the case (there is only one) is called the nim-value for the game.--RDBury (talk) 19:32, 4 October 2011 (UTC)
- How does the way you've stated the theorem 'help' us play G? My understanding of Sprague-Grundy was that it meant if you were good at Nim, you were good at all impartial games. As far as I see, Sprague-Grundy (the proof of which, I agree, isn't constructive) says that G is equivalent to some Nim-heap, n - equivalent in the sense that for all games X, G+X has the same outcome as n+X. In particular, if we take X to be the zero game, we get that G and n have the same outcome. I'm interpreting that as meaning: 'think of G as a Nim-pile of height n, and do the move which would be the winning strategy for that pile -- namely, picking up all the objects' (again, I'm aware the proof is non-constructive, it doesn't actually tell us how to determine the corresponding move in G). I've tried it with a small, concrete game, starting with the end-state having Nim-value zero, then working backwards using the MEX operator to assign each position a nim-value. So, starting at a position which has non-zero nim-value, the winning strategy is to perform the legal move taking us to a position with zero nim-value, yes? (To me, this corresponds to starting with a Nim-pile, and picking up all the objects.) Does this make sense? I'm aware it probably flies in the face of the rigours of game theory, but I'm just trying to get a feel for what's going on... Icthyos (talk) 21:18, 4 October 2011 (UTC)
- If G is not equivalent to the zero game then there is some move you can make, to G′ say, where G′ is equivalent to the zero game. In which case that should be your strategy if you're the first player. But in general, to figure out the nim-value of G you still have to work out the the nim-value of all possible moves from G and to find their nim-values you have to work out the nim-values of moves in those games, and so on recursively. The SG theorm does help when the game is, like Nim, the sum of simpler games. But for general games you still have to go though all possible positions and so it doesn't actually reduce the work, though it can make the bookkeeping a bit easier. It might actually make the problem more difficult since you're trying to compute an integer instead of just a yes/no value. An example is the 2×n case of Chomp; there is an easy strategy for player one to win but finding a formula for the nim-value of any position is rather involved.--RDBury (talk) 05:25, 5 October 2011 (UTC)
- Right, I get you. If we did know all the nim-values of the possible moves, Sprague-Grundy says this is the approach to take, but in general we don't. Thanks for helping to clarify! Icthyos (talk) 08:23, 5 October 2011 (UTC)
- If G is not equivalent to the zero game then there is some move you can make, to G′ say, where G′ is equivalent to the zero game. In which case that should be your strategy if you're the first player. But in general, to figure out the nim-value of G you still have to work out the the nim-value of all possible moves from G and to find their nim-values you have to work out the nim-values of moves in those games, and so on recursively. The SG theorm does help when the game is, like Nim, the sum of simpler games. But for general games you still have to go though all possible positions and so it doesn't actually reduce the work, though it can make the bookkeeping a bit easier. It might actually make the problem more difficult since you're trying to compute an integer instead of just a yes/no value. An example is the 2×n case of Chomp; there is an easy strategy for player one to win but finding a formula for the nim-value of any position is rather involved.--RDBury (talk) 05:25, 5 October 2011 (UTC)
- How does the way you've stated the theorem 'help' us play G? My understanding of Sprague-Grundy was that it meant if you were good at Nim, you were good at all impartial games. As far as I see, Sprague-Grundy (the proof of which, I agree, isn't constructive) says that G is equivalent to some Nim-heap, n - equivalent in the sense that for all games X, G+X has the same outcome as n+X. In particular, if we take X to be the zero game, we get that G and n have the same outcome. I'm interpreting that as meaning: 'think of G as a Nim-pile of height n, and do the move which would be the winning strategy for that pile -- namely, picking up all the objects' (again, I'm aware the proof is non-constructive, it doesn't actually tell us how to determine the corresponding move in G). I've tried it with a small, concrete game, starting with the end-state having Nim-value zero, then working backwards using the MEX operator to assign each position a nim-value. So, starting at a position which has non-zero nim-value, the winning strategy is to perform the legal move taking us to a position with zero nim-value, yes? (To me, this corresponds to starting with a Nim-pile, and picking up all the objects.) Does this make sense? I'm aware it probably flies in the face of the rigours of game theory, but I'm just trying to get a feel for what's going on... Icthyos (talk) 21:18, 4 October 2011 (UTC)