blib/lib/Game/Checkers/Bot.pm

filter: Statementstmt 99.6% 266 / 267 Branchbran 94.7% 161 / 170 Conditioncond 92.3% 85 / 92 MC/DCmcdc 87.2% 48 / 55 Subroutinesub 100% 20 / 20 Podpod 100% 1 / 1 totaltotal 96.0% 581 / 605 CC 134 SCAR 33.9
CC
134
Cov
97%
_evaluate
53.0
_search
34.0
choose
13.5
CRAP 29.8
↑ Summary blib/lib/Game/Checkers/Terminal.pm »
1 package Game::Checkers::Bot;
2  
3 15 ▶use strict;
Subroutine __ANON__: called CC=1 SCAR=0.0
4 15 ▶use warnings;
Subroutine __ANON__: called CC=1 SCAR=0.0
5  
6 15 ▶use Object::Proto::Sugar -types;
Subroutine __ANON__: called CC=1 SCAR=0.0
7 15 ▶use Game::Checkers::Squares;
Subroutine __ANON__: called CC=1 SCAR=0.0
8 15 ▶use Game::Checkers::Notation;
Subroutine __ANON__: called CC=1 SCAR=0.0
9 15 ▶use Game::Checkers::Rules;
Subroutine __ANON__: called CC=1 SCAR=0.0
10 15 ▶use Game::Checkers::Move;
Subroutine __ANON__: called CC=1 SCAR=0.0
11  
12 15 our $VERSION = '0.03';
13  
14 15 ▶use constant {
Subroutine __ANON__: called CC=1 SCAR=0.0
15 15 MATE => 10_000,
16 INFINITY => 1_000_000,
17 MAX_EXTENSION => 8,
18 MAX_PV => 20,
19 NO_PROGRESS_PLIES => 80,
20 EXACT => 0,
21 LOWER => 1,
22 UPPER => -1,
23 15 };
24  
25 15 ▶use constant {
Subroutine __ANON__: called CC=1 SCAR=0.0
26 15 RM_FROM => Game::Checkers::Move::RM_FROM,
27 RM_TO => Game::Checkers::Move::RM_TO,
28 RM_PROMOTED => Game::Checkers::Move::RM_PROMOTED,
29 RM_PATH => Game::Checkers::Move::RM_PATH,
30 RM_CAPTURES => Game::Checkers::Move::RM_CAPTURES,
31 RM_KING => Game::Checkers::Move::RM_KING,
32 15 };
33  
34 15 our (%WEIGHT, %LEVEL);
35  
36 # has runs at compile time, and so does anything a level table is read by, so
37 # these are built here rather than in the file body
38 15 ▶BEGIN {
Subroutine BEGIN: called CC=1 SCAR=0.0
39 15 %WEIGHT = (
40 man => 100,
41 king => 160,
42 advance => 4,
43 back_rank => 8,
44 centre => 4,
45 edge => -6,
46 mobility => 2,
47 trapped_king => -20,
48 chase => -2,
49 );
50  
51 15 %LEVEL = (
52 1 => { depth => 2, nodes => 300, jitter => 1 },
53 2 => { depth => 4, nodes => 2_000, jitter => 1 },
54 3 => { depth => 7, nodes => 20_000, jitter => 0 },
55 4 => { depth => 10, nodes => 120_000, jitter => 0 },
56 5 => { depth => 13, nodes => 600_000, jitter => 0 },
57 );
58 }
59  
60 15 my $ROW = \@Game::Checkers::Squares::ROW;
61 15 my $COL = \@Game::Checkers::Squares::COL;
62 15 my $STEP = \@Game::Checkers::Squares::STEP;
63 15 my $JUMP_OVER = \@Game::Checkers::Squares::JUMP_OVER;
64 15 my $JUMP_TO = \@Game::Checkers::Squares::JUMP_TO;
65  
66 15 my @DIRS = @Game::Checkers::Squares::DIRS;
67  
68 15 my %FORWARD = (
69 1 => [Game::Checkers::Squares::SE(), Game::Checkers::Squares::SW()],
70 -1 => [Game::Checkers::Squares::NE(), Game::Checkers::Squares::NW()],
71 );
72  
73 has level => (
74 is => 'rw',
75 isa => Int,
76 default => 3
77 15 );
78  
79 has seed => (
80 is => 'rw',
81 isa => Int,
82 default => 0
83 15 );
84  
85 has transposition => (
86 is => 'rw',
87 isa => Bool,
88 default => 1
89 15 );
90  
91 has last_search => (
92 is => 'rw'
93 15 );
94  
95 1221 ▶sub choose {
Subroutine choose: called CC=13 SCAR=26.0
Pod documented
96 1221 my ($self, $game) = @_;
97 1221 ▶ return undef if $game->result;
Branch: 1 branch
BranchTrueFalseTotal
if $game->result 1 1220 1221
98  
99 1220 my $legal = $game->legal_moves;
100 1220 ▶ return undef unless @{$legal};
Branch: 1 branch
BranchTrueFalseTotal
unless @{$legal;} 0 1220 1220
101  
102 1220 ▶ if (@{$legal} == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (@{$legal;} == 1) 175 1045 1220
103 175 $self->last_search({
104 depth => 0,
105 nodes => 0,
106 score => undef,
107 forced => 1,
108 move => $legal->[0]->notation,
109 pv => [$legal->[0]->notation]
110 });
111 175 return $legal->[0];
112 }
113  
114 1045 ▶ my $spec = $LEVEL{$self->level}
Branch: 1 branch
BranchTrueFalseTotal
my $spec = $Game::Checkers::Bot::LEVEL{$self->level} or die 'level must be 1 .. 5, got ' . $self->level 1045 0 1045
115 or die 'level must be 1 .. 5, got ' . $self->level;
116  
117 1045 my $position = [@{$game->board->position}];
118 1045 my $turn = $game->turn;
119 my $state = {
120 nodes => 0,
121 budget => $spec->{nodes},
122 jitter => $spec->{jitter},
123 1045 table => {},
124 history => {},
125 killers => [],
126 seen => $self->_seen($game),
127 aborted => 0
128 };
129  
130 1045 my ($best, $score, $reached);
131 1045 for my $depth (1 .. $spec->{depth}) {
132 3917 ▶ last if $state->{nodes} > $state->{budget};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"nodes"} > $state->{"budget"} 0 3917 3917
133 3917 $state->{aborted} = 0;
134 3917 my ($iteration_score, $move) = $self->_root(
135 $state, $position, $turn, $depth, $game->no_progress, $game->ply
136 );
137 3917 ▶ last if $state->{aborted} || !$move;
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"aborted"} or not $move 452 3465 3917
Condition66%2/3
$state->{"aborted"} or not $move
l!l&&r!l&&!r
45203465
MC/DC50%1/2
$state->{"aborted"} or not $move
$state->{"aborted"} not $move
Truth table66%2/3
A or not(B)
A= $state->{"aborted"}B= not $move
ABresult
1X1
011
000
138 3465 ($best, $score, $reached) = ($move, $iteration_score, $depth);
139 }
140  
141 my $notation = $best
142 ? Game::Checkers::Notation::format_move({
143 squares => $best->[RM_PATH],
144 1045 ▶ jump => scalar @{$best->[RM_CAPTURES]}
Branch: 1 branch
BranchTrueFalseTotal
$best ? : 1045 0 1045
145 })
146 : $legal->[0]->notation;
147  
148 $self->last_search({
149 depth => $reached || 0,
150 nodes => $state->{nodes},
151 1045 ▶ score => $score,
Condition50%1/2
$reached || 0
l!l
10450
MC/DC0%0/1
$reached || 0
$reached
Truth table50%1/2
A
A= $reached
Aresult
11
00
152 forced => 0,
153 move => $notation,
154 pv => $self->_pv($state, $position, $turn, $best)
155 });
156  
157 # the move handed back is the one out of the game's own legal list, so a
158 # caller may compare it by reference as well as by notation
159 1045 for my $move (@{$legal}) {
160 4189 ▶ return $move if $move->notation eq $notation;
Branch: 1 branch
BranchTrueFalseTotal
if $move->notation eq $notation 1045 3144 4189
161 }
162 0 return $legal->[0];
163 }
164  
165 1045 ▶sub _seen {
Subroutine _seen: called CC=3 SCAR=11.0
166 1045 my ($self, $game) = @_;
167 1045 my ($position, $turn) =
168 Game::Checkers::Notation::position_from_fen($game->fen);
169 1045 my %seen = (_key($position, $turn) => 1);
170 1045 for my $move (@{$game->history}) {
171 38316 Game::Checkers::Rules::apply($position, $move->to_raw);
172 38316 ▶ $turn = $turn eq 'black' ? 'white' : 'black';
Branch: 1 branch
BranchTrueFalseTotal
$turn eq 'black' ? : 19414 18902 38316
173 38316 $seen{_key($position, $turn)}++;
174 }
175 1045 return \%seen;
176 }
177  
178 2982597 ▶sub _key {
Subroutine _key: called CC=1 SCAR=0.0
179 2982597 my ($position, $turn) = @_;
180 2982597 return pack('c32', @{$position}[1 .. 32]) . $turn;
181 }
182  
183 3917 ▶sub _root {
Subroutine _root: called CC=12 SCAR=24.9
184 3917 my ($self, $state, $position, $turn, $depth, $no_progress, $ply) = @_;
185 3917 my $moves = Game::Checkers::Rules::generate($position, $turn);
186 3917 ▶ return (undef, undef) unless @{$moves};
Branch: 1 branch
BranchTrueFalseTotal
unless @{$moves;} 0 3917 3917
187  
188 3917 ▶ my $forced = @{$moves->[0][RM_CAPTURES]} ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
@{$moves->[0][4];} ? : 185 3732 3917
189 3917 ▶ my ($child_depth, $child_extension) = $forced
Branch: 1 branch
BranchTrueFalseTotal
$forced ? : 185 3732 3917
190 ? ($depth, 1)
191 : ($depth - 1, 0);
192  
193 3917 my $alpha = -INFINITY();
194 3917 my ($best, $best_score);
195 3917 for my $raw (@{$self->_ordered($state, $moves, 0, undef)}) {
196 # a move that fails low comes back as a bound rather than a score, and
197 # a bound plus a jitter is how a losing move gets chosen. So when the
198 # jitter is on every root move is searched with the full window and the
199 # scores it is added to are all exact.
200 25886 ▶ my $bound = $state->{jitter} ? -INFINITY() : $alpha;
Branch: 1 branch
BranchTrueFalseTotal
$state->{'jitter'} ? : 24698 1188 25886
201 25886 my $score = $self->_child(
202 $state, $position, $turn, $raw,
203 $child_depth, -INFINITY(), -$bound, 1, $child_extension, $no_progress
204 );
205 25886 ▶ return (undef, undef) if $state->{aborted};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"aborted"} 452 25434 25886
206  
207 25434 ▶ $score += _jitter($self->seed, $ply, $raw) if $state->{jitter};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"jitter"} 24251 1183 25434
208  
209 25434 ▶ if (!defined $best_score || $score > $best_score) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $best_score or $score > $best_score) 9343 16091 25434
Condition100%3/3
not defined $best_score or $score > $best_score
l!l&&r!l&&!r
3886545716091
MC/DC100%2/2
not defined $best_score or $score > $best_score
not defined $best_score $score > $best_score
Truth table100%3/3
not(A) or B
A= not defined $best_scoreB= $score > $best_score
ABresult
1X1
011
000
210 9343 ($best, $best_score) = ($raw, $score);
211 9343 ▶ $alpha = $score if $score > $alpha && !$state->{jitter};
Branch: 1 branch
BranchTrueFalseTotal
if $score > $alpha and not $state->{"jitter"} 393 8950 9343
Condition66%2/3
$score > $alpha and not $state->{"jitter"}
!ll&&!rl&&r
08950393
MC/DC50%1/2
$score > $alpha and not $state->{"jitter"}
$score > $alpha not $state->{"jitter"}
Truth table66%2/3
A and not(B)
A= $score > $alphaB= not $state->{"jitter"}
ABresult
0X0
100
111
212 }
213 }
214 3465 return ($best_score, $best);
215 }
216  
217 1469108 ▶sub _child {
Subroutine _child: called CC=4 SCAR=13.9
218 1469108 my ($self, $state, $position, $turn, $raw, $depth, $alpha, $beta, $ply,
219 $extension, $no_progress) = @_;
220  
221 1469108 ▶ my $next = $turn eq 'black' ? 'white' : 'black';
Branch: 1 branch
BranchTrueFalseTotal
$turn eq 'black' ? : 710960 758148 1469108
222 1469108 ▶ my $progress = Game::Checkers::Rules::progress($raw) ? 0 : $no_progress + 1;
Branch: 1 branch
BranchTrueFalseTotal
Game::Checkers::Rules::progress($raw) ? : 1236047 233061 1469108
223  
224 1469108 Game::Checkers::Rules::apply($position, $raw);
225 1469108 my $key = _key($position, $next);
226 1469108 $state->{seen}{$key}++;
227  
228 1469108 my $score = -$self->_search(
229 $state, $position, $next, $depth, $alpha, $beta, $ply, $extension, $progress
230 );
231  
232 1469108 ▶ delete $state->{seen}{$key} unless --$state->{seen}{$key};
Branch: 1 branch
BranchTrueFalseTotal
unless --$state->{"seen"}{$key} 1466994 2114 1469108
233 1469108 Game::Checkers::Rules::unapply($position, $raw);
234 1469108 return $score;
235 }
236  
237 1469108 ▶sub _search {
Subroutine _search: called CC=34 SCAR=35.3
238 1469108 my ($self, $state, $position, $turn, $depth, $alpha, $beta, $ply,
239 $extension, $no_progress) = @_;
240  
241 1469108 $state->{nodes}++;
242 1469108 ▶ if ($state->{nodes} >= $state->{budget}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($state->{"nodes"} >= $state->{"budget"}) 452 1468656 1469108
243 452 $state->{aborted} = 1;
244 452 return 0;
245 }
246  
247 1468656 my $key = _key($position, $turn);
248 1468656 ▶ return 0 if ($state->{seen}{$key} || 0) >= 3;
Branch: 1 branch
BranchTrueFalseTotal
if ($state->{"seen"}{$key} || 0) >= 3 108 1468548 1468656
Condition50%1/2
$state->{'seen'}{$key} || 0
l!l
14686560
MC/DC0%0/1
$state->{'seen'}{$key} || 0
$state->{'seen'}{$key}
Truth table50%1/2
A
A= $state->{'seen'}{$key}
Aresult
11
00
249 1468548 ▶ return 0 if $no_progress >= NO_PROGRESS_PLIES;
Branch: 1 branch
BranchTrueFalseTotal
if $no_progress >= 80 0 1468548 1468548
250  
251 1468548 ▶ my $entry = $self->transposition ? $state->{table}{$key} : undef;
Branch: 1 branch
BranchTrueFalseTotal
$self->transposition ? : 1465969 2579 1468548
252 1468548 my $table_move;
253 1468548 ▶ if ($entry) {
Branch: 1 branch
BranchTrueFalseTotal
if ($entry) 213699 1254849 1468548
254 213699 $table_move = $entry->[3];
255 213699 ▶ if ($entry->[0] >= $depth && abs($entry->[1]) < MATE - 100) {
Branch: 1 branch
BranchTrueFalseTotal
if ($entry->[0] >= $depth and abs $entry->[1] < 9900) 50284 163415 213699
Condition100%3/3
$entry->[0] >= $depth and abs $entry->[1] < 9900
!ll&&!rl&&r
157903551250284
MC/DC100%2/2
$entry->[0] >= $depth and abs $entry->[1] < 9900
$entry->[0] >= $depth abs $entry->[1] < 9900
Truth table100%3/3
A and B
A= $entry->[0] >= $depthB= abs $entry->[1] < 9900
ABresult
0X0
100
111
256 50284 ▶ return $entry->[1] if $entry->[2] == EXACT;
Branch: 1 branch
BranchTrueFalseTotal
if $entry->[2] == 0 5049 45235 50284
257 45235 ▶ return $entry->[1] if $entry->[2] == LOWER && $entry->[1] >= $beta;
Branch: 1 branch
BranchTrueFalseTotal
if $entry->[2] == 1 and $entry->[1] >= $beta 31130 14105 45235
Condition100%3/3
$entry->[2] == 1 and $entry->[1] >= $beta
!ll&&!rl&&r
10864324131130
MC/DC100%2/2
$entry->[2] == 1 and $entry->[1] >= $beta
$entry->[2] == 1 $entry->[1] >= $beta
Truth table100%3/3
A and B
A= $entry->[2] == 1B= $entry->[1] >= $beta
ABresult
0X0
100
111
258 14105 ▶ return $entry->[1] if $entry->[2] == UPPER && $entry->[1] <= $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $entry->[2] == -1 and $entry->[1] <= $alpha 8666 5439 14105
Condition100%3/3
$entry->[2] == -1 and $entry->[1] <= $alpha
!ll&&!rl&&r
324121988666
MC/DC100%2/2
$entry->[2] == -1 and $entry->[1] <= $alpha
$entry->[2] == -1 $entry->[1] <= $alpha
Truth table100%3/3
A and B
A= $entry->[2] == -1B= $entry->[1] <= $alpha
ABresult
0X0
100
111
259 }
260 }
261  
262 1423703 my $moves = Game::Checkers::Rules::generate($position, $turn);
263 1423703 ▶ return -MATE() + $ply unless @{$moves};
Branch: 1 branch
BranchTrueFalseTotal
unless @{$moves;} 8601 1415102 1423703
264  
265 1415102 ▶ my $forced = @{$moves->[0][RM_CAPTURES]} ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
@{$moves->[0][4];} ? : 465569 949533 1415102
266 1415102 ▶ my $extend = $forced && $extension < MAX_EXTENSION ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
$forced && $extension < 8 ? : 461608 953494 1415102
Condition100%3/3
$forced and $extension < 8
!ll&&!rl&&r
9495333961461608
MC/DC100%2/2
$forced and $extension < 8
$forced $extension < 8
Truth table100%3/3
A and B
A= $forcedB= $extension < 8
ABresult
0X0
100
111
267 1415102 ▶ return _evaluate($position, $turn) if $depth <= 0 && !$extend;
Branch: 1 branch
BranchTrueFalseTotal
if $depth <= 0 and not $extend 713503 701599 1415102
Condition100%3/3
$depth <= 0 and not $extend
!ll&&!rl&&r
354565347034713503
MC/DC100%2/2
$depth <= 0 and not $extend
$depth <= 0 not $extend
Truth table100%3/3
A and not(B)
A= $depth <= 0B= not $extend
ABresult
0X0
100
111
268  
269 701599 ▶ my ($child_depth, $child_extension) = $extend
Branch: 1 branch
BranchTrueFalseTotal
$extend ? : 461608 239991 701599
270 ? ($depth, $extension + 1)
271 : ($depth - 1, $extension);
272  
273 701599 my $original = $alpha;
274 701599 my ($best_score, $best_move) = (-INFINITY(), undef);
275 701599 for my $raw (@{$self->_ordered($state, $moves, $ply, $table_move)}) {
276 1443222 my $score = $self->_child(
277 $state, $position, $turn, $raw,
278 $child_depth, -$beta, -$alpha, $ply + 1, $child_extension, $no_progress
279 );
280 1443222 ▶ return 0 if $state->{aborted};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"aborted"} 2508 1440714 1443222
281  
282 1440714 ▶ if ($score > $best_score) {
Branch: 1 branch
BranchTrueFalseTotal
if ($score > $best_score) 836870 603844 1440714
283 836870 ($best_score, $best_move) = ($score, $raw);
284 836870 ▶ $alpha = $score if $score > $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $score > $alpha 602941 233929 836870
285 }
286 1440714 ▶ next if $alpha < $beta;
Branch: 1 branch
BranchTrueFalseTotal
if $alpha < $beta 1031860 408854 1440714
287  
288 408854 my $name = $raw->[RM_FROM] . '-' . $raw->[RM_TO];
289 408854 $state->{history}{$name} += $depth * $depth;
290 408854 ▶ my $killers = $state->{killers}[$ply] ||= [];
Condition100%2/2
$state->{"killers"}[$ply] ||= []
l!l
4021636691
MC/DC100%1/1
$state->{"killers"}[$ply] ||= []
$state->{"killers"}[$ply]
Truth table100%2/2
A
A= $state->{"killers"}[$ply]
Aresult
11
00
291 306978 unshift @{$killers}, $name
292 408854 ▶ unless @{$killers} && $killers->[0] eq $name;
Branch: 1 branch
BranchTrueFalseTotal
unless @{$killers;} and $killers->[0] eq $name 306978 101876 408854
Condition100%3/3
@{$killers;} and $killers->[0] eq $name
!ll&&!rl&&r
6691300287101876
MC/DC100%2/2
@{$killers;} and $killers->[0] eq $name
@{$killers;} $killers->[0] eq $name
Truth table100%3/3
A and B
A= @{$killers;}B= $killers->[0] eq $name
ABresult
0X0
100
111
293 408854 ▶ pop @{$killers} while @{$killers} > 2;
Branch: 1 branch
BranchTrueFalseTotal
@{$killers;} > 2 and do { pop @{$killers;} } 294030 408854 702884
294 408854 last;
295 }
296  
297 699091 ▶ if ($self->transposition) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->transposition) 697795 1296 699091
298 697795 ▶ my $flag = $best_score <= $original ? UPPER
Branch: 2 branches
BranchTrueFalseTotal
$best_score <= $original ? : 158924 538871 697795
$best_score >= $beta ? : 407987 130884 538871
299 : $best_score >= $beta ? LOWER
300 : EXACT;
301 $state->{table}{$key} = [
302 $depth, $best_score, $flag,
303 697795 ▶ $best_move && [@{$best_move}]
Condition50%1/2
$best_move && [@{$best_move;}]
!ll
0697795
MC/DC0%0/1
$best_move && [@{$best_move;}]
$best_move
Truth table50%1/2
A
A= $best_move
Aresult
00
11
304 ];
305 }
306 699091 return $best_score;
307 }
308  
309 705516 ▶sub _ordered {
Subroutine _ordered: called CC=13 SCAR=25.6
310 705516 my ($self, $state, $moves, $ply, $table_move) = @_;
311 my $wanted = $table_move
312 705516 ▶ ? join('.', @{$table_move->[RM_PATH]})
Branch: 1 branch
BranchTrueFalseTotal
$table_move ? : 168784 536732 705516
313 : '';
314 705516 ▶ my $killers = $state->{killers}[$ply] || [];
Condition100%2/2
$state->{'killers'}[$ply] || []
l!l
65740448112
MC/DC100%1/1
$state->{'killers'}[$ply] || []
$state->{'killers'}[$ply]
Truth table100%2/2
A
A= $state->{'killers'}[$ply]
Aresult
11
00
315 705516 my $history = $state->{history};
316  
317 705516 my @scored;
318 705516 for my $raw (@{$moves}) {
319 2267639 my $name = $raw->[RM_FROM] . '-' . $raw->[RM_TO];
320 2267639 my $score = 0;
321 2267639 ▶ $score += 1_000_000 if $wanted && join('.', @{$raw->[RM_PATH]}) eq $wanted;
Branch: 1 branch
BranchTrueFalseTotal
if $wanted and join(".", @{$raw->[3];}) eq $wanted 168784 2098855 2267639
Condition100%3/3
$wanted and join(".", @{$raw->[3];}) eq $wanted
!ll&&!rl&&r
1748078350777168784
MC/DC100%2/2
$wanted and join(".", @{$raw->[3];}) eq $wanted
$wanted join(".", @{$raw->[3];}) eq $wanted
Truth table100%3/3
A and B
A= $wantedB= join(".", @{$raw->[3];}) eq $wanted
ABresult
0X0
100
111
322 2267639 ▶ $score += 1_000 + (10 * scalar @{$raw->[RM_CAPTURES]}) if @{$raw->[RM_CAPTURES]};
Branch: 1 branch
BranchTrueFalseTotal
if @{$raw->[4];} 572804 1694835 2267639
323 2267639 ▶ $score += 500 if $raw->[RM_PROMOTED];
Branch: 1 branch
BranchTrueFalseTotal
if $raw->[2] 76941 2190698 2267639
324 2267639 ▶ $score += 400 if @{$killers} && $killers->[0] eq $name;
Branch: 1 branch
BranchTrueFalseTotal
if @{$killers;} and $killers->[0] eq $name 139795 2127844 2267639
Condition100%3/3
@{$killers;} and $killers->[0] eq $name
!ll&&!rl&&r
1672881960556139795
MC/DC100%2/2
@{$killers;} and $killers->[0] eq $name
@{$killers;} $killers->[0] eq $name
Truth table100%3/3
A and B
A= @{$killers;}B= $killers->[0] eq $name
ABresult
0X0
100
111
325 2267639 ▶ $score += 300 if @{$killers} > 1 && $killers->[1] eq $name;
Branch: 1 branch
BranchTrueFalseTotal
if @{$killers;} > 1 and $killers->[1] eq $name 76218 2191421 2267639
Condition100%3/3
@{$killers;} > 1 and $killers->[1] eq $name
!ll&&!rl&&r
205105198631676218
MC/DC100%2/2
@{$killers;} > 1 and $killers->[1] eq $name
@{$killers;} > 1 $killers->[1] eq $name
Truth table100%3/3
A and B
A= @{$killers;} > 1B= $killers->[1] eq $name
ABresult
0X0
100
111
326 2267639 ▶ $score += $history->{$name} || 0;
Condition100%2/2
$history->{$name} || 0
l!l
7769131490726
MC/DC100%1/1
$history->{$name} || 0
$history->{$name}
Truth table100%2/2
A
A= $history->{$name}
Aresult
11
00
327 2267639 push @scored, [$score, $raw];
328 }
329 705516 return [map { $_->[1] } sort { $b->[0] <=> $a->[0] } @scored];
330 }
331  
332 1045 ▶sub _pv {
Subroutine _pv: called CC=8 SCAR=20.8
333 1045 my ($self, $state, $position, $turn, $first) = @_;
334 1045 my @pv;
335 my @undo;
336  
337 # the root is searched outside the table, so the line starts with the move
338 # choose settled on and the table carries it from there
339 1045 my $raw = $first;
340 1045 ▶ while (@pv < MAX_PV) {
Branch: 1 branch
BranchTrueFalseTotal
if (@pv < 20) 6517 0 6517
341 6517 ▶ unless ($raw) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($raw) 5472 1045 6517
342 5472 ▶ my $entry = $state->{table}{_key($position, $turn)} or last;
Branch: 1 branch
BranchTrueFalseTotal
my $entry = $state->{"table"}{_key($position, $turn)} or last 4427 1045 5472
343 4427 ▶ $raw = $entry->[3] or last;
Branch: 1 branch
BranchTrueFalseTotal
$raw = $entry->[3] or last 4427 0 4427
344 }
345 5472 my $legal = Game::Checkers::Rules::generate($position, $turn);
346 5472 my $path = join '.', @{$raw->[RM_PATH]};
347 5472 ▶ last unless grep { join('.', @{$_->[RM_PATH]}) eq $path } @{$legal};
Branch: 1 branch
BranchTrueFalseTotal
unless grep {join(".", @{$_->[3];}) eq $path;} @{$legal;} 0 5472 5472
348 push @pv, Game::Checkers::Notation::format_move({
349 squares => $raw->[RM_PATH],
350 5472 jump => scalar @{$raw->[RM_CAPTURES]}
351 });
352 5472 Game::Checkers::Rules::apply($position, $raw);
353 5472 push @undo, $raw;
354 5472 ▶ $turn = $turn eq 'black' ? 'white' : 'black';
Branch: 1 branch
BranchTrueFalseTotal
$turn eq 'black' ? : 2723 2749 5472
355 5472 undef $raw;
356 }
357 1045 ▶ Game::Checkers::Rules::unapply($position, pop @undo) while @undo;
Branch: 1 branch
BranchTrueFalseTotal
@undo and do { Game::Checkers::Rules::unapply($position, pop @undo) } 5472 1045 6517
358 1045 return \@pv;
359 }
360  
361 24251 ▶sub _jitter {
Subroutine _jitter: called CC=2 SCAR=6.9
362 24251 my ($seed, $ply, $raw) = @_;
363 24251 my $string = $seed . ':' . $ply . ':' . join '.', @{$raw->[RM_PATH]};
364 24251 my $hash = 0;
365 24251 $hash = (($hash * 33) + ord) % 65_521 for split //, $string;
366 24251 return $hash % 25;
367 }
368  
369 713503 ▶sub _evaluate {
Subroutine _evaluate: called CC=53 SCAR=39.7
370 713503 my ($position, $turn) = @_;
371 713503 my $score = 0;
372 713503 my (%men, %kings, %back, %mobility, @kings, @pieces);
373  
374 713503 for my $square (1 .. 32) {
375 22832096 ▶ my $value = $position->[$square] or next;
Branch: 1 branch
BranchTrueFalseTotal
my $value = $position->[$square] or next 9226775 13605321 22832096
376 9226775 ▶ my $sign = $value > 0 ? 1 : -1;
Branch: 1 branch
BranchTrueFalseTotal
$value > 0 ? : 4595168 4631607 9226775
377 9226775 ▶ my $king = abs($value) == 2 ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
abs $value == 2 ? : 1006974 8219801 9226775
378 9226775 my $row = $ROW->[$square];
379 9226775 my $col = $COL->[$square];
380  
381 9226775 ▶ push @{$pieces[$sign > 0 ? 0 : 1]}, $square;
Branch: 1 branch
BranchTrueFalseTotal
$sign > 0 ? : 4595168 4631607 9226775
382 9226775 ▶ if ($king) {
Branch: 1 branch
BranchTrueFalseTotal
if ($king) { } 1006974 8219801 9226775
383 1006974 $kings{$sign}++;
384 1006974 $score += $sign * $WEIGHT{king};
385 1006974 ▶ push @{$kings[$sign > 0 ? 0 : 1]}, $square;
Branch: 1 branch
BranchTrueFalseTotal
$sign > 0 ? : 476121 530853 1006974
386 } else {
387 8219801 $men{$sign}++;
388 8219801 $score += $sign * $WEIGHT{man};
389 8219801 ▶ $score += $sign * $WEIGHT{advance} * ($sign > 0 ? $row : 7 - $row);
Branch: 1 branch
BranchTrueFalseTotal
$sign > 0 ? : 4119047 4100754 8219801
390 8219801 ▶ $score += $sign * $WEIGHT{edge} if $col == 0 || $col == 7;
Branch: 1 branch
BranchTrueFalseTotal
if $col == 0 or $col == 7 2273775 5946026 8219801
Condition100%3/3
$col == 0 or $col == 7
l!l&&r!l&&!r
111203411617415946026
MC/DC100%2/2
$col == 0 or $col == 7
$col == 0 $col == 7
Truth table100%3/3
A or B
A= $col == 0B= $col == 7
ABresult
1X1
011
000
391 8219801 ▶ $back{$sign}++ if ($sign > 0 ? $row : 7 - $row) == 0;
Branch: 2 branches
BranchTrueFalseTotal
if ($sign > 0 ? $row : 7 - $row) == 0 2720136 5499665 8219801
$sign > 0 ? : 4119047 4100754 8219801
392 }
393 9226775 ▶ $score += $sign * $WEIGHT{centre} if $col == 3 || $col == 4;
Branch: 1 branch
BranchTrueFalseTotal
if $col == 3 or $col == 4 2248958 6977817 9226775
Condition100%3/3
$col == 3 or $col == 4
l!l&&r!l&&!r
113447011144886977817
MC/DC100%2/2
$col == 3 or $col == 4
$col == 3 $col == 4
Truth table100%3/3
A or B
A= $col == 3B= $col == 4
ABresult
1X1
011
000
394  
395 # moves available to this piece, counted without expanding a jump
396 # sequence: a cheap stand in for mobility that costs four lookups
397 9226775 my $moves = 0;
398 9226775 my $base = $square * 4;
399 9226775 ▶ for my $dir ($king ? @DIRS : @{$FORWARD{$sign}}) {
Branch: 1 branch
BranchTrueFalseTotal
$king ? : 1006974 8219801 9226775
400 20467498 my $step = $STEP->[$base + $dir];
401 20467498 ▶ $moves++ if $step && !$position->[$step];
Branch: 1 branch
BranchTrueFalseTotal
if $step and not $position->[$step] 11137834 9329664 20467498
Condition100%3/3
$step and not $position->[$step]
!ll&&!rl&&r
3370170595949411137834
MC/DC100%2/2
$step and not $position->[$step]
$step not $position->[$step]
Truth table100%3/3
A and not(B)
A= $stepB= not $position->[$step]
ABresult
0X0
100
111
402 20467498 ▶ my $landing = $JUMP_TO->[$base + $dir] or next;
Branch: 1 branch
BranchTrueFalseTotal
my $landing = $$JUMP_TO[$base + $dir] or next 14038561 6428937 20467498
403 14038561 ▶ next if $position->[$landing];
Branch: 1 branch
BranchTrueFalseTotal
if $position->[$landing] 5529851 8508710 14038561
404 8508710 ▶ my $victim = $position->[$JUMP_OVER->[$base + $dir]] or next;
Branch: 1 branch
BranchTrueFalseTotal
my $victim = $$position[$$JUMP_OVER[$base + $dir]] or next 2674293 5834417 8508710
405 2674293 ▶ $moves++ if ($victim > 0 ? 1 : -1) != $sign;
Branch: 2 branches
BranchTrueFalseTotal
if ($victim > 0 ? 1 : -1) != $sign 64174 2610119 2674293
$victim > 0 ? : 1329948 1344345 2674293
406 }
407 9226775 $mobility{$sign} += $moves;
408 9226775 ▶ $score += $sign * $WEIGHT{trapped_king} if $king && !$moves;
Branch: 1 branch
BranchTrueFalseTotal
if $king and not $moves 5237 9221538 9226775
Condition100%3/3
$king and not $moves
!ll&&!rl&&r
821980110017375237
MC/DC100%2/2
$king and not $moves
$king not $moves
Truth table100%3/3
A and not(B)
A= $kingB= not $moves
ABresult
0X0
100
111
409 }
410  
411 # a home row is worth holding only while there is a man that could crown
412 713503 ▶ $score += $WEIGHT{back_rank} * ($back{1} || 0) if $men{-1};
Branch: 1 branch
BranchTrueFalseTotal
if $men{-1} 673067 40436 713503
Condition100%2/2
$back{'1'} || 0
l!l
454404218663
MC/DC100%1/1
$back{'1'} || 0
$back{'1'}
Truth table100%2/2
A
A= $back{'1'}
Aresult
11
00
413 713503 ▶ $score -= $WEIGHT{back_rank} * ($back{-1} || 0) if $men{1};
Branch: 1 branch
BranchTrueFalseTotal
if $men{1} 632888 80615 713503
Condition100%2/2
$back{'-1'} || 0
l!l
493634139254
MC/DC100%1/1
$back{'-1'} || 0
$back{'-1'}
Truth table100%2/2
A
A= $back{'-1'}
Aresult
11
00
414 713503 ▶ $score += $WEIGHT{mobility} * (($mobility{1} || 0) - ($mobility{-1} || 0));
Condition100%4/4
$mobility{'1'} || 0
l!l
71349013
$mobility{'-1'} || 0
l!l
7134994
MC/DC100%1/1
$mobility{'1'} || 0
$mobility{'1'}
MC/DC100%1/1
$mobility{'-1'} || 0
$mobility{'-1'}
Truth table100%2/2
A
A= $mobility{'1'}
Aresult
11
00
Truth table100%2/2
A
A= $mobility{'-1'}
Aresult
11
00
415  
416 713503 ▶ my $total = ($men{1} || 0) + ($kings{1} || 0) + ($men{-1} || 0) + ($kings{-1} || 0);
Condition100%8/8
$men{'1'} || 0
l!l
63288880615
$kings{'1'} || 0
l!l
318241395262
$men{'-1'} || 0
l!l
67306740436
$kings{'-1'} || 0
l!l
298631414872
MC/DC100%1/1
$men{'1'} || 0
$men{'1'}
MC/DC100%1/1
$kings{'1'} || 0
$kings{'1'}
MC/DC100%1/1
$men{'-1'} || 0
$men{'-1'}
MC/DC100%1/1
$kings{'-1'} || 0
$kings{'-1'}
Truth table100%2/2
A
A= $men{'1'}
Aresult
11
00
Truth table100%2/2
A
A= $kings{'1'}
Aresult
11
00
Truth table100%2/2
A
A= $men{'-1'}
Aresult
11
00
Truth table100%2/2
A
A= $kings{'-1'}
Aresult
11
00
417 713503 ▶ if ($total <= 6 && $total) {
Branch: 1 branch
BranchTrueFalseTotal
if ($total <= 6 and $total) 112995 600508 713503
Condition66%2/3
$total <= 6 and $total
!ll&&!rl&&r
6005080112995
MC/DC50%1/2
$total <= 6 and $total
$total <= 6 $total
Truth table66%2/3
A and B
A= $total <= 6B= $total
ABresult
0X0
100
111
418 112995 ▶ my $black = ($men{1} || 0) * $WEIGHT{man} + ($kings{1} || 0) * $WEIGHT{king};
Condition100%4/4
$men{'1'} || 0
l!l
4106971926
$kings{'1'} || 0
l!l
1072395756
MC/DC100%1/1
$men{'1'} || 0
$men{'1'}
MC/DC100%1/1
$kings{'1'} || 0
$kings{'1'}
Truth table100%2/2
A
A= $men{'1'}
Aresult
11
00
Truth table100%2/2
A
A= $kings{'1'}
Aresult
11
00
419 112995 ▶ my $white = ($men{-1} || 0) * $WEIGHT{man} + ($kings{-1} || 0) * $WEIGHT{king};
Condition100%4/4
$men{'-1'} || 0
l!l
7860534390
$kings{'-1'} || 0
l!l
7618936806
MC/DC100%1/1
$men{'-1'} || 0
$men{'-1'}
MC/DC100%1/1
$kings{'-1'} || 0
$kings{'-1'}
Truth table100%2/2
A
A= $men{'-1'}
Aresult
11
00
Truth table100%2/2
A
A= $kings{'-1'}
Aresult
11
00
420 112995 ▶ my $stronger = $black > $white ? 0 : $white > $black ? 1 : undef;
Branch: 2 branches
BranchTrueFalseTotal
$black > $white ? : 43404 69591 112995
$white > $black ? : 50250 19341 69591
421 112995 ▶ if (defined $stronger && $kings[$stronger]) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $stronger and $kings[$stronger]) 67010 45985 112995
Condition100%3/3
defined $stronger and $kings[$stronger]
!ll&&!rl&&r
193412664467010
MC/DC100%2/2
defined $stronger and $kings[$stronger]
defined $stronger $kings[$stronger]
Truth table100%3/3
A and B
A= defined $strongerB= $kings[$stronger]
ABresult
0X0
100
111
422 67010 my $distance = 0;
423 67010 for my $king (@{$kings[$stronger]}) {
424 126449 ▶ for my $enemy (@{$pieces[$stronger ? 0 : 1] || []}) {
Branch: 1 branch
BranchTrueFalseTotal
$stronger ? : 39415 87034 126449
Condition50%1/2
$pieces[$stronger ? 0 : 1] || []
l!l
1264490
MC/DC0%0/1
$pieces[$stronger ? 0 : 1] || []
$pieces[$stronger ? 0 : 1]
Truth table50%1/2
A
A= $pieces[$stronger ? 0 : 1]
Aresult
11
00
425 220151 my $rows = abs($ROW->[$king] - $ROW->[$enemy]);
426 220151 my $cols = abs($COL->[$king] - $COL->[$enemy]);
427 220151 ▶ $distance += $rows > $cols ? $rows : $cols;
Branch: 1 branch
BranchTrueFalseTotal
$rows > $cols ? : 89513 130638 220151
428 }
429 }
430 67010 ▶ $score += ($stronger ? -1 : 1) * $WEIGHT{chase} * $distance;
Branch: 1 branch
BranchTrueFalseTotal
$stronger ? : 24476 42534 67010
431 }
432 }
433  
434 713503 ▶ return $turn eq 'black' ? $score : -$score;
Branch: 1 branch
BranchTrueFalseTotal
$turn eq 'black' ? : 366656 346847 713503
435 }
436  
437 15 1;
438  
439 __END__
↑ Summary blib/lib/Game/Checkers/Terminal.pm »