[ List Latest Comments Only For Pages | Games | Rated Pages | Rated Games | Subjects of Discussion ]
Comments by Kenneth Regan

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.
2 comments displayed
Permalink to the exact comments currently displayed.