[computer-go] malibu beach go party

[Ray Tayek]

hi, eric cotsen (sponsor of the cotsen open) is having a go party at 
his house on the beach in mailbu on saturday, july 26'th. mr. yang 
(7p) will be there. anyone on this list that is in the area is welcome to come.


send me an email off the list for the details.

thanks

---
vice-chair http://ocjug.org/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] cotsen open will be on september 20-21'st

[Ray Tayek]

The dates for the Cotsen Go Tournament have been decided. The 
tournament will be held on September 20 and 21 at the Tom Bradley 
International Hall on the UCLA campus. This is the same location 
where the Toyota Denso North American Oza was held this past January.


thanks

---
vice-chair http://ocjug.org/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] cotsen open will be on september 20-21'st

[Nick Wedd]

In message 
<[EMAIL PROTECTED]>, 
Ray Tayek <[EMAIL PROTECTED]> writes
The dates for the Cotsen Go Tournament have been decided. The 
tournament will be held on September 20 and 21 at the Tom Bradley 
International Hall on the UCLA campus. This is the same location where 
the Toyota Denso North American Oza was held this past January.


Will it include a Computer Go event this year?

Nick
--
Nick Wedd[EMAIL PROTECTED]
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] cotsen open will be on september 20-21'st

[Ray Tayek]

At 03:08 AM 7/11/2008, you wrote:
In message 
<[EMAIL PROTECTED]>, 
 Ray Tayek <[EMAIL PROTECTED]> writes
The dates for the Cotsen Go Tournament have been decided. The 
tournament will be held on September 20 and 21 at the Tom Bradley 
International Hall on the UCLA campus. This is the same location 
where the Toyota Denso North American Oza was held this past January.


Will it include a Computer Go event this year?


don't know yet. i intend to ask him at the party on the 26'th.

thanks

---
vice-chair http://ocjug.org/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Graph history interaction

[Jason House]

I tracked down a rare hang/crash in my bot and I'm curious how others  
handle this.


I use simple ko state as part of my hash lookup, but I don't use super  
ko. I can't store the whole graph history because then there would be  
no transpositions at all. I can't really update legal moves to exclude  
super ko because the super ko legality changes based on how a node is  
reached.


In particular, a deterministic algorithm like UCT can get caught in an  
infinite loop. My random playouts may take a bit longer from super ko,  
but it gets quickly resolved.


Sent from my iPhone
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Graph history interaction

[Peter Drake]

My sense is that most programs ignore superko except for checking  
right before a "real" move (as opposed to a playout move) is played.


The way out of the infinite loop is to set a maximum number of moves  
in a playout; abort the playout if you reach this threshold.


On Jul 11, 2008, at 9:03 AM, Jason House wrote:

I tracked down a rare hang/crash in my bot and I'm curious how  
others handle this.


I use simple ko state as part of my hash lookup, but I don't use  
super ko. I can't store the whole graph history because then there  
would be no transpositions at all. I can't really update legal moves  
to exclude super ko because the super ko legality changes based on  
how a node is reached.


In particular, a deterministic algorithm like UCT can get caught in  
an infinite loop. My random playouts may take a bit longer from  
super ko, but it gets quickly resolved.


Sent from my iPhone
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


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] Graph history interaction

[John Fan]

 I had the same issue in UCT tree. What I did is to check if the current
node is a ko move, then compare it with its latest 6 ancestors. If any match
is found, then consider the move is a loss. So it cuts off the infinite
loop.

On Fri, Jul 11, 2008 at 12:08 PM, Peter Drake <[EMAIL PROTECTED]> wrote:

> My sense is that most programs ignore superko except for checking right
> before a "real" move (as opposed to a playout move) is played.
>
> The way out of the infinite loop is to set a maximum number of moves in a
> playout; abort the playout if you reach this threshold.
>
>
> On Jul 11, 2008, at 9:03 AM, Jason House wrote:
>
>  I tracked down a rare hang/crash in my bot and I'm curious how others
>> handle this.
>>
>> I use simple ko state as part of my hash lookup, but I don't use super ko.
>> I can't store the whole graph history because then there would be no
>> transpositions at all. I can't really update legal moves to exclude super ko
>> because the super ko legality changes based on how a node is reached.
>>
>> In particular, a deterministic algorithm like UCT can get caught in an
>> infinite loop. My random playouts may take a bit longer from super ko, but
>> it gets quickly resolved.
>>
>> Sent from my iPhone
>> ___
>> computer-go mailing list
>> computer-go@computer-go.org
>> http://www.computer-go.org/mailman/listinfo/computer-go/
>>
>
> 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/

