Re: computer-go: Good Play (was FPGA)

[Rich Brown <rbrown@xxxxxxxxxxxxxxx>]

There's literature out there that deals with some of these issues.

Andre Engels wrote:

> Don Dailey wrote:
[There could be an objective formulation of what a "difficult" game is.]

> And it gets even more difficult when we want to include games with random
> elements (like Backgammon) or imperfect information (like bridge) in our
> comparison.

Yes, quite so.  However, if, for the time being, the domain is
restricted to two-player, zero-sum games of perfect information,
then some of this work has already been done.

There was a _Scientific_American_ article from the early '80s which
showed that, if you reduce any such game[1] to a binary decision tree,
then you have a game--I think the authors called it "Roadrace"--where
your opponent drives his car across the tree, one intersection at a
time, alternating with you driving yours.  A move may establish a
"roadblock" for the foe (by making it impossible for him to choose
certain forks in the road).  Destination is a node where you've won.

I forget precisely how they calculated their hard numbers, but using a
certain metric across the binary decision trees for each game, they
showed a relationship whereby the difficulty of the games was such that
the difficulty of go > (that of) chess > checkers > tic-tac-toe.  The
difficulty was quantified not by the _size_ of the tree alone, but also
by the ways in which future states depended on previous choices, that
is, to what degree "roadblocks" pruned the tree for future choices.

One interesting thing they showed was that you could "convert" a chess
game into a go endgame by finding identical binary decision trees for
them.  Not always vice-versa, though.

Because go boards can be of an arbitrary size (or even shape!) without
affecting the essential character of the game--indeed, even handicaps
don't affect the essential character of the game--it is possible to
map _every_ chess game into some go endgame.  In that way--converting
the games into their binary-tree representations--games of chess (and
games of checkers, and of tic-tac-toe) may be _subsumed_ into go games.

One thing I found quite interesting about this research was that they
considered various sizes of go boards (square only) and showed that--
as one might expect--the difficulty of the game increases as the size
of the board increases.

For convenience, they considered only boards with a central point
(that is, with an odd number of lines each way).

My memory is a bit faulty, but if I recall correctly, they asserted
that adding a single line around the edge (for example,, going from a
15x15 board to a 17x17 one) increased the difficulty level as a triple
exponent of the previous size's difficulty.  So, if 9x9 go (which, by
the way, they calculated to have about the same level of difficulty as
that of chess) had a difficulty of, say, D=2, then 11x11 go has a level
of difficulty of 2**(3*2)==64, and 13x13 go has a difficulty level of
64**(3*3) which is about 1.8*(10**16) and so on.  It skyrockets!

Setting D=2 for 9x9 go was my arbitrary choice, but I am fairly certain
I have remembered the claim accurately:  In general, the difficulty of
a particular size of go board, Dsub(n) == Dsub(n-1)**(3*(n-1)) as in
this table:

Board           n    Dsub(n)
-----           -    -
 9x9            1    2
11x11           2    2**(3*1) == 8
13x13           3    8**(3*2) == 262144
15x15           4    262144**(3*3)  ~= 5.8 * (10**48)
17x17           5    (262144**(3*3)) ** (3*4)  ~= 1 gazillion, by God!
19x19           6    ((262144**(3*3)) ** (3*4)) ** (3*5)
21x21           7    (((262144**(3*3)) ** (3*4)) ** (3*5)) ** (3*6)

And so on.  (This is _way_ faster of an increase for each n than that
thing with the grains of rice on the chessboard, where they merely
double each time!)  I probably should have picked a smaller number than
2 to begin with (where n==1).  But I think I got that triple exponent
deal right, as fantastic as the claim might seem.  

Anyway, it was their claim, not mine.  That's just how I recall the
article.  I'm not sure whether or not I still have a copy.  I'll take
a look around, and report back.

Rich

[1]That is, _any_ two-person, zero-sum game of perfect information.

-- 
Richard L. Brown       Office of Information Services
Unix Guy               University of Wisconsin System Administration
                       780 Regent St., Rm. 246
rbrown@xxxxxxxxxxxxxxxxx        Madison, WI  53715