Another Rules Change

Sometimes I wonder how much players should expect board game designers to get the rules right the first time. It seems to me that there are lots of games being published these days and it might be difficult to detect all the errors prior to publication. Still, I am often surprised at what is either a small amount of playtesting or a bad translation of playtesting to actual rules.

Having said this, I know I am already guilty of not getting to do enough playtesting when it comes around to designing new combinatorial games. It's hard to see how a game will play out unless you can find opponents, which I assume is more difficult in the academic setting as opposed to an actual game manufacturer. Still, it does seem reasonable that small pieces may be missing from a rule (for example, a stalemate rule). It's nice when the solution to these is easy enough to see and implement.

I'm having a more difficult problem resolving a conundrum with Ninja versus Ninja. I've mentioned this game before, but after posting on the topic of confusing/incorrect rules this week, it again jumped into my head.

To quickly explain the uncertainty, this page describes the different possible moves in one turn after a throw of the two four-sided dice. The goal is for your ninja to infiltrate the opposing dojo and either end your move on one of their ninja (thus eliminating them from the game) or just returning for a number of points equal to the distance your ninja was able to infiltrate. Ninja only have three turns to leave their dojo and return, so you do not often hang out in enemy territory. Instead, ninja will often use the reverse move to go deep and then turn around.

In order to prevent the easy capture of ninja, movement is restricted to either going in a straight line or an L-shaped move, and jumping of other ninja (even your own) is not allowed. The reverse allows your ninja to move in a straight line, then turn back around at one point, though this is only allowed in the opponent's dojo. The rules then suggest that a good strategy is to move your ninja directly next to an opponent's ninja, since then "there is no way for that Ninja to eliminate your piece (the two dice can only roll the numbers 2–8)".

This isn't true, however! If they roll an odd number (and are in your dojo and are deeper in your dojo than your piece) they can move further in and then reverse into your ninja. If they roll a 2 and a 3 on the dice, they can move forward two spaces, then reverse three, landing on your ninja they were initially next to.

That seems mostly legal. It plays pretty well and can be a bit hard to make happen (see all the requirements above). Sadly, it means that the strategy of moving your piece in position to attempt to block them getting back to the dojo doesn't really work.

Even more unclear and potentially damaging is the use of combining an L-move and a reversal. In this scenario, a ninja is moved a few squares sideways (not deeper into either dojo), then towards the opponent's dojo, then reverses and heads backwards. Everything seems to work fine during the reverse---so long as you don't reverse past the space you turned at. For instance, a ninja who has 6 spaces to move could move 1 square to the left, then forwards 2 squares, then backwards 3. In this way, the ninja is essentially able to land on (and kill) a piece one square left and one square backwards from it's starting position, even though it didn't roll a 2. This combination is often too strong.

My fiancee and I have changed this to not allow the reversing-with-an-L ninja to use more spaces than occur in the L-shape. Thus, the ninja cannot move further backwards than forwards. This is a pretty tame change, though it plays a lot better than allowing the rules as they appear to be stated.

Other potential rules alterations I would consider:

1) Don't allow ninja to move further backwards than forwards on any reversal. This would actually prevent the can't-kill-neighboring-ninja statement the "strategies" part of the rules claims is impossible.

2) Allow ninja to move further backwards than forwards on reversals, but only if the move does not end them on another ninja. This allows more liberal reversals, but still restricts the ninja from using it to capture other ninja.

3) Don't allow reversals at all. (I want to try playing this way.)

Perhaps there are not many Ninja Versus Ninja players out there at this point, but if anyone has played this game and had a similar problem, please let me know!

On the other hand, which other games (seem to) need a change to the rules to make them (more) playable?

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.

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?