Re: [computer-go] Graph history interaction

[Jason House]

On Jul 11, 2008, at 12:08 PM, Peter Drake <[EMAIL PROTECTED]> wrote:

My sense is that most programs ignore superko except for checking  
right before a "real" move (as opposed to a playout move) is played.


That was my preference too, but...


The way out of the infinite loop is to set a maximum number of moves  
in a playout; abort the playout if you reach this threshold.


That trick only works when your playout is non-deterministic. Outside  
the search tree, things are non-deterministic and cycles are easy to  
break or ignore. Inside the search tree it isn't that easy. If no  
cached data is updated from an aborted search, UCT will walk the tree  
the same way it did for the last playout.


When the cycle is *inside* the search tree, this means another  
infinite/aborted playout. The abortted playout trick would cause the  
bot to cycle uselessly until the game takes another path.





On Jul 11, 2008, at 9:03 AM, Jason House wrote:

I tracked down a rare hang/crash in my bot and I'm curious how  
others handle this.


I use simple ko state as part of my hash lookup, but I don't use  
super ko. I can't store the whole graph history because then there  
would be no transpositions at all. I can't really update legal  
moves to exclude super ko because the super ko legality changes  
based on how a node is reached.


In particular, a deterministic algorithm like UCT can get caught in  
an infinite loop. My random playouts may take a bit longer from  
super ko, but it gets quickly resolved.


Sent from my iPhone

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Graph history interaction

[Peter Drake]

Since the tree is of finite size, you will eventually get to the  
nondeterministic part of the playout. The moves here will probably  
finish the playout (one way or another) before hitting the maximum  
move threshold, so the playout will not be aborted but will update the  
tree.


On Jul 11, 2008, at 9:39 AM, Jason House wrote:

The way out of the infinite loop is to set a maximum number of  
moves in a playout; abort the playout if you reach this threshold.


That trick only works when your playout is non-deterministic.  
Outside the search tree, things are non-deterministic and cycles are  
easy to break or ignore. Inside the search tree it isn't that easy.  
If no cached data is updated from an aborted search, UCT will walk  
the tree the same way it did for the last playout.


When the cycle is *inside* the search tree, this means another  
infinite/aborted playout. The abortted playout trick would cause the  
bot to cycle uselessly until the game takes another path.


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] Graph history interaction

[Jason House]

On Jul 11, 2008, at 12:43 PM, Peter Drake <[EMAIL PROTECTED]> wrote:

Since the tree is of finite size, you will eventually get to the  
nondeterministic part of the playout.


Unforunately, no. A graph cycle has finite size, in the case I  
debugged yesterday, it took only 4 nodes. I'm not sure how big the  
whole tree was, but it was at least 20 ply



The moves here will probably finish the playout (one way or another)  
before hitting the maximum move threshold, so the playout will not  
be aborted but will update the tree.



On Jul 11, 2008, at 9:39 AM, Jason House wrote:

The way out of the infinite loop is to set a maximum number of  
moves in a playout; abort the playout if you reach this threshold.


That trick only works when your playout is non-deterministic.  
Outside the search tree, things are non-deterministic and cycles  
are easy to break or ignore. Inside the search tree it isn't that  
easy. If no cached data is updated from an aborted search, UCT will  
walk the tree the same way it did for the last playout.


When the cycle is *inside* the search tree, this means another  
infinite/aborted playout. The abortted playout trick would cause  
the bot to cycle uselessly until the game takes another path.


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/

Re: [computer-go] Graph history interaction

[Peter Drake]

Ah, I forgot that you had a transposition table. (Orego currently does  
not.)


I, too, will be interested to hear the solution to this problem.

Peter Drake
http://www.lclark.edu/~drake/


On Jul 11, 2008, at 10:49 AM, Jason House wrote:


On Jul 11, 2008, at 12:43 PM, Peter Drake <[EMAIL PROTECTED]> wrote:

Since the tree is of finite size, you will eventually get to the  
nondeterministic part of the playout.


Unforunately, no. A graph cycle has finite size, in the case I  
debugged yesterday, it took only 4 nodes. I'm not sure how big the  
whole tree was, but it was at least 20 ply



The moves here will probably finish the playout (one way or  
another) before hitting the maximum move threshold, so the playout  
will not be aborted but will update the tree.



