Don and Dave,
Perhaps it might be useful to use something smaller than 5x5. For
example, is 2x2, 3x3 and 4x4 "solved" and "verfiable"? If so, how might
one go about providing evidence for the "solution" and then for the
"verifiability"? It seems that what might work for these ought to also
work for 5x5, 9x9 and 19x19. The process and evidence on the smaller
since can then be used to model achieving the same results for the
larger sizes as they fall to elevating computational power/space.
Jim
Don Dailey wrote:
On Sat, May 23, 2009 at 4:01 AM, Dave Dyer <[email protected]
<mailto:[email protected]>> wrote:
I've written dozens of games with alpha-beta searches, so I think
it's fair to say that I have a basic understanding of the process.
Your description is correct but incomplete. Alpha beta is good at
eliminating
lines of play once a strong outcome is known somewhere in the
tree, but much
weaker before that. If a "big capture" occurs at ply 30, but the
shortest
win is at ply 60, you still have to explore an enormous number of
silly
variations as you iteratively deepen between ply 30 and 59. The
fact that you
don't need to explore continuations of the silly moves past move 59 is
cold comfort. The other half of the bad news is that while only the
"best" move of the winning lines needs to be explored, generally all
of the possible responses have to be explored. So the tree actually
explored tends to be narrow for the winning line, but very wide as
all possible responses to the "correct" move are explored. In the
case
of a "big capture" being the correct move, pitching into every one of
the captured spaces will have to be explored.
Yes, it will have to be explored, but with iterative deepening it is
not explored to the end of the game.
Alpha beta engines which do not use inadmissible (but probably valid)
tricks waste exponentially more time than those that do. It's quite
possible that 5x5 is on the sweet side of the equation with today's
available CPUs, but at some point not much further away, you have
to accept results that you believe but can't prove, as better than
no result at all.
What we are talking about is solving 5x5 boards, nothing more. 7x7 is
out of the question right now and probably for a very long time.
I'm certainly not saying that you won't explore silly lines - you
certainly will with full width alpha beta search. But the long cycles
silly moves will be minimal because alpha beta with good move ordering
will try the silly moves last and they will be mostly irrelevant and
get cut off. Your search is NOT going to be dominated by long cycle
KO moves where you explore every possible way to fill the same space
over and over again.
- Don
_______________________________________________
computer-go mailing list
[email protected] <mailto:[email protected]>
http://www.computer-go.org/mailman/listinfo/computer-go/
------------------------------------------------------------------------
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
