RE: [computer-go] Modern brute force search (Gods handicap)

["Mark Boon" <tesuji@xxxxxxxxx>]

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of chrilly
> Sent: Monday, November 08, 2004 8:38
> To: computer-go
> Subject: Re: [computer-go] Modern brute force search (Gods handicap)
>
>
>
> The direct consequence of this barrier is: Human chessplayers are very far
> away from optimal play. God must just create quiet threats >12 Plies.
>
> If Go-Players state they can read easily to 30 Plies it does not mean that
> their barrier is 30 Plies. Once they are reading, they have
> already realized
> that there is some tactic around. The essential point is: Do they read any
> 30 Ply threat? I canīt believe it.

I don't think they do. But in this sense Go may be 'easier' than chess that
a pro can more easily accurately recognise when reading deep is warranted
and when not.

>
> But even 30 Plies sounds not impossible.If one would make a project like
> Deep-Blue it would be within 10 years at least within reach.
> As a first guess the effective branching factor is somewhat less than half
> of the theoretical optimal branching factor => 7-8.
> Modern brute-force  programms do not search brute-force. The Null-Move and
> other pruning techniques are very efficient. In case of Go the
> programm must
> be clever enough to realize Sente. Otherwise one can not use the
> Null-Move.
> This is probably a very big IF for using the Null-Move.

It's certainly true that null-move and sente are very related concepts. At
least it is in Goliath. Very often a pass (null-move) is inserted not so
much to limit the search depth as it is to see if the opponent needs to
respond to the last move in the line of play. In this case in Go a line of
play is said to be 'sente', and it causes all kinds of complications in the
search tree as it gets hard to compare the value of a sente-move with a
gote-move.

In classic Go theory, a sente-move is considered twice the value of a
gote-move. But this is actually only a rule-of-thumb. In fact the value
should be added to the value of the next-best non-local gote move. On
average the next-best move will be more or less the same size as the best
move because the board is so big, so the easy way out is just to double the
value of the best move. It saves having to look for the value of the
next-best move. But it only really works in end-game where there are lots of
independent areas where non-related moves can be played, enough to arrive at
the 'doubling' result.

It's important to realise that concepts of sente and gote are only useful as
shortcuts. Splitting the game in several independent battles makes them
easier to cope with for humans. As soon as you're considering full-width
search, the concepts of gote and sente completely disappear, as there are no
longer any non-local independent battles elsewhere. So full-width search
would get rid of a major head-ache for Go software. On the other hand, if Go
software is able to split up the game in independent battles as efficiently
as humans can, then I think in the local searches it becomes much more
likely that a computer can outperform a human. I think this is currently
already possible in life-and-death. Hardware nowadays should be fast enough
to make a life-and-death program outperform even a top-pro.

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