Supercomputing and Thanksgiving, Back Next Week

Last week I came down with an unexpected case of Lack-of-Wireless-Internet-Access while at the Supercomputing 2012 conference.  Unfortunately, I think this is more a case of my own machine having trouble than lack of access provided at the conference.  The result (as far as you care) is that there is no post for last week.

This week is American Thanksgiving, so I will probably not have something for you on Thursday.

Posts resume next week for the last two weeks of the semester. :)

Succinct Games

One year ago, at Integers 2011, Carlos Santos presented his awesome result about Konane and short games: any possible short game value can be realized as a Konane position.  This seemed like a tremendous result to me, but to be sure, I asked Neil McKay whether there were any other known games with this property.  He responded: "Yes, 'Tree'."

"What's th-... oh." is probably something similar to what I actually said.  "Tree" is just the ruleset where any position is the root of a game tree.  He was entirely correct, of course, because any other position in a short game can be represented by that position's game tree.  It wasn't until later that I realized why this answer wasn't satisfying.

I wanted a Succinct Game. 

I've been very informal so far.  The word "game" is dangerous, as it is often used to either mean a position in a game or (maybe more common) a ruleset to determine what the next possible move options for either player are.  A ruleset is actually a pair of functions, say f_L and f_R, each of which takes a position and returns all the options for Left or Right respectively.  What I meant earlier is that I wanted a Succinct Ruleset.  This means that the positions can be described with a small amount of information.  More rigorously: less than proportional to the size of the game tree.

Tree does not fit this definition, since the input positions have to contain a description of the entire game tree.  To know what to do next, the entire game tree needs to be represented, which can certainly have variable size.  The Konane ruleset, on the other hand, just explains what the possible moves are based on where the stones are.  It does not require a description that has each input-output pair "hardcoded". 

I'm probably revealing my computational background again.  What I am actually saying is: I know that I can write a succinct program representing the function pair for rulesets such as Konane.

So, the revised question is: Are there any other succinct rulesets that have possible positions for any short game value?  Errr.... short ruleset value.  (Avoiding "game" is hard!)

Postscript note: my industrious aide Ernie found that economic game theory uses the term Succinct Game to refer to the analagous property!  This is not too surprising, since this is exactly how succinct is used: there is a way to more concisely describe a system by using a program to determine the "state".

Graphs for Graph Games

There are lots of fun graph games: Kayles, Col, Snort, etc.  When people go to play these games, how do you decide which graph to use?  How does that work?  Does anyone know of any good graph generators for combinatorial games?

One could consider the game Fjords as a graph game, with some vertices initially painted red and others blue.  Then on your turn, you paint an uncolored vertex that is adjacent to a vertex already containing your color.  This is the game you play during the second stage of Fjords.  The first stage is a longer, somewhat random process that creates the graph and assigns the initial colors.  This stage does require the players to make decisions and is likely the "more fun" part of the game. 

How else can graphs-for-games be generated?  What other board games have processes like this?

Poset Games, a Clarification

One possible misconception from Daniel Grier's recent paper showing that the general partially-ordered set (poset) game is PSPACE-complete is that this property applies to all poset games.  Thus, Nim and Chomp are also PSPACE-complete.  For those who know the quick trick to evaluating Nim states, this doesn't quite match up.  Determining whether a Nim position has a win for the next player can be done very quickly.  What's wrong here?  Does this mean that PSPACE = P?

The unexciting answer is: No.  The issue is that Nim is played on very specific types of partially ordered sets.  The posets in Nim lend to this trick of quick evaluation.  Chomp also uses specific types of posets, and thus it also isn't immediately known to be PSPACE-hard.  (I believe it's unknown whether Chomp is a hard problem for either NP or PSPACE.)

One nice aspect of Grier's proof is that it uses posets that have chains (a <= b <= c <= d <=... <=z) with only three elements (a <= b <= c).  Thus, if you have another ruleset that has potential positions including all posets with chains of 3 (or 3 levels of elements) then that game is also PSPACE-complete.  Chomp's posets do not include all sets with chains of 3, so we can't directly infer that Chomp is PSPACE-complete.

