[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: computer-go: minimax and go
From: Heikki Levanto <heikki@xxxxxxxxxxxxxxxxx>
Yes, of course we need some sort of searching. Probably more than "just"
local string battles, but I believe that a global search alone will not be
practically possible in the next few decades or centuries.
I offered a theoretical model that I don't personally take seriously.
My goal was to construct (on paper) a model that has these
characteristics:
It plays Go.
It plays better Go with better hardware.
It plays perfect Go given "enough" hardware.
This was enough to demonstrate that it is possible to write a scalable
Go program. I didn't try to prove it was possible to write a scalable
Go program that is very good on CURRENT hardware, but I believe this
is possible. Perhaps some programs already exist that are like this.
Yes, I think it will involve global search. I didn't say fixed depth
full width search. I envision something like you describe in the next
paragrah.
These discussion always degrade to considering Go as having a
branching factor of 361 and a calculation of how much power it takes
to do a full width search to 1000 ply. But that is not the model that
makes any sense. There are many opportunities in Go, to be selective.
The Chess model of looking n ply deep and looking at everything was
even abandonded in Chess (although it actually still works reasonable
well, selectivity is still much better.) Go might respond extremely
well to a very sophisticated pruning mechansism. String searches
might be considered a part of the evaluation of a position although
they would have to be generalized tremendously (you need to hash the
result of little local searches and even more than that, you might
need to generalize the result so that minor configuration changes
don't get researched whenever possible.)
Or rather I believe that if there will be a global search, it will not be
directly related to the board image, but happen on a much higher level. For
example considering an invasion here, the search might jump directly (via
some patterns, one local search, or other means" to the seven most likely
results of that invasion, and only if it decides to make that invasion, it
will read it out in more details, and check that those fit in the global
"search". I guess this sort of search would better be called planning.
I believe this sort of approach is much more reasonable in go than in chess,
because the local subproblems are so much less interconnected.
No, I have no guaranteed path to prove that this approach (or any other)
will eventually provide a perfect player. I only have a strong gut feeling
that such a thing will not be seen in the next few centuries...
Have you calculated on your model: How much more computing power would you
need to get a perfect chess player? Assuming Moore's "law" holds, how long
would *that* take? And how long until we can have your perfect go player,
that searches the whole game? If we assume that there are some theoretical
limits on the size and speed of a processor (a switching unit the size of
electron, not working faster than light goes through it, perhaps), how fast
can this thing of yours ever play? How many parallel processors will it
need? Will there be enough material and time in the universe to play the
perfect game?
The universe is far too small, light is too slow to ever search the
entire game tree within a few billion years. But my argument is
theoretical. The practical goal is not even to play good Go, it's to
play "better" Go than we did yesterday with a computer.
There are two ways in which we could push forward:
1. Make the programs better (even on the same hardware)
2. Stop wasting computing power.
But I believe 2 is exactly the same as 1. If there exists, a
theoretical best possible Go program that will run on a 200 MHZ
pentium, it should play better on 1200 MHZ computer.
-H
--
Heikki Levanto LSD Levanto Software Development heikki@xxxxxxxxxxxxxxxxx
"In Murphy we Turst"