Algorithms for User Interface

[msgreg]

Continued from another thread...

Just to add another thing to the discussion.

Today I discovered that there is an algorithm used by computer programs to analyze the status of groups, especially if they are unconditionally alive. It's called Benson's algorithm and one of the necessary conditions is that the ruleset forbid suicides. With suicides the algorithm needs more analyzes and thus more time.

So, with a ruleset that allows suicide, computer programs would have a harder time to find the status of groups.

I've never heard of Benson's algorithm before, but I *just* wrote an algorithm to for playing go that determines when to remove stones. If suicide is allowed, I don't have to keep a memory of "prior to the move". If suicide is allowed, all analysis can occur in the same memory structures used to track the current position.

Algorithm if suicide is allowed
1. Place new stone.
2. Merge Groups attached to new stone.
3. Remove dead groups of opposite color.
4. Remove dead groups of same color.

If suicide is allowed, I have to save off the current state before the analysis.

0. Save current board state
...
5. If current stone has been removed, restore saved state, and indicate invalid move


Now I'm going to look up Benson's algorithm to see if it's the same

Edit: No Benson's Algorithm is not the same, which should have been obvious, given different conclusions on complexity of suicide.

FWIW, you do not have to save the current state. Just don't merge too early.

Any placed stone will be adjacent to at most four strings. Of those strings, remove opponent's strings without liberties. If none of them has been removed, check to see if the placed stone has a liberty. If so merge it with the friendly stones. If not, and any of the adjacent friendly strings has a liberty, merge all of them with the played stone. If none of them has a liberty, remove the placed stone and declare an illegal move.

BTW, when I first wrote a go program, for each string I kept a list for each stone in the string and another list for liberties. Doing so made the question of capture or suicide obvious.

Very good insights, Bill. Thank you!!

In my case, I'm programming for a limited memory device. So I'm trying to reduce the number of size-changing objects such as lists. In my case, I keep an array that is the size of the number of intersections. Each location is a "group number". I also keep a "dead/alive" array indicating which stones are without liberties, regardless of color. This way, a group with all zero-liberty stones is a dead group. A group with any non-zero-liberty stones is an alive group.

Any placed stone will be adjacent to at most four strings. Of those strings, remove opponent's strings without liberties.

This is the statement that's difficult to implement given my data structures. In reality, I think this should read "...remove opponent's strings without liberties (except for the newly placed stone)".

I had thought of "pre-emptive" determination of live/dead groups, but I already had whole-board algorithms that implemented some of the functions I needed to track groups and determine life/death of groups that were fully specified within the data structures.

I'll have to rethink to see if I can implement your algorithm with static arrays rather than dynamic lists.

[Bill Spight]

Continued from another thread...

FWIW, you do not have to save the current state. Just don't merge too early.

Any placed stone will be adjacent to at most four strings. Of those strings, remove opponent's strings without liberties. If none of them has been removed, check to see if the placed stone has a liberty. If so merge it with the friendly stones. If not, and any of the adjacent friendly strings has a liberty, merge all of them with the played stone. If none of them has a liberty, remove the placed stone and declare an illegal move.

BTW, when I first wrote a go program, for each string I kept a list for each stone in the string and another list for liberties. Doing so made the question of capture or suicide obvious.

Very good insights, Bill. Thank you!!

In my case, I'm programming for a limited memory device. So I'm trying to reduce the number of size-changing objects such as lists.

Well, that program was written in Smalltalk, so there you go. Forth, anyone? (Forth, Yoda likes. )

Anyway, I was using the philosophy of designing data structures to make the algorithms easy. I doubt if the algorithm I used is suitable for your situation. Have you tried the computer go mailing list?

I'll have to rethink to see if I can implement your algorithm with static arrays rather than dynamic lists.

I think that bitmaps are popular.

[EdLee]

Forth, anyone? (Forth, Yoda likes. )

I seem to remember back in college, a friend tried to write Othello in Forth.

[msgreg]

Algorithm if suicide is allowed
1. Place new stone.
2. Merge Groups attached to new stone.
3. Remove dead groups of opposite color.
4. Remove dead groups of same color.

If suicide is allowed, I have to save off the current state before the analysis.

0. Save current board state
...
5. If current stone has been removed, restore saved state, and indicate invalid move

you don't actually need to remember the prior board state. If anything is removed in step four, then the move is invalid.

The issue for me was that because of the particular data structures I've chosen (static "bitmap" vs. dynamic list), I can't determine if anything is removed (or, more precisely, group membership) until after I merge the groups.

Ps. if you are trying to find the computationally simplest (processor time) method of resolving the board after a move, you only have to check the oppositely colored stones immediately adjacent to the stone you placed during step 3, and you only have to check the stone that was played for your color.

The particular phrase here is "only have to check to oppositely colored stones...". I'm not sure what it is that I am checking. If it is "group liberties", then I may be able to do that in one pass of the group membership array (checking each stone for its group membership, then determine if any group member's liberties, excluding the new stone's location).

