[Computer-go] 7.0 Komi and weird deep search result

Don Dailey dailey.don at gmail.com
Tue Apr 5 22:04:06 PDT 2011


On Tue, Apr 5, 2011 at 9:45 PM, Aja <ajahuang at gmail.com> wrote:

> I don't think your current work is not valuable, and fully agree with you
> that MM/SB-based engines have a much greater effect on strength, which is
> clearly proved by Erica. But recently my feeling is that current MCTS almost
> reaches its limit on 19x19. We will need another breakthrough/good ideas to
> overcome KGS 5d or 6d.
>

I would like to ask you to reconsider your feeling on this, because I think
they are misguided.  Let me explain why I feel that way and you can take it
for what it's worth.

Many months ago there was a discussion on computer chess and people were
divided on the issue if most of amazing progress in computer chess was due
to software or hardware.  Most had always assumed it was hardware and that
is the standard sound bite cut and pasted into articles that talk about the
progress of computer chess.    However,  I was swayed convincingly to the
software side of the issue and I think most real experts on computer chess
agree now that it's roughly even - the software progress in computer chess
has been absolutely astounding when measure over decades and it has kept
pace and perhaps even outstripped hardware.

But here is the thing ...  the whole process was long and gradual and it
never involved any major breakthroughs.    Yes, there were things that stood
out and some refer to them as breakthroughs,   but none of them were even a
fraction of what we got from Monte Carlo methods for Go.    Go was really
ripe for this one because it was long overdue anyway and global search was
the only way forward and had been dismissed for so long.

At each step along the way,  it was almost impossible to imagine making a
program play much stronger as it seemed like we were doing everything
reasonably possible.

In 2004 a program called "Fruit" came out and it astounded the computer
chess community with it's incredible strength.    The strange thing about
this is  that there are NOW chess programs that are hundreds of ELO stronger
than Fruit, running on the SAME hardware.   It's not hardware, it's real
software advancements, good ideas and good engineering.   And there have
been no "major breakthoughs" since Fruit to produce these programs.   Even
Fruit itself did not have any new ideas of major significance, it just did a
lot of things a little bit better.  (Probably the biggest factor in Fruit
was something called LMR which was worth something like 50 ELO,  but even
that  was just an old idea all polished up with a better formulation.   And
many think the major thing that made it strong was simplicity and bug free
code.)

The lesson from this,  is that if you are standing in a dense forest, you
can only see a few trees around you.   YOUR feeling that we have "almost
reached our limit" and that we have exhausted all the good ideas in MCTS and
need something new is certainly shortsighted and I mean no disrespect.  I
have fallen for this kind of thinking a few times myself.

What you are very likely going to see is gradual steady progress and
constant refinements of ideas and incremental improvements which will add up
to an overwhelming amount of power in a relatively short time.    There will
not be any major new ideas but probably a lot of little ideas, each
contributing a small amount.

Here is an example of how this works,  using a principle every top chess
program author understands very well:

Imagine that you can make your program strong enough in a months time to win
51% of the games against the previous version.    If you can do that, you
will have added something like 5-10 ELO to the strength of your program.
5-10 ELO is a small amount of improvement and it is so difficult to measure
that it requires thousands of games to verify.     So we are not talking
about a herculean task.     And yet,  if you do that for a year you will
have added 1 dan of strength to your go program!    1 Dan in 1 year is a
lot.

But I don't think the engineers in Go programming think like that yet.
 (Maybe some do,  I applaud you if you so.)  They seem to get frustrated if
they cannot find an immediate big gain and speak of not making progress
without some major breakthrough because they cannot imagine their program
playing much better without one.     The way you make a strong program is
1-10 ELO at a time over months and years.     I think it is extremely unlike
that anybody will find a single 1 dan idea that is relatively painless to
code up.   However there  are probably many good ideas that will add up to 1
dan with a lot of engineering and tuning and hard work.

I admit that a big hurdle with GO is the ability to test 10,000 games (for
instance) in a reasonable amount of time.   It would probably tax the
patience of most GO authors to try to measure small improvements and thus
the mentality to only look for big things and dream of major breakthroughs.
   But I seriously doubt anything that is quickly measured is likely to be
