blib/lib/Game/Checkers/Bot.pm

filter: Statementstmt 99.6% 266 / 267 Branchbran 95.2% 162 / 170 Conditioncond 92.3% 85 / 92 MC/DCmcdc 87.2% 48 / 55 Subroutinesub 100% 20 / 20 Podpod 100% 1 / 1 totaltotal 96.2% 582 / 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/Notation.pm »
1 package Game::Checkers::Bot;
2  
3 18 ▶use strict;
Subroutine __ANON__: called CC=1 SCAR=0.0
4 18 ▶use warnings;
Subroutine __ANON__: called CC=1 SCAR=0.0
5  
6 18 ▶use Object::Proto::Sugar -types;
Subroutine __ANON__: called CC=1 SCAR=0.0
7 18 ▶use Game::Checkers::Squares;
Subroutine __ANON__: called CC=1 SCAR=0.0
8 18 ▶use Game::Checkers::Notation;
Subroutine __ANON__: called CC=1 SCAR=0.0
9 18 ▶use Game::Checkers::Rules;
Subroutine __ANON__: called CC=1 SCAR=0.0
10 18 ▶use Game::Checkers::Move;
Subroutine __ANON__: called CC=1 SCAR=0.0
11  
12 18 our $VERSION = '0.04';
13  
14 18 ▶use constant {
Subroutine __ANON__: called CC=1 SCAR=0.0
15 18 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 18 };
24  
25 18 ▶use constant {
Subroutine __ANON__: called CC=1 SCAR=0.0
26 18 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 18 };
33  
34 18 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 18 ▶BEGIN {
Subroutine BEGIN: called CC=1 SCAR=0.0
39 18 %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 18 %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 18 my $ROW = \@Game::Checkers::Squares::ROW;
61 18 my $COL = \@Game::Checkers::Squares::COL;
62 18 my $STEP = \@Game::Checkers::Squares::STEP;
63 18 my $JUMP_OVER = \@Game::Checkers::Squares::JUMP_OVER;
64 18 my $JUMP_TO = \@Game::Checkers::Squares::JUMP_TO;
65  
66 18 my @DIRS = @Game::Checkers::Squares::DIRS;
67  
68 18 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 18 );
78  
79 has seed => (
80 is => 'rw',
81 isa => Int,
82 default => 0
83 18 );
84  
85 has transposition => (
86 is => 'rw',
87 isa => Bool,
88 default => 1
89 18 );
90  
91 has last_search => (
92 is => 'rw'
93 18 );
94  
95 1813 ▶sub choose {
Subroutine choose: called CC=13 SCAR=26.0
Pod documented
96 1813 my ($self, $game) = @_;
97 1813 ▶ return undef if $game->result;
Branch: 1 branch
BranchTrueFalseTotal
if $game->result 13 1800 1813
98  
99 1800 my $legal = $game->legal_moves;
100 1800 ▶ return undef unless @{$legal};
Branch: 1 branch
BranchTrueFalseTotal
unless @{$legal;} 0 1800 1800
101  
102 1800 ▶ if (@{$legal} == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (@{$legal;} == 1) 232 1568 1800
103 232 $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 232 return $legal->[0];
112 }
113  
114 1568 ▶ 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 1568 0 1568
115 or die 'level must be 1 .. 5, got ' . $self->level;
116  
117 1568 my $position = [@{$game->board->position}];
118 1568 my $turn = $game->turn;
119 my $state = {
120 nodes => 0,
121 budget => $spec->{nodes},
122 jitter => $spec->{jitter},
123 1568 table => {},
124 history => {},
125 killers => [],
126 seen => $self->_seen($game),
127 aborted => 0
128 };
129  
130 1568 my ($best, $score, $reached);
131 1568 for my $depth (1 .. $spec->{depth}) {
132 5813 ▶ last if $state->{nodes} > $state->{budget};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"nodes"} > $state->{"budget"} 0 5813 5813
133 5813 $state->{aborted} = 0;
134 5813 my ($iteration_score, $move) = $self->_root(
135 $state, $position, $turn, $depth, $game->no_progress, $game->ply
136 );
137 5813 ▶ last if $state->{aborted} || !$move;
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"aborted"} or not $move 692 5121 5813
Condition66%2/3
$state->{"aborted"} or not $move
l!l&&r!l&&!r
69205121
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 5121 ($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 1568 ▶ jump => scalar @{$best->[RM_CAPTURES]}
Branch: 1 branch
BranchTrueFalseTotal
$best ? : 1568 0 1568
145 })
146 : $legal->[0]->notation;
147  
148 $self->last_search({
149 depth => $reached || 0,
150 nodes => $state->{nodes},
151 1568 ▶ score => $score,
Condition50%1/2
$reached || 0
l!l
15680
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 1568 for my $move (@{$legal}) {
160 6554 ▶ return $move if $move->notation eq $notation;
Branch: 1 branch
BranchTrueFalseTotal
if $move->notation eq $notation 1568 4986 6554
161 }
162 0 return $legal->[0];
163 }
164  
165 1568 ▶sub _seen {
Subroutine _seen: called CC=3 SCAR=11.0
166 1568 my ($self, $game) = @_;
167 1568 my ($position, $turn) =
168 Game::Checkers::Notation::position_from_fen($game->fen);
169 1568 my %seen = (_key($position, $turn) => 1);
170 1568 for my $move (@{$game->history}) {
171 84630 Game::Checkers::Rules::apply($position, $move->to_raw);
172 84630 ▶ $turn = $turn eq 'black' ? 'white' : 'black';
Branch: 1 branch
BranchTrueFalseTotal
$turn eq 'black' ? : 42704 41926 84630
173 84630 $seen{_key($position, $turn)}++;
174 }
175 1568 return \%seen;
176 }
177  
178 4550058 ▶sub _key {
Subroutine _key: called CC=1 SCAR=0.0
179 4550058 my ($position, $turn) = @_;
180 4550058 return pack('c32', @{$position}[1 .. 32]) . $turn;
181 }
182  
183 5813 ▶sub _root {
Subroutine _root: called CC=12 SCAR=24.9
184 5813 my ($self, $state, $position, $turn, $depth, $no_progress, $ply) = @_;
185 5813 my $moves = Game::Checkers::Rules::generate($position, $turn);
186 5813 ▶ return (undef, undef) unless @{$moves};
Branch: 1 branch
BranchTrueFalseTotal
unless @{$moves;} 0 5813 5813
187  
188 5813 ▶ my $forced = @{$moves->[0][RM_CAPTURES]} ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
@{$moves->[0][4];} ? : 265 5548 5813
189 5813 ▶ my ($child_depth, $child_extension) = $forced
Branch: 1 branch
BranchTrueFalseTotal
$forced ? : 265 5548 5813
190 ? ($depth, 1)
191 : ($depth - 1, 0);
192  
193 5813 my $alpha = -INFINITY();
194 5813 my ($best, $best_score);
195 5813 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 41402 ▶ my $bound = $state->{jitter} ? -INFINITY() : $alpha;
Branch: 1 branch
BranchTrueFalseTotal
$state->{'jitter'} ? : 40214 1188 41402
201 41402 my $score = $self->_child(
202 $state, $position, $turn, $raw,
203 $child_depth, -INFINITY(), -$bound, 1, $child_extension, $no_progress
204 );
205 41402 ▶ return (undef, undef) if $state->{aborted};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"aborted"} 692 40710 41402
206  
207 40710 ▶ $score += _jitter($self->seed, $ply, $raw) if $state->{jitter};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"jitter"} 39527 1183 40710
208  
209 40710 ▶ if (!defined $best_score || $score > $best_score) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $best_score or $score > $best_score) 14448 26262 40710
Condition100%3/3
not defined $best_score or $score > $best_score
l!l&&r!l&&!r
5782866626262
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 14448 ($best, $best_score) = ($raw, $score);
211 14448 ▶ $alpha = $score if $score > $alpha && !$state->{jitter};
Branch: 1 branch
BranchTrueFalseTotal
if $score > $alpha and not $state->{"jitter"} 393 14055 14448
Condition66%2/3
$score > $alpha and not $state->{"jitter"}
!ll&&!rl&&r
014055393
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 5121 return ($best_score, $best);
215 }
216  
217 2228407 ▶sub _child {
Subroutine _child: called CC=4 SCAR=13.9
218 2228407 my ($self, $state, $position, $turn, $raw, $depth, $alpha, $beta, $ply,
219 $extension, $no_progress) = @_;
220  
221 2228407 ▶ my $next = $turn eq 'black' ? 'white' : 'black';
Branch: 1 branch
BranchTrueFalseTotal
$turn eq 'black' ? : 1095007 1133400 2228407
222 2228407 ▶ my $progress = Game::Checkers::Rules::progress($raw) ? 0 : $no_progress + 1;
Branch: 1 branch
BranchTrueFalseTotal
Game::Checkers::Rules::progress($raw) ? : 1618060 610347 2228407
223  
224 2228407 Game::Checkers::Rules::apply($position, $raw);
225 2228407 my $key = _key($position, $next);
226 2228407 $state->{seen}{$key}++;
227  
228 2228407 my $score = -$self->_search(
229 $state, $position, $next, $depth, $alpha, $beta, $ply, $extension, $progress
230 );
231  
232 2228407 ▶ delete $state->{seen}{$key} unless --$state->{seen}{$key};
Branch: 1 branch
BranchTrueFalseTotal
unless --$state->{"seen"}{$key} 2222752 5655 2228407
233 2228407 Game::Checkers::Rules::unapply($position, $raw);
234 2228407 return $score;
235 }
236  
237 2228407 ▶sub _search {
Subroutine _search: called CC=34 SCAR=35.3
238 2228407 my ($self, $state, $position, $turn, $depth, $alpha, $beta, $ply,
239 $extension, $no_progress) = @_;
240  
241 2228407 $state->{nodes}++;
242 2228407 ▶ if ($state->{nodes} >= $state->{budget}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($state->{"nodes"} >= $state->{"budget"}) 692 2227715 2228407
243 692 $state->{aborted} = 1;
244 692 return 0;
245 }
246  
247 2227715 my $key = _key($position, $turn);
248 2227715 ▶ return 0 if ($state->{seen}{$key} || 0) >= 3;
Branch: 1 branch
BranchTrueFalseTotal
if ($state->{"seen"}{$key} || 0) >= 3 496 2227219 2227715
Condition50%1/2
$state->{'seen'}{$key} || 0
l!l
22277150
MC/DC0%0/1
$state->{'seen'}{$key} || 0
$state->{'seen'}{$key}
Truth table50%1/2
A
A= $state->{'seen'}{$key}
Aresult
11
00
249 2227219 ▶ return 0 if $no_progress >= NO_PROGRESS_PLIES;
Branch: 1 branch
BranchTrueFalseTotal
if $no_progress >= 80 3300 2223919 2227219
250  
251 2223919 ▶ my $entry = $self->transposition ? $state->{table}{$key} : undef;
Branch: 1 branch
BranchTrueFalseTotal
$self->transposition ? : 2221340 2579 2223919
252 2223919 my $table_move;
253 2223919 ▶ if ($entry) {
Branch: 1 branch
BranchTrueFalseTotal
if ($entry) 307136 1916783 2223919
254 307136 $table_move = $entry->[3];
255 307136 ▶ if ($entry->[0] >= $depth && abs($entry->[1]) < MATE - 100) {
Branch: 1 branch
BranchTrueFalseTotal
if ($entry->[0] >= $depth and abs $entry->[1] < 9900) 70235 236901 307136
Condition100%3/3
$entry->[0] >= $depth and abs $entry->[1] < 9900
!ll&&!rl&&r
230447645470235
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 70235 ▶ return $entry->[1] if $entry->[2] == EXACT;
Branch: 1 branch
BranchTrueFalseTotal
if $entry->[2] == 0 7317 62918 70235
257 62918 ▶ return $entry->[1] if $entry->[2] == LOWER && $entry->[1] >= $beta;
Branch: 1 branch
BranchTrueFalseTotal
if $entry->[2] == 1 and $entry->[1] >= $beta 40593 22325 62918
Condition100%3/3
$entry->[2] == 1 and $entry->[1] >= $beta
!ll&&!rl&&r
17036528940593
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 22325 ▶ return $entry->[1] if $entry->[2] == UPPER && $entry->[1] <= $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $entry->[2] == -1 and $entry->[1] <= $alpha 13729 8596 22325
Condition100%3/3
$entry->[2] == -1 and $entry->[1] <= $alpha
!ll&&!rl&&r
5289330713729
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 2162280 my $moves = Game::Checkers::Rules::generate($position, $turn);
263 2162280 ▶ return -MATE() + $ply unless @{$moves};
Branch: 1 branch
BranchTrueFalseTotal
unless @{$moves;} 14407 2147873 2162280
264  
265 2147873 ▶ my $forced = @{$moves->[0][RM_CAPTURES]} ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
@{$moves->[0][4];} ? : 636776 1511097 2147873
266 2147873 ▶ my $extend = $forced && $extension < MAX_EXTENSION ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
$forced && $extension < 8 ? : 632804 1515069 2147873
Condition100%3/3
$forced and $extension < 8
!ll&&!rl&&r
15110973972632804
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 2147873 ▶ return _evaluate($position, $turn) if $depth <= 0 && !$extend;
Branch: 1 branch
BranchTrueFalseTotal
if $depth <= 0 and not $extend 1135621 1012252 2147873
Condition100%3/3
$depth <= 0 and not $extend
!ll&&!rl&&r
5392474730051135621
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 1012252 ▶ my ($child_depth, $child_extension) = $extend
Branch: 1 branch
BranchTrueFalseTotal
$extend ? : 632804 379448 1012252
270 ? ($depth, $extension + 1)
271 : ($depth - 1, $extension);
272  
273 1012252 my $original = $alpha;
274 1012252 my ($best_score, $best_move) = (-INFINITY(), undef);
275 1012252 for my $raw (@{$self->_ordered($state, $moves, $ply, $table_move)}) {
276 2187005 my $score = $self->_child(
277 $state, $position, $turn, $raw,
278 $child_depth, -$beta, -$alpha, $ply + 1, $child_extension, $no_progress
279 );
280 2187005 ▶ return 0 if $state->{aborted};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"aborted"} 3490 2183515 2187005
281  
282 2183515 ▶ if ($score > $best_score) {
Branch: 1 branch
BranchTrueFalseTotal
if ($score > $best_score) 1211409 972106 2183515
283 1211409 ($best_score, $best_move) = ($score, $raw);
284 1211409 ▶ $alpha = $score if $score > $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $score > $alpha 886532 324877 1211409
285 }
286 2183515 ▶ next if $alpha < $beta;
Branch: 1 branch
BranchTrueFalseTotal
if $alpha < $beta 1573189 610326 2183515
287  
288 610326 my $name = $raw->[RM_FROM] . '-' . $raw->[RM_TO];
289 610326 $state->{history}{$name} += $depth * $depth;
290 610326 ▶ my $killers = $state->{killers}[$ply] ||= [];
Condition100%2/2
$state->{"killers"}[$ply] ||= []
l!l
6009759351
MC/DC100%1/1
$state->{"killers"}[$ply] ||= []
$state->{"killers"}[$ply]
Truth table100%2/2
A
A= $state->{"killers"}[$ply]
Aresult
11
00
291 449065 unshift @{$killers}, $name
292 610326 ▶ unless @{$killers} && $killers->[0] eq $name;
Branch: 1 branch
BranchTrueFalseTotal
unless @{$killers;} and $killers->[0] eq $name 449065 161261 610326
Condition100%3/3
@{$killers;} and $killers->[0] eq $name
!ll&&!rl&&r
9351439714161261
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 610326 ▶ pop @{$killers} while @{$killers} > 2;
Branch: 1 branch
BranchTrueFalseTotal
@{$killers;} > 2 and do { pop @{$killers;} } 430949 610326 1041275
294 610326 last;
295 }
296  
297 1008762 ▶ if ($self->transposition) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->transposition) 1007466 1296 1008762
298 1007466 ▶ my $flag = $best_score <= $original ? UPPER
Branch: 2 branches
BranchTrueFalseTotal
$best_score <= $original ? : 215305 792161 1007466
$best_score >= $beta ? : 609459 182702 792161
299 : $best_score >= $beta ? LOWER
300 : EXACT;
301 $state->{table}{$key} = [
302 $depth, $best_score, $flag,
303 1007466 ▶ $best_move && [@{$best_move}]
Condition50%1/2
$best_move && [@{$best_move;}]
!ll
01007466
MC/DC0%0/1
$best_move && [@{$best_move;}]
$best_move
Truth table50%1/2
A
A= $best_move
Aresult
00
11
304 ];
305 }
306 1008762 return $best_score;
307 }
308  
309 1018065 ▶sub _ordered {
Subroutine _ordered: called CC=13 SCAR=25.6
310 1018065 my ($self, $state, $moves, $ply, $table_move) = @_;
311 my $wanted = $table_move
312 1018065 ▶ ? join('.', @{$table_move->[RM_PATH]})
Branch: 1 branch
BranchTrueFalseTotal
$table_move ? : 245415 772650 1018065
313 : '';
314 1018065 ▶ my $killers = $state->{killers}[$ply] || [];
Condition100%2/2
$state->{'killers'}[$ply] || []
l!l
94767870387
MC/DC100%1/1
$state->{'killers'}[$ply] || []
$state->{'killers'}[$ply]
Truth table100%2/2
A
A= $state->{'killers'}[$ply]
Aresult
11
00
315 1018065 my $history = $state->{history};
316  
317 1018065 my @scored;
318 1018065 for my $raw (@{$moves}) {
319 3629247 my $name = $raw->[RM_FROM] . '-' . $raw->[RM_TO];
320 3629247 my $score = 0;
321 3629247 ▶ $score += 1_000_000 if $wanted && join('.', @{$raw->[RM_PATH]}) eq $wanted;
Branch: 1 branch
BranchTrueFalseTotal
if $wanted and join(".", @{$raw->[3];}) eq $wanted 245415 3383832 3629247
Condition100%3/3
$wanted and join(".", @{$raw->[3];}) eq $wanted
!ll&&!rl&&r
2789016594816245415
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 3629247 ▶ $score += 1_000 + (10 * scalar @{$raw->[RM_CAPTURES]}) if @{$raw->[RM_CAPTURES]};
Branch: 1 branch
BranchTrueFalseTotal
if @{$raw->[4];} 773735 2855512 3629247
323 3629247 ▶ $score += 500 if $raw->[RM_PROMOTED];
Branch: 1 branch
BranchTrueFalseTotal
if $raw->[2] 110477 3518770 3629247
324 3629247 ▶ $score += 400 if @{$killers} && $killers->[0] eq $name;
Branch: 1 branch
BranchTrueFalseTotal
if @{$killers;} and $killers->[0] eq $name 217908 3411339 3629247
Condition100%3/3
@{$killers;} and $killers->[0] eq $name
!ll&&!rl&&r
2719573139382217908
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 3629247 ▶ $score += 300 if @{$killers} > 1 && $killers->[1] eq $name;
Branch: 1 branch
BranchTrueFalseTotal
if @{$killers;} > 1 and $killers->[1] eq $name 115839 3513408 3629247
Condition100%3/3
@{$killers;} > 1 and $killers->[1] eq $name
!ll&&!rl&&r
3221803191228115839
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 3629247 ▶ $score += $history->{$name} || 0;
Condition100%2/2
$history->{$name} || 0
l!l
11522532476994
MC/DC100%1/1
$history->{$name} || 0
$history->{$name}
Truth table100%2/2
A
A= $history->{$name}
Aresult
11
00
327 3629247 push @scored, [$score, $raw];
328 }
329 1018065 return [map { $_->[1] } sort { $b->[0] <=> $a->[0] } @scored];
330 }
331  
332 1568 ▶sub _pv {
Subroutine _pv: called CC=8 SCAR=20.8
333 1568 my ($self, $state, $position, $turn, $first) = @_;
334 1568 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 1568 my $raw = $first;
340 1568 ▶ while (@pv < MAX_PV) {
Branch: 1 branch
BranchTrueFalseTotal
if (@pv < 20) 9306 0 9306
341 9306 ▶ unless ($raw) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($raw) 7738 1568 9306
342 7738 ▶ my $entry = $state->{table}{_key($position, $turn)} or last;
Branch: 1 branch
BranchTrueFalseTotal
my $entry = $state->{"table"}{_key($position, $turn)} or last 6170 1568 7738
343 6170 ▶ $raw = $entry->[3] or last;
Branch: 1 branch
BranchTrueFalseTotal
$raw = $entry->[3] or last 6170 0 6170
344 }
345 7738 my $legal = Game::Checkers::Rules::generate($position, $turn);
346 7738 my $path = join '.', @{$raw->[RM_PATH]};
347 7738 ▶ last unless grep { join('.', @{$_->[RM_PATH]}) eq $path } @{$legal};
Branch: 1 branch
BranchTrueFalseTotal
unless grep {join(".", @{$_->[3];}) eq $path;} @{$legal;} 0 7738 7738
348 push @pv, Game::Checkers::Notation::format_move({
349 squares => $raw->[RM_PATH],
350 7738 jump => scalar @{$raw->[RM_CAPTURES]}
351 });
352 7738 Game::Checkers::Rules::apply($position, $raw);
353 7738 push @undo, $raw;
354 7738 ▶ $turn = $turn eq 'black' ? 'white' : 'black';
Branch: 1 branch
BranchTrueFalseTotal
$turn eq 'black' ? : 3847 3891 7738
355 7738 undef $raw;
356 }
357 1568 ▶ Game::Checkers::Rules::unapply($position, pop @undo) while @undo;
Branch: 1 branch
BranchTrueFalseTotal
@undo and do { Game::Checkers::Rules::unapply($position, pop @undo) } 7738 1568 9306
358 1568 return \@pv;
359 }
360  
361 39527 ▶sub _jitter {
Subroutine _jitter: called CC=2 SCAR=6.9
362 39527 my ($seed, $ply, $raw) = @_;
363 39527 my $string = $seed . ':' . $ply . ':' . join '.', @{$raw->[RM_PATH]};
364 39527 my $hash = 0;
365 39527 $hash = (($hash * 33) + ord) % 65_521 for split //, $string;
366 39527 return $hash % 25;
367 }
368  
369 1135621 ▶sub _evaluate {
Subroutine _evaluate: called CC=53 SCAR=39.7
370 1135621 my ($position, $turn) = @_;
371 1135621 my $score = 0;
372 1135621 my (%men, %kings, %back, %mobility, @kings, @pieces);
373  
374 1135621 for my $square (1 .. 32) {
375 36339872 ▶ my $value = $position->[$square] or next;
Branch: 1 branch
BranchTrueFalseTotal
my $value = $position->[$square] or next 12876259 23463613 36339872
376 12876259 ▶ my $sign = $value > 0 ? 1 : -1;
Branch: 1 branch
BranchTrueFalseTotal
$value > 0 ? : 6422084 6454175 12876259
377 12876259 ▶ my $king = abs($value) == 2 ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
abs $value == 2 ? : 2644464 10231795 12876259
378 12876259 my $row = $ROW->[$square];
379 12876259 my $col = $COL->[$square];
380  
381 12876259 ▶ push @{$pieces[$sign > 0 ? 0 : 1]}, $square;
Branch: 1 branch
BranchTrueFalseTotal
$sign > 0 ? : 6422084 6454175 12876259
382 12876259 ▶ if ($king) {
Branch: 1 branch
BranchTrueFalseTotal
if ($king) { } 2644464 10231795 12876259
383 2644464 $kings{$sign}++;
384 2644464 $score += $sign * $WEIGHT{king};
385 2644464 ▶ push @{$kings[$sign > 0 ? 0 : 1]}, $square;
Branch: 1 branch
BranchTrueFalseTotal
$sign > 0 ? : 1271170 1373294 2644464
386 } else {
387 10231795 $men{$sign}++;
388 10231795 $score += $sign * $WEIGHT{man};
389 10231795 ▶ $score += $sign * $WEIGHT{advance} * ($sign > 0 ? $row : 7 - $row);
Branch: 1 branch
BranchTrueFalseTotal
$sign > 0 ? : 5150914 5080881 10231795
390 10231795 ▶ $score += $sign * $WEIGHT{edge} if $col == 0 || $col == 7;
Branch: 1 branch
BranchTrueFalseTotal
if $col == 0 or $col == 7 2772357 7459438 10231795
Condition100%3/3
$col == 0 or $col == 7
l!l&&r!l&&!r
138245413899037459438
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 10231795 ▶ $back{$sign}++ if ($sign > 0 ? $row : 7 - $row) == 0;
Branch: 2 branches
BranchTrueFalseTotal
if ($sign > 0 ? $row : 7 - $row) == 0 3422822 6808973 10231795
$sign > 0 ? : 5150914 5080881 10231795
392 }
393 12876259 ▶ $score += $sign * $WEIGHT{centre} if $col == 3 || $col == 4;
Branch: 1 branch
BranchTrueFalseTotal
if $col == 3 or $col == 4 3339720 9536539 12876259
Condition100%3/3
$col == 3 or $col == 4
l!l&&r!l&&!r
168653316531879536539
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 12876259 my $moves = 0;
398 12876259 my $base = $square * 4;
399 12876259 ▶ for my $dir ($king ? @DIRS : @{$FORWARD{$sign}}) {
Branch: 1 branch
BranchTrueFalseTotal
$king ? : 2644464 10231795 12876259
400 31041446 my $step = $STEP->[$base + $dir];
401 31041446 ▶ $moves++ if $step && !$position->[$step];
Branch: 1 branch
BranchTrueFalseTotal
if $step and not $position->[$step] 18264747 12776699 31041446
Condition100%3/3
$step and not $position->[$step]
!ll&&!rl&&r
5090352768634718264747
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 31041446 ▶ my $landing = $JUMP_TO->[$base + $dir] or next;
Branch: 1 branch
BranchTrueFalseTotal
my $landing = $$JUMP_TO[$base + $dir] or next 20809473 10231973 31041446
403 20809473 ▶ next if $position->[$landing];
Branch: 1 branch
BranchTrueFalseTotal
if $position->[$landing] 7351176 13458297 20809473
404 13458297 ▶ my $victim = $position->[$JUMP_OVER->[$base + $dir]] or next;
Branch: 1 branch
BranchTrueFalseTotal
my $victim = $$position[$$JUMP_OVER[$base + $dir]] or next 3599175 9859122 13458297
405 3599175 ▶ $moves++ if ($victim > 0 ? 1 : -1) != $sign;
Branch: 2 branches
BranchTrueFalseTotal
if ($victim > 0 ? 1 : -1) != $sign 87265 3511910 3599175
$victim > 0 ? : 1767355 1831820 3599175
406 }
407 12876259 $mobility{$sign} += $moves;
408 12876259 ▶ $score += $sign * $WEIGHT{trapped_king} if $king && !$moves;
Branch: 1 branch
BranchTrueFalseTotal
if $king and not $moves 9067 12867192 12876259
Condition100%3/3
$king and not $moves
!ll&&!rl&&r
1023179526353979067
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 1135621 ▶ $score += $WEIGHT{back_rank} * ($back{1} || 0) if $men{-1};
Branch: 1 branch
BranchTrueFalseTotal
if $men{-1} 868503 267118 1135621
Condition100%2/2
$back{'1'} || 0
l!l
586294282209
MC/DC100%1/1
$back{'1'} || 0
$back{'1'}
Truth table100%2/2
A
A= $back{'1'}
Aresult
11
00
413 1135621 ▶ $score -= $WEIGHT{back_rank} * ($back{-1} || 0) if $men{1};
Branch: 1 branch
BranchTrueFalseTotal
if $men{1} 846164 289457 1135621
Condition100%2/2
$back{'-1'} || 0
l!l
640573205591
MC/DC100%1/1
$back{'-1'} || 0
$back{'-1'}
Truth table100%2/2
A
A= $back{'-1'}
Aresult
11
00
414 1135621 ▶ $score += $WEIGHT{mobility} * (($mobility{1} || 0) - ($mobility{-1} || 0));
Condition100%4/4
$mobility{'1'} || 0
l!l
113560813
$mobility{'-1'} || 0
l!l
11356156
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 1135621 ▶ my $total = ($men{1} || 0) + ($kings{1} || 0) + ($men{-1} || 0) + ($kings{-1} || 0);
Condition100%8/8
$men{'1'} || 0
l!l
846164289457
$kings{'1'} || 0
l!l
633322502299
$men{'-1'} || 0
l!l
868503267118
$kings{'-1'} || 0
l!l
617757517864
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 1135621 ▶ if ($total <= 6 && $total) {
Branch: 1 branch
BranchTrueFalseTotal
if ($total <= 6 and $total) 298396 837225 1135621
Condition66%2/3
$total <= 6 and $total
!ll&&!rl&&r
8372250298396
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 298396 ▶ my $black = ($men{1} || 0) * $WEIGHT{man} + ($kings{1} || 0) * $WEIGHT{king};
Condition100%4/4
$men{'1'} || 0
l!l
58730239666
$kings{'1'} || 0
l!l
2907087688
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 298396 ▶ my $white = ($men{-1} || 0) * $WEIGHT{man} + ($kings{-1} || 0) * $WEIGHT{king};
Condition100%4/4
$men{'-1'} || 0
l!l
87710210686
$kings{'-1'} || 0
l!l
25963438762
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 298396 ▶ my $stronger = $black > $white ? 0 : $white > $black ? 1 : undef;
Branch: 2 branches
BranchTrueFalseTotal
$black > $white ? : 100868 197528 298396
$white > $black ? : 108057 89471 197528
421 298396 ▶ if (defined $stronger && $kings[$stronger]) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $stronger and $kings[$stronger]) 181923 116473 298396
Condition100%3/3
defined $stronger and $kings[$stronger]
!ll&&!rl&&r
8947127002181923
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 181923 my $distance = 0;
423 181923 for my $king (@{$kings[$stronger]}) {
424 468566 ▶ for my $enemy (@{$pieces[$stronger ? 0 : 1] || []}) {
Branch: 1 branch
BranchTrueFalseTotal
$stronger ? : 213931 254635 468566
Condition50%1/2
$pieces[$stronger ? 0 : 1] || []
l!l
4685660
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 814707 my $rows = abs($ROW->[$king] - $ROW->[$enemy]);
426 814707 my $cols = abs($COL->[$king] - $COL->[$enemy]);
427 814707 ▶ $distance += $rows > $cols ? $rows : $cols;
Branch: 1 branch
BranchTrueFalseTotal
$rows > $cols ? : 345241 469466 814707
428 }
429 }
430 181923 ▶ $score += ($stronger ? -1 : 1) * $WEIGHT{chase} * $distance;
Branch: 1 branch
BranchTrueFalseTotal
$stronger ? : 82027 99896 181923
431 }
432 }
433  
434 1135621 ▶ return $turn eq 'black' ? $score : -$score;
Branch: 1 branch
BranchTrueFalseTotal
$turn eq 'black' ? : 574434 561187 1135621
435 }
436  
437 18 1;
438  
439 __END__
↑ Summary blib/lib/Game/Checkers/Notation.pm »