On Jul 11, 2008, at 9:39 AM, Jason House wrote:

The way out of the infinite loop is to set a maximum number of  
moves in a playout; abort the playout if you reach this threshold.


That trick only works when your playout is non-deterministic.  
Outside the search tree, things are non-deterministic and cycles  
are easy to break or ignore. Inside the search tree it isn't that  
easy. If no cached data is updated from an aborted search, UCT  
will walk the tree the same way it did for the last playout.


When the cycle is *inside* the search tree, this means another  
infinite/aborted playout. The abortted playout trick would cause  
the bot to cycle uselessly until the game takes another path.


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 mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Graph history interaction

[Sanghyeon Seo]

2008/7/12 Jason House <[EMAIL PROTECTED]>:
> I tracked down a rare hang/crash in my bot and I'm curious how others handle
> this.
>
> I use simple ko state as part of my hash lookup, but I don't use super ko. I
> can't store the whole graph history because then there would be no
> transpositions at all. I can't really update legal moves to exclude super ko
> because the super ko legality changes based on how a node is reached.

Fuego source has this interesting comment:

Capture History

As a heuristic fix to the Graph-History-Interaction (GHI) problem,
the hash code also includes a component, that depends on the order, in
which stones were captured.

The idea is to eliminate hashing problems caused by the same
position reached at different level in the search, or recapture
is legal in one branch and illegal in another.

It is not a complete solution to the GHI problem.

-- 
Seo Sanghyeon
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Graph history interaction

[Peter Drake]

Another possibility would be to keep a list of nodes visited in the  
"tree" on each playout. In the rare event where the length of this  
list exceeds some max game length threshold, go back through the list  
looking for repetitions. Mark the first move that led to a repetition  
as a loss for the player that made that move. This should eventually  
cause the move to be rated so poorly by UCB that it will not be  
explored further.


On Jul 11, 2008, at 11:12 AM, Sanghyeon Seo wrote:


2008/7/12 Jason House <[EMAIL PROTECTED]>:
I tracked down a rare hang/crash in my bot and I'm curious how  
others handle

this.

I use simple ko state as part of my hash lookup, but I don't use  
super ko. I

can't store the whole graph history because then there would be no
transpositions at all. I can't really update legal moves to exclude  
super ko

because the super ko legality changes based on how a node is reached.


Fuego source has this interesting comment:

Capture History

As a heuristic fix to the Graph-History-Interaction (GHI) problem,
the hash code also includes a component, that depends on the order, in
which stones were captured.

The idea is to eliminate hashing problems caused by the same
position reached at different level in the search, or recapture
is legal in one branch and illegal in another.

It is not a complete solution to the GHI problem.

--
Seo Sanghyeon
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


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] Re: Operator needed

[Basti Weidemyr]

I can operate a couple of robots, and probably find more operators if  
needed.


If someone wants/needs Mac, I can provide that. If Linux required, I  
can probably bring a linux computer if you notify me before Tuesday  
July 16.


We now have around 700 participants in the main tournament which is  
on par with the record in Praha. Journalists are likely to appear. :)


Best Regards
Basti Weidemyr
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Graph history interaction

[John Fan]

I guess you missed my message.

I solved this by comparing the current node with its ancestors in the  path.
On each walking down the tree, I pass the list of nodes in the same path.
Then I check whether the current node already appear in the path. If yes, I
assign a loss there. To speed it up, I only check the current node against 6
nodes before it.

It is not perfect or accurate solution for the issue, but it solves the
problem at hand.



On Fri, Jul 11, 2008 at 12:23 PM, John Fan <[EMAIL PROTECTED]> wrote:

>  I had the same issue in UCT tree. What I did is to check if the current
> node is a ko move, then compare it with its latest 6 ancestors. If any match
> is found, then consider the move is a loss. So it cuts off the infinite
> loop.
>
>
> On Fri, Jul 11, 2008 at 12:08 PM, Peter Drake <[EMAIL PROTECTED]> wrote:
>
>> My sense is that most programs ignore superko except for checking right
>> before a "real" move (as opposed to a playout move) is played.
>>
>> The way out of the infinite loop is to set a maximum number of moves in a
>> playout; abort the playout if you reach this threshold.
>>
>>
>> On Jul 11, 2008, at 9:03 AM, Jason House wrote:
>>
>>  I tracked down a rare hang/crash in my bot and I'm curious how others
>>> handle this.
>>>
>>> I use simple ko state as part of my hash lookup, but I don't use super
>>> ko. I can't store the whole graph history because then there would be no
>>> transpositions at all. I can't really update legal moves to exclude super ko
>>> because the super ko legality changes based on how a node is reached.
>>>
>>> In particular, a deterministic algorithm like UCT can get caught in an
>>> infinite loop. My random playouts may take a bit longer from super ko, but
>>> it gets quickly resolved.
>>>
>>> Sent from my iPhone
>>> ___
>>> computer-go mailing list
>>> computer-go@computer-go.org
>>> http://www.computer-go.org/mailman/listinfo/computer-go/
>>>
>>
>> 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] US Congress - computer go operator volunteer

