See Benson's algorithm and related discussion on SL.
http://senseis.xmp.net/?BensonsDefiniti ... tionalLife
| Life In 19x19 http://www.lifein19x19.com/ |
|
| Mathematical definition of âunconditionally alive groupâ http://www.lifein19x19.com/viewtopic.php?f=10&t=11503 |
Page 1 of 1 |
| Author: | Alcadeias [ Sat Feb 21, 2015 2:43 am ] |
| Post subject: | Mathematical definition of âunconditionally alive groupâ |
Hello. I have tried to formalize a simple mathematical definition of the term “unconditionally alive group”, as well as of the terms “eye”, “false eye” and “real eye”. An unconditionally alive group is a group such that if the player of the same color as the group passes for an infinite number of moves then whatever sequence of moves the player of the opposing color plays he will never be able to capture the group. It took me a few hours, and I’m not even totally sure if my definitions are flawless, but here’s what I’ve made up: - String: A string is a set of stones of the same color which are connected together, and such that each stone composing the string is not connected to a stone not composing the string. - Group: A group is a set of strings of the same color which are linked together by eyes. - Eye: An eye is an empty point surronded by stones of only one color. - False eye: A false eye is an eye in which at least one of the chain adjacent to the eye is adjacent to no other eye that is not a false eye. - Real eye: A real eye is an eye for which each of the adjacent stones is part of a string which is adjacent to at least one other real eye. - Unconditionally alive group: An unconditionally alive group is a group such that each string composing the group is adjacent to at least two real eyes. Basically, here’s the algorithm to distinguish betwen real eyes and false eyes: UE = { e1, e2, e3, ... } is the set of unidentified/unclassified eyes (eyes for which we don’t know yet if they are false eyes or real eyes). FE is the set of false eyes (it’s empty at the start). RE is the set of real eyes (it’s also empty at the start). Run through each eye in UE. If, for one eye ‘e’ in UE, at least one of the chain adjacent to the eye ‘e’ is adjacent to no other eye in UE, then the eye ‘e’ is removed from UE and put into FE. If you’ve modified UE in the last iteration, then do another iteration. Once you’ve made an iteration without modifying UE, stop the loop, and move all remaining elements of UE to RE. Are my definitions really perfectly correct? Do you see some counter-examples? If my definitions have some flaws, how could we improve them? And how could we generalize my definitions so that they take into account eye-spaces instead of just one-point eyes? Thanks in advance for your answers. |
|
| Author: | RobertJasiek [ Sat Feb 21, 2015 3:31 am ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
Usually, "unconditionally alive" is associated with "independently alive". See http://home.snafu.de/jasiek/j2003.html http://home.snafu.de/jasiek/wagcmod.html http://senseis.xmp.net/?FormalDefinitionsOfEye#toc2 What you call "unconditionally alive" is called "pass-alive" or has other names. An infinite number of passes is possible only under rulesets allowing infinite sequences; this is not so for every ruleset. "Capture" should be defined. It is easier to speak of "removal". "will never be able to" is ambiguous. In order to remove the ambiguity, use definitions of hypothetical-sequence, hypothetical-strategy and force. Your "string" definition is not a definition but ambiguous. In particular, you need to define "connected". Your "eye" is a hopeless failure. See the above links for the solution. It follows that your "false eye", "real eye" and "algorithm to distinguish betwen real eyes and false eyes" are hopeless failures. Your "Unconditionally alive group" is ambiguous because it does not contain a maximal-set-condition. Instead of "group" you should speak with greater clarity of "set of strings of the same player". Remove the flaws from your definitions by applying the techniques and definitions of my solution. For the definition of "eye-space", see the links above for my solution. |
|
| Author: | Bill Spight [ Sat Feb 21, 2015 4:56 am ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
See Benson's algorithm and related discussion on SL. http://senseis.xmp.net/?BensonsDefiniti ... tionalLife |
|
| Author: | oca [ Sat Feb 21, 2015 6:48 am ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
Alcadeias wrote: An unconditionally alive group is a group such that if the player of the same color as the group passes for an infinite number of moves then whatever sequence of moves the player of the opposing color plays he will never be able to capture the group. What about seki ? I mean, you cannot pass if your opponent played there... or has seki its own category and are not considered as an "unconditionally alive group" ? |
|
| Author: | Mike Novack [ Sat Feb 21, 2015 8:50 am ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
oca wrote: What about seki ? I mean, you cannot pass if your opponent played there... or has seki its own category and are not considered as an "unconditionally alive group" ? No, seki is not a state of being unconditionally alive. Seki is a state of being conditionally alive. That's the point, the group will die if the opponent's move is not responded to. But what if that move were a ko threat? And the ko worth more than the group? |
|
| Author: | Bill Spight [ Sat Feb 21, 2015 10:58 am ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
Also see http://senseis.xmp.net/?TopologicalLife
|
|
| Author: | tiger314 [ Sun Feb 22, 2015 3:29 pm ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
Robert, just out of curiosity, what would you say about a definition of unconditionally alive (or pass alive as you call it) which would look like this (slightly altered first post defenition): Assuming the AGA rules of Go are in use. An unconditionally alive stone is a stone such that if the player of the same color as the stone passes for an infinite number of moves then whatever sequence of moves the player of the opposing color plays he will never be able to capture the stone. While the eye was totally hopeless, this looks good if you are looking for a self standing definition (only the ruleset has to be defined). Capture is now defined and the only remaining issue is the "will never be able to". Yes, it probably not the ideal formulation, but "be able to" is clear enough: a situation which allows someone or something to execute an action. "never" makes the meaning opposite. "will" means that this happens after everything described in present tense has taken place. Where are the remaining flaws? |
|
| Author: | RobertJasiek [ Sun Feb 22, 2015 3:44 pm ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
tiger314 wrote: Assuming the AGA rules of Go are in use. [...] passes for an infinite number of moves ALA you do not get the basic requirements for a definition right, I do not read your whole attempt. Definitions do not have any contradiction. An infinite number of moves contradicts the AGA rules. Furthermore, definitions rely on axioms, are unequivocal and are well-defined. |
|
| Author: | tiger314 [ Sun Feb 22, 2015 3:47 pm ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
Could you quote the rule that forbids playing an infinite amount of moves? |
|
| Author: | RobertJasiek [ Sun Feb 22, 2015 10:09 pm ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
tiger314 wrote: Could you quote the rule that forbids playing an infinite amount of moves? http://www.cs.cmu.edu/~wjh/go/rules/AGA.html "It is illegal to play in such a way as to recreate a previous board position from the game, with the same player to play." Superko. It makes any game finite because the number of board positions is finite. (And other rules specify the game end by two or three successive passes so that infinite successions of passes by both players are also prohibited.) |
|
| Author: | tiger314 [ Sun Feb 22, 2015 11:11 pm ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
OK and how about J89 and replacing 'capture' with 'remove' (due to the different wording of the rules). With AGA a pass is always legal, but you are right that the opponent will eventually run out of moves, so a light rewording of "infinite number of moves" to "every move" would be nessesary. |
|
| Author: | leichtloeslich [ Mon Feb 23, 2015 2:48 am ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
Whether or not infinite move sequences are allowed is completely besides the point, the definition for pass-alive is completely trivial either way. The given definitions for false/real eyes are very messy and imho contradictory. I assume this is because English isn't the OP's native tongue. The algorithm is clear enough however, but works backwards from a pass-alive group. Therefore, the algorithm will classify all eyes in the following diagram as false: |
|
| Author: | peti29 [ Mon Feb 23, 2015 6:09 am ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
I don't get the need for a definition of "absolutely unconditionally alive". E.g.: a solid two-eyed group is unconditionally alive, but that's not a rule. That's a consequence of the rules. If you want to program a score estimator then you'll need a more permissive definition for alive groups, e.g.: those groups that can not be killed assuming that the owner responds to direct threats should be considered alive. a) those may still end up dying (e.g.: in case of a KO threat) b) deciding what is a direct threat is not always easy Idea: if I just had access to Tygem's score estimator source code, I think I could learn a lot about GO by studying it (assuming it's not some iterative AI-based madness). |
|
| Author: | Bill Spight [ Mon Feb 23, 2015 8:56 am ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
peti29 wrote: I don't get the need for a definition of "absolutely unconditionally alive". E.g.: a solid two-eyed group is unconditionally alive, but that's not a rule. That's a consequence of the rules. If there were no such groups, there would be no go. You do not need such a definition to play the game, but people with a theoretical or mathematical bent like to come up with them. |
|
| Author: | Bill Spight [ Mon Feb 23, 2015 8:58 am ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
tiger314 wrote: Could you quote the rule that forbids playing an infinite amount of moves? A player who dies forfeits the game. |
|
| Author: | tiger314 [ Mon Feb 23, 2015 10:45 am ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
Bill Spight wrote: peti29 wrote: I don't get the need for a definition of "absolutely unconditionally alive". E.g.: a solid two-eyed group is unconditionally alive, but that's not a rule. That's a consequence of the rules. If there were no such groups, there would be no go. You do not need such a definition to play the game, but people with a theoretical or mathematical bent like to come up with them. Pretty much the only moment when definitions of this sort start becoming relevant to the game is when there is a dispute about group status under Japanese rules. Since a playout cannot be used to settle the dispute, it is nessesary to distinguish live groups through a rule of some sort. |
|
| Author: | Bill Spight [ Mon Feb 23, 2015 11:51 am ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
tiger314 wrote: Bill Spight wrote: peti29 wrote: I don't get the need for a definition of "absolutely unconditionally alive". E.g.: a solid two-eyed group is unconditionally alive, but that's not a rule. That's a consequence of the rules. If there were no such groups, there would be no go. You do not need such a definition to play the game, but people with a theoretical or mathematical bent like to come up with them. Pretty much the only moment when definitions of this sort start becoming relevant to the game is when there is a dispute about group status under Japanese rules. Since a playout cannot be used to settle the dispute, it is nessesary to distinguish live groups through a rule of some sort. The Japanese 1989 rules settle life and death disputes, of which I am unaware of any in pro play in modern times, by play. It is just hypothetical play with special rules. (Not that I like the J89 rules, but they do not rely upon definitions of unconditionally live groups or any such.) |
|
| Author: | tiger314 [ Mon Feb 23, 2015 12:44 pm ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
Looking through the J89 rules (Davies' translation), it seems that there is no playout, but an investigation of all possible sequences according to special (ko) rules. Could you point me to the playout paragraph of the rules? I found this in the commentary, but I am not sure how to interpret it: Quote: A player does not have to remove opposing dead stones from his territory
by occupying all their liberties as in Article 5. He can remove them as is, without making further moves. |
|
| Author: | RobertJasiek [ Mon Feb 23, 2015 2:25 pm ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
Japanese 1989 Rules interpretation: http://home.snafu.de/jasiek/j1989c.html http://home.snafu.de/jasiek/j2003.html http://home.snafu.de/jasiek/j2003com.html |
|
| Author: | Bill Spight [ Mon Feb 23, 2015 2:59 pm ] |
| Post subject: | Re: Mathematical definition of âunconditionally alive groupâ |
tiger314 wrote: Looking through the J89 rules (Davies' translation), it seems that there is no playout, but an investigation of all possible sequences according to special (ko) rules. Could you point me to the playout paragraph of the rules? I found this in the commentary, but I am not sure how to interpret it: Quote: A player does not have to remove opposing dead stones from his territory by occupying all their liberties as in Article 5. He can remove them as is, without making further moves. The J89 rules make use of hypothetical play, but the principle that life and death are decided by play is the basis of it. Some territory rules, such as Ikeda's, Lasker-Maas rules, and Spight rules, have an explicit encore with actual playout. However, such rules do not necessarily produce the same results as those desired by the Japanese rules makers. |
|
| Page 1 of 1 | All times are UTC - 8 hours [ DST ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|