blib/lib/Games/AlphaBeta.pm

filter: Statementstmt 97.4% 75 / 77 Branchbran 65.2% 30 / 46 Conditioncond n/a MC/DCmcdc n/a Subroutinesub 100% 9 / 9 Podpod 100% 2 / 2 totaltotal 86.5% 116 / 134 CC 26 SCAR 22.4
CC
26
Cov
85%
abmove
14.9
_alphabeta
9.3
_init
4.1
CRAP 9.4
« blib/lib/Games/AlphaBeta/Reversi.pm ↑ Summary blib/lib/Games/Sequential.pm »
1 package Games::AlphaBeta;
2 3 ▶use base qw(Games::Sequential);
Subroutine BEGIN: called CC=1 SCAR=0.0
3  
4 3 ▶use Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
5 3 ▶use 5.006001;
Subroutine BEGIN: called CC=1 SCAR=0.0
6  
7 3 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
8 3 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
9  
10  
11 3 our $VERSION = '0.4.7';
12  
13 =head1 NAME
14  
15 Games::AlphaBeta - game-tree search with object oriented interface
16  
17 =head1 SYNOPSIS
18  
19 package My::GamePos;
20 use base qw(Games::AlphaBeta::Position);
21  
22 # initialise starting position
23 sub _init { ... }
24  
25 # Methods required by Games::AlphaBeta
26 sub apply { ... }
27 sub endpos { ... } # optional
28 sub evaluate { ... }
29 sub findmoves { ... }
30  
31 # Draw a position in the game (optional)
32 sub draw { ... }
33  
34 package main;
35 my $pos = My::GamePos->new;
36 my $game = Games::AlphaBeta->new($pos);
37  
38 while ($game->abmove) {
39 print draw($game->peek_pos);
40 }
41  
42 =head1 DESCRIPTION
43  
44 Games::AlphaBeta provides a generic implementation of the
45 AlphaBeta game-tree search algorithm (also known as MiniMax
46 search with alpha beta pruning). This algorithm can be used to
47 find the best move at a particular position in any two-player,
48 zero-sum game with perfect information. Examples of such games
49 include Chess, Othello, Connect4, Go, Tic-Tac-Toe and many, many
50 other boardgames.
51  
52 Users must pass an object representing the initial state of the
53 game as the first argument to C<new()>. This object must provide
54 the following methods: C<copy()>, C<apply()>, C<endpos()>,
55 C<evaluate()> and C<findmoves()>. This is explained more
56 carefully in L<Games::AlphaBeta::Position> which is a base class
57 you can use to implement your position object.
58  
59 =head1 INHERITED METHODS
60  
61 The following methods are inherited from L<Games::Sequential>:
62  
63 =over
64  
65 =item new
66  
67 =item debug
68  
69 =item peek_pos
70  
71 =item peek_move
72  
73 =item move
74  
75 =item undo
76  
77 =back
78  
79 =head1 METHODS
80  
81 =over
82  
83 =item _init [@list]
84  
85 I<Internal method.>
86  
87 Initialize an AlphaBeta object.
88  
89 =cut
90  
91 3 ▶sub _init {
Subroutine _init: called CC=4 SCAR=14.2
92 3 my $self = shift;
93 3 my %config = (
94 # Runtime variables
95 ply => 2, # default search depth
96 alpha => -100_000,
97 beta => 100_000,
98 );
99  
100 3 @$self{keys %config} = values %config;
101 3 $self->SUPER::_init(@_);
102  
103 3 my $pos = $self->peek_pos;
104 3 ▶ croak "no endpos() method defined" unless $pos->can("endpos");
Branch: 1 branch
BranchTrueFalseTotal
unless $pos->can("endpos") 0 3 3
105 3 ▶ croak "no evaluate() method defined" unless $pos->can("evaluate");
Branch: 1 branch
BranchTrueFalseTotal
unless $pos->can("evaluate") 0 3 3
106 3 ▶ croak "no findmoves() method defined" unless $pos->can("findmoves");
Branch: 1 branch
BranchTrueFalseTotal
unless $pos->can("findmoves") 0 3 3
107  
108 3 return $self;
109 }
110  
111  
112 =item ply [$value]
113  
114 Return current default search depth and, if invoked with an
115 argument, set to new value.
116  
117 =cut
118  
119 1 ▶sub ply {
Subroutine ply: called CC=2 SCAR=7.0
Pod documented
120 1 my $self = shift;
121 1 my $prev = $self->{ply};
122 1 ▶ $self->{ply} = shift if @_;
Branch: 1 branch
BranchTrueFalseTotal
if @_ 1 0 1
123 1 return $prev;
124 }
125  
126  
127 =item abmove [$ply]
128  
129 Perform the best move found after an AlphaBeta game-tree search
130 to depth $ply. If $ply is not specified, the default depth is
131 used (see C<ply()>). The best move found is performed and a
132 reference to the resulting position is returned on success, and
133 undef is returned on failure.
134  
135 Note that this function can take a long time if $ply is high,
136 particularly if the game in question has many possible moves at
137 each position.
138  
139 If C<debug()> is set, some basic debugging is printed as the
140 search progresses.
141  
142 =cut
143  
144 126 ▶sub abmove {
Subroutine abmove: called CC=14 SCAR=27.0
Pod documented
145 126 my $self = shift;
146 126 my $ply;
147  
148 126 ▶ if (@_) {
Branch: 1 branch
BranchTrueFalseTotal
if (@_) { } 1 125 126
149 1 $ply = shift;
150 1 ▶ print "Explicit ply $ply overrides default ($self->{ply})\n" if $self->{debug};
Branch: 1 branch
BranchTrueFalseTotal
if $self->{"debug"} 0 1 1
151 }
152 else {
153 125 $ply = $self->{ply};
154 }
155  
156 126 my (@moves, $bestmove);
157 126 my $bestmove_valid = 0;
158 126 my $pos = $self->peek_pos;
159  
160 126 ▶ return if $pos->endpos;
Branch: 1 branch
BranchTrueFalseTotal
if $pos->endpos 0 126 126
161 126 ▶ return unless @moves = $pos->findmoves;
Branch: 1 branch
BranchTrueFalseTotal
unless @moves = $pos->findmoves 2 124 126
162  
163 124 my $alpha = $self->{alpha};
164 124 my $beta = $self->{beta};
165  
166 124 ▶ print "Searching to depth $ply\n" if $self->{debug};
Branch: 1 branch
BranchTrueFalseTotal
if $self->{"debug"} 0 124 124
167 124 $self->{found_end} = $self->{count} = 0;
168 124 for my $move (@moves) {
169 990 my ($npos, $sc);
170 990 $npos = $pos->copy;
171 990 ▶ $npos->apply($move) or croak "apply() failed";
Branch: 1 branch
BranchTrueFalseTotal
$npos->apply($move) or croak("apply() failed") 990 0 990
172 990 $sc = -$self->_alphabeta($npos, -$beta, -$alpha, $ply - 1);
173  
174 990 ▶ print "ab val: $sc" if $self->{debug};
Branch: 1 branch
BranchTrueFalseTotal
if $self->{"debug"} 0 990 990
175 990 ▶ if ($sc > $alpha) {
Branch: 1 branch
BranchTrueFalseTotal
if ($sc > $alpha) 246 744 990
176 246 ▶ print " > $alpha new best move" if $self->{debug};
Branch: 1 branch
BranchTrueFalseTotal
if $self->{"debug"} 0 246 246
177 246 $bestmove_valid = 1;
178 246 $bestmove = $move;
179 246 $alpha = $sc;
180 }
181 990 ▶ print "\n" if $self->{debug};
Branch: 1 branch
BranchTrueFalseTotal
if $self->{"debug"} 0 990 990
182 }
183 124 ▶ print "$self->{count} visited\n" if $self->{debug};
Branch: 1 branch
BranchTrueFalseTotal
if $self->{"debug"} 0 124 124
184  
185 124 ▶ return unless $bestmove_valid;
Branch: 1 branch
BranchTrueFalseTotal
unless $bestmove_valid 0 124 124
186 124 return $self->move($bestmove);
187 }
188  
189  
190 =item _alphabeta $pos $alpha $beta $ply
191  
192 I<Internal method.>
193  
194 =cut
195  
196 5609 ▶sub _alphabeta {
Subroutine _alphabeta: called CC=9 SCAR=22.3
197 5609 my ($self, $pos, $alpha, $beta, $ply) = @_;
198 5609 my @moves;
199  
200 # Keep count of the number of positions we've seen
201 5609 $self->{count}++;
202  
203 # When using iterative deepening we can optimise for the case
204 # when we find an end position at every branch (for example,
205 # near the end of the game)
206 #
207 5609 ▶ if ($pos->endpos) {
Branch: 2 branches
BranchTrueFalseTotal
if ($pos->endpos) { } 0 5609 5609
elsif ($ply <= 0) { } 4571 1038 5609
208 0 $self->{found_end}++;
209 0 return $pos->evaluate;
210 }
211 elsif ($ply <= 0) {
212 4571 return $pos->evaluate;
213 }
214  
215 1038 ▶ unless (@moves = $pos->findmoves) {
Branch: 1 branch
BranchTrueFalseTotal
unless (@moves = $pos->findmoves) 2 1036 1038
216 2 $self->{found_end}++;
217 2 return $pos->evaluate;
218 }
219  
220 1036 for my $move (@moves) {
221 4619 my ($npos, $sc);
222 4619 ▶ $npos = $pos->copy or croak "$pos->copy() failed";
Branch: 1 branch
BranchTrueFalseTotal
$npos = $pos->copy or croak("$pos->copy() failed") 4619 0 4619
223 4619 ▶ $npos->apply($move) or croak "$pos->apply() failed";
Branch: 1 branch
BranchTrueFalseTotal
$npos->apply($move) or croak("$pos->apply() failed") 4619 0 4619
224  
225 4619 $sc = -$self->_alphabeta($npos, -$beta, -$alpha, $ply - 1);
226  
227 4619 ▶ $alpha = $sc if $sc > $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $sc > $alpha 2013 2606 4619
228 4619 ▶ last unless $alpha < $beta;
Branch: 1 branch
BranchTrueFalseTotal
unless $alpha < $beta 769 3850 4619
229 }
230  
231 1036 return $alpha;
232 }
233  
234  
235 3 1; # ensure using this module works
236 __END__
« blib/lib/Games/AlphaBeta/Reversi.pm ↑ Summary blib/lib/Games/Sequential.pm »