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!

Advertisements

Permalink Leave a Comment

Misere quotients for impartial games

December 4, 2006 at 11:45 pm (abstracts, algebra, math, papers, software)

Elwyn Berlekamp suggested that the title of my recent paper with Aaron Siegel, The Phi-values of various games, be changed:

I urge you to change the title. I think you have a good chance to make an impact well beyond the small circle of experts such as those who come to conferences like the one in Banff. There are many more mathematicians and algebraists out there, as well as a big computer Go community. Terms like “Phi-function” are unlikely to become buzzwords that stick, as there are many Phi functions defined by many different authors. “Misere Quotient” might well be a unique pair of words. It could quite plausibly become buzzword that would help stir up more interest in combinatorial games in general. So I think it important that your title include that pair of words.  I’d propose a short title such as “Misere Quotients for Impartial Games”.

It’s hard to argue with that, and it’s still a preprint. So Misere Quotients for Impartial Games it is!

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

The Phi-values of various games

October 2, 2006 at 3:29 am (papers, software)

Just in time for Richard K. Guy’s 90th birthday a few days ago (30 September 2006), Aaron Siegel and I finished our paper The Phi-values of various games.

It just appeared on the arXiv.  Check it out!

Permalink 1 Comment

Advances in losing

March 1, 2006 at 5:04 am (papers)

I just put a paper into the arXiv called Advances in Losing. It’s actually been done for awhile; I just got around to doing it. Now I’m working on a paper with Aaron Siegel called “The Phi-values of various games,” and I needed to have a reference to this other paper, so I put it into the arXiv. “Advances in Losing” is eventually going to be in a Cambridge Univ Press book being edited by Richard Nowakowski and Michael Albert called Games of No Chance 3.

Permalink Leave a Comment

Taming the Wild in Impartial Combinatorial Games

July 15, 2005 at 1:26 am (papers)


My paper “Taming the Wild in Impartial Games” has been accepted by INTEGERS. Aaron Siegel and Dan Hoey helped me by pointing out some mistakes in section 11.5 that I’ve corrected in this new and (hopefully) final version that I just put into the arXiv.

Permalink Leave a Comment

Taming the Wild, improved

January 21, 2005 at 1:35 am (papers)

I’ve corrected some errata and improved the exposition in section 9 of my paper, “Taming the Wild in Impartial Combinatorial Games.” This is the paper you should start with if you’re interested in how the Sprague-Grundy theory of impartial combinatorial games generalizes to misere play via classical commutative semigroup theory and the indistinguishability quotient construction. The paper is available at the arXiv via this link.

Permalink Leave a Comment

Quotient semigroup presentations in misere impartial combinatorial games

August 14, 2004 at 1:39 am (papers, solutions)


A short note on the quotient semigroup viewpoint for misere games. I wrote this note two days after discovering the quotient semigroup construction. 

Permalink Leave a Comment

Allemang’s thesis

August 3, 2004 at 2:25 am (papers, software)

Machine Computation with Finite Games

In 1984, Dean Allemang wrote an M.Sc. thesis at Cambridge University that is today [January 2003] still an excellent resource for results on misère octal games. The title of his thesis is Machine Computation with Finite Games.

In many cases the contents of Allemang’s thesis go beyond what is contained in Chapter 13 of the 1985 (third printing) of Winning Ways (“the last and most complicated theory in this book,” according to the authors, Berlekamp, Conway, and Guy).

The original electronic version of Allemang’s thesis has been lost. After cajoling Dean into sending me a photocopy, I scanned it in and converted it to PDF.

I’ve split the document into two parts. Here’s a rough outline of the contents.

Part I [PDF, 48 pages, 2.56 MB]

Cover
Declaration by Author
Abstract
Misère Play of Impartial games
Normal play
Misère play
Conway’s Cancellation
The Genus Sequence Algorithm
Grundy’s Game
Other Games
Tins
Guiles
The octal game .17
Errors in Winning Ways
A Bigger Genus Sequence
The Generalized Genus Statement
Periodicity in Genus Sequences
An Algorithm for Generalized Genera
Errors in Winning Ways
The Game of Knots Ties Up all Genus Sequences
Which sequences arise as genus sequences?

Part II [PDF, 33 pages, 15.2 MB]

Complete Analysis for Misère Games
A Catalogue of Octal Games
Appendix III: “An implementation of many of the computations necessary for the analysis of normal partizan games, as treated in Conway, On Numbers and Games…”.

Permalink 1 Comment

The discovery of the solution to misere Kayles

September 21, 2003 at 4:54 pm (kayles, papers, solutions)

Conway describes normal play Kayles on pg 127 of On Numbers and Games, Academic Press, 1976:


Kayles is the octal game 0.77. It was first completely solved in normal play by Richard Guy, and by Sibert and Conway for misère play.

