Kenneth Regan wrote on Fri, Jan 4, 2013 05:13 AM UTC:
The horizon of action, also called the depth d, has more influence than the
branching factor b. The overall complexity is b^d (b raised to the power
of d), which can be re-written as 2^{d*log(b)}. A doubling of the
branching factor adds only 1 to log(b), and hence adds d to the exponent.
Whereas, a doubling of d adds d*log(b) to the exponent. OK, for b as low
as 2 this makes no difference, but for a healthy b like 30 it does.
Anyway, my intuition for why Go is so much more difficult points to the
long horizon, rather than the up-to-361 branching factor. Also in Shogi,
storming with pawns and the weaker pieces is much of the strategy, and
takes a long time---especially using paratroops. That horizon, rather than
the branching of paratroops, explains the greater difficulty for computers,
IMHO.
More simply put, I believe in a common version of Moore's Law for games,
phrased in terms of Laszlo Mero's concept of "depth of a game." Namely,
say two players are a "class unit" apart if the stronger one takes 75% of
the points in head-to-head play. Under the Elo system this corresponds to
roughly a 200-point rating difference (was exactly so before a re-basing on
logistic curves). The depth is the number of class units from "adult
beginner" to world champion. When I first saw reference to Mero's work
20 years ago, this was reckoned as 11 for chess (600 thru 2800), 14 for
Shogi, and "25-40" (sic!) for Go. If the CCRL 3200+ ratings for top
programs are accurate, then that corresponds well to computers knocking on
the door of the best Shogi players but being still tangibly behind. That
is, based on Moore's Law, top programs like Houdini on 8-core hardware are
at "Depth 13". Use of Monte-Carlo techniques may have computers further
along in Go than this idea would predict, however.
The horizon of action, also called the depth d, has more influence than the branching factor b. The overall complexity is b^d (b raised to the power of d), which can be re-written as 2^{d*log(b)}. A doubling of the branching factor adds only 1 to log(b), and hence adds d to the exponent. Whereas, a doubling of d adds d*log(b) to the exponent. OK, for b as low as 2 this makes no difference, but for a healthy b like 30 it does. Anyway, my intuition for why Go is so much more difficult points to the long horizon, rather than the up-to-361 branching factor. Also in Shogi, storming with pawns and the weaker pieces is much of the strategy, and takes a long time---especially using paratroops. That horizon, rather than the branching of paratroops, explains the greater difficulty for computers, IMHO. More simply put, I believe in a common version of Moore's Law for games, phrased in terms of Laszlo Mero's concept of "depth of a game." Namely, say two players are a "class unit" apart if the stronger one takes 75% of the points in head-to-head play. Under the Elo system this corresponds to roughly a 200-point rating difference (was exactly so before a re-basing on logistic curves). The depth is the number of class units from "adult beginner" to world champion. When I first saw reference to Mero's work 20 years ago, this was reckoned as 11 for chess (600 thru 2800), 14 for Shogi, and "25-40" (sic!) for Go. If the CCRL 3200+ ratings for top programs are accurate, then that corresponds well to computers knocking on the door of the best Shogi players but being still tangibly behind. That is, based on Moore's Law, top programs like Houdini on 8-core hardware are at "Depth 13". Use of Monte-Carlo techniques may have computers further along in Go than this idea would predict, however.