Quantum computers and Relative strength of best programs at chess/Chinese chess/go

#1 September 5th 03, 03:18 AM

"Paul" wrote in message
om...
Chess and Go are finite games and therefore can be solved (played
perfectly). Probably the first time this will happen is when quantum
computers get up and running (20 or 30 years). A quantum computer puts
*all* possible answers in a superposition, and selects the *one* best
answer from that superposition.

Also, RE one of the sub-threads, it is possible to store as much
information as you want using just 3 elementary particles (in
principle). There is a limit if space is quantized. You encode
information by adjusting the distance between two boundry particles
and the frequency of an intermediary photon (e.g.), since there is
resonance only at factors of the distance.

Paul

This is just a restatement of the naive belief that quantum computers
can carry out arbitrary exponential parallelism. They can't. Or at
least nobody can see how they can. For example, you could solve a
problem like 3-SAT by considering all possible 2^n truth assignments
and picking the satisfying assignment, if there is one. But in fact no
NP-complete problem is known to be in quantum polynomial time.

The sorts of parallelism you can get on a quantum computer is of a
very limited nature. Explain how to reduce go to a problem of
factoring large numbers and you might convince me.

#2 September 5th 03, 03:39 PM

"John P. Green" wrote in message

The sorts of parallelism you can get on a quantum computer is of a
very limited nature. Explain how to reduce go to a problem of
factoring large numbers and you might convince me.

We assume that merely by increasing the computing power that the programs
will become better, which isn't true. Computing power will increase faster
than go program playing strength for the forseeable future.

Another thing I'd like to mention. Go programs which don't learn can never
be dan strength. At some point there is a future point you can only get to
by learning. Learning how to apply all the static information you have
accquired.

Computers which attempt to read can never be any good at go. They are in
effect trying to solve the game. If you want to limit the searches, you are
in effect thinking for the program, and if people were ant good at that then
we'd have professional strength go programs.

So remember how you learned go, and start from there. Never try to "program"
a go program to "do" anything.

-frl

#3 September 5th 03, 05:45 PM

"John P. Green" wrote in message
The sorts of parallelism you can get on a quantum computer is
of a very limited nature. Explain how to reduce go to a problem
of factoring large numbers and you might convince me.

"Fu, Ren-Li" wrote:
We assume that merely by increasing the computing power that the
programs will become better, which isn't true. Computing power will
increase faster than go program playing strength for the forseeable future.

Everything "Fu, Ren-Li" has posted on this thread rings so
patently false that one wonders if he is deliberately trolling, or is
manifesting yet another instance of "endless" pathological lying.
Increases in computing power will generally yield slight increases
in apparent program strength, because the lookahead window will
be pushed out slightly by additional time-enabling, however slight
or insignificant the degree of improvement might be. Most programs
do not compute during player's think-time, so programmers could
also come up with strategies to re-utilize player's think-times, too.
Of course the simple doubling of processor speed does not double
the program's rating, or ability, yet since it was already accepted that
the fan-out problem was exponential, and not linear, there was no
expectation on anyone's part that increases in "go program playing
strength" should -match- increases in "computing power."

Another thing I'd like to mention. Go programs which don't learn
can never be dan strength. At some point there is a future point you
can only get to by learning. Learning how to apply all the static
information you have accquired.

It is simply unknown whether learning heuristics are necessary
for presentation of dan strength, even though most everyone agrees
that having some form of learning heuristics is a -very- good idea.
There is, perhaps, a -very- strong playing level "out there" which
would require learning heuristics, though the kyu-dan barrier is
not necessarily the rubicon whereby that -very- strong playing level
breaks, one way or another.

Computers which attempt to read can never be any good at go.
They are in effect trying to solve the game. If you want to limit the
searches, you are in effect thinking for the program, and if people
were ant good at that then we'd have professional strength go programs.