[terry mcintyre]

I will be attending the US Congress in Portland, OR from Aug 2-10. Will be 
bringing a core 2 duo laptop running Linux. 

Intel(R) Core(TM)2 Duo CPU T7300  @ 2.00GHz
MemTotal:  2034016 kB

If anyone needs an operator for the Computer Go tournament, let me know. Can 
use my laptop or (if you arrange availability) other equipment.

If your program can utilize a quadcore, I might be persuaded to shlep my HP 
desktop along, but it's easier for me to travel light; will be sharing a car 
with two others for a 14 hour drive.

Unix systems administration is my day job; can deal with most of the usual 
setup hassles. ;)

 Terry McIntyre <[EMAIL PROTECTED]>


“Wherever is found what is called a paternal government, there is found state 
education. It has been discovered that the best way to insure implicit 
obedience is to commence tyranny in the nursery.”

Benjamin Disraeli, Speech in the House of Commons [June 15, 1874]




___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Graph history interaction

[Peter Drake]

Do you always check it? Would it be faster to hold off on this check  
until you realize that you're in a cycle?


On Jul 11, 2008, at 12:06 PM, John Fan wrote:


I guess you missed my message.

I solved this by comparing the current node with its ancestors in  
the  path. On each walking down the tree, I pass the list of nodes  
in the same path. Then I check whether the current node already  
appear in the path. If yes, I assign a loss there. To speed it up, I  
only check the current node against 6 nodes before it.


It is not perfect or accurate solution for the issue, but it solves  
the problem at hand.




On Fri, Jul 11, 2008 at 12:23 PM, John Fan <[EMAIL PROTECTED]> wrote:
 I had the same issue in UCT tree. What I did is to check if the  
current node is a ko move, then compare it with its latest 6  
ancestors. If any match is found, then consider the move is a loss.  
So it cuts off the infinite loop.



On Fri, Jul 11, 2008 at 12:08 PM, Peter Drake <[EMAIL PROTECTED]>  
wrote:
My sense is that most programs ignore superko except for checking  
right before a "real" move (as opposed to a playout move) is played.


The way out of the infinite loop is to set a maximum number of moves  
in a playout; abort the playout if you reach this threshold.



On Jul 11, 2008, at 9:03 AM, Jason House wrote:

I tracked down a rare hang/crash in my bot and I'm curious how  
others handle this.


I use simple ko state as part of my hash lookup, but I don't use  
super ko. I can't store the whole graph history because then there  
would be no transpositions at all. I can't really update legal moves  
to exclude super ko because the super ko legality changes based on  
how a node is reached.


In particular, a deterministic algorithm like UCT can get caught in  
an infinite loop. My random playouts may take a bit longer from  
super ko, but it gets quickly resolved.


Sent from my iPhone
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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/


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] Graph history interaction

[John Fan]

I checked it whenever the current move is ko. And I think I only checked
against the latest 6 (or 8) ancestors. And only check it against the node
with even distance in the tree. And I am passing down the list of pointers,
so the comparison is not that much work. It is only pointer comparison, only
3 or 4 times of extra pointer comparison on each ko move.

When using hash table, you would want to stop the repition as soon as
possible. Since if you wait too many moves, lets say depth 32 into the tree,
the same node could have already appears many times in the path, and the UCT
update would have added too many losses for the same node.

On Fri, Jul 11, 2008 at 4:15 PM, Peter Drake <[EMAIL PROTECTED]> wrote:

