Check out Symmetric Chess, our featured variant for March, 2024.

Enter Your Reply

The Comment You're Replying To
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.

Edit Form

Quick Markdown Guide

By default, new comments may be entered as Markdown, simple markup syntax designed to be readable and not look like markup. Comments stored as Markdown will be converted to HTML by Parsedown before displaying them. This follows the Github Flavored Markdown Spec with support for Markdown Extra. For a good overview of Markdown in general, check out the Markdown Guide. Here is a quick comparison of some commonly used Markdown with the rendered result:

Top level header: <H1>

Block quote

Second paragraph in block quote

First Paragraph of response. Italics, bold, and bold italics.

Second Paragraph after blank line. Here is some HTML code mixed in with the Markdown, and here is the same <U>HTML code</U> enclosed by backticks.

Secondary Header: <H2>

  • Unordered list item
  • Second unordered list item
  • New unordered list
    • Nested list item

Third Level header <H3>

  1. An ordered list item.
  2. A second ordered list item with the same number.
  3. A third ordered list item.
Here is some preformatted text.
  This line begins with some indentation.
    This begins with even more indentation.
And this line has no indentation.

Alt text for a graphic image

A definition list
A list of terms, each with one or more definitions following it.
An HTML construct using the tags <DL>, <DT> and <DD>.
A term
Its definition after a colon.
A second definition.
A third definition.
Another term following a blank line
The definition of that term.