FW: [computer-go] SlugGo approach: GNU vs.Goliath

["Mark Boon" <tesujisoftware@xxxxxxxxx>]

> -----Original Message-----
> From: David G Doshay [mailto:ddoshay@xxxxxxxxxxxxxxxxx]
> Sent: Tuesday, January 04, 2005 22:13
> To: tesujisoftware@xxxxxxxxxxxxxxxxx; computer-go
> Subject: Re: [computer-go] SlugGo approach: GNU vs.Goliath
>
>
> > I think I understand your SlugGo approach a lot better now than I did
> > earlier.
> > ... I can see how
> > this reduces the effect of the horizon a great deal, but I can't see
> > yet why
> > combining the evaluation of the future board with the current board
> > helps.
> > To me this is counter-intuitive, so I'll have to think a bit more about
> > that. Any rationale from your side why you chose to do it this way?
>
> Isn't that what a lookahead algorithm always does? return back to the
> start
> of a sequence some information about how it turns out?

Not as far as I know. The evaluation in the leafs of a search-tree usually
replaces the evaluation in the internal nodes completely. What I understand
from your description the value of a move is a combination of the evaluation
of the first move and the last move in the sequence. This seems a rather
fundamental difference to me.

Consider the sequence ABCDEF and compare it to CBADEF. Traditionally this
should have the same value when they result in the same position. Since they
start with a different move however, in your method the value could be very
different.

>
> > And
> > do you intend to keep this evaluation approach when you add branching?
>
> Yes, we are doing thing incrementally ... one change at a time is
> preferable.

So as you can see I have some reservations to that in regards to making a
search-tree. I have trouble seeing all the ramifications, but I expect it to
mess up caching and alpha-beta. Making small steps is a good strategy of
course, especially if you get encouraging results early. But you have to be
a little careful not spending a lot of effort into steps that will become
obsolete when moving to te next fundamental stage.

> > The other bit is that you generate moves for both sides. I did see
> > this in
> > one of your posts, but didn't see the full point of it. Now I
> > understand
> > why, you need it because you include evaluation of the current move.
> > Since
> > for defensive moves it evaluates to no or small gain ,
>
> GNU Go values are not so simple.
>
> >  for those you need to
> > complement them with the gain for the opponents move.
>
> I do not think your view accurately captures why I do it or what we get
> from
> generating an array of possible moves from the perspective of both
> sides.
>
> I decided to do it because I could see an algorithm for implementing
> the Go
> proverb: Your best move may be your opponent's best move.
>
> I think it works because it expands the search space in a way that
> emphasizes
> urgency. We get to moves that evaluate as good for both earlier than
> moves
> that evaluate only as best for us. Of course that is slightly unfair
> because GNU
> Go does try to include lots of information about urgency in their move
> values. I
> use the additional perspective to slightly modify the weighting. But
> there surely
> are lots of times that the THEM perspective finds a big threat against
> us that is
> not near the top of GNU Go's list. I think it is simply that it is good
> to know
> where your best moves are, and where their best moves are, and to
> evaluate
> sequences based upon both perspective ... with particular emphasis on
> moves
> that are good for both. This really is simple stuff covered in every Go
> book.

The proverb "Your best move may be your opponent's best move" is very useful
of course, so anything that works in that direction will help. However, in a
search-tree this is usually taken care of by the 'killer-move' heuristic. It
may be the one-dimensional nature of your current lookahead that requires
something like your particular solution.

> > I decided not to generate the THEIRS list because I think making
> > decisions
> > based on the opponents precise move doesn't work well. It would only
> > work
> > well if I can decide which opponents moves are related to moves in the
> > US
> > list, and boost those. I think this is what you do?
>
> We are moving in that direction. The original SlugGo code was written by
> students in response to requests from me and additional guidance from
> Charlie McDowell, a professor of Computer Science who was the advisor
> of the students. What ended up in the implementation is not exactly
> what I
> wanted. The implementation as it is today results in things like the
> "reverse
> monkey jump," where SlugGo defends against an invading monkey jump
> by moving onto the exact same place that the opponent would have jumped
> to ... obviously not optimal. There are other things that happen
> similarly, but
> this one is easiest to see.

Generally there's a use for finding out if a move is preventing an opponents
threat or big move. However I don't think it works by requiring it to be the
same exact point on the board or use another arbitrary proximity rule. I
figure the best way to find out if two moves are related is to keep record
of where the points and/or influence are. Then after playing a move (or a
sequence) you see in what area the points and/or influence have changed. If
these area of a move and an opponents move have a certain overlap then you
can consider them to be related.

But this is just an idea. Due to holidays I haven't been able to run any
more experiments, I may try some more when I have some more time. There
seems to be something there that gives an interesting increase in playing
strength with modest effort and immodest computing power that is worth
checking out.

> Now that I have finished the rewrite of the code and we are satisfied
> that
> it gives the same answers and values as before, getting this part as I
> wanted
> it is my next task.
>
> GNU Go does do lookahead, and plenty of it. But its lookahead sequences
> are based upon a number of more local considerations. I just added the
> whole board length scale to the mix.

Yes, I know it does local search. I was referring to lookahead that takes
the whole board into account, something I was told GNU Go doesn't do.



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