Are there any rulesets out there that satisfy that condition?

Poset Games, part 2

Continuing from the last blog post, the reduction from Node Kayles to the General Poset Game is not difficult.  For each vertex, v, of the Kayles graph, G, add an element (also called v, let's say) to the partially-ordered set (poset), S.  Each of these elements should be incomparable with each other.  Thus, if there are no edges in G, all moves are equivalent and the game's value is *k where k is the parity of the number of nodes.

What if there are edges?  A-ha, then for each edge (u, v), in G, we add two elements to S: uv+, so uv+ > v and uv+ > u; and uv-, so that for all vertices w (in G) not equal to u or v, uv- < w.

Now the first player has a winning strategy in the Poset Game on the resulting set S exactly when they have a winning strategy in the Node Kayles game on G.  (This is not immediately obvious!)

... almost.  This construction always works if G has an odd number of edges.  This is not a terrible requirement, since Grier shows how to create an equivalently-winnable odd-edged graph from an even one.

I would like to post some pictures to explain the results of this reduction, but that might be wasted effort because the figures Grier supplies in his paper are very clear. 

Cool Board-Gaming "Tools"

I recently saw something cool about choosing which player should go first in a game.  A lot of people roll dice, though ties can happen.  One dice enthusiast came up with a set of four dice that can be used to determine who goes first among two players, with the awesome properties that:

  * The dice only need to be rolled once (no ties), and

  * Each die has an equal chance of being the highest among the four.

To do this, the dice cannot have any ties.  Four twelve-sided dice are used, so the numbers 1 - 48 must be on them.  The more complicated part is how to arrange the numbers so that each player has a 1/4 probability of winning the roll.

Is there a way to generalize this?  If you have n players, what size dice do you need?  (How many sides?)  If you have access to up to 20-sided dice, how many players does this support?  For four players, are 12-sided dice the smallest you need?

It seems like this must all be proven somewhere.

Another awesome thing I saw was this gaming shed someone built, mostly to house all their board games, but also with a place to play them.  That forum post shows all the steps to create the building.  Very cool!  I am extremely jealous!  Someday perhaps I'll have the funds to copy this exact thing. 

There are many other things I desire, but these two are definitely worth sharing.

High Schoolers and undergrads are awesome at Poset Games

A few weeks back, the Computational Complexity Blog had a great post about a PSPACE-completeness proof about games!  Even cooler, the result was found by an undergrad at the University of South Carolina!

This is the third result about games on partially-ordered sets (posets) from young researchers that I've heard of.  In 2003, Stephen Byrnes proved a cool theorem about the periodicity of chains in poset games.  Earlier this year, Adam Kalinich found a transformation that converts a current-player-is-winning poset game to an other-player-is-winning poset game.  (I'm less familiar with this result; I'm not sure whether it's assumed that these are all impartial games.)  Now, Daniel Grier has shown that the General Poset Game is PSPACE-complete.

What exactly is the General Poset Game?  It's a game played on elements of a partially-ordered set.  Each turn, a player removes an element from the set as well as all elements greater than the chosen element.  If there are no elements in the set at the beginning of your turn, then you can't make a move and lose the game.

