Scoring Senket is Hard

Not for humans, really. Just shade in the territories and do some math. For a computer, scoring is hard. At least it is for the computer I’m working with ;-).

Look at all the pretty colored posts!

Look at all the pretty colored posts!

I’m now at the point where my code can reliably detect territories and identify all the posts within them. An example is shown to the right. If I were doing post scoring, I’d be done.

Now I have to take what I have and translate it into visibly shading those territories, and reporting the (area-based) score. Shouldn’t be too hard, should it? (famous last words)

Here’s the algorithm I’m using (roughly):

  1. Create an array C of the colored posts.
  2. Strip from C all posts that are attached to only one other post.
  3. Repeat 2 until the list stops changing. This leaves only loops (potential territories). Note that the edges of the board count as one connection, so a lone post there will go away, but a post connected to any other post won’t.
  4. Create an array N of all the intersections, identifying their eight neighbors orthogonally and diagonally.
  5. Iterate through all the fences and remove from N the neighbors that the fences cut off. So 1,1 and 2,2 start off as a neighbors, but the fence from 2,1 to 1,3 separates them.
  6. For each post in C, split the entry in N and create one separate entry for each set of neighbors separated by the fences attached to the post. So for example, the red post at 2,1 in the diagram above would have two sets of neighbors: 1,1 and 2,2; 3,1. The red post at 9,7 would have three sets of neighbors: 8,8 and 9,8; 10,8; 10,7 and 10,6; 9,6; 8,6; 8,7. At the same time, split the entry in C as well, giving each new entry the same color as the original.
  7. Now go through C and color each post’s neighbors:
    1. If the neighbor is empty, give it C’s color.
    2. If C is gray (no one’s territory) then color the neighbor gray.
    3. If the neighbor is gray, color C gray.
    4. If C and the neighbor are different colors (not gray) then make both gray.
  8. Repeat 7 until the board stops changing.

I had originally thought to identify loops and then figure out which loops were in other loops, invalidating them. That was tough. I did manage to re-use some of the code for identifying loops in step 2 above. Before I added that step, a lone red post inside a blue territory would invalidate the blue territory.

When I started on this algorithm I only used the four orthogonal neighbors, which failed with territories like the large blue one above — the empty space within it that isn’t blue territory can’t be reached from the outside using only orthogonal connections.

My first attempts at this algorithm didn’t include step 6, and therefore tried to make posts unchangeable while leaving the intersections around them free to be updated. That didn’t work because of trying to identify the appropriate neighbors to change.

In all I’d say this is one of the hardest algorithms to get right that I’ve coded. I’m thinking about submitting it to Project Euler to see if they’d be interested in putting it up.

Advertisements

3 thoughts on “Scoring Senket is Hard

  1. Herman Hiddema

    One possible problem with this algorithm, I think, is that it will automatically assume strings of posts that are connected to two edges to be alive, right?

    For example, if you remove the red post at 8-9, then the red group there surrounds no more territory, and would (without additional posts) be dead inside a very large blue area, correct?

    Similarly, if you remove the blue post at 9-9, then that blue group would be dead inside a larger red area, right?

    But in both cases, the repetition of step 2 will not remove these posts.

    Is there actually any definition if the rules for what happens when both are removed? If you remove red 8-9 and blue 9-9, and add enough fences so that neither of them can surround any territory, what is their status at the end? Both alive? Both dead?

    Tricky stuff 🙂

    Oh, and for area calculation, have a look at: http://www.efg2.com/Lab/Graphics/PolygonArea.htm

    Reply
    1. gcanyon Post author

      EDIT: I see what you’re getting at. I added a post about this. I think you’ve found Senket’s seki rule. 😦 I wanted the rules of Senket to be simpler than Go’s, but now there’s a situation (extremely unlikely, I think) where the rules don’t make clear how to score the board. I’m thinking about it.

      Removing the post at 8-9 wouldn’t result in those posts being prisoners because they’re not separated from the 1 square red territory in the lower left. This principal is demonstrated at the end of https://gcanyon.wordpress.com/2009/04/10/senket-a-complex-problem/ where a chain of posts doesn’t make territory inside, but can’t be separated from a territory outside, and so doesn’t become prisoners.

      Of course if the above board were a real game, neither side would pass. If 8-9 went away and blue got one more play, he would connect from 2-3 to 1-5, cutting off the 1 square territory, and taking almost the whole board.

      Removing blue 9-9 (and preventing him from doing anything else there) would indeed make him into prisoners, because of the 1 square red territory in the upper right. Since Red built territory inside Blue’s, Blue can’t simply claim the corner.

      This isn’t really affected by steps 2 and 3 in the algorithm. From the standpoint of coloring the board, they’re unnecessary. In fact I now think they’re not necessary at all.

      To score the game (once I’ve identified valid territories, which I have now) I need to do a couple things:

      1. Make a list of all the independent territories (territories that are not in any way connected).
      2. For each of those territories, figure out the total area of it and the prisoners within it.
      3. Square the sums from 2, and add them together.

      I already have an algorithm that will take an arbitrary loop of posts and determine the area of it. I’m going to write a post about it somewhere along the way, because just that was an interesting challenge, and I like the solution I came up with. But the algorithm won’t handle stray strands coming off the loops, either dead ends, which 2 and 3 remove, or single strands connecting two loops. I think I have an algorithm in mind that will take a set of connected loops and get rid of all the connections, leaving just the loops, but it would also strip the dead ends as well, so again I don’t think 2 and 3 are necessary at this point.

      There have been more than a few dead ends in figuring out how to show a machine how to score this game.

      Reply
  2. Pingback: Scoring Senket is Hard, pt. II « Geoff Canyon’s Appeal to Authority

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s