Also, I'm not sure what "check the stone that was played for your color" means.

PPs. during my time trying to program a Go AI (that was a horrible failure in case you are curious), I thought rules permitting suicide would have been simpler, but that is just me.

I agree that permitting suicide is easier computationally and from the standpoint of memory usage.

Hmmm... I hope I'm not contradicting what I wrote above, but it sounds like a decent algorithm is
1. Determine if any opposite color attached groups (up to 4) have zero liberties, not counting the new stone position as a liberty. Remove any found groups with zero liberties.
2. If any groups were removed, it is a valid move.
3. If no groups are removed in step 2, determine if any attached groups (up to 4) of the same color have any liberties, not counting the new stone position as a liberty.
4. If step 3 contains no liberties and suicide is permitted, remove all attached groups of the same color, including the new stone.
5. If step 3 contains no liberties and suicide is not permitted, it is an invalid move.
6. If neither 4 or 5 are invoked, then place stone and merge groups.

This does not cover Simultaneous Capture and does not cover Delayed Suicide as mentioned here.

Based on my data structures, checking 4 attached groups would require 4 passes through the group membership array, checking liberties on each stone in each group. This is kind of expensive on the hardware I'm using. I'll have to think about a different data structure that might meet all the requirements (small size, static, etc).

On another note: I understand Simultaneous Capture and Delayed Suicide are potential logical extensions of suicide, but are either of them used in any actual rulesets?

[speedchase]

Algorithm if suicide is allowed
1. Place new stone.
2. Merge Groups attached to new stone.
3. Remove dead groups of opposite color.
4. Remove dead groups of same color.

If suicide is allowed, I have to save off the current state before the analysis.

0. Save current board state
...
5. If current stone has been removed, restore saved state, and indicate invalid move

you don't actually need to remember the prior board state. If anything is removed in step four, then the move is invalid.

The issue for me was that because of the particular data structures I've chosen (static "bitmap" vs. dynamic list), I can't determine if anything is removed (or, more precisely, group membership) until after I merge the groups.

Ps. if you are trying to find the computationally simplest (processor time) method of resolving the board after a move, you only have to check the oppositely colored stones immediately adjacent to the stone you placed during step 3, and you only have to check the stone that was played for your color.

The particular phrase here is "only have to check to oppositely colored stones...". I'm not sure what it is that I am checking. If it is "group liberties", then I may be able to do that in one pass of the group membership array (checking each stone for its group membership, then determine if any group member's liberties, excluding the new stone's location).

Also, I'm not sure what "check the stone that was played for your color" means.

PPs. during my time trying to program a Go AI (that was a horrible failure in case you are curious), I thought rules permitting suicide would have been simpler, but that is just me.

I agree that permitting suicide is easier computationally and from the standpoint of memory usage.

Hmmm... I hope I'm not contradicting what I wrote above, but it sounds like a decent algorithm is
1. Determine if any opposite color attached groups (up to 4) have zero liberties, not counting the new stone position as a liberty. Remove any found groups with zero liberties.
2. If any groups were removed, it is a valid move.
3. If no groups are removed in step 2, determine if any attached groups (up to 4) of the same color have any liberties, not counting the new stone position as a liberty.
4. If step 3 contains no liberties and suicide is permitted, remove all attached groups of the same color, including the new stone.
5. If step 3 contains no liberties and suicide is not permitted, it is an invalid move.
6. If neither 4 or 5 are invoked, then place stone and merge groups.

This does not cover Simultaneous Capture and does not cover Delayed Suicide as mentioned here.

Based on my data structures, checking 4 attached groups would require 4 passes through the group membership array, checking liberties on each stone in each group. This is kind of expensive on the hardware I'm using. I'll have to think about a different data structure that might meet all the requirements (small size, static, etc).

On another note: I understand Simultaneous Capture and Delayed Suicide are potential logical extensions of suicide, but are either of them used in any actual rulesets?

technically your algorithm fails to account for the possibility that the placed stone has liberties, but the stones it is attached to don't (besides the ones that were gained by placing the new stone), but other that that is seems reasonable.

[daniel_the_smith]

You don't have to actually connect any groups, you just need to check that at least one of them has a liberty other than the point you're checking.

$$W White to move
$$ ------------+
$$ . . . X O X |
$$ . . . X a X |
$$ . . . X O X |
$$ . . , X O X |
$$ . . . . X . |
$$ . . . . . . |
$$ . . . . . . |
$$ . . . . . . |

Click Here To Show Diagram Code

[go]$$W White to move
$$ ------------+
$$ . . . X O X |
$$ . . . X a X |
$$ . . . X O X |
$$ . . , X O X |
$$ . . . . X . |
$$ . . . . . . |
$$ . . . . . . |
$$ . . . . . . |[/go]

