Complexity of Games with Randomness

It is known that Hex is a PSPACE-hard game. (See this page, it is the "Hex ist PSPACE-vollstaendig" paper by Stefan Reisch.) Once we add a bit of randomness, however, the strategies suddenly become far easier! As I think I've mentioned before, if you change the game so that the current player is chosen by the flip of a coin, the winning strategy becomes simple.

I'm also interested in trying to analyze some games by removing their sources of randomness. Instead of relying on die rolls, for example, give each player the set of potential die rolls and let them choose one at a time, then removing that "roll" from their set of available moves. Once all options are chosen, either the player has no more moves or they get a new set of false rolls. I don't know of any analytical results like this, but I would love to see them!

On the other hand, I also have some interest in answering complexity questions of games that include randomness. For example: What is the probability that the current player has a winning strategy? Alternatively, rephrasing as a decision question, does the current player have a strategy that will allow them to win with probability > .5?

I don't know of any results like this. Do they exist?

Randomness and Games

During grad school I took a total of five different courses on randomness in computing (not including cryptography)! When my classes were winding down and my focus shifted to games, I wasn't sure how much randomness would still have to offer.

It seems like it makes a big difference.

There are two facets to randomness in games: using randomness in the rules of games (technically they no longer fit the strict definition of a combinatorial board game, but whatever) and using randomness as a tool to play and solve games. This second facet has gotten some attention lately.

In Lance Fortnow and Bill Gasarch's complexity blog, a post was recently made on using randomness to play Go. From their blog:

Consider the following seemingly crazy way to evaluate a game board: Have each player play randomly and see who wins. Repeat a few hundred times and score the position by the percent of time that White won.

It turns out, this may be a really good way to evaluate Go. I have seen (less scientifically) something similar with Atropos. Instead of giving our Java applet a complex AI to play, I just have it choose uniformly from all the not-immediately-losing options. This makes it pretty tough to play in a lot of situations (especially in boards of size 5 and 6). This is certainly less sophisticated, because it's not doing any smart tree-pruning things, etc, but it is not a trivial opponent.

The first of these facets seems to trivialize a lot of attempting to compute strategies for playing well. It seems that algorithms become more simple, often resorting to a more greedy approach. In some sense this is a boon; people are often more willing to play with me. I have some dice which I can use to randomize the colors available to a player each turn of Atropos, and potential opponents are often more willing to play. It's better to lose to the luck of the die than to not have thought hard enough about it.

For the game Ninja versus Ninja, both me and my fiancee think it would be interesting to get rid of the dice and play with 16 different moves available to us (2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7, 7, 8, one each of the different possibilities when rolling two 4-sided dice) and then check the score at the end of that. We think it would be interesting... but we haven't done it yet. Too much thought, perhaps. Instead of having our ninja be within a possible roll to die from an opponent's ninja, we know that they could "spend" that number, but then what if it's in the range from one of my own numbers? At which point is it worth spending the number to kill a ninja, etc. (I won't explain all the rules here.)

Indeed, using randomness to determine who gets to have a turn also simplifies strategies. Random-turn impartial games are certainly affected this way (at the end of the game, a coin flip will determine who wins and who loses), but even partisan games, such as Hex, can become simple.

I know of no examples which go the other way---showing that randomness in a game makes it more difficult---if any exist.