Pages

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.

Update

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.

10 comments:

  1. Hallo Zhen!
    You're a fast worker and thanks for your interest!!

    I have now uploaded the complete rules Saaguan.com "Complete rules".
    See 27. "Effects while moving"
    and 28. "Advantage".

    In your example, as soon as Blue-2 starts to rotate, Red-3 is Unlocked => Blue-7 Locked => Red-6 Unlocked => so poor Blue-2 is Locked before it has completed its rotation!
    Andrew

    ReplyDelete
  2. Oh and don't forget (like I just did!)...
    1. Robots only rotate 45 degrees on this board (Octaboard = 8 directions);
    2. new Robots can only be added to the "Corridor" of the board.
    Andrew

    ReplyDelete
  3. Hi Andrew! Thanks for the quick fix and pointing out my mistake! I've updated the post with a corrected example to illustrate the original point.

    ReplyDelete
  4. Thanks, Zhen, for going to the trouble to update so quickly. Your analysis is perfect!
    Luckily such complex situations don't arise too often in play!
    Have you played the java applet program yet?
    I suspect you will defeat it :-|
    Andrew

    ReplyDelete
  5. The Java applet kicked my ass a couple of times before I finally beat it by accidentally tricking the yellow bots to make a suicidal move.

    Terrific work, Andrew! How many plys does your applet look ahead? How do you prune the search tree?

    ReplyDelete
  6. I'm afraid I have no real knowledge of game theory! But here goes....
    There is a class* to assess danger (from other players) for all POSITIONS of the board.
    eg Any robot here could be
    - Shutdown in 3 movements,
    - Locked in 5,
    - Threatened in 1..
    etc.

    So, for the active player:
    - assess present danger*.
    Then, for each robot:
    - try all possible 3-movements, noting what happens, and
    - assess danger* then CAUSED to other player(s).

    All these events have +ve or -ve weightings, plus a small random element.

    So I think it only really does 1 ply properly(?)
    Quite a lot of pruning! (or no pruning??)

    ReplyDelete
  7. In a recent game on a standard hexboard, I eliminated all but three yellow bots, at which point the applet kept rotating two remaining bots in the corridor without advancing either of them. I think an additional rule is needed to forbid such idle moves. Any thoughts?

    ReplyDelete
  8. Did that not mean that it was easy to shutdown the one yellow bot in the arena to win the game?
    I hope that this rule is sufficient...
    Rule 29. "Fail to play"
    A player that fails to bring any robot into the arena, for five consecutive turns, shall be considered to have “resigned”!

    In my silly applet, there is just a simple additional weighting inducement to come into the arena!

    ReplyDelete
  9. Ah yes, you're right! Andrew, do you have any plans to create a human-to-human Saaguan platform?

    ReplyDelete
  10. Not really yet. My dream has always been that friends and families could sit together at a table and enjoy playing a real Saaguan board game.
    I only developed the computer program to test it. (Computers being infinitely more patient than humans!)
    Many thanks, Zhen, for your continued interest!

    ReplyDelete