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

[Vincent Diepeveen <diep@xxxxxxxxx>]

In reaction at the GO mailing list to the statement whether
a 9 dan will get beaten in 2010 by a machine

>I agree with Ray:

>>i doubt if a machine will beat any pro, let alone a 9-dan (have you ever 
>>played a 9-dan?) in 20 years, let alone 10.

To get a bound how long it would take to beat the best go players,
let's have a look in different worlds called draughts and chess.

Let's distinguish from a program 3 aspects that are needed to
beat an opponent in a game:
   - high tactical level
   - evaluation of a position 
   - strategical aspects

I'm not sure what dan level my chessrating of 2254 FIDE compares to,
it's sure not enough to be professional player.

However i beat currently most chessprograms without problems. The less
knowledge they have the simpler. The others i beat too, but at blitz
i need to be 'in shape' to kick them, as a lot of small tactical
victories for the computer slowly means my end even though i know how
to setup a game strategical such that the computer is fooled. 
Note that i know all stronger chessprogram or can categorize 
any chessprogram, which might be a big advantage for me over professional
chess players who simply don't care to distinguish between the programs.

My draughtsprogram (please don't confuse with checkers), 
though recently second in the world, 
gets beaten silly and very simply by my partner who plays national
level.

This is quite amazing, as the first version of
the draughtsprogram already solved any tactical trick that my
partner could find in his books, where i in the past years
not seldom managed to tactical fool chess programs even!

I tried to explain this by the fact that chess is a quite symmetric
game and in most of those games the battle is for the centre, a 
simple heuristic for a computer and tactics in the centre is something
where the computer is quite good at. Draughts however is after a few
moves completely asymmetric and the centre is of less importance.

This explanation failed completely getting when seeing facts that happened
in the endgame. In the endgame chess is a lot harder than draughts
as the main goal in draughts: getting to the overside thereby not allowing
the opponent promoting a single piece, which obviously a lot simpler
to evaluate than the endgame in chess.

Even though the draughtsprogram searches even at tournament level
40 ply fullwidth in the endgame (that excludes a lot of extensions)
a lot of mistakes are made there by it. So any obvious win or obvious
advantage in the first say 30 moves it certainly will not miss at that 
depth, yet when the board is quite empty and the goal is clearly
set, many mistakes are getting made.

As the branching factor in draughts is very small compared to chess
and go, it's very interesting to do tests with the program.

Tests that are in chess AND go impossible, namely letting it search
to unimaginable depths for mankind and then compare the difference
of a tournament search with an overnight analysis.

When we (Marcel Monteba and me) started our draughtsprogram Napoleon,
it obviously didn't have much knowledge. Lacking all sense of space
and dependancies. 

When it made a very obvious positional mistake short after the opening,
sometimes, which it did at tournament level, searching at say 14 ply depth,
then i allowed it to search for a few days, in an attempt to figure out
whether such a depth would backtrack a better move.

Not seldom it reached after a few days 30 plies or more.
STILL IT MADE THE SAME PATHETIC MOVE. 
Very seldom a move changed and if it changed it never changed at 
the big depths, only at tournament level it tended to change its 
thought sometimes, usually exchanging a strategical mistake for another
strategical mistake.

This convinced me that knowledge was the way to go for
any type of game that can't be searched completely.

Nowadays all this kind of info is in the draughtsprogram and it plays
a lot stronger. 

It nowadays might switch on say 12 or 14 ply to a different move
positionally, but searching at huge depths still doesn't make it
change its mind.

Some 'build up moves' it strategically plays wrong, it still tends to
remain doing wrong, even at those huge depths, at which no human
can analyze not even at home. 

Now in GO that go program i once made searches like 5 ply or
something (with basically only an influence function and very few
patterns as i don't play go very well).

So in chess i'm searching at tournament level 11 or 12 ply now 
at a quad xeon (same depth deep blue gets). Most programs do
also around that depth, or a bit deeper tactical.

That 11 to 12 ply solves the majority of all difficult tricks
made by chessgrandmasters.

They speculate when mankind loses to the chessprograms, but when
speculating about that i think they speculate about the wrong thing.
One should speculate when evaluation functions progress, as
the past few years programs hardly progressed in evaluation function.

Basically other conditions, such as openingsbooks and tuning a program
to a certain style, and letting it play more aggressive, were done to it.

Objectively seen programs still make the same evaluation mistakes, 
and got only better in tactics.
Just like the first version of my draughtsprogram found all tactical
combinations made by the very best draughtsplayers, in chess slowly
programs get tactically also that well that they find very difficult
tactical combinations also very quickly now.

Yet positionally chessprograms have *a long* way to go. Only
tactical they're nearly as strong now as the draughtsprograms are 
already for many years.

No doubt we will search deeper in the future in all games with the
different programs, yet all experiments in that direction and all
developments in that direction indicate that the end is far from
reached as the main problem, evaluation of a leafposition,
the progress there is obviously *very* slow. 

Not to mention that for most chessprograms that progress of evaluation
has completely stopped and halted.

Now as we all know GO because of branching factor
is a bit harder than this. We don't need just faster hardware.

We need a revolution in both programming languages (to represent
knowledge) and the way in which we evaluate positions.

Apart from that we also need a couple of tens of years before
Go programs get at tactical decent levels.

It would be very illogical that a GO program can beat a 9d in 2010
while a draughtsprogram nor a chessprogram can beat the equivalent at
tournament level (playing for their title) in that year!

Most important thing now might be to estimate how deep the average
combination in GO is, and how many plies the programs lack.

Then using the different 'laws' we can extract how many years it might
take before we have the hardware to solve the average professional
go tactics and simple positional manoeuvres (manoeuvres that take quite
some moves to see but take an average evaluation function to see).

Then we can take a look at strategics and whether any depth or
evaluation might tackle that problem.

Simply ignoring the fact that combinations in GO might need
a much bigger depth than in chess, let's simply assume that
getting the same depth as in draughts&chess to see most combinations
is what we try to achieve.

With nearly 1 billion nodes a second Deep Blue searched around
11 or 12 ply the majority of moves of the game.

With around 50,000 nodes a second my own chessprogram (Diep),
searches at a quad xeon to the same depth.

This is because of the search technique we call nullmove. I would
be very interested to know whether this can be used in GO.

In draughts i can't use that search technique as doing a nullmove
is usual very good.

For now i will assume it can be used.

That means that it's good to figure out the branching factor i have
in chess with DIEP.

I have done quite some measurements at overnight analysis to what the
average number of moves was, and i came to 40 (in litterature they
estimate it at 35).

12 ply at 50,000 nodes at 180 seconds a move 

That is 12 ply with 9 million nodes ==> branching factor is 3.8
Now the weird thing is that getting a ply deeper is not 3.8
on average, but more like 2.5 to 3.0

There is simply an overhead which starts at ply = 1 already.
At ply = 1 the branching factor is 40. Now a rude method is first
dividing the total nodes by the root and then calculating the
branching factor; this means that the effective branching factor 
which in the future will get me a ply deeper is has to be calculated 
for 11 ply with 9000000 / 40 = 225000 

So approximation: 11th root from 22500 = 3.07
However given is that the average number of nodes is 40
The square root from 40 is 6.3

Alphabeta without double nullmove (double nullmove is in contradiction
to nullmove a correct form of searching invented by me and hopefully
soon described in ICCA journal) has theoretical a branching factor
which is a bit higher than this.

Now the reduction with nullmove is huge to that. In ComputerGO
the reduction from by nullmove will be even bigger then this.

A near to empty board has around 350 possibilities. Square root 
from 350 is about 18.7
If nullmove halfs that to 9 then we have a rude estimation
upon what number we need to get a ply deeper.

My program gets like 5 to 6 ply now, so it's still lacking about 6 ply
for some tactical tricks to a depth that we can see as absolute minimum.

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. 
Even though i'm hopefully nearly making my retirement by then at 65, 
which might me make care less about the future of go, 
even speculating that in 38 years programmers might make
progress in evaluation and programming languages still don't
make me bet that after my retirement in 2038 the best 
go players get clearly beaten by a program!

Vincent Diepeveen
diep@xxxxxxxxxxxxxxxxx






Vincent Diepeveen
diep@xxxxxxxxxxxxxxxxx

---