Many games are examples of poset games, including Chomp and Nim.  This result does not immediately mean those games are PSPACE-complete to determine which player is winning!  (Nim is definitely not, since there's an easy way to evaluate Nim states.)  This says that the following problem is hard: given a set, S, and a partial ordering of S, P, determine whether the General Poset Game using P on S is in Fuzzy or Zero.  Thus, worst-case instances are going to be difficult, not just ones that are easily recognizable as a Nim state.

The reduction for this is extremely simple!  I'm out of time, however!  More next time! :)

Back to Blogging, Fall 2012

I stopped posting early last semester and am starting up again late.  Oops!  Here's a quick summer summary:

* I'm better.  I've had a bad illness the past few years that is now nearly invisible, thanks to modern medicine!  Awesome!

* I missed Games at Dal(housie) during the summer.  I'm certain it was awesome!

* I learned a lot of Javascript (not yet enough to get a javascript version of Atropos up).

* I learned a lot about parallel programming design patterns.

* I prepared to present a workshop at Supercomputing in November.

* I played with my one year old.

* We made lots of long road trips (with the one year old).

This semester I have spent some extra time putting together a game lunch, including a barebones webpage.  This time it's sandwiched between my two intro-programming labs.  The timing is nice because I see some of my programming students from each lab coming to play board games.  The downside is that I can't linger longer than an hour, which I would usually do in previous semesters.

So, yes, there will be posts this semester, though I may not quite hit two per week due to many of the summer projects that spilled over into the fall semester.  If you are especially interested in a certain topic, let me know and I'll do my best to cover it! :)

Happy Fall Semester!

Possible PushPush-type games

I spend a bunch of time perusing questions posed to the cstheory stackexchange page. Lately, I saw this question about a variant to the puzzle PushPush. The idea is that you have a grid, with a boundary and some obstacles. There is a square on the grid that is the goal, and a disc that is trying to reach the goal. Each turn, the player moves the disc in one of the cardinal directions until the disc hits the boundary or an obstacle, then it stops. The question is whether the player can move the disc to the goal.

I would expect the questioner to have trouble finding information about this if they're looking through combinatorial game theory papers, as it is a one-player game.

Perhaps there are some nice ways to add a second player and make this combinatorial. Here are a few options off the top of my head:

* Impartial version: take turns making moves, whichever player reaches the goal on their turn wins.

* Balanced Partisan: there are two goals, one belonging to each player. If the disc stops in a goal, the corresponding player wins, regardless of who moved it.

* Different Roles: One player is trying to reach the goal while the other player moves the disc and tries to prevent the player from reaching the goal.

The interesting part about this is that the puzzle version is in P, but some of these two-player variants might have a more difficult computational complexity! (Or maybe you can prove me wrong there!)

Game Description: Hey, That's my Fish!

Hey, That's my Fish! is a great example of a combinatorial game that is mass-produced and purchasable.

The initial game board is a randomly generated grid of hexagons, each containing an iceberg with 1, 2 or 3 fish on it. Players then take turns putting their penguins on bergs with exactly one fish.

Each turn, a penguin moves any number of spaces in a straight line (in the 6 "hexcardinal" directions) from one iceberg to another. That penguin may not jump any other penguins or any empty hexagons in their path. After moving, the hexagon the penguin left is removed from the board, and that player earns points equal to the number of fish on that tile.

If a player cannot move on their turn, they forfeit their turn. Once no more moves are available to any player, all players pick up the tiles their penguins are on and add those fish to their points. The player with the most points (fish) wins.

There are rules for up to four players, which is excellent for flexibility. Once the board has been created, if there are only two players, the game is combinatorial (assuming adoption for points).

This is a really interesting game because there are greedy strategies that are often used in the beginning, even if they're not the best move down the line!

A New CGT Blog and some complexity thoughts.

Oops, I missed an extra week in there. For some reason, these papers don't get graded unless I look at them... ;)

Fraser Stewart has a wonderful (relatively) new blog up at: http://combinatorialgametheory.com/.

I will continue with more regular posts! I promise!

I've been thinking a lot about the dichotomy of game complexity. Are there any rulesets with symmetric starting positions where the complexity of the game is NP-complete? (Usually they are PSPACE-hard or in P.)

If you drop the symmetric aspect, then it's easy to design games that are NP-complete. Take, for example, the following coloring game on graphs. Starting positions consist of a single red-colored vertex and a connected, uncolored graph. The red vertex is then connected to each vertex in the uncolored graph. In addition, there are some number, k, of additional uncolored vertices, each connected only to a single blue-colored vertex.

Play proceeds as in Col, meaning on their turn, a player chooses an uncolored vertex that is also not adjacent to a vertex of their own color, then paints that vertex. This game is NP-complete because the blue player is essentially trying to find a maximum independent set on the connected uncolored graph, with size greater than k.

Not all starting positions are symmetric, however. Col doesn't fit this description, because the starting positions in Col are uncolored and thus are symmetric.

EDIT (3/29/12): Corrected some spelling.

Weekly "Game Lunch"

This semester, I've (finally) gotten a social game lunch at Wittenberg in full swing. This is a great way for faculty, staff and students to interact casually, but also exercise our minds!

I've had a couple past semesters that were attended regularly, but now it is finally common to have different groups of people wanting to play different games on any given week.

Some aspects that seem to work well are the following:

* Short games with variable numbers of players. Tsuro, Tetris Link, World War 5, and Hey, that's my Fish! have all been popular.

* Games with less hidden knowledge tend to promote discussion. The less time you spend not on your turn trying to figure out what you're going to do next and more time paying attention to what other people are doing, the more you may interact with them.

* Games with shorter turns keep people interested. Hey, that's my Fish! has a problem where players may try to analyze the game too deeply to try to win this turn. This can drag turns out unnecessarily. This relates to the next point...

* Games with randomness seem to keep turns shorter. Although they're no longer combinatorial, there's still plenty of discussion/consideration in these games to keep them interesting. I bet some will disagree with me here...

I fully recommend adopting a weekly game lunch! :) Our Tuesdays have become very fun! So much fun that I've missed a bunch of Tuesday posts lately! Oops!

