Tuesday, June 21, 2011

Saaguan Paradox

A new entry for Daniel Solis' thousand year game design challenge caught my attention today. It's an interesting abstract board game called Saaguan, designed by Andrew Cooke.

Full rules can be found here. In a nutshell, players maneuver their robots on an oct-board or hex-board to kill other robots. Each robot emits a beam toward where it's heading for, threatening enemy bots along the line. If a bot is threatened by two enemy bots, it gets "locked down", and its beam is immediately disabled; if a bot is threatened by three enemies, it gets killed and immediately removed from the board. On each turn, a player can either add a new bot to the board or make three movements of existing bots of their own by rotation or advancement.

I was quickly intrigued by Saaguan's simple rules and the difficulty to write a decent A.I. player due to its huge branching factor even on very small boards. When I started to mull over an algorithm to detect locked down and dead bots, it then occurred to me that certain contrived bot move sequences would expose an ambiguity in Saaguan's rules.

Let's consider an example on an oct-board.

In the previous diagram, blue bot #2 and #4 both threaten red bot #3, therefore locking it down (marked by a black border).

When bot #5 and #6 join the battlefield as shown above, blue bot #2 gets locked down, freeing red bot #3.

Blue turns the table again with the reinforcement of bot #7.

The addition of red bot #8 rescues neither #3 nor #6 as red is short of one more beam to lock down blue bot #7.

Here comes an interesting turning point: What happens if blue bot #2 now rotates by 90 degrees?

One might examine bot #3 first and conclude that since #2 is no longer threatening it, #3 becomes active and locks down #7 with the help of #8. One might even argue that before #2 reorients its beam downward, #6 has a chance to lock down #2 together with #1 since #7's threat is dissolved.

On the other hand, one might also check the state of bot #6 first and claim that it's under a three-way attack from #2, #5, #7 and should be immediately killed.

As this example has shown, the order of state changes is critical in evaluating delicate Saaguan situations, which hopefully will be addressed by an updated rule set.


Andrew has already disambiguated the rules on his site. That was fast!

Also, I made a mistake in the original example — robots on octboards rotate by 45° on each turn, not 90°. An updated example follows:

Red-a is locked down by Blue-b and Blue-c; Red-d by Blue-e and Blue-g. Now Blue-c rotates clockwise by 45°. Depending on the order of state evaluation, either Red-d or Blue-e could be said to be shut down. According to the new rules — if I'm interpreting them correctly — once Blue-c starts to rotate, Red-a gets activated, thus locking down Blue-e, which in turn activates Red-d. Blue-e then gets shut down before Blue-c points to the right and locks down Red-d.