[Computer-go] Combinatorics of Go

[Erik van der Werf]

Hi Robert,

Perhaps my answer was a bit cryptic. I'll try to explain.

In a computer go program it is indeed needed to detect cycles when you
want to claim, for example, a tie or no-result. So you're right about
that.

However, to evaluate a position and infer the best move it is
generally not needed as long as you don't care about distinguishing
between not having a final result due to the position being too
complex to reach a terminal state and not having a final result
because the search will never reach a final state. (Notice though that
in both cases eventually the optimal move can still be found).

Say for simplicity we select our move based on an iterative deepening
alpha beta search that ignore some aspects of the history. In case of
a potential long cycle the search will simply not return a final
result unless the komi is high or low enough for one side to deviate
from the cycle.

The way I think about it is that a cycle is only a true cycle when
nothing in the state distinguishes the first occurrence of a position
form later occurrences. Superko requires adding something to the state
that distinguishes the first occurrence from later occurrences, so in
that sense I meant that the cycle is no longer a true cycle (i.e., it
is broken).

Regarding the conjecture you propose, I'd rather formulate it as:

"Under Japanese style ko rules, the long-term history is never needed
to infer the best move".

Some short-term history is however still needed for things like
basic-ko end game-ending passes.

Best,
Erik


On Mon, Jan 3, 2011 at 7:57 AM, Robert Jasiek <jasiek at snafu.de> wrote:
> On 02.01.2011 22:04, Erik van der Werf wrote:
>>
>> to 'not return a result' you don't need the history.
>
> How? A cycle is a presupposition for the result No Result (or long cycle
> tie). (Of course, hashing by numbers of stones on the board or Cycle Law's
> prisoner difference etc. may often be sufficient, but if it is not, then
> determining a cycle by referring to history is necessary.)
>
>> When optimal play leads to a cycle
>
> a) necessarily
>
> b) optionally
>
>> then any state in that cycle should lead to an equivalent cycle.
>
> I am not sure exactly what you mean by this. Do you want to say that, given
> the game's move-sequence so far, its last moves, if they are about to be in
> cycles, then necessarily they are in the same cycle? You still need to
> establish the fact whether they are in a cycle.
>
>> Superko rules, always returning a result, just need more because they
>> break more.
>
> How do they break more? They break less by not creating any repetition:)
> Maybe you want to say: They have to detect the first repetition before it is
> executed.
>
> Ok, let us assume that under Japanese style rules the programs just recycle
> a bit, using the same or different cycles, until trying to apply the long
> cycle rule. They still need to detect that they have been playing some cycle
> at all. See above: You need the history because hashing does not guarantee
> detection. So, you or Olivier tell me why not having to use history! Are you
> having some insight I overlook?
>
> (In CG practice, the history can be ignored as a first approach - under
> superko or Japanese style ko rules. To be sure though, history is needed.)
>
> Do we need to do the maths? Your conjecture seems to be: "Under Japanese
> style ko rules, the history is never needed to apply the No Result / long
> cycle tie rule." I claim the opposite (might be needed).
>
> --
> robert jasiek
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>