Next week is Wittenberg's spring break. Posts will return the following week.

Game Description: Rule 60 Game

Urban Larsson gave a cool talk at Integers 2011 about combinatorial games based on cellular automata.

Unlike the Game of Life (which is an automata, but not a game in the "combinatorial" sense), Urban concocted actual two-player impartial rulesets based on Wolfram's rules 60 and 110. I'm not familiar with these, but I do think the two games are very interesting!

The Rule 60 Game is a ruleset that uses a pile of matches and a pile of tokens. On turn i, the current player may remove as many matches as they want on their turn (at least 1) and a number of tokens between 0 and the number of matches taken last turn (inclusive). Additionally, you may not take the last match unless you also remove the last token.

Consider the position with a heap of four tokens, a heap of two matches and that last turn there were three matches removed. What is the outcome class of this game?

As it turns out, this game is in Fuzzy. You can't end the game this turn by taking both matches) because you can't take all of the tokens. Thus, the current player has to take one match and either zero, one, two or three tokens. By taking three tokens, the resulting game is still in fuzzy, as the next player wins by taking both the last match and token. Taking zero, one or two tokens, however, leaves the opponent unable to move because they cannot legally take the last match. Any of these three positions are in Zero.

Urban has also created a game based on Automata rule 110. Although the relevance to automata-theory is a bit lost on me, these games are interesting nonetheless!

Game Description: Clobbineering

The first time I taught a games class, my student Will Herrmann combined the games Clobber and Domineering into the excellent ruleset Clobbineering.

If you're familiar with both of these games, perhaps the rules are already clear to you. In case they're not, a turn consists of either making a legal clobber move with the checkers on the board or placing a domino on two empty spaces a la domineering. Thus, the player that clobbers with the black checkers is playing dominoes vertically, while the red-or-white checker clobber-player plays dominoes horizontally.

This is enough to make the game states quite difficult to analyze. Often times the game will seem like it's over in one player's favor, but then there's a really sneaky move that changes everything.

My usual strategy is to concentrate on clobbering to open up domineering plays for myself for later that don't allow my opponent to play dominoes. I don't have any better considerations than that; if my opponent catches the drift, I'm generally in trouble!

Game Description: Odd Scoring

Oops, I previously talked about Odd Scoring without giving a descriptive post. Let me fix that now!

One of my students presented this game in my first-year seminar to the class last semester. Here are the rules.

There are a total of an even number of horizontally-set spaces, with one marker placed at the far-right space. Both players keep their own score, which starts off at 0. Each turn, a player moves the marker 1, 2 or 3 spaces to the left, then adds to their score that number of spaces moved. Once the marker is in the far-left space, the player with an odd score wins.

Some interesting points:

