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

["Gary Boos" <gboos@xxxxxxx>]

Nullmove ?
Where can I read more about that technique ?
Are you familiar with PN search ?  What do you think of it ?
        Gary
------------
-----Original Message-----
From: Vincent Diepeveen <diep@xxxxxxxxxxxxxxxxx>
To: computer-go@xxxxxxxxxxxxxxxxx <computer-go@xxxxxxxxxxxxxxxxx>
Cc: herik@xxxxxxxxxxxxxxxxx <herik@xxxxxxxxxxxxxxxxx>; Robert M. Hyatt
<hyatt@xxxxxxxxxxxxxxxxx>; csvn@xxxxxxxxxxxxxxxxx <csvn@xxxxxxxxxxxxxxxxx>;
drd@xxxxxxxxxxxxxxxxx <drd@xxxxxxxxxxxxxxxxx>; Ralph Hellmig
<ralph.joerg.hellmig@xxxxxxxxxxxxxxxxx>; Ahmad Althani
<midnight@xxxxxxxxxxxxxxxxx>; Bradley Woodward <bradw@xxxxxxxxxxxxxxxxx>; Dann
Corbit <DCorbit@xxxxxxxxxxxxxxxxx>; Andrew Dados <frakir@xxxxxxxxxxxxxxxxx>;
peter_mckenzie@xxxxxxxxxxxxxxxxx <peter_mckenzie@xxxxxxxxxxxxxxxxx>;
empeys@xxxxxxxxxxxxxxxxx <empeys@xxxxxxxxxxxxxxxxx>
Date: Saturday, November 13, 1999 8:41 PM
Subject: computer-go: extracting date to beat 9d from chess and draughts
scene


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