> Do you always check it? Would it be faster to hold off on this check until
> you realize that you're in a cycle?
>
> On Jul 11, 2008, at 12:06 PM, John Fan wrote:
>
> I guess you missed my message.
>
> I solved this by comparing the current node with its ancestors in the
> path. On each walking down the tree, I pass the list of nodes in the same
> path. Then I check whether the current node already appear in the path. If
> yes, I assign a loss there. To speed it up, I only check the current node
> against 6 nodes before it.
>
> It is not perfect or accurate solution for the issue, but it solves the
> problem at hand.
>
>
>
> On Fri, Jul 11, 2008 at 12:23 PM, John Fan <[EMAIL PROTECTED]> wrote:
>
>>  I had the same issue in UCT tree. What I did is to check if the current
>> node is a ko move, then compare it with its latest 6 ancestors. If any match
>> is found, then consider the move is a loss. So it cuts off the infinite
>> loop.
>>
>>
>> On Fri, Jul 11, 2008 at 12:08 PM, Peter Drake <[EMAIL PROTECTED]> wrote:
>>
>>> My sense is that most programs ignore superko except for checking right
>>> before a "real" move (as opposed to a playout move) is played.
>>>
>>> The way out of the infinite loop is to set a maximum number of moves in a
>>> playout; abort the playout if you reach this threshold.
>>>
>>>
>>> On Jul 11, 2008, at 9:03 AM, Jason House wrote:
>>>
>>>  I tracked down a rare hang/crash in my bot and I'm curious how others
 handle this.

 I use simple ko state as part of my hash lookup, but I don't use super
 ko. I can't store the whole graph history because then there would be no
 transpositions at all. I can't really update legal moves to exclude super 
 ko
 because the super ko legality changes based on how a node is reached.

 In particular, a deterministic algorithm like UCT can get caught in an
 infinite loop. My random playouts may take a bit longer from super ko, but
 it gets quickly resolved.

 Sent from my iPhone
 ___
 computer-go mailing list
 computer-go@computer-go.org
 http://www.computer-go.org/mailman/listinfo/computer-go/

>>>
>>> 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/
>
>
> 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/

Re: [computer-go] Graph history interaction

[Jason House]

On Jul 11, 2008, at 4:42 PM, "John Fan" <[EMAIL PROTECTED]> wrote:

I checked it whenever the current move is ko. And I think I only  
checked against the latest 6 (or 8) ancestors. And only check it  
against the node with even distance in the tree. And I am passing  
down the list of pointers, so the comparison is not that much work.  
It is only pointer comparison, only 3 or 4 times of extra pointer  
comparison on each ko move.


Checking against the ancestor two moves back is unnecessary. That will  
only find violations of the simple ko rule, which I assume all bot  
authors avoid to begin with




When using hash table, you would want to stop the repition as soon  
as possible. Since if you wait too many moves, lets say depth 32  
into the tree, the same node could have already appears many times  
in the path, and the UCT update would have added too many losses for  
the same node.


I don't like adding losses. The ideal handling would be to split the  
search tree. While a split is expensive, complex ko violations are  
extremely rare.








On Fri, Jul 11, 2008 at 4:15 PM, Peter Drake <[EMAIL PROTECTED]> wrote:
Do you always check it? Would it be faster to hold off on this check  
until you realize that you're in a cycle?


On Jul 11, 2008, at 12:06 PM, John Fan wrote:


I guess you missed my message.

I solved this by comparing the current node with its ancestors in  
the  path. On each walking down the tree, I pass the list of nodes  
in the same path. Then I check whether the current node already  
appear in the path. If yes, I assign a loss there. To speed it up,  
I only check the current node against 6 nodes before it.


It is not perfect or accurate solution for the issue, but it solves  
the problem at hand.




On Fri, Jul 11, 2008 at 12:23 PM, John Fan <[EMAIL PROTECTED]> wrote:
 I had the same issue in UCT tree. What I did is to check if the  
current node is a ko move, then compare it with its latest 6  
ancestors. If any match is found, then consider the move is a loss.  
So it cuts off the infinite loop.



On Fri, Jul 11, 2008 at 12:08 PM, Peter Drake <[EMAIL PROTECTED]>  
wrote:
My sense is that most programs ignore superko except for checking  
right before a "real" move (as opposed to a playout move) is played.


The way out of the infinite loop is to set a maximum number of  
moves in a playout; abort the playout if you reach this threshold.



On Jul 11, 2008, at 9:03 AM, Jason House wrote:

I tracked down a rare hang/crash in my bot and I'm curious how  
others handle this.


I use simple ko state as part of my hash lookup, but I don't use  
super ko. I can't store the whole graph history because then there  
would be no transpositions at all. I can't really update legal  
moves to exclude super ko because the super ko legality changes  
based on how a node is reached.


