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?