Game Description: Amazons

Amazons was first introduced to me by Dale Garraway, a visiting professor at Colby while I was an undergrad. It is a nice combinatorial game because it can be played on a common checkerboard using chess pieces (though if you use the queen piece as an amazon, you will need multiple sets of pieces) and something to mark destroyed squares. Each turn, a player chooses one of their amazons, then moves that amazon just as a queen piece in chess, but may not move onto or through a square either occupied by another amazon or which had been "destroyed". After moving, that queen shoots an "arrow" at another square which is a "queen move" away from their current location.

The next player then takes their turn, continuing until the current player does not have a move.

Amazons was invented in 1988 by Walter Zamkauskas. The rules are simple to learn and enjoys computer-based opponent championships. In 2005, Bob Hearn showed Amazons to be PSPACE-complete, thus it is unlikely that an efficient algorithm can evaluate all Amazons boards of general size.

The play tip that Dale and I learned was that sugar packets do a great job of marking destroyed squares.

Enjoy the winter break! I am planning on returning to a normal posting schedule on Monday, Jan. 11, 2010.

Short Disjunctive Game Sums

A few weeks ago, I attempted to define Paul Ottaway's Short Disjunctive sum in terms of game summands instead of the method of play. I am interested in doing this because other game sums are written this way and also because there is a big difference between game definitions and methods used for play.

For example, combinatorial games are defined just in terms of plays available to each player, but then Normal and Misere are two play methods used in competition. Thus, the basic operations do not sum two misere games together, but rather sum two games together and then to compete on that composite state, a play method is chosen. Winning and losing is not defined via the games, but by the way they're played.

The short disjunctive sum definition seems to refer to a play method, except that it doesn't describe who wins or loses:

The short disjunctive sum of games is played by first choosing a component then making a legal move in that component if such a move exists. The game ends when a player chooses a component in which he has no legal move.

The other week, I tried to express this in set notation the following way: (G1 = {L1 | R1} and G2 = {L2 | R2})

G1 + G2 = { Left | Right } where
if either L1 = null or L2 = null, Left = { L + G2 : L \in L1} U { G1 + L: L \in L2} U { | 0}
otherwise, Left = { L + G2 : L \in L1} U { G1 + L: L \in L2}
and
if either R1= null or R2=null, Right = {R + G2: R \in R1} U {G1 + R: R \in R2} U {0 | }
otherwise, Right = {R + G2: R \in R1} U {G1 + R: R \in R2}

The idea behind this is that in the case where one of the children on the appropriate side is null, then there's an extra "bad child" that player could choose to move to (for example, { | 0} for the Left player). In this case, the right player can choose to move to 0 = {|} next turn, and then the game has ended, just before the Left player's turn.

Why did I use this in my definition? With these sum rules in place, in both Misere and Normal play, the correct player wins. In normal play, the Left player, upon making the bad move, would give the Right the last chance to play and win. In misere play, Left would choose that game and, if I understand short disjunctive sums, they would not complete a move and would win. With the above model, that choice would leave Right with a final complete move, which would lose them the game.

This was only my basic logic; I don't know how well it holds up under other game operations. It is often the case that preserving the value of strategies is not the same as actual game equivalence! Also, I should apologize for not having studied the notation Paul has actually introduced for these game sums!

This week and next semester

Unfortunately, I am too busy today to get down a proper post. Finals have begun at Wittenberg and I have a stack of exam-writing and grading to get down to. On Wednesday I expect to write a longer post than the past few Wednesdays have allowed. I plan also to post on Friday.

After that, winter break is well underway and things will likely be more scattered until the new year. The spring semester begins here at Wittenberg on January 11, so regular posting will resume quickly. I again have MWF classes so I should be able to keep up the same MWF schedule we've become accustomed to here. I may even get my posts up earlier in the morning.

I'd like to graphically jazz up the blog a bit, but I'm not much of a layout specialist. If you have any ideas or images, I'm all ears! (Or eyes.)

Although the break seems like a great time to post about games, I will be somewhat distracted trying to prepare for the FUN with Algorithms paper deadline on January 15. I can only assume gamesters have a good shot at this conference :)

Game: The Voronoi Game

As someone mentioned on the computational complexity blog yesterday, the Voronoi Game is a game of perfect information without randomness. The two-player version is a good partisan combinatorial game.

The game is based on Voronoi diagrams, which describes which areas of a plane are closest to each of a collection of points. Given a set of points, S, in a space, a Voronoi diagram is a partition of that space such that each partition contains exactly those points closest to one of the elements of S. Border-case points (those equivalently far from multiple points in S) are in a separate set belonging to other points that are also equivalently far from the same subset of S.

In the Voronoi Game, players take turns choosing points on a filled square until each has chosen some fixed number, m. At that point, a Voronoi diagram of the square is created and each player scores points equal to the total area of diagrams containing the points they chose.

As far as I can tell, the game was created by Indrit Selimi, as he is mentioned on the original Voronoi Game page. The blog mentions a newer version which can be played with many people.

Is there anything known about strategies for this game?

Another Game post on Complexity Blog

Just an FYI: Bill Gasarch has posted an interesting discussion about games on the computational complexity blog:

http://blog.computationalcomplexity.org/2009/12/whats-your-game-mr-bond-nim.html

