Re: computer-go: A little Arithmetic

[Marco Krüger <grisu@xxxxxxxxxxxxxxx>]

I do prefer using information entropy to sort out rules, but I do not
think
why I should search any space that human being never landed. If a 9K
program
wants to do it, that is fine to me. I have bunch of 14K programs were
doing
that, I guess.

GO was created just about 2000 years ago, there are very limited games
played since then, comparing to the hypothetical large number we put
here
and there. If considering 0.5-point difference is a tie (or 2.5-point,
what
ever), otherwise a win or loss, the game only has three output: win,
tie,
and loss, not a 25-point swing case. If this is a-priori, will this
hurt?

A 3-layer ANN, by default, uses same number of weights towards any of
its
middle layer nodes. I doubt the ANN will have any advantage towards a
rule-learning system, if input and output are all discrete values. Added
disadvantage is that the overfit or underfit condition is hard to
determine
under ANN.

As a chemical reaction based computer (human brain) can barely scan
couple
thousands sample data with bunch of rule-of-thumb to figure out a 9K
evaluation formula, or be a supper player (e.g., 9K+), 361 modern
computers
supposed to check all games human ever played would not have a single
solution, what kind of model, architecture, or induction we were using?

Weimin

----- Original Message -----
From: "Nicol N. Schraudolph" <nic@xxxxxxxxxxxxxxxxx>
To: <computer-go@xxxxxxxxxxxxxxxxx>
Sent: Tuesday, November 14, 2000 7:21 AM
Subject: Re: computer-go: A little Arithmetic


> Let's say we have 362 computers (361 computers evaluate positions and one
> does everything else), and 1000,000 good games (not 100,000). Assume every
> good game has about 250 moves, and no duplicated board configuration and
> move (even though we know many of them will be duplicated configurations.)

You are asking a learning machine to pick a good position evaluation
function from a vast space of possibilities, based on very little data:

The 143 gigabit of information you assume (572 bits per position times
250 million) allow a maximally efficient learner to at best reduce its
search space by a factor of, well, 2^(143 x 10^9).  Assuming you want
to represent swings up to +/-25 points accurately, your search space
contains nearly 50^(3^361) = 2^(10^173) hypotheses.  One needs on the
order of 10^160 times more data than you propose to have a shot at it.

The fundamental point is: you can't learn much of interest (in any
area) unless you make strong a priori assumptions about the nature
of what you want to learn.  These serve to reduce the search space to
manageable proportions; in fact they are typically used to *define* a
manageable search space.  This is called selecting the "inductive bias"
(by learning theorists), the "model" (by statisticians), "architecture"
(neural networkers), or "representation" (everybody else), and it is
absolutely essential.

Give me a good representation for Go positions, and a million good
games,
and I can give you a good position evaluation.  This is the easy part;
we have both the know-how and (as you point out) computer resources to
do that.  The bad news is that while learning can bridge the last 11
orders of magnitude (or however many bits your computer can handle),
the hand-crafting of a good representation has to cover the other 160.
This is what currently limits machine learning (indeed, all) approaches
to computer Go.

Best wishes,

- nic

--
    Dr. Nicol N. Schraudolph
    IDSIA, Galleria 2
    CH-6928 Manno, Switzerland
    http://www.idsia.ch/~nic/