* exactly one player will have an odd score, because there are an odd number of moves the marker will make in total.
* you really only need to keep track of the parity of the players' score. Having 9 and 3 points are the same.
* this is not strictly a combinatorial game; the last player to move may not be the winner!

Even though this game is not quite combinatorial, can it be considered all-small? Whenever one player has a move, the other also has a move. However, in some cases this is a move where the game ends, but the last player to move still loses. Consider the following game state:

_X_ ___ ___ ___ ___ ...

Left: 0 Right: 1

What is the value of this position? That definition may change whether this game is considered all-small or not! This may not be consistent with the definition of "points" considered earlier this week!

Combinatorializing Games: How do points actually work?

We've talked recently about combinatorializing connection games, but what about point-based games. Here's a general definition of a point-based game:

Players make moves and earn points during the game. This continues until there are no possible moves. When all moves have been made, the player with the most points wins.

What makes this not-quite-combinatorial is that it is not necessarily the case that the last player to move is the one who wins the game.

Flume is an example of such a game. Players score "a point" for each piece they play, and at the end the player with the most of their pieces on the board wins. Since there are an odd number of spaces, there will be no tie.

What happens, then, if you add two games of Flume together? What if you add a game of Flume to a game of Hex?

The way I've always envisioned these games working is as follows. Let's say the game ends with the left and right players each with their point totals (called left-points and right-points, respectively). Then a new game immediately starts with value: left-points - right-points, the winner of which wins the whole thing.

Thus, if you play a game of Flume and at the end the left player (Blue) played 9 disks while the right player (Red) played 16, then the result is game of value: -7, which the right player should win.

Is this how the "combinatorialization" is usually conceived? Is there another good way to handle this?

EDIT: Fixed a typo in the title. (Feb. 10, 2012)

Game Sum Demonstration Videos

A few weeks back, my aide, Ernie, and I played some game sums as demonstrations. Of special note, you may not have agreed with the non-all-smalling of Hex, and that may make you want to watch the last three!

Here are the links to videos:

Domineering + Clobber [6:32]

Domineering + Checkers (Draughts) [5:24] (Warning: this one is unsatisfying!)

Domineering + NoGo [4:14]

Y + NoGo [7:32] (Using the non-all-small Y)

Hex + NoGo [4:27] (Using the non-all-small Hex)

Hex + Clobber [13:16] (Using the all-small Hex!)

Clearly Combinatorializing Connection Games: Un-all-smalling

Game sums are at the heart of Combinatorial Game Theory. If you give me two different rulesets, a third exists that is the sum of those two and you don't have to specify anything new.

Unfortunately, some games add poorly or uninterestingly. Hex may be a good example, because the game is over when a path is created. The standard Hex rules cause the game to be all-small: if one player has a move option, then the other also does. As I mentioned before (late in the post) it's perhaps more exciting to redefine the game to make it more "sum-friendly" (very arguable). Instead of ending the game when one player has created a path, instead allow the path-creating player to keep painting uncolored hexagons. Thus, the rule is that you cannot play if the opposing color has formed a path. Now the game is no longer all-small.

Paul Ottaway and I had a conversation a year ago where we both argued for this change. I don't know how to change the rules to a 65-year old game, however. Luckily, when played atomically (not part of a sum), the new rules do not change the game play. Make the connecting path and you win.

This works for any connection game that I know of (Y, Twixt, etc). There are many inherently all-small games that cannot accommodate such a change, however. Clobber and MadRooks are games that are all-small and for which I don't see a method to fix that that doesn't change the original game.

The inherent problem here is that prior to combinatorial game theory, games were defined by explaining the conditions for one player to win the game. Under the normal play convention, that's not entirely relevant. Instead, the game author need only describe what the legal plays are for each player from any position. It's a subtle difference that is only important in the context of game sums.

Game Description: Connect Score

Many combinatorial games that are studied in an academic setting have very simple rules. Just because a game has a multitude of rules does not remove it from the combinatorial setting, however. For example, Rick Nordal sent me a link to his game, Connect Score.

