Life In 19x19 :: Algorithms for User Interface

msgreg wrote:

Samura wrote:

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. :ugeek:

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.

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

Continued from another thread...

Bill Spight wrote:

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

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.

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

Forth, anyone? (Forth, Yoda likes. :mrgreen:

)

msgreg wrote:

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.

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.

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.

speedchase wrote:

msgreg wrote:

speedchase wrote:

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.

speedchase wrote:

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.

speedchase wrote:

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?

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?

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.

panic: Need same number of lines as characters!

panic: runtime error: index out of range

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...

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

Author:	msgreg [ Sun Dec 16, 2012 10:13 am ]
Post subject:	Algorithms for User Interface
Continued from another thread... Bill Spight wrote: msgreg wrote: Samura wrote: 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. Quote: 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.

Author:	Bill Spight [ Sun Dec 16, 2012 11:00 am ]
Post subject:	Re: Algorithms for User Interface
msgreg wrote: Continued from another thread... Bill Spight wrote: 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? Quote: 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.

Author:	EdLee [ Sun Dec 16, 2012 1:10 pm ]
Post subject:
Bill Spight wrote: Forth, anyone? (Forth, Yoda likes. ) I seem to remember back in college, a friend tried to write Othello in Forth.

Author:	msgreg [ Sun Dec 16, 2012 5:52 pm ]
Post subject:	Re: Algorithms for User Interface
speedchase wrote: msgreg wrote: 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 speedchase wrote: 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. speedchase wrote: 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. speedchase wrote: 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?

Author:	speedchase [ Sun Dec 16, 2012 6:53 pm ]
Post subject:	Re: Algorithms for User Interface
msgreg wrote: speedchase wrote: msgreg wrote: 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 speedchase wrote: 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. speedchase wrote: 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. speedchase wrote: 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.

Life In 19x19 http://prod.lifein19x19.com/

Algorithms for User Interface http://prod.lifein19x19.com/viewtopic.php?f=18&t=7440	Page 1 of 2

Author:	daniel_the_smith [ Mon Dec 17, 2012 9:06 pm ]
Post subject:	Re: Algorithms for User Interface
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. 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.

Author:	msgreg [ Tue Dec 18, 2012 8:14 am ]
Post subject:	Re: Algorithms for User Interface
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?

Author:	daniel_the_smith [ Tue Dec 18, 2012 11:45 am ]
Post subject:	Re: Algorithms for User Interface
msgreg wrote: 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?

Author:	msgreg [ Tue Dec 18, 2012 12:07 pm ]
Post subject:	Re: Algorithms for User Interface
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.

Author:	daniel_the_smith [ Wed Dec 19, 2012 8:37 pm ]
Post subject:	Re: Algorithms for User Interface
From the server logs a bit ago: Quote: panic: Need same number of lines as characters! and Quote: 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.

Author:	msgreg [ Wed Dec 19, 2012 8:45 pm ]
Post subject:	Re: Algorithms for User Interface
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...

Author:	msgreg [ Wed Dec 19, 2012 9:31 pm ]
Post subject:	Re: Algorithms for User Interface
Error messages helped a lot. I'm getting a result back. I need to fix my parsing. Will have a screenshot hopefully shortly...

Author:	msgreg [ Wed Dec 19, 2012 10:03 pm ]
Post subject:	Re: Algorithms for User Interface
Haven't reviewed the accuracy of the scoring, but I'm getting and displaying results. Attachment: File comment: Scoring example using daniel_the_smith's web service and msgreg UI program ScoreExample9x9.jpg [ 53.79 KiB \| Viewed 13859 times ]

Author:	daniel_the_smith [ Thu Dec 20, 2012 6:16 am ]
Post subject:	Re: Algorithms for User Interface
msgreg wrote: Haven't reviewed the accuracy of the scoring, but I'm getting and displaying results. Nice! I didn't check the final number it gives, either-- it should be implementing AGA (area) rules. Of course, you can always just use it to mark the dead stones and do the addition manually.

Author:	daniel_the_smith [ Mon Feb 04, 2013 9:56 am ]
Post subject:	Re: Algorithms for User Interface
Since I'm between jobs for the week, I added some features to this, including the ability to take in SGF and set the number of playouts it uses (see the "iterations" parameter). It remains backwards compatible. Enjoy. http://daily-joseki.appspot.com/score

Author:	daniel_the_smith [ Mon Feb 04, 2013 12:19 pm ]
Post subject:	Re: Algorithms for User Interface
It will pay attention to SZ, KM, B, W, AB, AW, and AE. SZ is required, KM is required if you want it to take komi into consideration. It plays through the first branch at every node and ignores everything else. Results are exactly the same as before (json), no change there! If the game is already finished, I'd leave the iterations parameter low, and you should still get consistent answers. Otherwise, set it high and don't expect quick or consistent results! I recommend playing around and seeing what the best balance of speed/accuracy is for your application. Also, I just made the demo page much prettier (maybe you already saw the pretty version, depending on when you looked).

Page 1 of 2	All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/

Author:	msgreg [ Mon Feb 04, 2013 10:19 am ]
Post subject:	Re: Algorithms for User Interface
Interesting. Do you have a recommended range for the iterations? (perhaps based on the board size and or number of unfilled stones, or other aspect)? And what are the minimum required SGF tags? (i.e. are both B and AB recognized?) How about KM, and are results returned in JSON or SGF? And especially, thank you for the backward compatibility!

Author:	cyclops [ Mon Aug 19, 2013 11:39 am ]
Post subject:	Re: Algorithms for User Interface
daniel_the_smith wrote: Give it a shot: http://daily-joseki.appspot.com/score Hi Daniel. I was sort of disappointed that your tool seems to give random scores for the same position. Are you still developing it?