Archives For combinatorial game theory

A simplified structure diagramMy colleague Nandor Sieben and I recently submitted for publication a paper titled “Impartial achievement and avoidance games for generating finite groups.” The current arXiv version of the article is located here. My typical pure mathematics research interests are in the combinatorics of Coxeter groups and their associated algebras, so while I have a background in group theory and combinatorics, this was my first research experience in combinatorial game theory. In fact, prior to working on this project, I knew next to nothing about the subject. In the year and a half we worked on the project, I learned a tremendous amount of new material, which was a lot of fun. It was exciting to branch out and try something new.

Here is the abstract for the paper:

We study two impartial games introduced by Anderson and Harary and further developed by Barnes. Both games are played by two players who alternately select previously unselected elements of a finite group. The first player who builds a generating set from the jointly selected elements wins the first game. The first player who cannot select an element without building a generating set loses the second game. After the development of some general results, we determine the nim-numbers of these games for abelian and dihedral groups. We also present some conjectures based on computer calculations. Our main computational and theoretical tool is the structure diagram of a game, which is a type of identification digraph of the game digraph that is compatible with the nim-numbers of the positions. Structure diagrams also provide simple yet intuitive visualizations of these games that capture the complexity of the positions.

The fundamental problem in the theory of impartial combinatorial games is the determination of the nim-number of the game. This allows for the calculation of the nim-numbers of game sums and the determination of the outcome of the games. The major aim of this paper is the development of some theoretical tools that allow the calculation of the nim-numbers of the achievement and avoidance games for a variety of familiar groups. In the paper, we introduce the structure diagram of a game, which is an identification digraph of the game digraph that is compatible with the nim-numbers of the positions. Structure diagrams also provide simple but intuitive visualizations of these games that capture the complexity of the positions. By making further identifications, we obtain the simplified structure diagram of a game, which is our main computational and theoretical tool in the paper.

We developed a software package that computes the simplified structure digraph of the achievement and avoidance games. We used GAP to get the maximal subgroups and the rest of the computation is implemented in C++. The software is efficient enough to allow us to compute the nim-numbers for the smallest 100,000 groups, which includes all groups up to size 511. The result is available on our companion web page.

In April of 2013, I gave two talks at the University of Nebraska at Omaha that introduce the two games that this paper is about, but did not elaborate on the nim-number aspect. I summarized those talks in this blog post.

On April 23, 2013, I gave two talks at the University of Nebraska at Omaha. The first talk was part of the Cool Math Talk Series and was titled “Impartial games for generating groups.” Here is the abstract.

Loosely speaking, a group is a set together with an associative binary operation that satisfies a few modest conditions: the “product” of any two elements from the set is an element of the set (closure), there exists a “do nothing” element (identity), and for every element in the set, there exists another element in the set that “undoes” the original (inverses). Let $G$ be a finite group. Given a single element from $G$, we can create new elements of the group by raising the element to various powers. Given two elements, we have even more options for creating new elements by combining powers of the two elements. Since $G$ is finite, some finite number of elements will “generate” all of $G$. In the game DO GENERATE, two players alternately select elements from $G$. At each stage, a group is generated by the previously selected elements. The winner is the player that generates all of $G$. There is an alternate version of the game called DO NOT GENERATE in which the loser is the player that generates all of $G$. In this talk, we will explore both games and discuss winning strategies. Time permitting, we may also relay some current research related to both games.

The content of the talk falls into the category of combinatorial game theory, which is a topic that is fairly new to me. The idea of the talk is inspired by a research project that I recently started working on with Nandor Sieben who is a colleague of mine at NAU. In particular, Nandor are working on computing the nimbers for GENERATE and DO NOT GENERATE for various families of groups. If all goes according to plan, we’ll have all the details sorted out and a paper written by the end of the summer.

After a brief introduction to combinatorial game theory and impartial games, I discussed both normal and misère play for three impartial games: Nim, X-Only Tic-Tac-Toe, and GENERATE. You might think that X-Only Tic-Tac-Toe is rather boring, but the misère version, called Notakto (clever name, right?) is really interesting. In fact, there is a free iPad game that you can download if you want to try it out. Also, if you want to know more about the mathematics behind Notakto, check out The Secrets of Notakto: Winning at X-only Tic-Tac-Toe by Thane Plambeck and Greg Whitehead.

Here are the slides for my talk.

Immediately after giving the Cool Math Talk, I facilitated a 2-hour Math Teachers’ Circle as part of the Omaha Area MTC. The audience for the MTC mostly consisted of middle and high school mathematics teachers. The theme for the circle was the same as the Cool Math Talk, but instead of me talking the whole time, the teachers played the games and attempted to develop winning strategies.

This was my second time running a MTC at UNO. In February of 2012, I ran a circle whose general topic was permutation puzzles. You can find the slides from last year’s circle here.

Both talks were a lot of fun (especially the MTC). Thanks to Angie Hodge for inviting me out to give the talks.