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

[Vincent Diepeveen <diep@xxxxxxxxx>]

At 12:32 AM 11/14/99 -0800, you wrote:
>At 12:20 AM 11/14/99 +0100, you wrote:
>>... In the endgame chess is a lot harder than draughts
>>as the main goal in draughts:

>the endgame rules in chess are artificial and not natural. in go, you can 
>sort of just keep playing stones (like chinese rules)

>>This convinced me that knowledge was the way to go for
>>any type of game that can't be searched completely. ...
>
>>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!=15511210043330985984000000 or 1.5*10^25. furthermore, there are major 
>branch points in most sequences where one side can tenuki and start 
>something (that may relate) elsewhere.

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

Then applying nullmove you get another *huge* reduction, halfing
usual branching factor. The big question here is
whether nullmove *can* be applied.

Also reductions are derived from transpositions, which are
also reducing tree size considerably.

>>We need a revolution in both programming languages (to represent
>>knowledge) and the way in which we evaluate positions.
>
>yes
>
>>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. (if you 
>know the problem is to connect the stones, then you can get real good at 
>this). the first problem will be to choose the right tactics. later 
>problems will be more difficult.

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! 

>>Most important thing now might be to estimate how deep the average
>>combination in GO is, and how many plies the programs lack.
>
>i am an amatuer 1-dan. i can look 5-15 moves ahead (not real good) 
>depending how much of a one-way street it is, how open/complicated the area 
>is etc. pros can look a lot further and they know which lines to ignore.

Right, let's skip one way streets, as those are very simple to travel
for both mankind and computer.

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

>>...let's simply assume that
>>getting the same depth as in draughts&chess to see most combinations
>>is what we try to achieve.
>
>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?

In my calculations i'm not busy with local tactical search but with
a global search that doesn't miss a single move.

>>...
>>If every 2 years the speed of hardware doubles, then that means
>>that for 6 ply we need about 9^6 = 531441 times faster hardware.
>>To get 531441 times faster hardware we need to wait:
>>  2 * (log 531441 / log 2)  = 2 * 19 = 38 years
>>
>>That's 2037. I get 64 in that year.

>hmmm, thats when the unix clock expires (i'll be 91 or not here :)
>maybe we can beat some strong amateurs by 2037.

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

Vincent Diepeveen
diep@xxxxxxxxxxxxxxxxx

---