Notakto: X-only Tic-Tac-Toe
Notakto is an iPad application for impartial misere Tic-Tac-Toe.
Bob Koca suggested this game, and there is some discussion of it on MathOverflow.net (search for “Neutral Tic Tac Toe”) in a thread created by Timothy Chow.
The misere quotient of X-only Tic Tac Toe has eighteen elements and four P-position types. Here is a paper draft with title “The Secrets of Notakto: How to Win at X-Only Tic-Tac-Toe.”
Some MisereSolver questions answered
Mike Weimerskirch asked some questions about MisereSolver. They’re answered inline by Aaron Siegel:
* * *
In what sense do the candidate quotients ‘converge’ to the correct quotient? I’ve read that “MisereSolver sometimes chooses very poor candidates; often they are considerably larger than the true quotient.” Do you have a quick example of when this happens?
Q_30(0.07) has size 360 but one of the candidates has size 848:
java -jar misere.jar 0.07 -maxheap 30
The candidates converge in the sense that their lexicographically least failures are strictly lexicographically increasing. Therefore strictly more of the lexicographic space is correct for each successive candidate.
On the other hand, MisereSolver doesn’t have the problem that my algorithm has, that being to produce a candidate quotient that is correct in terms of pretending function and outcome partition, but isn’t reduced in that it assigns multiple monoid elements to the same indistinguishability class. So MisereSolver doesn’t give candidates that are too large in that sense.
Note, it’s extremely easy to pass from an unreduced bipartite monoid to a reduced one; just quotient out by the indistinguishability relation
x \rho y iff P(xz) = P(yz) for all z \in Q
So if you have an unreduced bipartite monoid that is correct for a given game, you can find the misere quotient by modding out by this relation. Indeed, an early version of miseresolver worked by finding a large unreduced quotient and then passing from there to the reduced quotient. The problem was that the unreduced quotients rapidly became too large to be useful. That is why I switched to the current iterative algorithm; essentially it performs the reduction repeatedly at each stage of the iteration.
Also, how does MisereSolver know that the lexicographically least failure occurs for game G when the number of games preceding G in the lex order is infinite?
It uses the verification algorithms described in our paper (Misere quotients for impartial games, supplementary material, http://www.arxiv.org/abs/0705.2404 ) The basic idea is to prove that the lex-least failure must satisfy certain constraints, and the constraints are sufficiently strong that they are satisfied by only a finite number of words in the heap alphabet. (That is, we can prove that if a failure occurs for a word that is not among the finitely many critical cases, then it must also occur for one of the critical words.) Therefore it suffices to verify just finitely many critical cases in ascending order.
Hope this helps,
Aaron
New papers by Aaron Siegel
1) The structure and classification of misere quotients.
2) Misere canonical forms of partizan games
…or visit his home page.
Lectures by Aaron Siegel at the Weizmann Institute
Aaron Siegel has come back from Israel where he gave five two-hour lectures on misere games.
- Normal play
- Octal games and misere play
- The periodicity theorem
- More examples
- 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!
Misere quotients for impartial games
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!
Misere solutions for particular octal games
Some commutative monoids for specific games are now online for you to browse, if you like.
There’s more to come!
An invitation to combinatorial games
Aaron Siegel’s slides from his recent talk, “An invitation to combinatorial games, (Part I).”
The commutative algebra of T2
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).
An invitation to combinatorial games
Aaron Siegel is giving talks on combinatorial games at the Institute for Advanced Study in Princeton, NJ this month, on Oct 10 and 17.
Here is his abstract in the announcement:
Combinatorial game theory is the study of combinations of two-player games with no hidden information and no chance elements. The subject has its roots in recreational mathematics, but in its modern form involves a rich interplay of ideas borrowed from algebra, combinatorics, and the theory of computation.
The first part of this talk will be a general introduction to the classical theory of partizan games. I will show how a few simple axioms give rise to the group of short games, a partially-ordered Abelian group with enormously rich structure. I will discuss how the theory can be applied to extract useful information about a diverse array of games, including Nim, Domineering, Go, and to a lesser extent Chess.
In the second half of the talk, I will briefly discuss three areas of current research in combinatorial games: the theory of misere quotients; the lattice structure of short games; and the temperature theory of Go endgames. There has been significant activity in all three topics in the last five years, but nonetheless I will be able to state some major (and reasonably elementary) open problems in each of them.
The Phi-values of various games
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!
Advances in losing 