Lectures by Aaron Siegel at the Weizmann Institute

December 19, 2006 at 6:12 pm (algebra, kayles, lectures, nim, papers)

Aaron Siegel has come back from Israel where he gave five two-hour lectures on misere games.

  1. Normal play
  2. Octal games and misere play
  3. The periodicity theorem
  4. More examples
  5. Further topics

Students and faculty from the Weizmann helped Aaron prepare excellent notes that are now available (PDF).

Many thanks to Aviezri Fraenkel at the Weizmann Institute for creating this opportunity to spread the word about misere games and their intriguing algebra!

Permalink Leave a Comment

The commutative algebra of T2

October 6, 2006 at 12:01 am (algebra, nim, papers)

I’ve been reading about semigroup rings and other things in commutative algebra. In looking though old notes I found this email from Aaron Siegel from about a year ago, recounting some interesting information from a meeting with David Eisenbud. It corresponds pretty closely to what I was trying to compute myself, this morning

The meeting went well. He showed me a new (to me) way of looking at monoids in terms of commutative rings. Namely, instead of considering the monoid

Q = {a,b : a^2=1,b^3=b }

[ Aside: the monoid Q is the (tame) misere quotient of the game of Nim played using heaps of size 1 and 2 only. In this paper, Q is called T2. ]

we instead look at the ring

R = k[a,b] / (1-a^2,b-b^3)

and now we can apply the techniques of commutative algebra to analyze this ring. One observation is that because Q six elements, R is a 6-dimensional vector space over k. A basis for this vector space is Q itself, but it’s instructive to look at other bases and to study various decompositions of R.

For example, if x is an idempotent of R, then so is 1-x, since (1-x)(1-x) = 1-2x+x^2 = 1-2x+x = 1-x. Further, x(1-x) = 0, so R can be written as the internal direct sum of R/(x) and R/(1-x), with the isomorphism

R -> R/(x) + R/(1-x)

given by y -> ((1-x)y,xy).

Using the above example, we have

R = R/(b^2) + R/(1-b^2),

and it’s not hard to see that R/(1-b^2) is four-dimensional with basis {b^2,ab^2,b,ab} (which you’ll recognize as a maximal subgroup of Q), and R/(b^2) is two-dimensional with basis {1-b^2,a-ab^2} (which of course is equal to {1,a} in R/(b^2)).

Note the parallel with semigroup theory. In the ring R/(1-b^2), we’ve asserted that b^2 = 1, making b^2 into the identity. So the group {b^2,ab^2,b,ab} corresponds exactly with the multiplicative structure of R/(1-b^2). In other words, R/(1-b^2) is isomorphic to the group ring k[Z_2 x Z_2]. Likewise, in R/(b^2) we’ve set b^2 = 0 and the result is isomorphic to the group ring k[Z_2], corresponding to the maximal subgroup {1,a}. So the ring decomposition by idempotents matches the monoid decomposition we’re used to (archimedean components).

All very interesting. Eisenbud also pointed out that the rings can be decomposed further:

1 – b^2 = (1-b)(1+b) so R/(1-b^2) = R/(1-b) + R/(1+b),

and we can further break off the “a” part of each component, since it never interacts with the “b” component. This fully decomposes R as the vector space product of six copies of k and gives a new basis.

Finally, we know that we always have a^2 = 1 in any misere quotient Q. Because of this, the corresponding ring R always decomposes into two isomorphic components

R = R/(1-a) + R/(1+a)

and it’s simpler, therefore, to discard a and study just one of these (R/(1-a) is preferable, since that’s equivalent to just setting a = 1.) Of course, the structure of the P-positions is different on each component. It’s unclear what all of this might mean in game-theoretic terms.

He also recommended a book by Gilmer, “Commutative Semigroup Rings,” which I’ve checked out from Berkeley’s library. The paper by Eisenbud & Sturmfelds, “Binomial Ideals,” might also be useful (it’s on the arxiv).

Permalink Leave a Comment

Last Year at Marienbad

August 5, 2006 at 4:29 am (marienbad, nim)

Dan Hoey sent me this interesting page he’s put together on the game of Nim in the screenplay of the movie Last Year at Marienbad.

Permalink 1 Comment

Moments in Last Year at Marienbad when that weird character plays misere Nim against the other hotel guests

February 5, 2006 at 6:19 pm (marienbad, nim)

Last Year at Marienbad is a 1961 French movie directed by Alan Renais. It’s mostly annoying to watch, but it has the benefit of having the game of Misere Nim played several times in the movie.The starting position is always four heaps of cards (more often, matchsticks). The heaps have sizes 1, 3, 5, and 7. A move is to take some number of cards from one heap only, removing them from play (including the whole heap, if desired). Play ends when the last card is taken, and the player who takes that card loses the game. This starting position is a forced win for the second player to move (ie a P-position) in best play.

Last night, I suffered through the whole movie, keeping track of when Misere Nim is played.

#1) Elapsed time: 15:11 (roughly): Misere nim with cards. Best view of play in the movie. As always in the movie, the strange-looking guy who proposes that the game be played wins. He lets the other guest move first. The actor playing the Guest does a great job of looking disgruntled as he is forced to take the last card (and loses the game).

#2) Elapsed time: 20:56: Misere nim with matchsticks. “What if you play first?” The weird guy obliges, and makes a (losing) first move, but the guest makes an error and the weird guy wins again.

#3) Elapsed time: 37:00: Misere nim with matchsticks, set up for play only.

#4) Elapsed time: 1hr 13:00: Misere nim with matchsticks. This is the best part, with the highly amusing speculation on the part of the guests—”I think you should always take an odd number.” “He’s using the theory of logarithms.” [In translation to English on my DVD, that is “It is a type of logarithmic series.” “How does he always win?” This last scene is the best one for commentary by the guests.

I like this review of the movie at Amazon, by Jack Walter:

I am an avid fan of foreign, avant-garde, bizarre, challenging and/or enigmatic films, but this one is just plain agonizing to watch. The photography and the characters are beautiful, but I had to view this film in two sessions, both of them tormentingly slow. At first I thought it was some kind of variation on Sartre’s “No Exit,” but if it was, I was the one in the waiting room in Hell! This movie is pointless, vapid and pathetically pretentious. I hope God adds ninety-four minutes onto my life as a reward for sitting through Last Year at Marienbad!

Permalink Leave a Comment