One wonders what "Fu, Ren-Li" means by "reading" since programs
generally spend about three times as much doing "reads" as "writes."
Let's assume that he means "reading" in the sense of attempting to
"solve the game" (whatever this means -exactly- was not specified).
There is no necessary requirement that reading for solving the game
implies a limitation on searches. Indeed, the -opposite- should also
be the case: that a wide-open throttle for full reading, which attempts
to "solve the game", is the approach which separates weaker programs
from stronger programs. Of course there is also time-clock management
to consider, so those lookaheads will need to be budgeted generally.
In many positions there might be a horizon where further lookaheads
do not reveal any information significantly different from particular
lookaheads already invested. When speaking of "solving the game"
it should be pointed out that Go can, at times, be broken apart into
several sub-games, through partitioning schemes which are, more
or less, reliable as a means whereby reduction in search-space is
enabled. Of course much of the game progresses without an obvious
way to obtain partitioning schemes, but this does not imply that some
program improvements are not available during latter mid-game or
entry into end-game, once partitioning schemes are more clearly
evident. Having partitioning schemes means that each sub-position
can be treated as an independent game applied into CGT analysis
for _yose_ without which no ultimately successful program can be
without.

A further remark, which may quite likely be lost on "Fu, Ren-Li"
(since he brags about using a "killfile" on me). The fact that we do
not have "professional strength go programs" does not mean that
people are not any good. The goodness/badness of people has
very little relationship to associated playing strength at boardgames.
Undoubtedly, "Fu, Ren-Li" has continued along a course of life where
this sort of message has not yet percolated to his ears, so if there is
some important reason why he should hear it now, then I'm fairly
confident that some readers out there may forward this posting to
him via private email, or repost the message in entirety to bypass
those ignorance-causing effects of his "killfile" filters.

So remember how you learned go, and start from there.
Never try to "program" a go program to "do" anything.

Why not? Playing a strong game is a workingman's endeavor.

- regards
- jb

#4 September 5th 03, 07:09 PM

Fu, Ren-Li wrote:
"John P. Green" wrote in message

The sorts of parallelism you can get on a quantum computer is of a
very limited nature. Explain how to reduce go to a problem of
factoring large numbers and you might convince me.

We assume that merely by increasing the computing power that the programs
will become better, which isn't true.

I don't know how you mean that, but the first three interpretations
I came up with are false. In particular, a program that can read a
hard life-or-death problem over-the-board will be objectively better
than one that cannot. As computing power increases, programs that
can solve these problems will get better at them. Additionally, nearly
forced situations such as ladders with some options can be read more
accurately if you have more computing power... the more power you have,
the more options you can read.

Computing power will increase faster
than go program playing strength for the forseeable future.

I don't know how you're measuring this. Do you mean that if a CPU
runs twice as fast your program doesn't get twice as good? I'm not
sure what that means -- perhaps that it beats a randomized version
of itself twice as often with the additonal speed? Or that it beats
a 9p player twice as often with a 25-stone handicap? Either way, I
regard this as unobvious at best.

Another thing I'd like to mention. Go programs which don't learn can never
be dan strength.

This isn't at all obvious to me, depending on what you mean by
learning. Is it "learning" if the programmers inject all the
recently discovered theoretical opening improvements into the
program as they're reported in the go literature? None of the
top chess programs do what a human would call learning, and yet
they play very well indeed compared to humans. I'm not suggesting
that the methods that work for chess will also work for go -- but
simply that it's not clear to me that there isn't *some* strategy
that would lead to a dan-level program without human-style learning.

At some point there is a future point you can only get to
by learning. Learning how to apply all the static information you have
accquired.

True enough for humans, but of course that's the only way we
*can* improve. Computers operate differently from humans: better
in some ways, worse in others. What works best for a program may
be nothing like methods used by humans.

Computers which attempt to read can never be any good at go. They are in
effect trying to solve the game. If you want to limit the searches, you are
in effect thinking for the program, and if people were ant good at that then
we'd have professional strength go programs.

I'm guessing you haven't studied game-playing by computer at all,
right? Reading (in the go sense) is necessary to solve life-and-death
situations and ladders, and it's one of the few places where you *can*
apply the calculating strengths of computers effectively. It doesn't
mean that you're trying to solve the game globally, but it does mean
that you usefully explore the value of a tactical situation. Do you
mean instead that they can't progress far if they attempt to use the
same algorithm for choosing a move in a fuseki that they would use for
tsume-go situations? If so, I'll agree with you for once.

So remember how you learned go, and start from there. Never try to "program"
a go program to "do" anything.

This is opaque to me. What works best for humans may not be what
works best for programs -- compare, again, with the situation in
chess programming, where the best programs don't use anything like
the thought process humans would use for their analysis.

Despite disagreeing with all of your specifics, I will go on record as
saying that I believe no 9-dan pro level program will appear in the
next two or three decades, and that quantum computing will have no
significant effect on whether these exalted levels can be reached by
a program.
--
Jim Gillogly
Highday, 9 Halimath S.R. 2003, 00:00
12.19.10.9.17, 7 Caban 5 Mol, Eighth Lord of Night

