Re: [Computer-go] super ko
Although a theoretical maximum is nice to ponder upon, in an experiment to safe computationtime, I tested my software for a superko up to cycles of ten. After several tens of thousands of game it came in an infinite loop due to a 12-cycle positional superko. So it is not common, but it can happen. Kind regards, Lukas On Thu, Jun 7, 2012 at 5:44 AM, Robert Jasiek jas...@snafu.de wrote: On 07.06.2012 01:47, Darren Cook wrote: Is four moves the longest super-ko cycle possible? Yawn. Regardless of the suicide rule, the longest implicit construction of a perfect play superko cycle is my four quadrupel kos on a 19x19 board with a sequence of probably 19,668,992 moves, using the ideas of Spight-Rickard-Davies: http://groups.google.com/group/de.rec.spiele.brett+karten/msg/3ef812707d21de8c?hl=dedmode=source However, in practice (with at least somewhat intelligent play) the most exciting things are a quintuple-ko and a few further basic kos on the board. For shapes, see here: http://home.snafu.de/jasiek/ko.pdf If your program is a complete duffer (many cute single passes at the right moments), then in theory (as I proved) it can put ANY position (no suicide: other than the empty board) in a cycle (with my simplistic construction having upper bound O(n)), but... even MC programs are not that dull. *** Can someone please reconstruct a good cycle of length 7 board plays? -- robert jasiek ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] super ko
Fascinating answers, thanks everyone. Although a theoretical maximum is nice to ponder upon, in an experiment to safe computationtime, I tested my software for a superko up to cycles of ten. After several tens of thousands of game it came in an infinite loop due to a 12-cycle positional superko. So it is not common, but it can happen. Wow, that is more common than I expected. (Can you give more details? 9x9 or 19x19 games? Did the program have much knowledge? I assume self-play?) Darren ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] super ko
Hi Darren, it was a 9 x 9 game, the bot was a random bot but for suicide moves and positional superko moves (or so I thought) ;) The bot was, as you have correctly assumed, playing against itself. After the filling up in the middle of board, the only legal moves remaining There were in two ko like structures in two corners of the the board, spreading a bit to the side. If you wish, I can try te reproduce and make an SGF file, but no guarantees here. ;) The game would ofcourse not be the same, but perhaps a similar situation will arise. Because the bot had no further intelligence, it might not be very interesting, though. Kind regards Lukas On Thu, Jun 7, 2012 at 11:23 AM, Darren Cook dar...@dcook.org wrote: Fascinating answers, thanks everyone. Although a theoretical maximum is nice to ponder upon, in an experiment to safe computationtime, I tested my software for a superko up to cycles of ten. After several tens of thousands of game it came in an infinite loop due to a 12-cycle positional superko. So it is not common, but it can happen. Wow, that is more common than I expected. (Can you give more details? 9x9 or 19x19 games? Did the program have much knowledge? I assume self-play?) Darren ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
[Computer-go] super ko
Hi, Should a bot understand and handle super ko to be able to play on CGOS? Thanks, Folkert van Heusden -- Nagios user? Check out CoffeeSaint - the versatile Nagios status viewer! http://www.vanheusden.com/java/CoffeeSaint/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] super ko
Hi There have been known incidents of bots playing, wanting to play a superko. This move was rejected by the server, causing the bot to time-out, in an otherwise favorable position. It might be possible to ignore superko, and in case the best move causes a superko and is rejected to play the second best move etc. until a non-superko move is encountered. This could cause a lot of extra computation time in an otherwise illegal move. Moreover it could cause your MC tree to cycle through a superko. Experiments would have to show whether the gained computation time is worth the risk. Kind regards Lukas On Wed, Jun 6, 2012 at 1:34 PM, folkert folk...@vanheusden.com wrote: Hi, Should a bot understand and handle super ko to be able to play on CGOS? Thanks, Folkert van Heusden -- Nagios user? Check out CoffeeSaint - the versatile Nagios status viewer! http://www.vanheusden.com/java/CoffeeSaint/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] super ko
On 06/06/2012 13:48, Nick Wedd wrote: On 06/06/2012 12:34, folkert wrote: Hi, Should a bot understand and handle super ko to be able to play on CGOS? To humans, and computers, playing where there is a superko rule, I give the same advice: One option is to understand the superko rule and all its consequences. Another option is to plan never to make a rule that might be forbidden by superko, but always to allow for your opponent making such a move. In almost all games, the result will be the same. Let's try that again (with sane use of carriage return, and no typo): One option is to understand the superko rule and all its consequences. Another option is to plan never to make a move that might be forbidden by superko, but always to allow for your opponent making such a move. In almost all games, the result will be the same. Nick -- Nick Wedd n...@maproom.co.uk ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] super ko
On Wed, Jun 6, 2012 at 7:34 AM, folkert folk...@vanheusden.com wrote: Hi, Should a bot understand and handle super ko to be able to play on CGOS? No. You can still play but you will lose if you violate any of the rules. A game cannot be reasonably played with rules and you don't just relax rules because someone or some program doesn't want to implement it. Is it a huge deal?Probably not - but positional superko is one of the rules for CGOS play and it's not like this is some bizarre made up rule, it's very standard. Such a change would also have side-effects and I have discovered as a software engineer that trying to get clever usually comes with a lot of pain. Do some research and try to figure out WHY there is even a superko rule in the first place to see what I mean. Then you have to determine what to do about normal ko, which is a subset of superko. Oh boy, now we have to start coding exceptions to rules and redefining concepts ... yuck! Would this be a disadvantage to the conforming program? I ask that because I don't know the answer.Suppose one program ignored the superko rule and the other program thought it had to honor it,couldn't that make gaming the system possible? I don't know how likely this is but what about a possible scenario where one program is winning based on believe the opponent has to avoid superko but he doesn't? Such a rule might require the currently conforming bots to have to reprogram in order to accomodate the programs that refuse to conform. That does not seem fair to me. And what about long ko cycles where the game just comes down to who has the most time on their clocks? I think CGOS has a hard coded game limit - a very liberal one but a limit nonetheless and now games (especially with 2 non-conforming bots) could go thousands of moves - as fast as the bots can play they can generated huge SGF game files. I don't know how valid all my concerns are here, but I am really not inclined to just change the rules for the benefit of lazy programmers especially when the change idea is to create a non-standard hybrid of sensible rules. Don Thanks, Folkert van Heusden -- Nagios user? Check out CoffeeSaint - the versatile Nagios status viewer! http://www.vanheusden.com/java/CoffeeSaint/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] super ko
On Wed, Jun 6, 2012 at 10:11 AM, Don Dailey dailey@gmail.com wrote: On Wed, Jun 6, 2012 at 7:34 AM, folkert folk...@vanheusden.com wrote: Should a bot understand and handle super ko to be able to play on CGOS? No. You can still play but you will lose if you violate any of the rules. A game cannot be reasonably played with rules and you don't just relax rules because someone or some program doesn't want to implement it. Don interprets handle super ko as accepting moves that violate superko, but I think folkert just meant avoid playing moves that violate superko ?! regards, -John ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] super ko
On Wed, Jun 6, 2012 at 10:17 AM, John Tromp john.tr...@gmail.com wrote: On Wed, Jun 6, 2012 at 10:11 AM, Don Dailey dailey@gmail.com wrote: On Wed, Jun 6, 2012 at 7:34 AM, folkert folk...@vanheusden.com wrote: Should a bot understand and handle super ko to be able to play on CGOS? No. You can still play but you will lose if you violate any of the rules. A game cannot be reasonably played with rules and you don't just relax rules because someone or some program doesn't want to implement it. Don interprets handle super ko as accepting moves that violate superko, but I think folkert just meant avoid playing moves that violate superko ?! I'm not sure I understand the distinction. Right now if a program plays a move that violates superko it is deemed to be an illegal move. What is the proposal? You either avoid playing these moves or you play them, right? I know I'm missing something here because John is too smart to not have something in mind and I have no experience as an actual go player. Don regards, -John ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] super ko
On 06/06/2012 11:05 AM, Kahn Jonas wrote: CGOS immediately scores the the game as a loss if a program attempts to make an illegal move (eg. super-ko). Thanks for the information. It does not change the question, though. Is it OK for a programm that still plays the next round to lose like that, or is it a problem for the other bots/the server…? no problem at all, IMHO Chrsitoph ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] super ko
Aja wrote:
It is not really expensive to detect and avoid superko in simulations. Some
repetitions occur every 4 moves, so you only need to incrementally keep
four keys and compare two keys. For instance,
Key1position before the third last move
Key2position before the second last move
Key3position before the last move
Key4current position
Is four moves the longest super-ko cycle possible? I thought it could be
longer, using some capture and refill approach. But I could be very
wrong on that.
Darren
P.S. Well if the bots are psychotic, and because tromp-taylor rules
allow suicide, then of course very long cycles are possible, with one
player always passing, and the other player filling in the same large
eye over and over...
My question is more: is a very long cycle possible in a game where both
players are playing to win?
To check super ko for move a in the current position, just do
if (Key1 == ComputeZobristKey(Key4, a))
{
// Forbid move a
}
--
Darren Cook, Software Researcher/Developer
http://dcook.org/work/ (About me and my work)
http://dcook.org/blogs.html (My blogs and articles)
___
Computer-go mailing list
Computer-go@dvandva.org
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] super ko
On Wed, Jun 6, 2012 at 1:47 PM, Darren Cook dar...@dcook.org wrote: Is four moves the longest super-ko cycle possible? I thought it could be longer, using some capture and refill approach. But I could be very wrong on that. Darren P.S. Well if the bots are psychotic, and because tromp-taylor rules allow suicide, then of course very long cycles are possible, with one player always passing, and the other player filling in the same large eye over and over... My question is more: is a very long cycle possible in a game where both players are playing to win? Four is not the longest, even when you try to win. Quadruple ko takes eight moves to cycle back. Although not common, it can happen. I had it happen in a game in the Dutch championship many years ago. Participation in the World Championship in Japan was on the line, so I can assure you we were both trying to win. Whether it was ideal play to let it happen, that's another question altogether... I don't know what the longest 'reasonable' cycle would be, but I've learned not to put my estimates too low with this type of thing in Go. Before you know it, someone comes up with a 'reasonable' cycle of longer length than you can count. Mark ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] super ko
There was a triple Ko recently on kgs during a youth match. I'm not qualified to say how naturally it arose, but it was under NZ rules, so kept play progressing (and was a major disadvantage to black, if I recall correctly). I think that the edge cases are much more easily exploited by stronger players, so it seems reasonable that strong players should know how to recognize them. s. On Jun 6, 2012 6:47 PM, Mark Boon tesujisoftw...@gmail.com wrote: On Wed, Jun 6, 2012 at 1:47 PM, Darren Cook dar...@dcook.org wrote: Is four moves the longest super-ko cycle possible? I thought it could be longer, using some capture and refill approach. But I could be very wrong on that. Darren P.S. Well if the bots are psychotic, and because tromp-taylor rules allow suicide, then of course very long cycles are possible, with one player always passing, and the other player filling in the same large eye over and over... My question is more: is a very long cycle possible in a game where both players are playing to win? Four is not the longest, even when you try to win. Quadruple ko takes eight moves to cycle back. Although not common, it can happen. I had it happen in a game in the Dutch championship many years ago. Participation in the World Championship in Japan was on the line, so I can assure you we were both trying to win. Whether it was ideal play to let it happen, that's another question altogether... I don't know what the longest 'reasonable' cycle would be, but I've learned not to put my estimates too low with this type of thing in Go. Before you know it, someone comes up with a 'reasonable' cycle of longer length than you can count. Mark ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] super ko
Ya, I agree with you all. In fact, four-move cycle is just a basic type of superko, see http://senseis.xmp.net/?Cycle I never managed to prohibit moves that form a cycle of length over six. because I thought cases other than triple ko might occur rarely. But it might be worth a try to handle superko with a hash table, though it might be slow. Aja 2012/6/6 Mark Boon tesujisoftw...@gmail.com On Wed, Jun 6, 2012 at 1:47 PM, Darren Cook dar...@dcook.org wrote: Is four moves the longest super-ko cycle possible? I thought it could be longer, using some capture and refill approach. But I could be very wrong on that. Darren P.S. Well if the bots are psychotic, and because tromp-taylor rules allow suicide, then of course very long cycles are possible, with one player always passing, and the other player filling in the same large eye over and over... My question is more: is a very long cycle possible in a game where both players are playing to win? Four is not the longest, even when you try to win. Quadruple ko takes eight moves to cycle back. Although not common, it can happen. I had it happen in a game in the Dutch championship many years ago. Participation in the World Championship in Japan was on the line, so I can assure you we were both trying to win. Whether it was ideal play to let it happen, that's another question altogether... I don't know what the longest 'reasonable' cycle would be, but I've learned not to put my estimates too low with this type of thing in Go. Before you know it, someone comes up with a 'reasonable' cycle of longer length than you can count. Mark ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] super ko
On 07.06.2012 01:47, Darren Cook wrote: Is four moves the longest super-ko cycle possible? Yawn. Regardless of the suicide rule, the longest implicit construction of a perfect play superko cycle is my four quadrupel kos on a 19x19 board with a sequence of probably 19,668,992 moves, using the ideas of Spight-Rickard-Davies: http://groups.google.com/group/de.rec.spiele.brett+karten/msg/3ef812707d21de8c?hl=dedmode=source However, in practice (with at least somewhat intelligent play) the most exciting things are a quintuple-ko and a few further basic kos on the board. For shapes, see here: http://home.snafu.de/jasiek/ko.pdf If your program is a complete duffer (many cute single passes at the right moments), then in theory (as I proved) it can put ANY position (no suicide: other than the empty board) in a cycle (with my simplistic construction having upper bound O(n)), but... even MC programs are not that dull. *** Can someone please reconstruct a good cycle of length 7 board plays? -- robert jasiek ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
