Author: Peter McKenzie
Date: 10:39:33 11/27/02
Go up one level in this thread
On November 27, 2002 at 00:34:45, Russell Reagan wrote:
>While I was at work tonight sitting at a computer, having nothing to do, I
>opened up the calculator program and started playing around with the branching
>factor for the game of go. I quickly realized that with such a large branching
>factor at each level (361 from the starting position), it's no wonder computer
>go programs play well below master level.
>
>Are there any games that have a high branching factor that computers are good
>at? The only games that I'm somewhat familiar with are chess, checkers, and go.
>Of those, it seems that the branching factor of the game largely determines how
>well computers play them. It seems that checkers with the lowest branching
>factor gives humans the hardest time, then chess, and then go with a much larger
>branching factor is not even in the same ballpark with the top humans.
Like most people, you make the mistake of assuming it is the high branching
factor that makes it extremelly hard to write a strong Go program. This is NOT
the main reason.
Buy far the main difficulty with Go is making a good (and fast) evaluation
function.
For example, there can be large groups of stones in Go that will eventually die.
Now if you score those stones as alive, you will get a terribly inaccurate
evaluation. Working out if stones will live/die is very difficult, and usually
requires some sort of (slow) search for a half decent approximation.
In terms of chess, you could think of a trapped queen. If you evaluate that
queen as you would evaluate a normal queen then your evaluation will be very
inaccurate. Now trapped queens don't happen very often in chess, but that sort
of thing happens *all the time* in Go.
Another big difficulty of Go is the fuzzy nature of determining when a game is
finished! There are even several grey areas ('bent 4 in the corner') in the
rules, and two different versions of the rules, when it comes to scoring the
game.
Peter
>
>Does this relationship between branching factor and computer strength hold for
>other games? Or do some games break the pattern? If some games do break the
>pattern, why? Simplicity of the game? Magical shortcuts?
>
>Russell
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.