Game Description: Zuniq

Wow, some good games were suggested by readers two weeks ago! In addition to Nick Bentley donating Y with Shifts, Marcos Donnantuoni commented about his own impartial game, Zuniq. Ernie and I tried this out on Monday, and we immediately liked playing this! Here's how the game works:

The starting board is a grid of dots, similar to dots and boxes. Each turn, a player connects two adjacent (vertical or horizontal; not diagonal) dots, but not exactly like dots and boxes. If a new line segment closes off a region, no future turns can be made inside that region. Also, no two regions can have the same size. Thus, you can't close off a region if a region of that size already exists.

The suggested starting 8x8 board is a bit large, but we gave it a go. (Video: [7:16]) Afterwards we tried with 3x3 boards, to quickly learn that they are not very interesting. (The first player can always win by being just a little bit smart.)

The 4x4 game is definitely more interesting. (Video of lots of little games. [6:08]) After a few of these games, and later with games played against Patrick and my WittSem peer mentor, Alec, I think I can consistently win going first there. Still, my initial guess is that the game is PSPACE-complete in general.

I feel like there are lots of nice theorems that can be shown about this game. At the same time, I'm not familiar with what sort of theorems are "useful" from a CGT perspective (aside from computational complexity results).

Quiz Time!

I asked my students the following questions in class. We've covered outcome classes, but are not quite at game values yet.

Let X be the Domineering position that is two empty squares tall.

Let Y be the Domineering position that is four empty squares tall.

Find a Domineering position, G, such that X + G is in P (Zero) but Y + G is in L (Positive)

That one's not too tough. Neither is the next one:

Find G such that X + G is in R (Negative) but Y + G is in P.

This one's nice:

Find G such that X + G is in N (Fuzzy) but Y + G is in L.

My first solution for this one had a composite (sum) game for G, but I've since found a non-composite solution:

Find G such that X + G is in R, but Y + G is in L.

If you know a bunch about the values of Domineering positions, I guess these are relatively simple. If not (or if you are good at forgetting), perhaps they require a bit of extra time to consider.

Shifting Connection games

After last Friday's post, reader Nick Bentley suggested playing again but allowing each player to not only place a new piece, but also shift an old piece each turn. Ernie and I easily spent all of our Monday meeting trying this out. Here's one of those games. During the game, we had a lot of questions about what was legal (e.g. declining the shift, etc). Hopefully Nick can answer those for us!

This really changes the game! You can see one point where I was about to lose because I hadn't anticipated the power of the shift. Ernie was nice enough to let me go back... :-D

Nick suggested another game to play, and then another reader, Marcos, suggested his own game. I guess Ernie and I have plenty on our plate! :)

I'm really interested in playing the shift version of Hex. Or the shift version of Adjex! Is there some ruleset to combine this with an adjacency restriction?

The Joy of Teaching Games

Last Wednesday was the second day we just spent playing games in class, and the first one where they had learned some of the theory (specifically, outcome classes). What a blast! I started putting up Amazons positions for them to find the outcome classes of partway through the class. They picked up on this challenge immediately, students flocking to the boards to post the class they had found, then either verifying or questioning the results of others. I had about twenty positions around the room and only a few of them remained unexplored by the end of the hour. The air is very charged, but the feeling is very positive. Students are working together to solve the problems, and this requires them to try out moves on physical boards, then confer with the people around them. Your opponent quickly becomes your best teammate as you collaborate to test all possible game tree paths. For some of the harder boards I put on the marker boards, groups had banded together to discuss their results as a bigger team. There was not an unengaged mind in the room!

As I've mentioned, this class is a first-year-experience seminar at Wittenberg (a WittSem) and has the dual purpose of helping integrate the students into college life. After teaching the math/compsci-elective version of the class last year, I thought games could make for a nice WittSem topic. I was further spurred on by David Wolfe, who told me he had once taught a freshman-introduction class all about playing Go. (I only just played my first game of Go last week, so I wasn't ready for that!)

These new students have actually been very patient. I promised them early on we would spend entire class periods playing games, and it took over two weeks of class before we covered outcome classes; giving them something to analyze while playing.

Also on the point of teaching, I happened across an old reddit post of Joshua Biedenweg's, prior to his teaching a CGT course at UCSB. Josh finished teaching his course right as I was prepping for mine over a year ago; I took some good advice from him and unfortunately ignored some better advice! (Josh, I'm using Toads and Frogs more this year! Pictoral Evidence:

)

Next on the class agenda is Game Sums, and soon it will be time for them to find actual game values! Woohoo!

Conclusion: Teaching CGT is awesome. If you have the opportunity, take it!

Messing with Y

