| 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
| |||||||||||||||
| 105 | 3 | ▶ | croak "no evaluate() method defined" unless $pos->can("evaluate"); | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 106 | 3 | ▶ | croak "no findmoves() method defined" unless $pos->can("findmoves"); | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 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
| |||||||||||||||
| 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
| |||||||||||||||
| 149 | 1 | $ply = shift; | |||||||||||||
| 150 | 1 | ▶ | print "Explicit ply $ply overrides default ($self->{ply})\n" if $self->{debug}; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 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
| |||||||||||||||
| 161 | 126 | ▶ | return unless @moves = $pos->findmoves; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 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
| |||||||||||||||
| 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
| |||||||||||||||
| 172 | 990 | $sc = -$self->_alphabeta($npos, -$beta, -$alpha, $ply - 1); | |||||||||||||
| 173 | |||||||||||||||
| 174 | 990 | ▶ | print "ab val: $sc" if $self->{debug}; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 175 | 990 | ▶ | if ($sc > $alpha) { | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 176 | 246 | ▶ | print " > $alpha new best move" if $self->{debug}; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 177 | 246 | $bestmove_valid = 1; | |||||||||||||
| 178 | 246 | $bestmove = $move; | |||||||||||||
| 179 | 246 | $alpha = $sc; | |||||||||||||
| 180 | } | ||||||||||||||
| 181 | 990 | ▶ | print "\n" if $self->{debug}; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 182 | } | ||||||||||||||
| 183 | 124 | ▶ | print "$self->{count} visited\n" if $self->{debug}; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 184 | |||||||||||||||
| 185 | 124 | ▶ | return unless $bestmove_valid; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 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
| |||||||||||||||
| 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
| |||||||||||||||
| 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
| |||||||||||||||
| 223 | 4619 | ▶ | $npos->apply($move) or croak "$pos->apply() failed"; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 224 | |||||||||||||||
| 225 | 4619 | $sc = -$self->_alphabeta($npos, -$beta, -$alpha, $ply - 1); | |||||||||||||
| 226 | |||||||||||||||
| 227 | 4619 | ▶ | $alpha = $sc if $sc > $alpha; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 228 | 4619 | ▶ | last unless $alpha < $beta; | ||||||||||||
|
Branch: 1 branch
| |||||||||||||||
| 229 | } | ||||||||||||||
| 230 | |||||||||||||||
| 231 | 1036 | return $alpha; | |||||||||||||
| 232 | } | ||||||||||||||
| 233 | |||||||||||||||
| 234 | |||||||||||||||
| 235 | 3 | 1; # ensure using this module works | |||||||||||||
| 236 | __END__ | ||||||||||||||