This game uses printable boards of chess pieces, each given a number. The game proceeds as a mix of Dots and Boxes and Chess. Each turn, a player first chooses to add one line which is the boundary of one or two boxes, just as in Dots and Boxes. Unlike Dots and Boxes, you do not earn additional turns by closing off boxes. Instead, the chess piece in that box becomes activated. (All pieces begin inactive.)

In the second phase of each turn, the player gets to use all activated pieces and have them shoot at each other. The colors do not matter; each player can shoot with any of the active pieces. Any piece which gets shot is then removed from the game, and the current player earns the number of points associated with the "killed" piece. Those pieces can then no longer shoot. Pieces shoot in any order the current player wishes, and can shoot multiple times per turn. They do have to shoot in order, so two pieces cannot shoot each other in the same turn. At the end of any turn after the first piece has been activated, there will still be at least one active piece.

Each Chess piece shoots in a different manner, so they can't (all) target each space on the board. The rules for each are described on the website; I will not list them here as they are too numerous. Most of the pieces shoot similar to the way they can move in Chess, so it's not terribly difficult to remember if you've played some Chess.

After the shooting phase, the current player's turn is over and the game proceeds to the next player.

When all pieces are either active (and can't shoot each other) or removed, the game is over and the player with the highest point total wins.

Rick has produced a bunch of starting boards available on his site. Ernie and I found it fun to both play with a bunch of different pieces and one where each piece was a rook.

If you wanted to play this game not on paper, you could presumably use actual chess pieces, each on a stack of coins to keep track of how many points they're worth, and dominoes to denote the edges drawn. Sounds like it might be more epic, but also harder to wrap your head around! :)

Partiality Continues to be Confusing, part 2

Common Trip-Ups:

Confusing Impartiality with Symmetry. Symmetric positions seem impartial because each of the moves for one player has an opposite in the set of moves for the other player. Those opposing positions have opposite values, however. While it is true that all impartial games are symmetric, the converse does not hold.

Separate Scores. Many games are nearly impartial, except the players keep track of different scores. The game board (not including the scores) may be changeable in the exact same ways by both players, except that then the players get different scores. 3,6,9 and Odd Scoring are good examples of this. These games are not impartial, because the scores are different.

All the positions are impartial games. { 0, *, *2, *3 | 0, * } may look impartial because all the positions are impartial positions. This is not impartial, however, because the players don't have all the same move options.

The Position is equivalent to an impartial game or 0. A game equivalent to * is not necessarily impartial. The game could be: { 0 | 0, *2 }, which is equivalent to * but does not have the same options for both players. Equivalence does not preserve impartiality. (Perhaps not everyone agrees with this!)

What are some other common problems I didn't list here?

Partiality Continues to be Confusing

Happy new semester & year! Let's dive right in!

I thought I had done a much better job explaining the difference between impartial and strictly partisan games last semester, but again far too many of my students claimed that their game was impartial during their presentations.

A few students presented symmetric games, and claimed they were impartial. A few made mistakes on games that were impartial except that each player had a separate score. These games, such as 3,6,9 and Odd Scoring, are not impartial because your turn affects your own score but does not affect your opponent's. Thus, the same moves are not allowed for both players.

For example, given the following Odd Scoring state: (parity of scores is given instead of actual numbers)

Left: Odd Right: Even
___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ _X_ ___ ...

One legal move for Left is to slide the marker one spot:

Left: Even Right: Even
___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ _X_ ___ ___ ...

Right does not have that move as one of its options. It can still slide the marker, but then the scores will both be odd instead of even. Thus, Odd Scoring is not impartial.

Last semester, I made a distinction to the class about impartial positions and impartial rulesets, defining each separately. A position is impartial if, recursively, all it's positions are impartial and if the set of Left positions is the SAME SET as the set of Right positions. (Not whether they are equivalent.) A ruleset is impartial if all positions available in that ruleset are impartial.

Before defining these, I defined symmetric positions as those equivalent to their opposite (G = -G means G is symmetric). I think this helped, because many students knew that their games were symmetric, but not impartial. This was a change from the previous year when most students claimed impartiality.

Perhaps it would be better next time to list common misconceptions about determining partiality.