[Standard terminology: a P-position is a win for the previous player, an N-position is a win for the next player] If you allow players to make either 1 or 2 moves, so that a single heap with one object in it is an N-position, a modified version of the standard Sprague-Grundy theory still works. Calculate the Grundy number of each heap in the usual way (If there are legal moves to positions with Grundy numbers of 0,1,2,...n-1, but not to n, then the position had Grundy number n). Given k heaps, with Grundy numbers n_1, n_2, ... n_k, write the n_i in binary, and add them without carry. The resulting position is an P-position if the total of each place in the "sum" of the binary expansions is a multiple of 3. If you want to make the rule that you must make two moves, so that a single heap with 1 object is a P-position, then as with misere nim, a trivial modification of the standard strategy still works for nim, but not for arbitrary impartial games. As long as a position has at least 1 heap with more than one object, it is a P-position in "make exactly two moves" iff it is a P-position in the "make one or two moves" game. (and analysis of positions where every heap has a single object is trivial). But as with misere nim, I think this is no longer true when you replace a nim-heap with 1 object with an arbitrary impartial game position with Grundy number 1. All this works with making N moves, where the "sum" of the binary Grundy values must be divisible by N+1 in each place. I don't have my copy of Winning Ways handy, but I think this is all in there, mostly because I don't think I would have been able to work this out this easily if I hadn't seen it before. Here's a problem that might be interesting that I think isn't solved by the above theory; the two-move version of Lasker's nim. You have a bunch of piles, and a move is to either diminish a heap, or split a heap in two, and you can make one or two moves. Andy On Tue, Dec 30, 2014 at 8:02 AM, James Propp <jamespropp@gmail.com> wrote:
Has anyone studied variants of standard combinatorial games (such as Nim) in which each player makes two standard moves in succession on each turn instead of just one?
(This is the way my 8-year-old son likes to play tic-tac-toe against me: he puts down two X's, then I put down two O's, then he puts down two X's and wins. Fair, right?)
Note that this form of two-player game can be seen as a four-player game in which players #1 and #2 collaborate and players #3 and #4 collaborate.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com