In particular, a deterministic algorithm like UCT can get caught in  
an infinite loop. My random playouts may take a bit longer from  
super ko, but it gets quickly resolved.


Sent from my iPhone
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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/


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 mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Graph history interaction

[John Fan]

I agree that the check against two moves back is not necessary.

As for the solution, I think it is good enough to prevent the infinite loop
at least for the current level of my engine. StoneGrid had relatively often
crashes due to superko by running out of stack. But there is no crashes due
to the superko since I added the check. It's been almost one year.  As for
the effect on accuracy or strength, the triple ko is rare. And computer
engine generated triple ko most times are non-sense triple ko. Usually in
those situations, the winning side can find better moves to secure a win by
avoiding the super ko. So I guess it really does not matter how well does
the engine handle the superko, more importantly is to prevent a crash when
the situation arises.

On Fri, Jul 11, 2008 at 5:24 PM, Jason House <[EMAIL PROTECTED]>
wrote:

> On Jul 11, 2008, at 4:42 PM, "John Fan" <[EMAIL PROTECTED]> wrote:
>
> I checked it whenever the current move is ko. And I think I only checked
> against the latest 6 (or 8) ancestors. And only check it against the node
> with even distance in the tree. And I am passing down the list of pointers,
> so the comparison is not that much work. It is only pointer comparison, only
> 3 or 4 times of extra pointer comparison on each ko move.
>
>
> Checking against the ancestor two moves back is unnecessary. That will only
> find violations of the simple ko rule, which I assume all bot authors avoid
> to begin with
>
>
>
> When using hash table, you would want to stop the repition as soon as
> possible. Since if you wait too many moves, lets say depth 32 into the tree,
> the same node could have already appears many times in the path, and the UCT
> update would have added too many losses for the same node.
>
>
> I don't like adding losses. The ideal handling would be to split the search
> tree. While a split is expensive, complex ko violations are extremely rare.
>
>
>
>
>
>
> On Fri, Jul 11, 2008 at 4:15 PM, Peter Drake < <[EMAIL PROTECTED]>
> [EMAIL PROTECTED]> wrote:
>
>> Do you always check it? Would it be faster to hold off on this check until
>> you realize that you're in a cycle?
>>
>> On Jul 11, 2008, at 12:06 PM, John Fan wrote:
>>
>> I guess you missed my message.
>>
>> I solved this by comparing the current node with its ancestors in the
>> path. On each walking down the tree, I pass the list of nodes in the same
>> path. Then I check whether the current node already appear in the path. If
>> yes, I assign a loss there. To speed it up, I only check the current node
>> against 6 nodes before it.
>>
>> It is not perfect or accurate solution for the issue, but it solves the
>> problem at hand.
>>
>>
>>
>> On Fri, Jul 11, 2008 at 12:23 PM, John Fan < <[EMAIL PROTECTED]>
>> [EMAIL PROTECTED]> wrote:
>>
>>>  I had the same issue in UCT tree. What I did is to check if the current
>>> node is a ko move, then compare it with its latest 6 ancestors. If any match
>>> is found, then consider the move is a loss. So it cuts off the infinite
>>> loop.
>>>
>>>
>>> On Fri, Jul 11, 2008 at 12:08 PM, Peter Drake < <[EMAIL PROTECTED]>
>>> [EMAIL PROTECTED]> wrote:
>>>
 My sense is that most programs ignore superko except for checking right
 before a "real" move (as opposed to a playout move) is played.

 The way out of the infinite loop is to set a maximum number of moves in
 a playout; abort the playout if you reach this threshold.


 On Jul 11, 2008, at 9:03 AM, Jason House wrote:

  I tracked down a rare hang/crash in my bot and I'm curious how others
> handle this.
>
> I use simple ko state as part of my hash lookup, but I don't use super
> ko. I can't store the whole graph history because then there would be no
> transpositions at all. I can't really update legal moves to exclude super 
> ko
> because the super ko legality changes based on how a node is reached.
>
> In particular, a deterministic algorithm like UCT can get caught in an
> infinite loop. My random playouts may take a bit longer from super ko, but
> it gets quickly resolved.
>
> Sent from my iPhone
> ___
> computer-go mailing list
>  computer-go@computer-go.org
>  
> http://www.computer-go.org/mailman/listinfo/computer-go/
>

 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.or