[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] Computer Olympiad photo
Thanks for your interesting listing Don,
I hope you realize that the local tactical search in the todays go programs
are searching at hundreds of thousands of nodes a second, if not more, so
they are a phase further than chessprograms in that sense.
The 3000 nps i got a few years ago are a joke compared to these speeds.
Where i refer to and what is a big difference with chess, is that in go
once a pattern is put to the board it lays there forever when it cannot get
captured.
In chess that is not the case. Most patterns continuesly keep changing.
the center is very important in chess. In go it is not so important like it
is in chess in the opening.
A weak chessprogram by just centralizing pieces can get a good level when
compared to a go program.
The real branching factor in chess is far smaller than the theoretical and
practical one.
That's why todays software like shredder is easily searching 19 ply in the
middlegame in a very selective way.
It would be a mistake to say that it is impossible to search 19 ply in go.
The fact is however that laying down a few patterns on the board, already
takes like 50 ply to recognize it.
*that* is the problem.
With a branching factor of 10 in 19x19, it will be not so easy to get to 50
ply in the decisive openings phase of the game.
I'm under the impression that the strong go players spent all their time
onto the first few moves in this game. Perhaps some stronger players can
give confirmation onto this?
Because if this is the case, beating go players with a brute force search
is going to be far from easy.
Go programs using the same selectivity still will have branching factors of
8.0 - 9.0.
So i hope that at least for those who focus upon search, the problem is
made clear.
Note that chess programs search very selective nowadays and that the only
big progress of the last 4 years has been in the knowledge of the
evaluation function and openingsbooks, not so much search.
>From the last 3 tournaments diep played, the DECISIVE errors not long after
diep had left book, they took place at depths of around 10-13 ply, when i
searched them at 24 hours a move, so getting depths of up to 20 ply, the
vaste majority of moves still were played. Only 1 of the moves another 2
ply was helping (i simply got too small of a search depth with my slow
knowledge oriented chessprogram which is not so selective like most top
programs are).
So where overwhelming brute force power would fix 1 move,
all of the errors i could easily fix by some improvements
in evaluation function.
Keeping that in mind, all the western european chessprogrammers which focus
upon go now, they do not have a chance without good go knowledge.
Best regards,
Vincent
At 13:24 4-12-2003 -0500, Don Dailey wrote:
>
>> My poor nameless go program searched 6 - 7 ply in 19x19 at 100-200Mhz
>> hardware a few years ago.
>>
>> Yet that's pretty useless when a pattern takes 150 plies to show its
use...
>
>It sounds like you have a solution. What is it?
>
>
>Let's get some historical perspective using chess.
>
>
>1. The earliest chess programs were (or tried hard to be) positional.
> That is because everyone "KNEW" that chess had little to do with
> tactics, a lot to do with human mastery and understanding. Of
> course they were lousy in all areas of the game (by our standards.)
>
>2. The programs made hillarious tactical blunders because computers
> could only do 1 or 2 ply searches.
>
> As a consequence, everyone "KNEW" you had to have a selective
> search. A selective search, in theory, would allow you to see far
> enough ahead to avoid silly tactical errors, thus allowing you to
> focus on the "real" game, not the distracting tactics.
>
>3. The experts kept making fun of the programs, mostly because of
> their ridiculous positional errors although their tactical errros
> were laughable too. We laughed too, because we "knew" there was
> nothing that could be done. A simple calculation showed that it
> would take ENORMOUS computing power to get even 1 more move ahead
> and it was obvious to even the stupidest of us that 2 moves was not
> even close to what we needed. CHESS is a deep game for humans and
> not something computers would ever be good at. (Does this sound
> familiar?)
>
> At the same time, we were convinced that to even think about
> progress we should be spending even more effort on highly selective
> programs. These programs needed to be incredibly smart to make up
> for the lack of computing power (the idea that the slower the
> computer, the smarter it needs to be is a stupid idea which I'll
> explain later.)
>
>4. A university team decided to write a brute force program. They
> were frustrated with attempts to write smart selective programs.
> SUPRISE! The program was amazingly strong for the time and
> dominated computer chess for a few years.
>
> Suddenly there was a major shift in thinking. For a while it was
> all about brute force and selective search was mostly discarded,
> even though everyone knew brute force was not the right approach.
> How could it be right? That's now how humans play chess therefore
> it must be wrong.
>
> Still, at this point in time computers were weak. 5-6 ply searches
> was about the depth the fastest machines were achieving. On the
> one hand it was "very clear" that brute force was not the way to
> achieve mastery and it was foolishly predicted by some that
> computers had reached a "conceptual barrier" where they would not
> get any stronger no matter how fast they got. This fallacy was
> based on the notion that extra speed would not make them "smarter"
> in the chess uderstanding sense of the word and that the tactics
> were pretty much irrelevant once they were "reasonably competent."
>
> People sometimes put facts together in emotional ways and come to
> wrong conclusions. It was actually chess masters who were the most
> negative about progress, perhaps because they felt they possessed
> something no computer could match.
>
> The truth of the matter, in my opinion, is that humans are not very
> good at knowing what it really takes to be good at something. We
> can become good at things, but we cannot always explain why or we
> get confused about which skills actually had the most relevance.
> Chess programs today are VERY GOOD at chess, but not for reasons
> that fit our ego-centric notions of how things should be.
>
> I remember one strong player pointing out a bad move a computer had
> made and proclaiming that no (USCF) 1600 player would make that
> kind of error, and therefore the computer must be weaker than 1600.
> He did this based on a single move observation. It turns out the
> computer he was talking about had actually achieved a 2000 USCF
> rating in the US. People argued whether it was really that strong,
> but it could certainly take 1600 players apart without a lot of
> trouble.
>
> And yes, it made some moves not worthy of a 1600 player, but then
> even grandmasters have made the most foolish of errors on
> occasions.
>
>5. After the brute force era, selective search programs based on
> estimating a conservative bounds on the score began to surface.
> Usually this was in the form of NULL move pruning, which was easy
> to implement and relatively safe. These programs seemed to have at
> least a 50 rating point edge and to this day the very strongest
> programs use this.
>
>
>The term "selective" is like the term "AI", when something labeled AI
>loses it's magic, it gets redefined so it's not called AI any longer.
>Computer chess used to be called AI. Computer GO is AI now because it
>is "hard." If computers ever get really good at GO it will not be
>called AI because it can't be intelligent if a computer can do it.
>
>What lessons have we learned from chess? Do they apply to Go? I
>think they do. The lesson I take away is that we shouldn't be too
>quick to make assumptions about what will or will not work.
>
>In the old days of computer chess, when we were running with 2 MHZ
>Z80's we could only achieve 2 or 3 ply searches. We enjoyed our
>programs anyway and laughed at them, realizing no computer would ever
>play even close to master chess.
>
>Instead we concentrated on what worked the best. Most people stood
>back and criticized and pointed out why we would not succeed, but
>others kept trying, just because it was fun.
>
>We are doing that in computer Go.
>
>What I imagine happening in computer GO is a constant refinement
>and perhaps a few major shifts in thinking over several decades.
>Some of those shifts may simply be a response to what hardware is
>avaiable and therefore what we can do with it.
>
>
>Now,
>
>> the idea that the slower the computer, the smarter it needs to be
>> is a stupid idea which I'll explain later.
>
>Well then, why don't we start using old fashioned slower hardware so
>that can we write really smart programs?
>
>Computer chess programs have gradually gotten smarter, not dumber and
>it seems like a natural course. Yes, the searching is faster but most
>of the software progress is based on more intelligent programs.
>
>-Don
>
>
>
>
>
>
>
>
>
>
>
>
> The computer chess guys making 9x9 go programs will have the problem that
> the first few moves of the game can be decisive and they lack go knowledge
> there...
>
> At 17:26 3-12-2003 +0100, Erik van der Werf wrote:
> >Hiroshi Yamashita wrote:
> >> Dear all,
> >>
> >> I put some photos of Computer Olympiad in Graz, 23-27 November.
> >> http://207.218.206.38/~admin82/photo/graz2003/graz2003.html
> >
> >Thanks!
> >
> >> Aya search 4-5 plies in 19x19, and 6-7 plies in 9x9.
> >> Nodes per second is 200-300 nps in 19x19 and 500-600 nps in 9x9
> >
> >Just to be sure, is this speed in nps and not knps?
> >
> >At 500 nodes per second it's still nowhere near what the chess guys are
> >doing :-)
> >
> >Best,
> >Erik
> >
> >_______________________________________________
> >computer-go mailing list
> >computer-go@xxxxxxxxxxxxxxxxx
> >http://computer-go.org/mailman/listinfo/computer-go
> >
> >
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx
> http://computer-go.org/mailman/listinfo/computer-go
>
>_______________________________________________
>computer-go mailing list
>computer-go@xxxxxxxxxxxxxxxxx
>http://computer-go.org/mailman/listinfo/computer-go
>
>
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://computer-go.org/mailman/listinfo/computer-go