[Perl资源总汇]Mastering Algorithms with Perl

1. Alpha-beta pruning
   
2. One form of pruning is especially useful for any adversarial situation. It avoids evaluating many positions, but still returns the same result it would if it had evaluated them all. Suppose you’ve analyzed one of your possible moves and determined that your opponent’s best reply will lead to no change in relative advantage. Now you are about to examine another of your possible moves. If you find that one response your opponent might make leads to the loss of one of your pieces, you need not examine the rest of your opponent’s replies. You don’t care about finding out whether he may be able to checkmate you instead, because you already know that this move is not your best choice. So, you skip further analysis of this move and immediately go on to examine alternate moves that you actually might make.
   
3. Of course, the analysis of the opponent’s moves can use the same strategy. The algorithm that implements this is a slight variation of minimax called alpha-beta pruning. It uses two additional parameters, alpha and beta, to record the lower and upper cutoff bounds that are to be applied. The caller doesn’t have to provide these parameters; they are initalized internally. Like minimax, this routine is recursive. Note that on the recursive calls, the parameters $alpha and $beta are swapped and negated. That corresponds to the change of viewpoint as it becomes the other player’s turn to play.

复制代码

1. # Usage:
   
2. #    To minimize the next move:
   
3. #        ($move,$score) = ab_minimax($position,$depth)
   
4. #    You provide a game position object, and a maxmimum depth
   
5. #    (number of moves) to be expanded before cutting off the
   
6. #    move generation and evaluating the resulting position.
   
7. 
   
8. sub ab_minimax {
   
9.     my ( $position, $depth, $alpha, $beta ) = @_;
   
10. 
    
11.     defined ($alpha) or $alpha = -$position->best_rating;
    
12.     defined ($beta)  or $beta  =  $position->best_rating;
    
13. 
    
14.     # Have we gone as far as permitted or as far as possible?
    
15.     if ( $depth-- and defined($position->prepare_moves) ) {
    
16.         # no - keep trying additional moves from $position
    
17.         my $move;
    
18.         my $best_score = -$position->best_rating;
    
19.         my $best_move_seq;
    
20.         my $alpha_cur = $alpha;
    
21. 
    
22.         while ( defined($move = $position->next_move) ) {
    
23.             # Evaluate the next move.
    
24.             my ( $this_move_seq, $this_score ) =
    
25.                 ab_minimax( $position->make_move($move),
    
26.                                 $depth, -$beta, -$alpha_cur );
    
27.             # Opponent's score is opposite meaning from ours.
    
28.             $this_score = -$this_score;
    
29.             if ( $this_score > $best_score ) {
    
30.                 $best_score = $this_score;
    
31.                 $alpha_cur = $best_score if $best_score > $alpha_cur;
    
32.                 $best_move_seq = $this_move_seq;
    
33.                 unshift ( @$best_move_seq, $move );
    
34. 
    
35.                 # Here is the alpha-beta pruning.
    
36.                 #    - quit when someone else is ahead!
    
37.                 last if $best_score >= $beta;
    
38.             }
    
39.         }
    
40. 
    
41.         # Return the best one we found.
    
42.         return ( $best_move_seq, $best_score );
    
43. 
    
44.     } else {
    
45.         # Yes - evaluate current position, no move to be taken.
    
46.         return ( [ $position ], -$position->evaluate );
    
47.     }
    
48. }

复制代码

,,,,,,,,,,,,,,,,,,,,,,

谢谢分享。

Thanks for Sharing!