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

Double Games

Sometimes it's fun to try and combine multiple game boards or sets at the same time. We can always use the normal ways of adding two games together, but there are some other alternatives too...

In high school, a friend of mine mentioned he used to play "boxcar chess" with his family. This is a version of chess using two sets and four players on two teams. Two games went on at the same time, except whenever you capture an opponent's piece, your teammate gets to add that piece to their board. Thus, you had to play the opposite color of your teammate.

I don't know the details of how you add "new" pieces, but I assume you can spend a turn to place one of them in your back row.

I tried to adapt this for Stratego, since my family had two sets. I made the rules a bit too strict, however, and it wasn't all that interesting. I'd like to give it another try some day with more flexible rules.

Then, just last week, I was chatting with Brian about old war games (I really am only familiar with Risk and Diplomacy) and he mentioned enjoying "Double Risk" using two boards. The boards interact by including adjacencies between each pair of countries with the same names. Thus, if I wanted to get past Central America on board A (which has a bunch of armies on it) and I have a big force on Venezuela on board A, I could instead attack Venezuela on board B, then Central America on board B, then, say, Western United States on board B and on to Western United States on board A. I don't actually think this is a good Risk strategy, but I'm still bitter at that game for the power of cards...

Difficulty of "Who Can Win?"

I am back early from GenCon 2009 (my first time!) because my orientation starts today. I'm not sure what there is to say about the convention, except that I did play a lot of board games and for many of them, I wonder about the difficulty of playing well. Is there a point where you can say, "I am winning!" unless you've already won?

Well, being a computer scientist, I would consider having computers trying to determine who is winning. If there is no randomness in the situation, then we could go through each possible sequence of moves from the current position and see what the possibilities are. Unfortunately, there are usually an there are usually an exponential number (in the size of a generic description of the game) of these different sequences, so we can't expect computers to evaluate a game that way.

Some games, such as Nim, have very fast methods for determining whether there's a winning strategy to play from a given position. Others, such as Chess, have no such algorithm. Computers can play chess well, however, because there are good ways to evaluate your strength on the game board. Even if you don't know for certain you're going to win, if you have a lot more of the strong pieces than your opponent has left, you can confidently state that you are in a better situation.

This doesn't always work, however. I was demoing the game Ninja versus Ninja from Out of the Box on Friday, and made some moves that I thought really put me in a strong position with more ninjas and points than my opponent, only to find that they could counterattack safely and be out of the way of any response from me. To be fair, this is a bit of a difficult comparison, because Ninja versus Ninja has a random aspect to it (dice rolling) that chess does not.

We can classify the difficulty of games based on the length of an algorithm to determine whether a winning strategy exists for the current player. Nim has a strategy that can be calculated in a polynomial amount of time---which we deem "efficient". Thus, we call Nim "easy". Chess, on the other hand, requires an exponential amount of time to solve, so we call it "hard".

Some games exist in realms (classes) somewhere between P (polynomial time) and EXP-TIME (exponential time) such as NP and PSPACE, which could be either equal to P, equal to EXP-TIME or neither (but not both); we don't yet know where this class is for absolute certain, though most believe that it is separate from P. (Feel free to harass the nearest complexity theorist to try to solve this. Remind them they would become famous if they did.) The best known algorithms to us right now take exponential time to solve PSPACE-hard problems, so these are also not usually tackled by brute force.

This computational logic carries over into play between humans. It's more difficult to play these hard games because it's too difficult to be certain what the best strategy is until you get close to the end of the game. Thus, these games tend to be more fun. Playing Nim a few times is fun until at least one of the players knows the trick to win. Then the game is no longer interesting, everyone already knows the best possible play.

Of great interest to me is: are there any tell-tale aspects of a game that help determine whether a game is easy or hard? Analyzing a game can be tricky: proving that a given game is PSPACE-hard or is in P can often be quite a feat. One of the things I've considered lately is the way games are added together:

Question: If you add two instances of a game together which creates a new instance of the same game, does this imply that the game is easy?

To clarify, I should mention quickly how we get a new game from adding two games together. Simply put, each turn you make a move on one of the boards. Since CGT defines losing as no longer being able to make a move, you lose if there are no more moves available in either of the two boards of your composite game.

The question above holds for nim. Adding two sets of nim piles together just creates a new nim game. On the other hand, Hex, which is PSPACE-hard, does not have some obvious method for adding two games together to get a new Hex game. Perhaps the inverse of the question could also be true...

Does anyone know anything about the validity of either?