found and I'm convinced that even the best ideas need a lot of refinements
and engineering - the stuff that takes so long and requires so many games.

So my predictions is that without anything really major (but no doubt some
new small ideas) we are going to see your KGS 5 and 6 dan and much higher in
5 to 10 years.   I'm assuming that the good engineers in computer go will
improve on their testing methodology (and I think multi-core newer hardware
will make this much easier to do.)

Don




> Aja
>
> ----- Original Message ----- From: "Brian Sheppard" <sheppardco at aol.com>
>
> To: <computer-go at dvandva.org>
> Sent: Wednesday, April 06, 2011 7:00 AM
>
> Subject: Re: [Computer-go] 7.0 Komi and weird deep search result
>
>
>  I spend a lot of time on computer Go, but probably not in the right
>> places.
>>
>> My work currently focuses on expressing positional features using 3x3
>> neighborhoods, so that domain knowledge is easier to express as data rather
>> than if/else code. This is useful stuff, to be sure.
>>
>> Instead, I really ought to build two systems: an MM-based engine to
>> prioritize moves in the tree search, and an SB-based engine for random
>> search in the playout. I am sure that these would have a much greater effect
>> on strength.
>>
>> But I started the other effort, and I should continue for a while before
>> changing. Probably I will do MM next.
>>
>> Brian
>>
>> -----Original Message-----
>> From: computer-go-bounces at dvandva.org [mailto:
>> computer-go-bounces at dvandva.org] On Behalf Of Aja
>> Sent: Tuesday, April 05, 2011 1:35 PM
>> To: computer-go at dvandva.org
>> Subject: Re: [Computer-go] 7.0 Komi and weird deep search result
>>
>> I might not really catch what you meant, but I wonder why. :)
>>
>> Aja
>>
>> -----原始郵件----- From: Brian Sheppard
>> Sent: Wednesday, April 06, 2011 12:29 AM
>> To: computer-go at dvandva.org
>> Subject: Re: [Computer-go] 7.0 Komi and weird deep search result
>>
>> I don't know if the worst could be worse; UCT convergence for a 1-ply
>> search
>> is a probabilistic function with an exponential bound. The bound for an
>> N-ply search is a tower of N exponentials: Exp(Exp(Exp(...Exp()))). Ugh.
>>
>> Because of this bound, guessing good moves quickly is absolutely vital for
>> strong play from UCT. Which calls into question why I haven't taken MM and
>> Sim Balancing more seriously. :-)
>>
>> -----Original Message-----
>> From: computer-go-bounces at dvandva.org
>> [mailto:computer-go-bounces at dvandva.org] On Behalf Of Petr Baudis
>> Sent: Monday, April 04, 2011 10:27 PM
>> To: computer-go at dvandva.org
>> Subject: Re: [Computer-go] 7.0 Komi and weird deep search result
>>
>> On Mon, Apr 04, 2011 at 12:56:54PM -0400, Brian Sheppard wrote:
>>
>>> >> MCTS using RAVE prioritization *does* converge to game theoretic >>
>>> values
>>> in a
>>> >> binary-valued space.
>>>
>>> >Can you reference some more detailed analysis claiming this?
>>>
>>>
>>>
>>> Theorem: In a binary-valued game of finite length, the RAVE score of all
>>> winning moves converges to 1, provided that 0 < FPU < 1.
>>>
>>
>> Oh of course, it is obvious. Sorry for being slow and confused.
>>
>> But it seems it should be possible to prove that even theoretical
>> convergence in case of RAVE discrepecancies is much slower than with
>> plain UCT... Might be a fun exercise.
>>
>> Petr "Pasky" Baudis
>> _______________________________________________
>> Computer-go mailing list
>> Computer-go at dvandva.org
>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>>
>> _______________________________________________
>> Computer-go mailing list
>> Computer-go at dvandva.org
>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>>
>> _______________________________________________
>> Computer-go mailing list
>> Computer-go at dvandva.org
>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>>
>> _______________________________________________
>> Computer-go mailing list
>> Computer-go at dvandva.org
>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>>
>
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20110406/67e53f4f/attachment.html>


More information about the Computer-go mailing list