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. 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. _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
