## Monday, September 28, 2009

### Avoiding Loops and Rewriting Rules

Some games, such as Tic-Tac-Toe, have a clear maximum number of moves. Either the game ends before nine moves have been made, or the ninth move is the last. On the other hand, there are games that don't have such a trait; they have the potential to run an unbounded number of turns.

When I was a kid, I enjoyed playing Stratego with my grandmother. One of the (very sensible) rules that often got me into trouble was the non-repetition rule: a piece cannot be moved back and forth between the same two spaces more than three times in a row (or something similar). Another example is the following rule in Oshi:
Stalemate
When you move one of your pieces, you cannot end its move in the same space it occupied at the beginning of your previous turn.
Oshi is all about moving your pieces around a grid and trying to push the opponents' pieces off the board. It's an excellent game, and this rule prevents a lot of potential "loops" from occurring. By loop, I mean a situation where the sequence of game states repeats. This could potentially still happen in Oshi if two players play a little back-and-forth dancing game between two different pairs of stalemating pieces. Many unbounded-turn games have this difficulty and these sort of loops (which can force stalemates) can often not be easily ruled out through the addition of these sort of stalemate rules.

Unfortunately, however, there are often situations in Oshi where the above stalemate rule fails. As I mentioned above, the game pieces are used to push opponents' pieces off the board. In a very basic case, if there were two pieces (of the same size) they could push each other the same distance. For example, the red piece could push the white piece towards the board's edge. On the white player's turn, the white piece might want to push back, moving both pieces back towards the the other edge.

The red player would likely want to respond by pushing back. The white responds by doing the same thing back, and the game loops. Unfortunately, this very simple repetition and often happens during the game. It happens in almost this exact situation, but also in more complex situations. You get pushed, and you immediately respond by pushing back. This seems like a good strategy, but leads to these bad situations. Thus, for a few years, I've been using the following replacement for the above published rule:
Stalemate
When you move one of your pieces, you cannot end its move in the same space it occupied at the beginning or end of your previous turn.

The rule is only slightly changed, but it makes Oshi far more playable. If you're about to start a game, I highly recommend playing this version!