It is currently Thu Mar 28, 2024 1:18 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 92 posts ]  Go to page Previous  1, 2, 3, 4, 5
Author Message
Offline
 Post subject: Re: Go 'Suicide'?
Post #81 Posted: Sun Dec 16, 2012 7:20 am 
Lives with ko

Posts: 294
Liked others: 47
Was liked: 94
Universal go server handle: MSGreg
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.

_________________
Founder, Central Mississippi Go Club
Free tips and resources for clubs and teaching
Go Kit Club Pack - pack of 13x13 go sets for clubs
Go Tin - very portable go

Top
 Profile  
 
Offline
 Post subject: Re: Go 'Suicide'?
Post #82 Posted: Sun Dec 16, 2012 9:46 am 
Honinbo

Posts: 10905
Liked others: 3651
Was liked: 3374
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. :)

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: Go 'Suicide'?
Post #83 Posted: Sun Dec 16, 2012 10:15 am 
Lives with ko

Posts: 294
Liked others: 47
Was liked: 94
Universal go server handle: MSGreg
Bill, your input is awesome. I've continued the thread on Algorithms for User Interface (if anyone wants to follow...)

viewtopic.php?f=18&t=7440

_________________
Founder, Central Mississippi Go Club
Free tips and resources for clubs and teaching
Go Kit Club Pack - pack of 13x13 go sets for clubs
Go Tin - very portable go

Top
 Profile  
 
Offline
 Post subject: Re: Go 'Suicide'?
Post #84 Posted: Sun Dec 16, 2012 1:43 pm 
Lives in sente

Posts: 800
Liked others: 141
Was liked: 123
Rank: AGA 2kyu
Universal go server handle: speedchase
msgreg wrote:
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.


This post by speedchase was liked by: Bill Spight
Top
 Profile  
 
Offline
 Post subject: Re: Go 'Suicide'?
Post #85 Posted: Sun Dec 16, 2012 5:55 pm 
Lives with ko

Posts: 294
Liked others: 47
Was liked: 94
Universal go server handle: 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.

_________________
Founder, Central Mississippi Go Club
Free tips and resources for clubs and teaching
Go Kit Club Pack - pack of 13x13 go sets for clubs
Go Tin - very portable go

Top
 Profile  
 
Offline
 Post subject: Re: Go 'Suicide'?
Post #86 Posted: Mon Dec 17, 2012 8:52 am 
Dies with sente
User avatar

Posts: 124
Location: still above sea level: http://bit.ly/eQYULx
Liked others: 1
Was liked: 8
Rank: 3d EGF
GD Posts: 1700
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:

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]

_________________
Greetings,
Tommie

3dan EGF (AGA no 13477) || Tommie on KGS: 'June'|| DGS: 'Zhi Laohu' 纸老虎 = 'paper tiger' || Senseis : http://senseis.xmp.net/?tderz ||
ENFP (MBTI) - 'Find your own style within the Fundamentals of Go! '

Top
 Profile  
 
Offline
 Post subject: Re: Go 'Suicide'?
Post #87 Posted: Wed Dec 19, 2012 2:10 am 
Lives in sente

Posts: 852
Location: Central Coast
Liked others: 201
Was liked: 333
Rank: KGS [-]
GD Posts: 428
Tommie wrote:
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

Top
 Profile  
 
Offline
 Post subject: Re: Go 'Suicide'?
Post #88 Posted: Wed Dec 19, 2012 2:39 am 
Dies with sente
User avatar

Posts: 124
Location: still above sea level: http://bit.ly/eQYULx
Liked others: 1
Was liked: 8
Rank: 3d EGF
GD Posts: 1700
Mef wrote:
Tommie wrote:
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


:bow:
I will try to understand:
Are you saying ironically :grumpy: , 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 :)

_________________
Greetings,
Tommie

3dan EGF (AGA no 13477) || Tommie on KGS: 'June'|| DGS: 'Zhi Laohu' 纸老虎 = 'paper tiger' || Senseis : http://senseis.xmp.net/?tderz ||
ENFP (MBTI) - 'Find your own style within the Fundamentals of Go! '

Top
 Profile  
 
Offline
 Post subject: Re: Go 'Suicide'?
Post #89 Posted: Wed Dec 19, 2012 3:02 am 
Gosei
User avatar

Posts: 2011
Location: Groningen, NL
Liked others: 202
Was liked: 1087
Rank: Dutch 4D
GD Posts: 645
Universal go server handle: herminator
Tommie wrote:
Mef wrote:
Tommie wrote:
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


:bow:
I will try to understand:
Are you saying ironically :grumpy: , 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 :b7: (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)".

Top
 Profile  
 
Offline
 Post subject: Re: Go 'Suicide'?
Post #90 Posted: Fri Dec 21, 2012 11:22 am 
Lives in sente

Posts: 852
Location: Central Coast
Liked others: 201
Was liked: 333
Rank: KGS [-]
GD Posts: 428
HermanHiddema wrote:
I think this is what Mef is referring to, specifically the mistake of :b7: (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). (=

Top
 Profile  
 
Offline
 Post subject: Re: Go 'Suicide'?
Post #91 Posted: Wed Jul 31, 2013 10:29 pm 
Beginner

Posts: 1
Liked others: 0
Was liked: 0
NZ rules allows it.

Top
 Profile  
 
Offline
 Post subject: Re: Go 'Suicide'?
Post #92 Posted: Mon Aug 19, 2013 9:46 am 
Beginner

Posts: 11
Liked others: 0
Was liked: 0
HermanHiddema wrote:
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.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 92 posts ]  Go to page Previous  1, 2, 3, 4, 5

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group