1. Does the move have an empty adjacent point? If yes: legal.
2. Are there any adjacent enemy groups that this captures? If yes: legal.
3. Are there any adjacent friendly groups with at least one liberty other than this one? If yes: legal.
4. Else, suicide.

Ko complicates things considerably. I keep an array of zobrist hashes for detecting this. I can construct a hypothetical zobrist hash without changing my board structures in memory.

[msgreg]

This is great. Hopefully this will serve as a thread for others to reference when getting into go/game programming.

I like your simplified description of the algorithm. I had to look up "zobrist hash" which led to a few great websites on game programming. The clearest explanation of a zobrist hash is in the gnugo documentation. It appears to be good for recognizing "this is the same position as a previous position" by comparing a current hash against a set of previous hashes, but it is not for explicitly saving a position.

The next area that I am a little stuck on is calculating end score. Note that I am not trying to create game playing code, only code that can calculate the score as automatically as possible. I realize that this may include some notion of playing out to determine dead stones. Any pointers?

[daniel_the_smith]

The next area that I am a little stuck on is calculating end score. Note that I am not trying to create game playing code, only code that can calculate the score as automatically as possible. I realize that this may include some notion of playing out to determine dead stones. Any pointers?

This is not easy at all, in fact I'm not sure if it's really feasible without some "game playing code". I have code that could do it, though-- a while ago I was considering putting it up on a google app engine site where it could be called as a service by other applications. Is that something you could use for your application?

[msgreg]

For project 1, yes, it is an internet-connected device and I can easily call a service (http easily, tcp if necessary). For project number 2, it is a self contained, non-computer device and only occasionally connected. For project 2, I might have to require the user to remove dead stones. If dead stones are removed manually, I'm hoping the score calculation is much easier.

I think that leaves identifying alive vs. seki. This is probably the first step for both coding projects.

[daniel_the_smith]

For project 1, yes, it is an internet-connected device and I can easily call a service (http easily, tcp if necessary). For project number 2, it is a self contained, non-computer device and only occasionally connected. For project 2, I might have to require the user to remove dead stones. If dead stones are removed manually, I'm hoping the score calculation is much easier.

I think that leaves identifying alive vs. seki. This is probably the first step for both coding projects.

Give it a shot:

http://daily-joseki.appspot.com/score

Interface should be easy, just view source for an example. JSON in, JSON out. Use the developer tools in chrome if you want to see *exactly* what goes over the wire. It's a little slow, I'm not sure what google is running it on, it runs instantly locally. I didn't spend any time robustifying it, if you send an invalid board it will not be happy. It accepts boards of any reasonable size.

This uses ~50 playouts of a very, very stupid nature, so it's kind of astonishing that it works at all. You can use it to score or to automatically suggest dead stones, or both.

[daniel_the_smith]

From the server logs a bit ago:

panic: Need same number of lines as characters!

and

panic: runtime error: index out of range

Yeah, this is super robust code...

It's going to be very picky about having only the characters "X", "O", ".", and "\n" in the input string, and the number of lines must equal the number of characters in each line. I just hooked up a function that I was using to parse ascii boards in some test code, so it didn't have to be robust.

OK, I'm going to make it a bit nicer.

[msgreg]

Thanks, I've been pinging it this evening. I have to hand construct my http request into a JSON request and I'm not sure I have all the headers correct.

Or the data, for that matter. It took me a while to notice that "\n" in the input strings are literally those two characters (usually, that's a shorthand for ASCII character code 10). Then I noticed a space before the last \n.

Then I tried a lot of combinations, and never got it to give me anything besides either the original HTML or code 500.

Submitting the form from a browser works fine.

Will try again after a bit after you have a chance to modify it...

[daniel_the_smith]

Thanks, I've been pinging it this evening. I have to hand construct my http request into a JSON request and I'm not sure I have all the headers correct.

Or the data, for that matter. It took me a while to notice that "\n" in the input strings are literally those two characters (usually, that's a shorthand for ASCII character code 10). Then I noticed a space before the last \n.

Then I tried a lot of combinations, and never got it to give me anything besides either the original HTML or code 500.

Submitting the form from a browser works fine.

Will try again after a bit after you have a chance to modify it...

OK, give it another shot. It should give back a meaningful error now at least. ({Error: "blah"})

The \n actually needs to be a 0x0A newline character by the time it gets to my code, but in json representation it might literally be a \n, I'm not sure. You may need to do the http url encoding after the json encoding (You know, the %020 thing you see if you put a space in a URL). The space at the end was unintentional, hehe.

[msgreg]

Error messages helped a lot. I'm getting a result back. I need to fix my parsing. Will have a screenshot hopefully shortly...

[msgreg]

Haven't reviewed the accuracy of the scoring, but I'm getting and displaying results.

Scoring example using daniel_the_smith's web service and msgreg UI program

ScoreExample9x9.jpg (53.79 KiB) Viewed 13968 times