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.