In order to describe the disjunctive sum, we did some examples. First, I added 1-2-3 Nim to a Kayles 4-line:
+
We played around with this a bit. My students are both very bright, and we've been moving pretty quickly through the class, so it was fine to take a big chunk of class time to actually try to win this summed game. My students correctly determined that you want to be the second player to go on this board (thus it's in "zero" or P... but not meaning Polynomial-time P... the other one).
I knew I also had to describe what to do with misere games. Thus, we played the same game as above, but with the nim side being misere. The class again correctly decided this game is in P.
For a last trick, I switched, making the nim game normal but the Kayles misere. The class now noticed that the game is in N! The amount of misereness hadn't changed, but where it was located had!
This is what is a bit startling. Namely, the misereness can make a difference depending on which side of the summand it's on! I can't think of a better example for students to use the Composite design pattern (I'm putting a strong Object-Oriented emphasis on the software course). This curve ball of misereness can be a bit frustrating, but it can be a fun curve ball to play with as well!
As a question for this post: nim is solved for both the normal and misere versions. What about versions where some of the piles are misere and some are not? Additionally, what if we designate certain subsets of piles to all be misere. As with examples above, that doesn't mean that each of the piles is misere, but that that collection of piles as a whole has misere status. Can we efficiently evaluate all those piles? What if some of the misereness groupings overlap? (Notice this last one doesn't fall into the theory of summed games, which break down as trees of subgames. Does it matter?)
I knew I also had to describe what to do with misere games. Thus, we played the same game as above, but with the nim side being misere. The class again correctly decided this game is in P.
For a last trick, I switched, making the nim game normal but the Kayles misere. The class now noticed that the game is in N! The amount of misereness hadn't changed, but where it was located had!
This is what is a bit startling. Namely, the misereness can make a difference depending on which side of the summand it's on! I can't think of a better example for students to use the Composite design pattern (I'm putting a strong Object-Oriented emphasis on the software course). This curve ball of misereness can be a bit frustrating, but it can be a fun curve ball to play with as well!
As a question for this post: nim is solved for both the normal and misere versions. What about versions where some of the piles are misere and some are not? Additionally, what if we designate certain subsets of piles to all be misere. As with examples above, that doesn't mean that each of the piles is misere, but that that collection of piles as a whole has misere status. Can we efficiently evaluate all those piles? What if some of the misereness groupings overlap? (Notice this last one doesn't fall into the theory of summed games, which break down as trees of subgames. Does it matter?)
I guess my question would be: What do you mean by having only one pile misere? If you take the last counter there, do you lose regardless of the state of the other components? Technically speaking, this is not the traditional disjunctive sum but it may still be an interesting question to answer.
ReplyDeleteNow that I have answered my own question (by reading part 1) I have some answers to your questions:
ReplyDeleteWhen you are playing under a short sum (which is as you have described in part 1) then a misere component is regular (since it is all-small). Furthermore, the transformation to a regular play game does not remove the fact that the game must remain impartial. Therefore, for any misere nim component, it must be equivalent to some *n.
With only a little work, it isn't too hard to show that any misere nim component is equivalent to its normal play value unless it is composed entirely of heaps of size 1. In that case, its value is 0 or * based on the parity of the number of heaps (odd is 0, even is *).
So, the analysis of nim in multiple components with a short sum where each component may have multiple heaps and is assigned to be either normal or misere is just as easy (computationally) to solve as normal play nim.
Since Kayles is also an impartial game, the same technique would apply but I'm not aware of a direct relation to find the equivalent normal play value of a misere component without applying the algorithm described in my thesis. In your specific example, that Kayles position is equivalent to a nim component with two heaps of size 1 so it's easy to see why you switch from P to N under misere rules.
Here's an interesting question for your students to answer:
ReplyDeleteWe know that any nim position has the same value under normal and misere rules as long as there is a heap of size greater than 1.
Is there a Kayles path on k vertices which has the same value under both normal and misere rules?
Some quick calculations seem to indicate the answer is no up to k=11 but there are some values of k for which it's in N for both normal and misere (3,5,9,10 so far).
A somewhat easier problem: Construct a Kayles position which is in P under both normal and misere rules.
Thanks, Paul, for all your awesome comments!
ReplyDeleteI used the Kayles line of 4 nodes because I knew that had nimber 0 in normal play :)
I will have to remember these questions for my class once I am actually teaching a games course. I am actually using this all as a project for my software design course. So far it's been an excellent choice as a continuing topic!