[computer-go] COGS bug in Ko detection?
[computer-go] COGS bug in Ko detection? === Sorry to jump into this thread -- I have only just joined the compgo mailing list since Nick Wedd told me that my work on Hanezeki had been mentioned here ... In reply to Terry McIntyre > Robert, your reference to hane-seki, also called hanezeki, > was new to me, so I did a bit of googling. My head is now > spinning; I figure that any program which embodies the > knowledge in the following paper should be quite interesting: > http://www.goban.demon.co.uk/go/seki/hanezeki/hanezeki_abstract.pdf 0) That paper has got at least one omission of which I am aware -- it fails to analyse configurations including "bulky 7", which can/will lead to kos! 1) There is something similar (both players lose points if they capture first), but simpler: a seki in which 2 opposing groups can each capture a dead shape (nakade) of the same size, but do not want to. 2) There is also something similar, but more complicated -- I call it (Mutual, Immediate) Capture and Delayed Recapture (CDR). I discuss CDR briefly in a paper that gives an overview of Seki, and the research still to be done: This paper was given at the International Conference on Baduk, in October 2005, and was published in the Korean Journal of Baduk Studies: http://www.earticle.net/Search/Open/ArticleView.aspx?view=MgAxADcAOQAyAA== It is available via my web-site: http://www.goban.demon.co.uk/go/seki/overview/overview.html It is _possible_, though I believe extremely unlikely, that there exists a "one-sided" predecessor version of (Mutual, Immediate) Capture and Delayed Recapture, such that only one of the players can sensibly initiate play, and when they do it becomes a "normal" (Mutual, Immediate) Capture and Delayed Recapture! :-( I do not know if any of this affects your concerns about kos. Regards Harry -+-+-+-+-+-+ ha...@goban.demon.co.uk38 Henley St, Oxford, OX4 1ES, UK http://www.goban.demon.co.ukTel: +44 1865 248775 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] Computer Olympiad Reminder
Rémi Coulom wrote: Hi, If you plan to participate in the Computer Olympiad, then don't forget to register soon. The deadline for early registration is April 15th: http://www.grappa.univ-lille3.fr/icga/event_info.php?id=25 We have received the registrations of 7 programs so far. Hi, I have entered early registrations into the web site, if you are curious: http://www.grappa.univ-lille3.fr/icga/tournament.php?id=194 http://www.grappa.univ-lille3.fr/icga/tournament.php?id=193 Let me know if there is any mistake. I added myself as a cc of the registration e-mails late, so I may have missed early registrations. I cannot check with Joke, as she is in vacation. David, do you intend to enter Many Faces ? Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Computer Olympiad Reminder
I can't afford to go this year, so Many faces will not be there. David > -Original Message- > From: computer-go-boun...@computer-go.org [mailto:computer-go- > boun...@computer-go.org] On Behalf Of Rémi Coulom > Sent: Wednesday, April 15, 2009 8:35 AM > To: computer-go > Subject: Re: [computer-go] Computer Olympiad Reminder > > Rémi Coulom wrote: > > Hi, > > > > If you plan to participate in the Computer Olympiad, then don't forget > > to register soon. The deadline for early registration is April 15th: > > http://www.grappa.univ-lille3.fr/icga/event_info.php?id=25 > > We have received the registrations of 7 programs so far. > > Hi, > > I have entered early registrations into the web site, if you are curious: > http://www.grappa.univ-lille3.fr/icga/tournament.php?id=194 > http://www.grappa.univ-lille3.fr/icga/tournament.php?id=193 > > Let me know if there is any mistake. I added myself as a cc of the > registration e-mails late, so I may have missed early registrations. I > cannot check with Joke, as she is in vacation. David, do you intend to > enter Many Faces ? > > Rémi > ___ > 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] Tree Contention
On Apr 14, 2009, at 7:57 PM, Rémi Coulom wrote: Jason House wrote: Out of curiosity, how do you intelligently delete old nodes? Reference counting won't always work due to cycles, and a nieve scan of the tree could block all threads. I store a date of birth in every node. At the beginning of a new search, I increment time, and refresh the date of birth of all the descendants of the new root. When allocating a new node, I can reuse old hash entries. Reuse hash entries? I assume you don't mean reuse entries because a later hash value matches (should be quite rare, even with 32 bit hash codes). The lockless hash you gave links to does not handle ever changing a hash value once it's set. If you CAS the tombstone value before the key, I guess it'd be reasonably safe, but not guaranteed. Did you add any new states to guarantee safety? Or am I thinking about this the wrong way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Tree Contention
You can change the value all you want. You just can't change the key. Jason House wrote: On Apr 14, 2009, at 7:57 PM, Rémi Coulom wrote: Jason House wrote: Out of curiosity, how do you intelligently delete old nodes? Reference counting won't always work due to cycles, and a nieve scan of the tree could block all threads. I store a date of birth in every node. At the beginning of a new search, I increment time, and refresh the date of birth of all the descendants of the new root. When allocating a new node, I can reuse old hash entries. Reuse hash entries? I assume you don't mean reuse entries because a later hash value matches (should be quite rare, even with 32 bit hash codes). The lockless hash you gave links to does not handle ever changing a hash value once it's set. If you CAS the tombstone value before the key, I guess it'd be reasonably safe, but not guaranteed. Did you add any new states to guarantee safety? Or am I thinking about this the wrong way? ___ 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] Tree Contention
On Apr 15, 2009, at 6:50 PM, Michael Williams > wrote: You can change the value all you want. You just can't change the key. Right... That's the design in the google talk. Remi said he "can reuse cache entries" and so avoids resizing / copying (greatly simplifying the algorithm). I find that 32 bit zobrist hashing takes a few minutes before reusing a single hash value. That's too infrequent to use in place of real cleanup. Smaller hashes (such as 16 bit) would have too much ovelap to be useful... So rejecting that possibility leaves me clueless about what reusing a hash entry could mean besides replacing a complete slot in the table. Jason House wrote: On Apr 14, 2009, at 7:57 PM, Rémi Coulom fr> wrote: Jason House wrote: Out of curiosity, how do you intelligently delete old nodes? Reference counting won't always work due to cycles, and a nieve scan of the tree could block all threads. I store a date of birth in every node. At the beginning of a new search, I increment time, and refresh the date of birth of all the descendants of the new root. When allocating a new node, I can reuse old hash entries. Reuse hash entries? I assume you don't mean reuse entries because a later hash value matches (should be quite rare, even with 32 bit hash codes). The lockless hash you gave links to does not handle ever changing a hash value once it's set. If you CAS the tombstone value before the key, I guess it'd be reasonably safe, but not guaranteed. Did you add any new states to guarantee safety? Or am I thinking about this the wrong way? ___ 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] Tree Contention
I think your hash value is your first-try index into the hash table. So a 32-bit hash would be a 4E9 sized table. Probably too big for Remi's computer. I'd guess that he's using something between 16 and 32 bits in his hash hey. Jason House wrote: On Apr 15, 2009, at 6:50 PM, Michael Williams wrote: You can change the value all you want. You just can't change the key. Right... That's the design in the google talk. Remi said he "can reuse cache entries" and so avoids resizing / copying (greatly simplifying the algorithm). I find that 32 bit zobrist hashing takes a few minutes before reusing a single hash value. That's too infrequent to use in place of real cleanup. Smaller hashes (such as 16 bit) would have too much ovelap to be useful... So rejecting that possibility leaves me clueless about what reusing a hash entry could mean besides replacing a complete slot in the table. Jason House wrote: On Apr 14, 2009, at 7:57 PM, Rémi Coulom wrote: Jason House wrote: Out of curiosity, how do you intelligently delete old nodes? Reference counting won't always work due to cycles, and a nieve scan of the tree could block all threads. I store a date of birth in every node. At the beginning of a new search, I increment time, and refresh the date of birth of all the descendants of the new root. When allocating a new node, I can reuse old hash entries. Reuse hash entries? I assume you don't mean reuse entries because a later hash value matches (should be quite rare, even with 32 bit hash codes). The lockless hash you gave links to does not handle ever changing a hash value once it's set. If you CAS the tombstone value before the key, I guess it'd be reasonably safe, but not guaranteed. Did you add any new states to guarantee safety? Or am I thinking about this the wrong way? ___ 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Tree Contention
Jason House wrote: On Apr 15, 2009, at 6:50 PM, Michael Williams wrote: You can change the value all you want. You just can't change the key. Right... That's the design in the google talk. Remi said he "can reuse cache entries" and so avoids resizing / copying (greatly simplifying the algorithm). I find that 32 bit zobrist hashing takes a few minutes before reusing a single hash value. That's too infrequent to use in place of real cleanup. Smaller hashes (such as 16 bit) would have too much ovelap to be useful... So rejecting that possibility leaves me clueless about what reusing a hash entry could mean besides replacing a complete slot in the table. I simply consider entries from previous searches as free for replacement, unless they descend from the current root. So I may replace them completely by a new node. Date of birth is really what indicates whether a slot is free or not. The principle of the table is like this: I allocate an array of N nodes. if hash code is h, I probe at h%N,(h+1)%N,...,(h+R)%N, were R is a "rehash" parameter. There is never any node de-allocation, except between searches, with the date-of-birth mechanism, but this not done concurrently. If the table is not big enough, then node allocation may fail, although the table may still have plenty of free slots. In that case, I just don't allocate the node, which is OK with a MC search. In practice, with 1Gb of RAM, this never happens. I don't remember precisely, but maybe I needed to implement a special logic to make allocation thread safe. It is not very difficult. I am very confident that my implementation is correct, although I did not try a formal proof. The only difficulty is when two threads try to allocate the same slot. Also, it is important to avoid that two threads create the same node in two different slots. This is not very difficult to do with compare-and-swap. It may be a bit different from what Cliff Click does, though. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] April 2009 KGS tournament
Ingo Althöfer wrote: >Other question: Might it be possible to find a >volunteer for operating Zen19 in Pamplona? I forgot to say it here - Mr. Kato came forward as an operator of Zen. It will play via KGS. Have a good game, all. -- Yamato ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] April 2009 KGS tournament
Yamato: <20090416003730.32a584...@aic-smtp1.ayu.ne.jp>: >Ingo Althöfer wrote: >>Other question: Might it be possible to find a >>volunteer for operating Zen19 in Pamplona? > >I forgot to say it here - Mr. Kato came forward as an operator of Zen. I'll, of course, operate Fudo Go as well. I believe this does not violate the rules of the tournament, right? Hideki >It will play via KGS. Have a good game, all. > >-- >Yamato -- g...@nue.ci.i.u-tokyo.ac.jp (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
