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