Go 'Suicide'?

[msgreg]

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.

[Bill Spight]

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.

[msgreg]

Bill, your input is awesome. I've continued the thread on Algorithms for User Interface (if anyone wants to follow...)

http://www.lifein19x19.com/forum/viewto ... =18&t=7440

[speedchase]

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.

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.

[msgreg]

Thank you speedchase! I've moved my response to this thread so we don't pollute this Go Suicide thread with computer algorithm conversation.

[Tommie]

OK, thank you Herman, speedchase and hyperpape,
I should have read the thread before.

Especially my suggestion NOT to have a rule on suicide
- no matter how economical the ruleset might be -
cannot prevent the need for discussing suicide when it might occur.

BTW, below is a problem within context:

$$c
$$ +---------------------------------------+
$$ | X X O . X O O . X . . . . . . . . . . |
$$ | X . O . X X O . X . O . . . . . . . . |
$$ | O O O X . X O . X . O . . . . . . . . |
$$ | X X X X X X O O X X O . . . . , . . . |
$$ | . . O O O O . O . . O . . . . . . . . |
$$ | O O O . X O O O X X O . . . . . . . . |
$$ | O X O . X X X X X O . . . . . . . . . |
$$ | X X X X X . . . O O . . . . . . . . . |
$$ | . O . . . O . . . . . . . . . . . . . |
$$ | . . O , O . O . . , . . . . . , . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . , . . . . . , . . . . . , . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ +---------------------------------------+

Click Here To Show Diagram Code

[go]$$c
$$ +---------------------------------------+
$$ | X X O . X O O . X . . . . . . . . . . |
$$ | X . O . X X O . X . O . . . . . . . . |
$$ | O O O X . X O . X . O . . . . . . . . |
$$ | X X X X X X O O X X O . . . . , . . . |
$$ | . . O O O O . O . . O . . . . . . . . |
$$ | O O O . X O O O X X O . . . . . . . . |
$$ | O X O . X X X X X O . . . . . . . . . |
$$ | X X X X X . . . O O . . . . . . . . . |
$$ | . O . . . O . . . . . . . . . . . . . |
$$ | . . O , O . O . . , . . . . . , . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . , . . . . . , . . . . . , . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ +---------------------------------------+[/go]

[Mef]

BTW, below is a problem within context:

Sure, but when the problem description is "Black to check the ruleset and play elsewhere regardless" it loses much of its luster

[Tommie]

BTW, below is a problem within context:

Sure, but when the problem description is "Black to check the ruleset and play elsewhere regardless" it loses much of its luster

I will try to understand:
Are you saying ironically , that, because that sentence was not written there,
i.e. it is not told whose turn it is, the problem is less interesting?

A status problem is more equivalent to a real-game situation, challenging and interesting to me.
The term 'context' was the only hint - indeed with a bat

[HermanHiddema]

BTW, below is a problem within context:

Sure, but when the problem description is "Black to check the ruleset and play elsewhere regardless" it loses much of its luster

I will try to understand:
Are you saying ironically , that, because that sentence was not written there,
i.e. it is not told whose turn it is, the problem is less interesting?

A status problem is more equivalent to a real-game situation, challenging and interesting to me.
The term 'context' was the only hint - indeed with a bat

I think this is what Mef is referring to, specifically the mistake of (see variation there for correct play)



If you play it like that, then the problem indeed comes down to "Black to check the ruleset (to see if suicide is allowed), then to play elsewhere regardless (because you've read it out not to work anyway)".

[Mef]

I think this is what Mef is referring to, specifically the mistake of (see variation there for correct play)

If you play it like that, then the problem indeed comes down to "Black to check the ruleset (to see if suicide is allowed), then to play elsewhere regardless (because you've read it out not to work anyway)".

Actually it's simpler than that, I miscounted the liberties...I was thinking this was one of those positions where B is alive unconditionally with suicide and dead unconditionally without it (hence doesn't play either way). (=

[fogohx]

NZ rules allows it.

[gour]

2. Play stone. Remove any opposing stones without liberties. Remove any of your own stones without liberties. (NewZealandRules)
3. Play stone. Remove any opposing stones without liberties. (DelayedSuicide)
4. Play stone. Remove any stones without liberties (SimultaneousCapture)

The New Zealand style suicide rule is not really simpler than disallowing it. Simpler rules exist, but are not played anywhere.

This, unless you assume that simultaneous capture is default, anti-suicide rules will not be more complex.
And I dont see anything saying we need to change to simultaneous capture here.

Trying to imagine a game with this rule:
5. Play stone. Remove any stones without liberties. If you stone has no liberties, the move was illegal.
so, simultaneous capture without suicide.

EDIT: Found that this already exist, and is called one eyed go ( http://senseis.xmp.net/?OneEyedGo )
Also this variant is 2 in one, Its both simultaneous capture without suicide, and "remove your own pieces if possible and THEN if still possible then capture enemy pieces, suicide is not allowed". Since both variants lead to exact same result.