Y is a game that is very similar to Hex: players take turns claiming hexagons with the hope of connecting sides. In Y, however, the board is a triangular array of hexagons, and the goal of each player is to connect all three sides instead of just their two sides. Perhaps more surprising than the Hex Theorem is the Y Theorem: if all hexagons are colored, exactly one contiguous group of same-color hexagons touches all three sides.

This game plays similarly to hex, except that there are, like, 1.5 sub hex games going on at the same time. Ernie has taken a quick liking to this game; he's very good at beating me before I know I'm beaten! To escape this dilemma, I proposed that we give this the same treatment we gave to Hex: let's force adjacent play. We spent a bunch of time trying out different starting positions, and unfortunately it always seemed that the first player to move had a strategic advantage, even if that first play was on different ends of the board (or smack in the center, of course). This means the second player always wants to evoke the pie rule. Earlier this week, we sat down for a few games and taped them. Our first game has Ernie starting in the center. Spoiler alert: he manages to get to all sides, but the game is quite close!

In the next two games, we try instead from the middle of one of the sides. These are both great games! We are already getting a handle on how this game works.

I'm not sure, however, that I like this as much as Adjacent Hex. Of course, I've gotten more interested in FLex (Follow-the-Leader Hex) so perhaps it's time for a game of FLY!

Does anyone have a story to share about trying out an "adjacent-enforced" version of another game?

An answer to an old Nimber question

Near to the start of this blog, I posed a question:

if the nimbers for a game are bounded above, does this imply that there is an efficient algorithm, or shortcut, to evaluate impartial games?

I recently realized there is strong evidence against this. It is true that any impartial ruleset where all the nimber values are either *0 or *1 is very easy to evaluate---all options from one position have the opposite value (otherwise there would be *2 states)---so all paths down the game tree have the same parity. All that's needed to create PSPACE-hard instances, however, are states with the value *2. Why is this? Well, we can change the rules for any game with higher values into an equivalently-winnable* game with maximum nimber *2. The plan here is to break down the options from a game when there are more than two. We do this by splitting up those options into separate groups, then preventing the other player from being able to make any choices.

For example, we can transform the game G = {A, B, C} into the game G' = { { { A, B } }, { { C } } }.

Here's a diagram of the game trees, with the nimbers *0, *1, and *2 respectively assigned to A, B, and C.
For positions with more than 3 options, this splitting can be done in a recursive fashion. Thus, games with any range of nimbers can be transformed into a game with maximum nimber of *2.

* game states may not have the same value, but winning strategies from one translate into winning strategies in the other.

Game Descriptions: NimG and Neighboring Nim

What happens if you restrict which games can be moved on in a game sum? This seems to be the idea behind NimG, a game played on a collection of Nim Heaps embedded in a graph. There are a few variants, but each turn a player does two things:

* traverse an edge of the graph adjacent to the last move, and
* remove sticks on the nim heap embedded either into the edge traversed or one of the vertices.

In the sticks-on-edges version, players remove sticks from the edges while traversing them during the turn. Naturally, if the heap on the edge is empty, it cannot be traversed. In other words, the player who starts their turn on a vertex where all incident edges have empty nim heaps loses. Masahiko Fukuyama studied this game a bunch and more recently Lindsay Erickson has looked into instances on the complete graph.

When sticks are embedded into the vertices, a move still consists of traversing one edge to arrive at a new vertex. Upon arriving at the new vertex, a move is made on the nim heap embedded there. Gwendolyn Stockman may have been the first person to analyze this game in an REU advised by Alan Frieze and Juan Vera. This is the version that interests me: the vertices act like different heaps in a game sum, but the edges restrict which heap can be chosen each turn. In this ruleset, the complete-graph version is equivalent to standard Nim. (If each vertex is adjacent to a "self-loop", an edge connected twice to the same vertex.) In this game, you lose if all vertices adjacent to the current location contain empty nim-heaps.

In order to avoid the self-loop issue, I altered the rules slightly and set out to do some analysis. Neighboring Nim is exactly the same game as (Vertex) NimG, but a player may choose not to traverse an edge and instead remove sticks from the current vertex (again).

I have actually played this game very rarely, mostly because I can't imagine a standard starting position. Nevertheless, I helped show that the game is PSPACE-hard. I was lucky enough to present this result at BIRS in January, which was quite pleasant. The paper should appear in Games of No Chance 5. (arXiV version)

The cool thing about the computational complexity of this game is that once all vertices have maximum heaps of size 1, the game is the same as undirected vertex geography, which is solvable efficiently. In order to get PSPACE-hard instances, we needed most vertices to have a heap of size 1, with only a few having a second stick on them (less than 1 in 7 of the vertices need the extra stick)! It's very interesting that such a small rule change can result in such a big complexity change!