Re: computer-go: extracting date to beat 9d from chess and draughts scene

[Vincent Diepeveen <diep@xxxxxxxxx>]

At 09:15 PM 11/14/99 -0800, you wrote:
>At 11:30 AM 11/14/99 +0100, you wrote:
>>At 12:32 AM 11/14/99 -0800, you wrote:
>> >At 12:20 AM 11/14/99 +0100, you wrote:
>>...
>> >>Now as we all know GO because of branching factor
>> >>is a bit harder than this.
>> >
>> >its a *lot*harder. in the late fuskei and early midgame. locally you can
>> >easily have 20-30 open spaces, so you are looking at say
>> >25! ...
>>
>>For the 20-30 open spaces, the formula is not 25!
>>
>>With alfabeta pruning that's already reduced to around squareroot( 25! ),
>>though that's still a huge number...
>
>not that familiar with ab, but i'll take your word for it.

The basic search technique to search any gameplaying gametree.

See all basic math books or computer science books that deal with
algorithms.

Proven correct by Knuth, though this is a for human
very naturally way to search.

>>Then applying nullmove ...
>
>don't know what nullmove is

That is a very well known search technique which is
correct also in go, but might be not a good idea to use
searching forced lines.

Humans use nullmove bigtime themselves.

Of course in a smarter way than the computer can do it!

>>...
>> >>Apart from that we also need a couple of tens of years before
>> >>Go programs get at tactical decent levels.
>> >
>> >maybe much sooner, tactical stuff can probably done fairly well...
>>the first problem will be to choose the right tactics. ...
>>
>>That is shifting the problem from search to intelligent selecting moves,
>>which is dead wrong, and can be proven wrong directly; if you already know
>>what move to select say at 9d level, then a say 15 years old would already
>>start at 9dan level after taking a good look at how your source code selects
>>moves!
>
>we don't know the move, but we could know the goal (i.e. connect my stones, 
>make a live shape).

That is also knowledge, so with deduction to 'intelligent selecting moves'
and 'knowing the subgoal' we can directly see that this is also
impossible.

If we already know what the best plan we have (apart from winning which is
a goal that is foreseeable practical incalculatable) we don't
need to search at all.

We can do the best move without thinking.

So we can then play GO perfectly.

That last line you might object to, but a simple deduction, mathematical
speaking, of the fact that we are able to select the best plan.

If however our plan is suboptimal, then we can never assume
that we play better than the programs play now, as those play 
subobtimal too!

So the whole theory about making something that solves the game
for us, is simply shifting the problem to that 'making something'.

>> >>Most important thing now might be to estimate how deep ...
>> >i am an amatuer 1-dan. i can look ...
>> >depending how much of a one-way street it is...
>>
>>Right, let's skip one way streets, as those are very simple to travel
>>for both mankind and computer.
>
>no, a sort of worst case example is the 17 stone sacrifice. this is a 
>one-way street, but only to a human that can see it. the machine will have 
>to search, and since its a long sequence, will probably not find it, unless 
>it maybe had some goal directed smarts helping it out.

I didn't realize that a one way street has more than a single possibility.

However in chess and draughts one has the same problem. In draughts
the lines can be *very* long, but basicaly quite obvious.

This is what we call extensions. Extensions solve this problem for
a big part.

Yet it's obvious that not all deep combinations can be found at once.
There will remain combinations or method to play,
which no program will see for a long period of time.

This is why the chesscomputer is not unbeatable and this is why
the go computer for the foreseeable future will not be unbeatable either.

>>The difference between pro's and amateurs is not the number of moves
>>they look ahead. De Groot already proved that the basic difference is
>>the quality of what they see...
>
>don't know him, but i doubt it's a proof in the mathematical sense. could 
>you point his stuff?

You're insulting here the whole Artificial Intelligence world here!

This research was done a long time ago and done extensively.
Later some other researches have been done zooming in into details.

Let me find for you a good link to a big load of paper describing
this.

>>...
>> >you won't get that far in an open area of the board (say 30 empty spaces).
>> >you can do real well in the endgame. and nothing at all in the fuseki.
>>
>>Are we talking here about local tactical search?
>
>not sure what you mean here. i was thinking of 15-40 stones on the board 
>(late fuseki or early midgame).
>
>let me try to clarify my thinking. even assuming moor's law continues and 
>we have machines that are say 10^6 times as fast as we have today in say 20 
>years. you still have no chance in the late fuseki and early endgame. if 
>you look at a completed game that was fairly peaceful, the winner is the 
>one whose stones are the most efficient in surrounding territory. the pro 
>will simply find a way to make his stones more efficient than the 
>computer's. this is fairly clear to me, but i don't know if i have 
>explained it very well.

I know it's hard to imagine, but the branching factor is just about 9 to 10
at most. With 10^6 faster hardware they'll search the late endgame
or late fuseki with only 40 spaces left with perfect knowledge 
nearly in 20 years, as the search techniques will allow
to search nearly all possibilities.

just like they search in computerchess the far endgame with perfect
knowledge which makes that endgame a few pieces before that near-perfect.

Perhaps look in a book from Knuth for alfabeta search?

>thanks

>Ray (will hack java for food) http://home.pacbell.net/rtayek/
>hate spam? http://www.blighty.com/products/spade/
>
>
Vincent Diepeveen
diep@xxxxxxxxxxxxxxxxx

---