Normal Play Nim Sequence

                    0  1  2  3  4  5  6  7  8  9 10 11
                    ----------------------------------
                0+  0  1  2  3  1  4  3  2  1  4  2  6
               12+  4  1  2  7  1  4  3  2  1  4  6  7
               24+  4  1  2  8  5  4  7  2  1  8  6  7
               36+  4  1  2  3  1  4  7  2  1  8  2  7
               48+  4  1  2  8  1  4  7  2  1  4  2  7
               60+  4  1  2  8  1  4  7  2  1  8  6  7
               72+  4  1  2  8  1  4  7  2  1  8  2  7

The Kayles nim sequence is periodic of length 12—the values in final row of the table repeat themselves indefinitely.

Sibert-Conway Decomposition for Misère Play

The surprising solution to the misère version of Kayles was discovered by the amateur William L. Sibert in 1973, but it was not published until over seventeen years later. There’s an interesting story behind these events. In 1989, Sibert wrote a description of his solution and a proof in an unpublished 43 page document entitled The Game of Misere Kayles: The “Safe Number” vs “Unsafe Number” Theory. Sibert wrote the following “Preamble” to this document:

Some years ago (about 1961) I was stumped by a problem in an old puzzle book (possibly by Dudeney). It described the plight of a group of tourists in the Alps who were consistently defeated by a young Swiss miss at a pluck-the-petals-from-the-daisy type of game.

Two players took turns plucking petals, and the game required each player to take either one or to petals at a time … with the proviso that if two petals were taken, they had to physically adjacent.

The winner was the player who took the last petal, and, according to the author, the young lass always won … whether she played first or second.

The “solution” given in the back of the book described her strategy as one of presenting her opponent with a daisy which had been divided into two identical segments. She then simply matched her opponent’s play each time, usng the sector opposite the one into which the opponent had just played.

This struck me as an unsatisfactory answer, in that she had to rely on inept play by her opponent in those cases where she played first.

This led me, for some reason, to try and find the winning strategy for a re-defined game in which the wind had randomly blown away a number of petals from a large daisy before the game began.

(It was only much later that I learned that the problem I had set for myself was to find the solution to the well-known [normal play] game “Kayles”.)

After many, many, many hours of work, I had the strategy for all possible games in which the largest unbroken string of petals was 168 or less… and was satisfied that this strategy could be applied to any game with a string or strings exceeding 168. (I could have stopped at 166, but did the next two numbers just to round out a final cycle of 12).

The work was done on a commuter train, returning home from work in the evenings, and I used worksheets which bore a crude resemblance to the Grundy scale described in “Winning Ways” … except that my worksheets didn’t “slide”. A copy of one of those worksheets is attached, as Appendix IV.

Having solved the problem, I forgot about it until I happened to see a Martin Gardner column in an issue of Scientific American in which he discussed Kayles. The issue came out in 1969 or 1970, and, as I recall, his number values matched mine exactly, except for one number (28 ?). I rechecked by calculations, and concluded that the variance was almost certainly caused by a “typo” in the article. Many years later, when I acquired a copy of “Winning Ways” my values were confirmed as correct.

In any case, reading the Gardner article reawakened my interest in Kayles, and I set out to try and solve the problem of the Misere version of the game.

In time, I developed the theory of “Safe” and “Unsafe” numbers … and by 1973 I had what I believed was a general solution to the game.

Again, I set the matter aside, but for some reason in 1979 I sent an outline of my solution to Mr. Gardner, asking him whether it was correct. He replied that he didn’t know, and suggested that I check with Professor Guy.

Once more I let matters slide, but in 1989 I finally sent the “solution” to Professor Guy, and asked for his reaction. The subsequent exchange led me to assemble my work papers into what I trust is a coherent document. What follows is the document wich I hope will confirm, under scrutiny, that my theory is correct.

Here is the solution as presented in the paper by Sibert and Conway, Mathematical Kayles:

The PN Positions of Kayles (ie those that are P-positions in normal play, and N-positions in misere play) are precisely those positions that have one of the following three forms:


E(5) E(4,1)
E(17,12,9) E(20,4,1)
25 E(17,12,9) D(20,4,1)

While the N-normal, P-misere positions are the

NP Positions
D(5) D(4,1)
E(5) D(4,1)
E(4,1) D(9)
12 E(4,1)
E(17,12,9) D(20,4,1)
25 D(9) D(4,1)

The notation E(a, b, . . .) (resp. D(a, b, . . .)) refers to any position composed by taking an even (resp., odd) number of isolated rows of pins of length of size a or b or . . ..

For example,

5 + 4 + 1 + 1
is a position included in the set

D(5) D(4, 1)
since it is composed by taking a single (ie, odd number) row of size 5 and the total number of 4’s or 1’s (ie, three) is also odd. For every other position in misere Kayles not listed in the forms of PN- and NP-positions above, its misere and normal play outcomes agree.

It’s possible to frame this solution using the language of misere quotients. The misere quotient of Kayles is a commutative monoid of order 40, and its misere pretending function is also of period 12, just as its normal play nim sequence has period twelve. This paper gives the details.

Permalink Leave a Comment