On Sat, May 23, 2009 at 4:01 AM, Dave Dyer <dd...@real-me.net> 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 > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ >
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
