On Mon, Nov 13, 2006 at 04:25:28PM +0000, Arthur Cater wrote: > > On Monday, November 13, 2006, at 04:02 PM, Eduardo Sabbatella wrote: > > > > >Using alfa-beta pruning allows you to see more 'deep' > >in the game tree. > > > >We could say: You exchanges "tree wide view" for "tree > >deep view".
But only by throwing away variations which are strictly irrelevant to the result which would be returned by minimax. (See example described below.) > >Its not soo difficult to miss "the" move, prunning the > >tree. That is a valid criticism of many approaches which are called pruning, but it is not a valid criticism of alpha-beta. Alpha-beta prunes a subtree only when it can prove, from inequalities on earlier search results, that no possible set of values found in that subtree can affect the result returned which would be returned by minimax. > Alpha-beta pruning is "safe", in the sense that it will find the same > move as a full > minimax search. You need to do "aggressive forward pruning" in order to > run the > risk of missing "the" move, but alpha-beta is conservative not > aggressive. > > You may indeed 'miss "the" move', but when you do, minimax would do so > too. Yes. One way for Eduardo Sabbatella, or anyone else, to see what's going on in alpha-beta is to imagine the situation when the search has already found that move X is worth 10 points if the opponent makes his strongest response. Then, in searching move Y, the search discovers that Y is worth only 7 points if the opponent replies at Z. In straight minimax, the search will go on to figure out exactly how many points Y is worth, looking for moves Z' and Z'' which bring the value of Y down to values even lower than 7. In alpha-beta, the search algorithm says "even if Z is not the opponent's strongest refutation, the possibility of replying with Z is enough to show that Y is not as good as X," and prunes the search of all other variations starting with Y. Such pruning doesn't affect the returned result, because in effect straight minimax doesn't really care exactly how inferior Y is either. Straight minimax does waste its time figuring out precisely how inferior Y is, but the precision of the result doesn't have any effect on the ultimate result: no matter what it finds for Y, minimax ultimately tells you it is better to move at X for 10 points, just like alpha-beta. _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
