|
The massive branching factor is of course one of
the largest obstacles, but it isn't the most important: even if one could look
ahead 12 moves, there is no clear evaluation heuristic for board positions which
comes close to h*.
I.e., in chess you can just count material value
and maybe have a small pattern database for elements of good position (ie:
strong castle'd king in the midgame is (almost) always nice). In
go....there is nothing quite as obvious or effective.
The main reason behind this, I feel, is that it is
very difficult to set up a position that is truly unassailable -- and doing so
early in the game usually means that you end up losing (because one played too
slowly). So counting the 'value' of a board position is very difficult
since any particular piece of the board that you decide to claim as 'yours'
could easily be invaded until very very late in the game. (what you do is
make sure that being invaded is unprofitable in the long run (the sneakier you
are, the longer it takes before it is obvious that it was unprofitable), but
possible)
The other reason that the traditional search model
developed for chess fails on go is that, in go, greedy play loses.
Attempting to maximize any naive heuristic value over a lookahead tree is the
essence of greediness -- and it will cause one to end up with a weak
position. Of course, if one had non-naive heuristic (something reasonably
close to h*) then it would be a different matter -- but as that isn't the case,
the trick is to have several heuristic functions which attempt to describe
various attributes of a board (the two most important being territory and
power), and try to maintain a balance between them, and between the two players,
for the majority of the game. 'Real' games are won by as little as 1
point, and as much as 7-10 points -- games that are won by more than that
indicate serious errors of judgement. (one starts to earn handicaps if one
loses by more than 10 points). Which makes sense, a long game with a huge
branching factor between even players should end evenly most of the time.
(as opposed to a short game with a small branching factor, where landslide
victory should be common, and 'even' players would have even records over many
rounds of play).
That, at least, is my opinion, having destroyed the
strongest computer opponent I have available over and over and over .... again
;).
-Will
----- Original Message -----
Sent: Friday, September 26, 2003 3:48
AM
Subject: Re: Game Playing: Chess vs.
Go
Yes--GO is still quite beyond computers (because
of the massive branching factor
involved even a small look ahead turns out
to be infeasible apparently).
I am going to mention it as part of
"state of the art" discussion at the end of the
adversarial search lectures
(which is likely on next Tuesday)
Rao
At 10:06 PM 9/25/2003,
you wrote:
Dr. Kambhampati,
First I
wanted to say that today's lecture was the most enjoyable yet. I liked
the talk on chess and game playing, but I was a little disappointed that
you
didn't mention a new goal for AI game agent: building a go (also
called weiqi
in chinese) playing program. The book mentions it in
passing, and it's kind of
curious that only the Japanese seem interested
in funding a serious effort into
Go AI research. IMHO, the
simplicity and the elegance of the rules of Go, make
for a much more
interesting and challenging topic than chess (not to disparage
chess
fans).
There's an article that I found that talks about it from an AI
perspective.
The section of Go AI complexity seems to complement
our current discussion
fairly well.
http://ai-depot.com/LogicGames/Go.html
Here is a
websit on Computer Go. Apparently, the strongest Go playing program
out there is ranked at 6 kyu, the equivalent to an experienced
amateur.
According to the author, it accomplishes this by using a
pattern database.
http://www.reiss.demon.co.uk/webgo/compgo.htm
Regards,
Yicheng
|