#5 September 5th 03, 07:10 PM

On 5-Sep-2003, wrote:

Everything "Fu, Ren-Li" has posted on this thread rings so
patently false

Oh, for the love of Mike, jb! It is so obvious that you want Fu Ren-Li, and
are sublimating your desire in this transparent way! Chill out!!! Go to the
gym. Find some guy who wants you!

#6 September 5th 03, 07:51 PM

wrote:
Everything "Fu, Ren-Li" has posted on this thread rings so
patently false that one wonders if he is deliberately trolling, or is
manifesting yet another instance of "endless" pathological lying.

From: "Timothy Little"
Oh, for the love of Mike, jb! It is so obvious that you want Fu
Ren-Li, and are sublimating your desire in this transparent way!
Chill out!!! Go to the gym. Find some guy who wants you!

Your words, not mine. You managed -not- to post anything
related to the topic, which means your splooge did not accomplish
anything at all, except establish how easily you are manipulated.

- regards
- jb

#7 September 5th 03, 08:10 PM

In message , -
writes

- regards
- jb

Last word, as ever.
--
T Mark Hall
http://www.gogod.demon.co.uk

#8 September 6th 03, 10:49 PM

"Jim Gillogly" wrote in message
news

Fu, Ren-Li wrote:
"John P. Green" wrote in message

The sorts of parallelism you can get on a quantum computer is of a
very limited nature. Explain how to reduce go to a problem of
factoring large numbers and you might convince me.

We assume that merely by increasing the computing power that the
programs
will become better, which isn't true.

I don't know how you mean that, but the first three interpretations
I came up with are false.

Then I will clarify by responding to what you said.

In particular, a program that can read a
hard life-or-death problem over-the-board will be objectively better
than one that cannot.

My original point was that this is not true. Sure, the program would be
better "in life and death situations" but I am saying that this is a dead
end road. There are other things that a program must do besides brute force
reading. For example.. 9x9 go is not solved. So the local reading would take
place within a 9x9 square area. This can't even cover most josekis.

As computing power increases, programs that
can solve these problems will get better at them. Additionally, nearly
forced situations such as ladders with some options can be read more
accurately if you have more computing power... the more power you have,
the more options you can read.

True.. but I mean to say that out of 300 moves, 10 are good. Out of those
10, 2 or 3 are high quality and perhaps only one is the proper move. But if
you analyze any particular situation, there is a "right" local move. Let's
say white creates a splitting attack on three groups. Which one will black
attempt to save? A "reading" computer has to do more than mere reading to
answer this... assuming that reading is not an option.

We may find that a so-called quantum computer produces moves that would be
impossible for any human to find, and that we could not learn from it
because there would be no explanation, and the moves too random-looking even
to professional eyes.

Computing power will increase faster
than go program playing strength for the forseeable future.

I don't know how you're measuring this. Do you mean that if a CPU
runs twice as fast your program doesn't get twice as good?

Yes that is exactly what I mean. Doubling computing power in some cases
makes no real difference in a computer go program's playign strength.

Another thing I'd like to mention. Go programs which don't learn can
never
be dan strength.

This isn't at all obvious to me, depending on what you mean by
learning.

Well perhaps if you sit and think about it, it will become clear. Perhaps
not.

At some point there is a future point you can only get to
by learning. Learning how to apply all the static information you have
accquired.

True enough for humans, but of course that's the only way we
*can* improve. Computers operate differently from humans: better
in some ways, worse in others. What works best for a program may
be nothing like methods used by humans.

I know, but the brute force method might not work for go.

So remember how you learned go, and start from there. Never try to
"program"
a go program to "do" anything.

This is opaque to me.

I'm insinuating that we need to create neural nets which play go. Give them
a couple terabytes and see what happens.

What works best for humans may not be what
works best for programs

And then again maybe it would work best for programs.

-- compare, again, with the situation in
chess programming, where the best programs don't use anything like
the thought process humans would use for their analysis.

That's because bruteforcing works for chess, right? Think about it.

Despite disagreeing with all of your specifics, I will go on record as
saying that I believe no 9-dan pro level program will appear in the
next two or three decades, and that quantum computing will have no
significant effect on whether these exalted levels can be reached by
a program.

Why?

-frl