Re: Superko vs transposition table (was Re: [computer-go] Double/Triple Ko situation)
I fixed allowing multiple suicide in playouts, but it didn't make the many wasted playouts go away on Sheppard's position. On further investivation, the problem has to do with the interaction between superko and the transposition table. Currently, Orego checks only simple ko most of the time. Superko is only checked at the top level, before playing a real move (as opposed to a move in a playout). This means that, within the transposition table, superko can lead to an actual cycle. Orego does have a max number of moves per playout, so it doesn't crash, but it does throw away such playouts. What is superko? My program keeps a list of all board-positions and then if it whants to do a move it checks if the new board-position is in the list. If so, it throws that move away. Are there other checks I need to do as well? Folkert van Heusden -- Feeling generous? - http://www.vanheusden.com/wishlist.php -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Superko vs transposition table (was Re: [computer-go] Double/Triple Ko situation)
In message 20090807092625.gj15...@vanheusden.com, Folkert van Heusden folk...@vanheusden.com writes What is superko? My program keeps a list of all board-positions and then if it whants to do a move it checks if the new board-position is in the list. If so, it throws that move away. Are there other checks I need to do as well? Superko involves repeating a previous board position. Various forms of this are forbidden by various rulesets, see http://www.britgo.org/rules/compare.html#threeKK What you are doing ensures that your program will never violate any form of the rule. Nick -- Nick Weddn...@maproom.co.uk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Superko vs transposition table (was Re: [computer-go] Double/Triple Ko situation)
What is superko? My program keeps a list of all board-positions and then if it whants to do a move it checks if the new board-position is in the list. If so, it throws that move away. Are there other checks I need to do as well? Superko involves repeating a previous board position. Various forms of this are forbidden by various rulesets, see http://www.britgo.org/rules/compare.html#threeKK What you are doing ensures that your program will never violate any form of the rule. Not this one, does it? Restatement of the ko rule. One may not capture just one stone, if that stone was played on the previous move, and that move also captured just one stone. (from wikipedia) Folkert van Heusden -- MultiTail is a versatile tool for watching logfiles and output of commands. Filtering, coloring, merging, diff-view, etc. http://www.vanheusden.com/multitail/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Superko vs transposition table (was Re: [computer-go] Double/Triple Ko situation)
On Fri, Aug 7, 2009 at 5:51 AM, Folkert van Heusden folk...@vanheusden.comwrote: What is superko? My program keeps a list of all board-positions and then if it whants to do a move it checks if the new board-position is in the list. If so, it throws that move away. Are there other checks I need to do as well? Superko involves repeating a previous board position. Various forms of this are forbidden by various rulesets, see http://www.britgo.org/rules/compare.html#threeKK What you are doing ensures that your program will never violate any form of the rule. Ah ok! Odd is though that CGOS complains about Illegal KO attempted. Many time CGOS has been accused of calling a move illegal that wasn't - due to the KO rule. But so far it has never once been wrong when closely inspected. So I challenge you to show me a position where CGOS got this rule wrong! I'll give you a small monetary prize if you can :-)Just give the CGOS game number. Please note that the KO rule CGOS uses does NOT consider side to move. For example if the same exact board configuration repeats that has occurred previously, it is a positional superko violation regardless of which color is to move. Note that this is different than repetition in chess, where the same side must be on the move before consider the position as repeated. Also please note that when you play go there are other ways to define what a KO violation is. Players must agree to use the same rules when you sit down to play any game.CGOS uses the positional superko KO rule but it's also possible to play a game of go with the situational superko rule defined - which DOES take into consider the side to move. You can find disscussions on situational vs positional superko in the archives and on the web in other places - essentially there are some who feel the situational rule is more correct and more fundamental. I agree and I consider positional superko a slight complication (although by definition it is slighly simpler.) However, even though I feel that way, I chose positional superko for CGOS because I think it is more standard and accepted. - Don Folkert van Heusden -- Multitail es una herramienta flexible que permite visualizar los log file y seguir la ejecución de comandos. Permite filtrar, añadir colores, combinar archivos, la visualización de diferencias (diff- view), etc. http://www.vanheusden.com/multitail/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Double/Triple Ko situation
The largest nakade shape is the rabbity six. My wild guess would be to outlaw self-atari for groups of 7+ stones. The fun thing about computer go is how hard it is to make hard and fast rules: http://senseis.xmp.net/?BiggestKnownEyeSpaceForWhichThereIsANakade Outlawing self-atari of 18+ stones is probably okay, but not quite so useful :-). Darren -- Darren Cook, Software Researcher/Developer http://dcook.org/gobet/ (Shodan Go Bet - who will win?) http://dcook.org/mlsn/ (Multilingual open source semantic network) http://dcook.org/work/ (About me and my work) http://dcook.org/blogs.html (My blogs and articles) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Double/Triple Ko situation
Darren Cook wrote: The largest nakade shape is the rabbity six. My wild guess would be to outlaw self-atari for groups of 7+ stones. The fun thing about computer go is how hard it is to make hard and fast rules: http://senseis.xmp.net/?BiggestKnownEyeSpaceForWhichThereIsANakade Outlawing self-atari of 18+ stones is probably okay, but not quite so useful :-). http://www.dgob.de/dgoz/trmdpe/ Shows where not defending 20 stones in atari is best. This position is easily modified to give a position where self atari is best. Clearly this, as well as the 18-stone nakade, is pathological and will _never_ occur in a real game ... :-) I would guess that there will be a fair number of self-atari of up to 11 stones (especially on the edge, or in the corner, and where there are cutting points) where the self-atari would be the best move. Harry -+-+-+-+-+-+ ha...@goban.demon.co.uk38 Henley St, Oxford, OX4 1ES, UK http://www.goban.demon.co.ukTel: +44 1865 248775 http://harryfearnley.com *** NEW site *** Oxford Go Club:http://www.britgo.org/clubs/oxford_c.html ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Double/Triple Ko situation
You should set the limit to whatever yields the highest ELO in YOUR program. Harry Fearnley wrote: Darren Cook wrote: The largest nakade shape is the rabbity six. My wild guess would be to outlaw self-atari for groups of 7+ stones. The fun thing about computer go is how hard it is to make hard and fast rules: http://senseis.xmp.net/?BiggestKnownEyeSpaceForWhichThereIsANakade Outlawing self-atari of 18+ stones is probably okay, but not quite so useful :-). http://www.dgob.de/dgoz/trmdpe/ Shows where not defending 20 stones in atari is best. This position is easily modified to give a position where self atari is best. Clearly this, as well as the 18-stone nakade, is pathological and will _never_ occur in a real game ... :-) I would guess that there will be a fair number of self-atari of up to 11 stones (especially on the edge, or in the corner, and where there are cutting points) where the self-atari would be the best move. Harry -+-+-+-+-+-+ ha...@goban.demon.co.uk38 Henley St, Oxford, OX4 1ES, UK http://www.goban.demon.co.ukTel: +44 1865 248775 http://harryfearnley.com *** NEW site *** Oxford Go Club:http://www.britgo.org/clubs/oxford_c.html ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Double/Triple Ko situation
This is probably the best route. Either this, or get rid of the rule. This rule cannot be shown to be correct in general, it may work for most life and death problems, but can be wrong in semeai. You may get a nice ELO increase, but you are still actively building a wrong rule into the program. Check out the most difficult Go problem, problem 120 from Igo Hatsuyo Ron, for example, where black keeps trying to push white to capture his group which is getting bigger and bigger.. but surprisingly, white loses if he does! http://senseis.xmp.net/?MostDifficultProblemEver http://www.harryfearnley.com/go/trmdpe/hats-120-2009.html Christian Michael Williams wrote: You should set the limit to whatever yields the highest ELO in YOUR program. Harry Fearnley wrote: Darren Cook wrote: The largest nakade shape is the rabbity six. My wild guess would be to outlaw self-atari for groups of 7+ stones. The fun thing about computer go is how hard it is to make hard and fast rules: http://senseis.xmp.net/?BiggestKnownEyeSpaceForWhichThereIsANakade Outlawing self-atari of 18+ stones is probably okay, but not quite so useful :-). http://www.dgob.de/dgoz/trmdpe/ Shows where not defending 20 stones in atari is best. This position is easily modified to give a position where self atari is best. Clearly this, as well as the 18-stone nakade, is pathological and will _never_ occur in a real game ... :-) I would guess that there will be a fair number of self-atari of up to 11 stones (especially on the edge, or in the corner, and where there are cutting points) where the self-atari would be the best move. Harry -+-+-+-+-+-+ ha...@goban.demon.co.uk38 Henley St, Oxford, OX4 1ES, UK http://www.goban.demon.co.ukTel: +44 1865 248775 http://harryfearnley.com *** NEW site *** Oxford Go Club:http://www.britgo.org/clubs/oxford_c.html ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Double/Triple Ko situation
Actually, it's even worse than this: following LibEGO, my playouts allow (multi-stone) suicide! I may fix this before this weekend's KGS tournament. (Speaking of which, where are all the contestants?) Peter Drake http://www.lclark.edu/~drake/ On Aug 5, 2009, at 8:10 PM, Peter Drake wrote: On Aug 5, 2009, at 6:15 PM, Brian Sheppard wrote: Pebbles has the same ko rules as Orego, but it doesn't have the same search behavior. If Orego rejects self-atari moves of large strings, then the left side should become a seki almost always. If you are seeing 60% wins then something must be wrong there. There's the rub. I should implement that. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Double/Triple Ko situation
On Aug 6, 2009, at 12:19 PM, Peter Drake dr...@lclark.edu wrote: I may fix this before this weekend's KGS tournament. (Speaking of which, where are all the contestants?) I procrastinate, but I'll compete. I may enter more than one bot, but that depends on how much prep time I have. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Double/Triple Ko situation
In message 333558b6-c030-4656-8c35-0b766185a...@lclark.edu, Peter Drake dr...@lclark.edu writes Actually, it's even worse than this: following LibEGO, my playouts allow (multi-stone) suicide! I may fix this before this weekend's KGS tournament. (Speaking of which, where are all the contestants?) Unfortunately some entrants prefer to register at the last minute. I have received three entries so far; Aya, Orego, and break. I have been unable to register break, as its KGS account has lapsed. I have tried to explain this to its author, but either he has not received my email, or there is a language problem. I would like to see more weak entrants. I miss Aloril's collection of weak bots. Please, if there's anyone out there with a weak bot, like Stop, enter it! Everyone concerned will appreciate it if you do. Strong ones too of course, it's a pity that MoGo, CrazyStone, and Leela, among others, have stopped competing. And I can accept an unofficial GNU Go, if the GNU Go team does not enter one. Nick Peter Drake http://www.lclark.edu/~drake/ On Aug 5, 2009, at 8:10 PM, Peter Drake wrote: On Aug 5, 2009, at 6:15 PM, Brian Sheppard wrote: Pebbles has the same ko rules as Orego, but it doesn't have the same search behavior. If Orego rejects self-atari moves of large strings, then the left side should become a seki almost always. If you are seeing 60% wins then something must be wrong there. There's the rub. I should implement that. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Nick Weddn...@maproom.co.uk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Double/Triple Ko situation
I plan to compete, probably. -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go-boun...@computer-go.org] On Behalf Of Jason House Sent: Thursday, August 06, 2009 9:38 AM To: computer-go Subject: Re: [computer-go] Double/Triple Ko situation On Aug 6, 2009, at 12:19 PM, Peter Drake dr...@lclark.edu wrote: I may fix this before this weekend's KGS tournament. (Speaking of which, where are all the contestants?) I procrastinate, but I'll compete. I may enter more than one bot, but that depends on how much prep time I have. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Double/Triple Ko situation
I planned to enter the august tournament but development progressed slower than expected. I plan to enter the september tournament. You'll have 1 weak bot more ;) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Superko vs transposition table (was Re: [computer-go] Double/Triple Ko situation)
I fixed allowing multiple suicide in playouts, but it didn't make the many wasted playouts go away on Sheppard's position. On further investivation, the problem has to do with the interaction between superko and the transposition table. Currently, Orego checks only simple ko most of the time. Superko is only checked at the top level, before playing a real move (as opposed to a move in a playout). This means that, within the transposition table, superko can lead to an actual cycle. Orego does have a max number of moves per playout, so it doesn't crash, but it does throw away such playouts. To fix this, I plan to always check for superko violations. Is this what others are doing, or is there another way out? Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: Superko vs transposition table (was Re: [computer-go] Double/Triple Ko situation)
I check for superko during the UCT tree part of the search, but just simple ko during playouts. -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go-boun...@computer-go.org] On Behalf Of Peter Drake Sent: Thursday, August 06, 2009 11:42 AM To: computer-go Subject: Superko vs transposition table (was Re: [computer-go] Double/Triple Ko situation) I fixed allowing multiple suicide in playouts, but it didn't make the many wasted playouts go away on Sheppard's position. On further investivation, the problem has to do with the interaction between superko and the transposition table. Currently, Orego checks only simple ko most of the time. Superko is only checked at the top level, before playing a real move (as opposed to a move in a playout). This means that, within the transposition table, superko can lead to an actual cycle. Orego does have a max number of moves per playout, so it doesn't crash, but it does throw away such playouts. To fix this, I plan to always check for superko violations. Is this what others are doing, or is there another way out? Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Double/Triple Ko situation
I analyzed the following position as a win for O, but there are two or three kos involved (A1/A2, H1/G1, and the bent four at J9), so I am wondering if there are any other opinions. 1 2 3 4 5 6 7 8 9 A X - X X - X X X - B O X X O X - X O O C - O O O X X O O O D O O X - X O O O - E X O - X X X O - O F - O X X O O O O X G - O X O O O O X X H O X X O O X X X - J - X X X O X - - - O to play ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Double/Triple Ko situation
Orego thinks it's probably a win for O (around 60%, with a lot of variance from one run to another). On most runs, almost all of the playouts are discarded, because they get caught in cycles and hit the maximum playout length limit. Following LibEGO, Orego doesn't check for superko during playouts, just simple ko. Do other programs handle this issue differently? Peter Drake http://www.lclark.edu/~drake/ On Aug 5, 2009, at 2:20 PM, Brian Sheppard wrote: I analyzed the following position as a win for O, but there are two or three kos involved (A1/A2, H1/G1, and the bent four at J9), so I am wondering if there are any other opinions. 1 2 3 4 5 6 7 8 9 A X - X X - X X X - B O X X O X - X O O C - O O O X X O O O D O O X - X O O O - E X O - X X X O - O F - O X X O O O O X G - O X O O O O X X H O X X O O X X X - J - X X X O X - - - O to play ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Double/Triple Ko situation
Many Faces thinks that whoever moves first wins. I think you are right that O must win since the lower right is ko, and O wins if it makes seki on the left. -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go-boun...@computer-go.org] On Behalf Of Brian Sheppard Sent: Wednesday, August 05, 2009 2:20 PM To: computer-go@computer-go.org Subject: [computer-go] Double/Triple Ko situation I analyzed the following position as a win for O, but there are two or three kos involved (A1/A2, H1/G1, and the bent four at J9), so I am wondering if there are any other opinions. 1 2 3 4 5 6 7 8 9 A X - X X - X X X - B O X X O X - X O O C - O O O X X O O O D O O X - X O O O - E X O - X X X O - O F - O X X O O O O X G - O X O O O O X X H O X X O O X X X - J - X X X O X - - - O to play ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Double/Triple Ko situation
Brian Sheppard wrote: I analyzed the following position as a win for O, but there are two or three kos involved (A1/A2, H1/G1, and the bent four at J9), so I am wondering if there are any other opinions. 1 2 3 4 5 6 7 8 9 A X - X X - X X X - B O X X O X - X O O C - O O O X X O O O D O O X - X O O O - E X O - X X X O - O F - O X X O O O O X G - O X O O O O X X H O X X O O X X X - J - X X X O X - - - O to play If komi is 7.5, it looks like a simple win for White. White will win if the main fight turns seki, without trying to kill the bottom right. Black has no ko threats and White already has an eye on the left, so seki seems inevitable. -M- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Double/Triple Ko situation
Orego thinks it's probably a win for O (around 60%, with a lot of variance from one run to another). On most runs, almost all of the playouts are discarded, because they get caught in cycles and hit the maximum playout length limit. Following LibEGO, Orego doesn't check for superko during playouts, just simple ko. Pebbles has the same ko rules as Orego, but it doesn't have the same search behavior. If Orego rejects self-atari moves of large strings, then the left side should become a seki almost always. If you are seeing 60% wins then something must be wrong there. Another possibility is Orego's handling of transpositions. There are only 16 points that could possibly vary (again, assuming self-atari processing) so the position is almost bounded. Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Double/Triple Ko situation
On Aug 5, 2009, at 6:15 PM, Brian Sheppard wrote: Pebbles has the same ko rules as Orego, but it doesn't have the same search behavior. If Orego rejects self-atari moves of large strings, then the left side should become a seki almost always. If you are seeing 60% wins then something must be wrong there. There's the rub. I should implement that. What's your threshold for large? Do you absolutely reject such moves, or just penalize them? Another possibility is Orego's handling of transpositions. There are only 16 points that could possibly vary (again, assuming self-atari processing) so the position is almost bounded. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Double/Triple Ko situation
The largest nakade shape is the rabbity six. My wild guess would be to outlaw self-atari for groups of 7+ stones. Sent from my iPhone On Aug 5, 2009, at 11:10 PM, Peter Drake dr...@lclark.edu wrote: On Aug 5, 2009, at 6:15 PM, Brian Sheppard wrote: Pebbles has the same ko rules as Orego, but it doesn't have the same search behavior. If Orego rejects self-atari moves of large strings, then the left side should become a seki almost always. If you are seeing 60% wins then something must be wrong there. There's the rub. I should implement that. What's your threshold for large? Do you absolutely reject such moves, or just penalize them? Another possibility is Orego's handling of transpositions. There are only 16 points that could possibly vary (again, assuming self-atari processing) so the position is almost bounded. Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