CGT Class description

There were some issues and comments from Monday's post that I still have to look into. I will! Fear not!

I wanted to run the latest iteration of a game class description here:

Combinatorial Games are an avenue to model basic decision-making and computation. In this course, we will look at computational and mathematical basics of combinatorial game theory, analyzing such games as Chess, Go, Checkers, Domineering and Amazons as well as many others! Topics will include basic algorithm design, strategy analysis, games as a number system, impartiality, parity and a dip into computational complexity.

I mentioned in a previous post that this class is intended for undergrads, and will only require both basic programming and discrete math pre-requirements. Is this a good description?

Different Game Sums

Previously there had been some discussion about different methods for summing games. Normally, given two games G1 = {L1 | R1} and G2 = {L2 | R2}, we use the disjunctive sum to describe making one move:

Disjunctive:
G1 + G2 =

{ { L + G2 : L \in L1} U { G1 + L: L \in L2} |
{R + G2: R \in R1} U {G1 + R: R \in R2} }

Informally, a player may choose one of the subgames, and make one of the moves available to them normally on that summand.

Lots of the discussion of last month concerned "where to apply misereness" to a game. I was trying to apply it to the game objects themselves, while it is usually applied to the play of a game instead. Paul Ottaway stepped in and said this was okay while evaluating games using the short disjunctive sum. When taking the short disjunctive sum, a player does not need to choose a subgame on which they have a move, but if none legal move exists, they immediately lose.

This is not as immediately obvious to define in the above set-notation, so let's give it a try:
(Warning: Attempted Ascii Brackets ahead! Update: Ascii Brackets removed!)

Short Disjunctive: (Update: fixed spacing issue. Did I get it right, though?)
G1 + G2 = { Left | Right } where
if either L1 = null or L2 = null, Left = { L + G2 : L \in L1} U { G1 + L: L \in L2} U { | 0}
otherwise, Left = { L + G2 : L \in L1} U { G1 + L: L \in L2}
and
if either R1= null or R2=null, Right = {R + G2: R \in R1} U {G1 + R: R \in R2} U {0 | }
otherwise, Right = {R + G2: R \in R1} U {G1 + R: R \in R2}

(Did I do that right?)

Alternatively, one may want to consider the sum where each player chooses to make a move on each of the available game boards. This is called the conjunctive sum of games:

Conjunctive:
G1 + G2 = { { l1 + l2 | r1 + r2} : l1 \in L1, l2 \in L2, r1 \in R1, r2 \in R2}

This may seem simpler, but after getting used to the disjunctive sum, it likely seems much more complicated from a gamester's point of view. Perhaps we will cover these sums more in the future!

Are there sums I missed? Please let me know!

Game Description: Cookie Cutter

One thing I remembered I hoped to do with this blog was describe different combinatorial games. In honor of Paul Ottaway who made many comments the other week concerning adding misere games, I would like to talk about a game presented by him, Cookie Cutter. If there are other games you would like me to talk about, I would be glad to do so. Just let me know!

Cookie cutter is an impartial game that is deliciously reminiscent of Chomp. The state of this game is an n-by-m grid of squares---some of which may have already been cut out of the board---and an i-by-j cutter that is used throughout the game. During a player's turn, they may overlay the cutter anywhere on the board (without turning it) so that it overlaps at least one non-cut square (cookie). The cutter does not need to be totally contained within the n-by-m cookie grid (it can stick out over the side). All cookies under the cutter are then removed from the grid, and play passes to the next player. If no cookies are left, then the game is over and the player who cannot make a move loses.

This is similar to Chomp not only in that it makes me hungry to think about it, but also that Chomp is a misere instance of this game where the cutter is just as big as the square grid and it must cover up the bottom-right cookie each turn.

Perhaps this is a bit of a stretch, and some of the patterns Paul notices in his master's thesis are actually more reflective of Kayles.

This relationship is more clear in games with one row of cookies and a cookie cutter of odd width (say k). In this case, the first player may either cut up to k cookies off one end or remove k cookies and split the row into two parts. If k = 3, that's a lot like Kayles on a line graph. There you can either chop up the line into two parts, removing 3 nodes from between the two pieces, or cut two or three nodes off one of the ends. The difference? You can't remove just one node on an end.

It turns out that this form of Cookie Cutter results in periodic nimbers based on the size. For a row of cookies of size k, and an odd cookie cutter of width i, the Grundy value of the game is: k (mod (i+1)). This simple periodicity is due to the ability to remove one node from the end of a game, missing in Kayles.

Cookie cutter is only one of three games explored in Paul's masters thesis. His analysis naturally carries beyond the one-row version of the game.

Talking about Stubborn Matchmaker tomorrow

Wednesdays often require short posts. This one perhaps more so than others.

Tomorrow, I will be talking about some of my thesis work on the impartial game Stubborn Matchmaker. The game is based on pairing candidates in a Stable Matching environment where both sets have a universal preference. The game ends when the matching is stable (the ith candidate on the left is matched to the ith on the right, for all i).

In case you're in the Wittenbergish area (central-western Ohio), feel free to stop by at 4pm for the talk, which will be in room 320 in the Science Center.

Perhaps someone out there will have an answer to how the patterns we see in the game actually work!

-Kyle