It's official: Go search space a fractal
Frank de Groot
fractal topology, and that it should be possible to use knowledge of the
fractal "hyperspace" to speedup searches astronomically.
My opinion is that "ordinary" search methods are wholly inadequate sod I am
not even going to *try* them.
I had yet no publications to back up my claim that zero-sum games of full
information are in fact fractals, but it apears there has been some work in
this area:
http://www.cs.cornell.edu/gomes/fract.pdf
(paid for by the good old US military :)
I am especially interested in "backtracking".
My original idea of a fractal topology of the Go search space included
"backtracking", something I have never read about until a few minutes ago. I
was happy to see that the above publication also emphasizes forms of
"backtracking".
If anyone can brainstorm/enlighten/add to this, feel free.
Just to clarify: The object of this brainstorming session is to find a
method that speeds up (fruitfully) searching the Go game space by an
astronomical factor, for example the square root of all quarks in the
universe compared to current efficiency - NOT marginal improvements to
search algorithms.
Frank
www.moyogo.com
fizzy
universe compared to current efficiency"
Uh, that would be about a factor of 10^40.
Frank de Groot
> "for example the square root of all quarks in the
> universe compared to current efficiency"
>
> Uh, that would be about a factor of 10^40.
Yes.
But as you know, the number of permutations needed to "solve" Go or even
naively think ahead deeply alledgedly is "more than all elementary particles
in the universe", therefore such a speedup is _needed_.
denis feldmann
acceleration by 10^40 (with a branching factor of more than usually 10
plausible moves at each turn (and this number is probably vastly
underestimated), you get a horizon at 50 moves ahead, still quite far
from the end of the middle game (usually 120 to 150 moves). And the
absence of an evaluation function at any intermediate depth makes
exhaustive searches a doomed-in-advance approach. In fact, my bet (for
the moment) is that a 10^40 speed-up on any existing program would not
raise its level by more than a few grades (except, perhaps, for the
weakest of them :-))
Frank de Groot
> acceleration by 10^40 (with a branching factor of more than usually 10
> plausible moves at each turn (and this number is probably vastly
> underestimated), you get a horizon at 50 moves ahead, still quite far from
> the end of the middle game (usually 120 to 150 moves).
So you are saying that my condition of a speedup of 10^40 is quite a modest
requirement?
I thought so <g>.
> And the absence of an evaluation function at any intermediate depth makes
> exhaustive searches a doomed-in-advance approach. In fact, my bet (for the
> moment) is that a 10^40 speed-up on any existing program would not raise
> its level by more than a few grades (except, perhaps, for the weakest of
> them :-))
To clarify: I was talking about a speedup for a new tree "search" algorithm
that provides a speedup over traditional search techniques.
The goal is not to speedup traditional techniques but find a radically new
technique based on the fractal topology of the search space.
Kirk McElhearn
> If anyone can brainstorm/enlighten/add to this, feel free.
> Just to clarify: The object of this brainstorming session is to find a
> method that speeds up (fruitfully) searching the Go game space by an
> astronomical factor, for example the square root of all quarks in the
> universe compared to current efficiency - NOT marginal improvements to
> search algorithms.
>
> Frank
> www.moyogo.com
Just stopped by your website... I had actually been wondering if the way
to make a more powerful go program wasn't to use a database of pro games
and have the program look for similar patterns and play accordingly. So
I see your program for analyzing games uses this idea; have you thought
about incorporating this into a playing engine?
Also, any chance of a Mac version?
Kirk
Frank de Groot
> to make a more powerful go program wasn't to use a database of pro games
> and have the program look for similar patterns and play accordingly.
This will work for Fuseki & Joseki and is even able to transcend the
knowledge of individual players, but it will hardly ever discover new
variations.
So it's nice-to-have and can enhance current Go software, but it is not the
solution to (non-trivial) Go problems. (The problems near the fringe of the
fractal boundary of the search tree).
> I see your program for analyzing games uses this idea; have you thought
> about incorporating this into a playing engine?
Yes, it will be in my future playing engine, heaven permitting :)
AFAIK I get better pro-prediction with that module alone than some
commercial Go programs / research projects, so it surely is something I
would want to use.
> Also, any chance of a Mac version?
I am having trouble enough as it is to roll out the first Windows version :)
When Free Pascal/Lazarus has become mature, there will be a Mac & Linux
version.
Kirk McElhearn
> > Also, any chance of a Mac version?
>
> I am having trouble enough as it is to roll out the first Windows version :)
> When Free Pascal/Lazarus has become mature, there will be a Mac & Linux
> version.
That's good to hear!
Kirk
John F Hall
Frank de Groot <fran...@online.no> wrote:
>But as you know, the number of permutations needed to "solve" Go or even
>naively think ahead deeply alledgedly is "more than all elementary particles
>in the universe", therefore such a speedup is _needed_.
But that assumes that any form of search is the way to go. *I* don't
play that way, nor aspire to do so - nor, as I understand it, do better
players :-).
Rather look-ahead is employing *locally* to establish the status of
groups and territories - and the factors that influence their status -
when the patterns aren't immediately obvious. Then separate *strategic*
analysis combines that into a determination of the moves to be played.
This perhaps raises a deeper point. Is the way to proceed to try and
understand how people play, or to develop a different "computer
technique" for playing?
--
John F Hall
Frank de Groot
> play that way, nor aspire to do so - nor, as I understand it, do better
> players :-).
Humans *do* use a form of search.
Imagining the consequences of move candidates is search.
> This perhaps raises a deeper point. Is the way to proceed to try and
> understand how people play, or to develop a different "computer
> technique" for playing?
I have a strong hunch that people's neural networks learn to use the fractal
topology of the search space to massively speed up theior search.
malweth
Last I heard was end of March.
Frank de Groot
> Do you have a new date you're aiming for (for the windows version)?
> Last I heard was end of March.
I stopped estimating a release date (it was probably a mistake to do that in
the first place).
One of the things slowing me down are fatal corruption of Windows on my boot
disk.
Not once, but about five times, this year. The last time it happened is a
few days ago.
I have gone as far as using a RAID1, but that of course doesn't help when
the RAM writes bad data to the disk.
The reason this time was specifying the wrong timings for the new RAM I
bought, which I bought because last month I had a fatal corruption of
Windows because the old RAM was rotten. It takes about a week of hard work
to recover from such a crash. I had a copy of a RAID1 mirror, but it worked
only a few hours, then i got a BSOD with UNMOUNTABLE_BOOT_VOLUME. The backup
of that backup refused to copy some files over the network (and Windows then
refuses to copy all the rest of the one-million odd files..)
Just before I got the last "crash", I discovered a showstopper bug that
makes it neccessary to re-build all the data for MoyoGo.
This takes several weeks, so I decided to speed that up by merging the
various cycles into one.
But I got a heavy fever in the meantime :)
So, as you see, the last 10% of software takes 90% of the time :)
I think it's not good to release buggy software so I will refrain from
mentioning release dates and it will simply be "ready when it's ready".
It is my hope that a first release will be ready before summer though.
Sorry if anyone is disappointed because of it. I work as hard as I can on
it, but I have accepted a full-time job three months ago so my original
estimations are invalid. MoyoGo looks small but it is almost one million
lines of code! (the great majority purchased from third parties, for things
as docking, SQL database engine, Rich Text editing etc.).
fre...@jellyfish.no
Go is known to be P-space complete, which (most likely) makes it harder
than the combinatorial problems of NP. A consequence of this is that
possible solutions of the search are exponential in size themselves.
We meet this in practice when we analyze, say, life and death problems:
To verify that a given black move lives, you must list all white's
replies,
giving blacks (single) response, all white's responses to those etc,
until the group has two eyes.
So, if you want to search 100 moves ahead, with no heuristic pruning,
there is no way you can inspect less than
(#opponent options) to the power of 50
variations (except for variations that grow back together,
but that is well known alpha-beta stuff).
Blind alpha-beta by itself reduces the exponent from 100 to 75,
compared to insepcting all possible 100-move sequences,
and perfect candidate ordering (which really means knowing the
solution)
reduces it to 50.
I like the "mechanical bird" analogy:
When people started making airplanes, they naturally tried to make
mechanical birds, but fixed wings and jet engines turned out better.
Alpha-beta search with a simple evaluation function is
the jet engine of chess, but not for go.
We're looking for it, but the jet engine for go may not even exist.
WinHonte ( http://www.jellyfish-go.com/ ) and other computer programs
therefore still follow the mechanical bird approach of imitating
the human thought process.
Fredrik
Bob Hearn
fre...@jellyfish.no wrote:
> Go is known to be P-space complete, which (most likely) makes it
> harder than the combinatorial problems of NP.
Actually, Go is even harder. It was indeed shown to be PSPACE-hard, by
Lichtenstein and Sipser:
D. Lichtenstein and M. Sipser, Go is polynomial-space hard, J. ACM
27 (1980) 393-401.
But that left open the possibility that it could be harder than PSPACE;
all that was shown was that it was *at least* PSPACE-hard. Robson later
showed that Go with Japanese rules is EXPTIME-complete:
J. M. Robson, The complexity of Go, Proc. IFIP (1983) 413-417.
This is what is to be expected based on basic properties of the game.
If the length of the game could be polynomially bounded based on the
board size, then it would be solvable in PSPACE, hence PSPACE-complete.
But due to ko (in fact potentially, due to general capturing) games can
last arbitrarily long. Therefore, the strategy of explicitly searching
all possible game trees cannot be carried out using only polynomial
space. However, a simple algorithm can determine the status of a
position in exponential time. Robson showed that exponential time is
required as well; therefore, it's EXPTIME-complete.
However! Note that I said Japanese rules. If you use the superko rule,
as in Chinese, AGA, and other rulesets, the situation gets much more
interesting. Both the lower and the upper bounds in the
EXPTIME-completeness proof fail! Then go with superko could potentially
be as easy as PSPACE (unlikely), or as hard as EXPSPACE - that is,
requiring an exponential amount of space, not just time, to solve. The
intuition here is that with superko, you potentially have to carry
around an exponential amount of extra information with each board
position - the complete history leading up to it - to even know when a
move is legal. So ordinary searching breaks down.
Robson and others worked on this problem for a while. The last relevant
published results I know of are here:
J. M. Robson. Combinatorial games with exponential space complete
decision problems. Proc. Mathematical Foundations of Computer Science,
Springer-Verlag, LNCS 176, 1984, pp. 498-506.
... over 20 years ago. The problem is still open! I have worked on it
some recently with some new techniques, trying to show
EXPSPACE-completeness. But the problem is too hard, and I put it aside.
Robson and others who have thought about it (e.g. John Tromp) now
evidently believe that even with superko it's still EXPTIME-complete,
or, at least, that an EXPSPACE-hardness proof is very unlikely.
Bob Hearn
Till Crueger
> Go is known to be P-space complete, which (most likely) makes it harder
I know this is a bit of pedantry, but isn't go P-Space hard rather than
P-Space complete.
At least I think I recall a few articles which mentioned specific
Go-subproblems, which were proven to be in EXP-Time (I am not sure wether
they were EXP-Time hard or not though).
Greetings,
Till
--
Please add "Salt and Peper" to the subject line to bypass my spam filter
fre...@jellyfish.no
Yes, as Bob Hearn also pointed out, it is in fact EXP-Time complete
(under Japanese rules).
This only strengthens my argument, of course.
Full board unpruned lookahead with unsophisticated leaf node evaluation
really is doomed, no matter how fractile the search space is,
because the elements among which you search are exponential themselves.
complexity theory is asymptotic in nature, but 19x19 is large enough
to make it meaningless with present day computers.
In this light, maybe the current state-of-the art programs aren't so
bad
after all :-).
So do try WinHonte1.03 ( http://www.jellyfish-go.com/ ).
It beats (almost) all other programs, has a fine human touch to its
play,
and even the crippled freeware version plays quite well.
Fredrik
ps: Excuse me for using this group for advertising, but I need to sell
more
copies in order to convince my wife that I should invest more time in
it :)
Btw, how do people feel about the Virtual Software Store that we're
using?
Would it feel safer to buy it directly from our site?
-
Thank you for some fascinating articles on this topic.
- regards
- jb
------------------------------------------------------------------------
Capita Games and Computer Science
http://staff.science.uva.nl/~peter/teaching/thmod03.html
------------------------------------------------------------------------
[ ... ]
INT. SOL'S STUDY - MOMENTS LATER
Sol and Max sit on either side of a half-played Go board.
SOL
Listen to me. The Ancient Japanese considered the Go board to be a
microcosm of the universe. Although when it is empty it appears to be
simple and ordered, in fact, the possibilities of game play are
endless. They say that no two Go games have ever been alike. Just like
snowflakes. So, the Go board actually represents an extremely complex
and chaotic universe. That is the truth of our world, Max. It can't be
easily summed up with math. There is no simple pattern.
MAX
But as a Go game progresses, the possibilities become smaller and
smaller. The board does take on order. Soon, all moves are predictable.
SOL
So?
MAX
So, maybe, even though we're not sophisticated enough to be aware
of it, there is an underlying order...a pattern, beneath every Go game.
Maybe that pattern is like the pattern in the market, in the Torah.
The two sixteen number.
SOL
That is insanity, Max.
MAX
Or maybe it's genius. I have to get that number.
SOL
Hold on, you have to slow down. You're losing it, you have to take a
breath. Listen to yourself. You're connecting a computer bug I had, a
computer bug you might have had, and some religious hogwash. If you
want to find the number two sixteen in the world, you'll be able to
pull it out of anywhere. Two hundred and sixteen steps from your
street comer to your front door. Two hundred and sixteen seconds you
spend riding on the elevator. When your mind becomes obsessed with
anything, it will filter everything else out and find examples of that
thing everywhere. Three hundred and twenty, four hundred and fifty,
twenty-three. Whatever! You've chosen two sixteen and you'll find it
everywhere in nature. But Max, as soon as you discard scientific
rigor, you are no longer a mathematician. You become a numerologist...
http://www.dailyscript.com/scripts/pi.html
------------------------------------------------------------------------
Alex Selby
> fre...@jellyfish.no wrote:
>
>>Go is known to be P-space complete, which (most likely) makes it
>>harder than the combinatorial problems of NP.
>
>
> Actually, Go is even harder. It was indeed shown to be PSPACE-hard, by
> Lichtenstein and Sipser:
>
> D. Lichtenstein and M. Sipser, Go is polynomial-space hard, J. ACM
> 27 (1980) 393-401.
>
> But that left open the possibility that it could be harder than PSPACE;
> all that was shown was that it was *at least* PSPACE-hard. Robson later
> showed that Go with Japanese rules is EXPTIME-complete:
>
> J. M. Robson, The complexity of Go, Proc. IFIP (1983) 413-417.
>
> This is what is to be expected based on basic properties of the game.
> If the length of the game could be polynomially bounded based on the
> board size, then it would be solvable in PSPACE, hence PSPACE-complete.
> But due to ko (in fact potentially, due to general capturing) games can
> last arbitrarily long. Therefore, the strategy of explicitly searching
> all possible game trees cannot be carried out using only polynomial
> space. However, a simple algorithm can determine the status of a
> position in exponential time. Robson showed that exponential time is
> required as well; therefore, it's EXPTIME-complete.
I'm curious about this, but I wonder what Robson means by Japanese rules
(I can't find his article). The exact rule-definition won't matter for
these purposes, but to get a game which is well-defined enough to allow
the kind of reasoning he is using needs some sort of mechanism to make
it finite. Is he using something like "simple ko + the restriction that
black is forbidden to complete any longer loop" (which would be like
Japanese rules if white were satisfied with the null-game arising from a
repeting cycle)?
Alternatively, can you say what is the EXPTIME algorithm used in his
proof (which will make it clear what definition is being used)?
Thanks,
Alex
John Tromp
> I'm curious about this, but I wonder what Robson means by Japanese rules
> (I can't find his article). The exact rule-definition won't matter for
> these purposes, but to get a game which is well-defined enough to allow
> the kind of reasoning he is using needs some sort of mechanism to make
> it finite. Is he using something like "simple ko + the restriction that
> black is forbidden to complete any longer loop" (which would be like
> Japanese rules if white were satisfied with the null-game arising from a
> repeting cycle)?
By Japanese rules he means using only the basic ko rule that forbids cycles
of length 2. He doesn't need to enforce finite games. His problem instances
are positions on arbitrarily sized boards for which the question is whether
Black has a forced win. I.e. infinite repetition is a failure for Black...
He leaves open the question of what is the complexity of Go with superko;
in fact his reduction is useless for that case, since Black can easily
force white into a longer cycle in the positions he constructs.
regards,
-John
Alex Selby
Thanks for that clarification. What you describe - "does black have a
forced win, infinite repetition considered a failure for black?" - is
equivalent to the above-mentioned finite game "simple ko + the
restriction that black is forbidden to complete any longer loop".
Alex
Robert Jasiek
>Robson later showed that Go with Japanese rules is EXPTIME-complete:
> J. M. Robson, The complexity of Go, Proc. IFIP (1983) 413-417.
Which model of Japanese rules did he use?
--
rj
John Tromp
The only thing Japanese about it was the lack of superko rule.
Either allowing long repetitions or ruling the game null would be fine,
since his problem instances ask whether Black has a forced win or not.
-john