Tuesday, January 31, 2012

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.

Friday, January 27, 2012

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! :)

Wednesday, January 25, 2012

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?

Tuesday, January 17, 2012

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.