blib/lib/Game/Merrills/Bot.pm

filter: Statementstmt 100% 292 / 292 Branchbran 96.0% 144 / 150 Conditioncond 87.5% 70 / 80 MC/DCmcdc 74.4% 35 / 47 Subroutinesub 100% 25 / 25 Podpod 75.0% 3 / 4 totaltotal 95.1% 569 / 598 CC 118 SCAR 28.0
CC
118
Cov
97%
_search
33.0
_evaluate
23.0
choose
14.1
CRAP 16.4
« blib/lib/Game/Merrills/Terminal.pm ↑ Summary blib/lib/Game/Merrills/Notation.pm »
1 package Game::Merrills::Bot;
2  
3 74 ▶use strict;
Subroutine __ANON__: called CC=1 SCAR=0.0
4 74 ▶use warnings;
Subroutine __ANON__: called CC=1 SCAR=0.0
5  
6 74 ▶use Object::Proto::Sugar -types;
Subroutine __ANON__: called CC=1 SCAR=0.0
7 74 ▶use Game::Merrills ();
Subroutine __ANON__: called CC=1 SCAR=0.0
8 74 ▶use Game::Merrills::Points;
Subroutine __ANON__: called CC=1 SCAR=0.0
9 74 ▶use Game::Merrills::Notation;
Subroutine __ANON__: called CC=1 SCAR=0.0
10 74 ▶use Game::Merrills::Rules;
Subroutine __ANON__: called CC=1 SCAR=0.0
11 74 ▶use Game::Merrills::Move;
Subroutine __ANON__: called CC=1 SCAR=0.0
12  
13 74 our $VERSION = '0.02';
14  
15 74 ▶use constant {
Subroutine __ANON__: called CC=1 SCAR=0.0
16 74 WIN => 10_000,
17 INFINITY => 1_000_000,
18 MAX_EXTENSION => 2,
19 MAX_PV => 20,
20 EXACT => 0,
21 LOWER => 1,
22 UPPER => -1,
23 74 };
24  
25 74 ▶use constant {
Subroutine __ANON__: called CC=1 SCAR=0.0
26 74 RM_FROM => Game::Merrills::Move::RM_FROM,
27 RM_TO => Game::Merrills::Move::RM_TO,
28 RM_REMOVE => Game::Merrills::Move::RM_REMOVE,
29 RM_CLOSES => Game::Merrills::Move::RM_CLOSES,
30 HAND_WHITE => Game::Merrills::Rules::HAND_WHITE,
31 HAND_BLACK => Game::Merrills::Rules::HAND_BLACK,
32 74 };
33  
34 74 our (%LEVEL, $MAN, $OPEN_TWO, $REACH, $MOBILITY, $JUNCTION);
35  
36 74 ▶BEGIN {
Subroutine BEGIN: called CC=1 SCAR=0.0
37 74 %LEVEL = (
38 1 => { depth => 1, nodes => 300, jitter => 1 },
39 2 => { depth => 3, nodes => 3_000, jitter => 1 },
40 3 => { depth => 5, nodes => 20_000, jitter => 0 },
41 4 => { depth => 7, nodes => 100_000, jitter => 0 },
42 5 => { depth => 9, nodes => 400_000, jitter => 0 },
43 );
44  
45 74 $MAN = 100;
46 74 $OPEN_TWO = 8;
47 74 $REACH = 10;
48 74 $MOBILITY = 2;
49 74 $JUNCTION = 3;
50 }
51  
52 74 my %OTHER = (white => 'black', black => 'white');
53 74 my %VALUE = (white => 1, black => -1);
54  
55 74 my $ADJACENT = \@Game::Merrills::Points::ADJACENT;
56 74 my $MILLS = \@Game::Merrills::Points::MILLS;
57 74 my $MILLS_OF = \@Game::Merrills::Points::MILLS_OF;
58  
59 has level => (
60 is => 'ro',
61 isa => Int,
62 default => 3
63 74 );
64  
65 has seed => (
66 is => 'ro',
67 isa => Int,
68 default => 0
69 74 );
70  
71 has transposition => (
72 is => 'rw',
73 isa => Bool,
74 default => 1
75 74 );
76  
77 has last_search => (
78 is => 'rw'
79 74 );
80  
81 294 ▶sub BUILD {
Subroutine BUILD: called CC=4 SCAR=14.2
Pod undocumented
82 294 my ($self) = @_;
83 die 'level must be 1 .. 5, got ' . (defined $self->level ? "'" . $self->level . "'" : 'undef')
84 294 ▶ unless defined $self->level && $LEVEL{ $self->level };
Branch: 2 branches
BranchTrueFalseTotal
unless defined $self->level and $Game::Merrills::Bot::LEVEL{$self->level} 3 291 294
defined $self->level ? : 3 0 3
Condition66%2/3
defined $self->level and $Game::Merrills::Bot::LEVEL{$self->level}
!ll&&!rl&&r
03291
MC/DC50%1/2
defined $self->level and $Game::Merrills::Bot::LEVEL{$self->level}
defined $self->level $Game::Merrills::Bot::LEVEL{$self->level}
Truth table66%2/3
A and B
A= defined $self->levelB= $Game::Merrills::Bot::LEVEL{$self->level}
ABresult
0X0
100
111
85 291 return $self;
86 }
87  
88 77 ▶sub levels {
Subroutine levels: called CC=1 SCAR=0.0
Pod documented
89 77 return sort { $a <=> $b } keys %LEVEL;
90 }
91  
92 15 ▶sub setting_for {
Subroutine setting_for: called CC=4 SCAR=13.9
Pod documented
93 15 my ($class, $level) = @_;
94 15 ▶ my $setting = defined $level ? $LEVEL{$level} : undef;
Branch: 1 branch
BranchTrueFalseTotal
defined $level ? : 14 1 15
95 15 ▶ die 'level must be 1 .. 5, got ' . (defined $level ? "'$level'" : 'undef') unless $setting;
Branch: 2 branches
BranchTrueFalseTotal
unless $setting 4 11 15
defined $level ? : 3 1 4
96 11 return { %{$setting} };
97 }
98  
99 2345 ▶sub choose {
Subroutine choose: called CC=14 SCAR=26.4
Pod documented
100 2345 my ($self, $game) = @_;
101 2345 ▶ return undef if $game->result;
Branch: 1 branch
BranchTrueFalseTotal
if $game->result 2 2343 2345
102  
103 2343 my $legal = $game->legal_moves;
104 2343 ▶ return undef unless @{$legal};
Branch: 1 branch
BranchTrueFalseTotal
unless @{$legal;} 0 2343 2343
105  
106 2343 ▶ if (@{$legal} == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (@{$legal;} == 1) 8 2335 2343
107 8 $self->last_search({
108 depth => 0,
109 nodes => 0,
110 score => undef,
111 forced => 1,
112 move => $legal->[0]->notation,
113 pv => [ $legal->[0]->notation ]
114 });
115 8 return $legal->[0];
116 }
117  
118 2335 my $spec = $LEVEL{ $self->level };
119 2335 my $position = Game::Merrills::Rules::position($game->board);
120 2335 my $turn = $game->turn;
121 my $state = {
122 nodes => 0,
123 budget => $spec->{nodes},
124 jitter => $spec->{jitter},
125 2335 ▶ table => {},
Branch: 1 branch
BranchTrueFalseTotal
$game->flying ? : 2333 2 2335
Condition50%1/2
$Game::Merrills::NO_MILL_LIMIT || 0
l!l
23350
MC/DC0%0/1
$Game::Merrills::NO_MILL_LIMIT || 0
$Game::Merrills::NO_MILL_LIMIT
Truth table50%1/2
A
A= $Game::Merrills::NO_MILL_LIMIT
Aresult
11
00
126 history => {},
127 killers => [],
128 flying => $game->flying ? 1 : 0,
129 limit => $Game::Merrills::NO_MILL_LIMIT || 0,
130 aborted => 0
131 };
132 2335 my $seen = { %{ $game->repetition } };
133  
134 2335 my ($best, $score, $reached);
135 2335 for my $depth (1 .. $spec->{depth}) {
136 3977 ▶ last if $state->{nodes} >= $state->{budget};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"nodes"} >= $state->{"budget"} 0 3977 3977
137 3977 $state->{aborted} = 0;
138 3977 my ($iteration_score, $move) = $self->_root(
139 $state, $position, $turn, $depth, $game->no_mill, $seen, $game->ply
140 );
141 3977 ▶ last if $state->{aborted} || !$move;
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"aborted"} or not $move 135 3842 3977
Condition66%2/3
$state->{"aborted"} or not $move
l!l&&r!l&&!r
13503842
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
142 3842 ($best, $score, $reached) = ($move, $iteration_score, $depth);
143 }
144  
145 2335 my $chosen = $legal->[0];
146 2335 ▶ if ($best) {
Branch: 1 branch
BranchTrueFalseTotal
if ($best) 2311 24 2335
147 2311 my $name = _name($best);
148 2311 for my $move (@{$legal}) {
149 19814 ▶ next unless _name($move->to_raw) eq $name;
Branch: 1 branch
BranchTrueFalseTotal
unless _name($move->to_raw) eq $name 17503 2311 19814
150 2311 $chosen = $move;
151 2311 last;
152 }
153 }
154  
155 $self->last_search({
156 depth => $reached || 0,
157 nodes => $state->{nodes},
158 2335 ▶ score => $score,
Condition100%2/2
$reached || 0
l!l
231124
MC/DC100%1/1
$reached || 0
$reached
Truth table100%2/2
A
A= $reached
Aresult
11
00
159 forced => 0,
160 move => $chosen->notation,
161 pv => $self->_pv($state, $position, $turn, $best)
162 });
163 2335 return $chosen;
164 }
165  
166 6702642 ▶sub _name {
Subroutine _name: called CC=2 SCAR=6.9
167 6702642 my ($raw) = @_;
168 6702642 ▶ return join '.', map { defined $_ ? $_ : '-' } @{$raw}[ RM_FROM, RM_TO, RM_REMOVE ];
Branch: 1 branch
BranchTrueFalseTotal
defined $_ ? : 11123549 8984377 20107926
169 }
170  
171 3854 ▶sub _notation {
Subroutine _notation: called CC=1 SCAR=0.0
172 3854 my ($raw) = @_;
173 3854 return Game::Merrills::Notation::format_move({
174 from => $raw->[RM_FROM],
175 to => $raw->[RM_TO],
176 remove => $raw->[RM_REMOVE],
177 });
178 }
179  
180 3977 ▶sub _root {
Subroutine _root: called CC=10 SCAR=23.0
181 3977 my ($self, $state, $position, $turn, $depth, $no_mill, $seen, $ply) = @_;
182 3977 my $moves = Game::Merrills::Rules::generate($position, $turn, $state->{flying});
183 3977 ▶ return (undef, undef) unless @{$moves};
Branch: 1 branch
BranchTrueFalseTotal
unless @{$moves;} 0 3977 3977
184  
185 3977 my $alpha = -INFINITY();
186 3977 my ($best, $best_score);
187 3977 for my $raw (@{ $self->_ordered($state, $moves, 0, undef) }) {
188 63915 ▶ my $bound = $state->{jitter} ? -INFINITY() : $alpha;
Branch: 1 branch
BranchTrueFalseTotal
$state->{'jitter'} ? : 51459 12456 63915
189 63915 my $score = $self->_child(
190 $state, $position, $turn, $raw,
191 $depth - 1, -INFINITY(), -$bound, 1, 0, $no_mill, $seen
192 );
193 63915 ▶ return (undef, undef) if $state->{aborted};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"aborted"} 135 63780 63915
194  
195 63780 ▶ $score += _jitter($self->seed, $ply, $raw) if $state->{jitter};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"jitter"} 51339 12441 63780
196  
197 63780 ▶ if (!defined $best_score || $score > $best_score) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $best_score or $score > $best_score) 11885 51895 63780
Condition100%3/3
not defined $best_score or $score > $best_score
l!l&&r!l&&!r
3975791051895
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
198 11885 ($best, $best_score) = ($raw, $score);
199 11885 ▶ $alpha = $score if $score > $alpha && !$state->{jitter};
Branch: 1 branch
BranchTrueFalseTotal
if $score > $alpha and not $state->{"jitter"} 1997 9888 11885
Condition66%2/3
$score > $alpha and not $state->{"jitter"}
!ll&&!rl&&r
098881997
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
200 }
201 }
202 3842 return ($best_score, $best);
203 }
204  
205 2302012 ▶sub _child {
Subroutine _child: called CC=7 SCAR=19.5
206 2302012 my ($self, $state, $position, $turn, $raw, $depth, $alpha, $beta, $ply,
207 $extension, $no_mill, $seen) = @_;
208  
209 2302012 my $next = $OTHER{$turn};
210 2302012 ▶ my ($child_seen, $child_quiet) = !defined $raw->[RM_FROM] || defined $raw->[RM_REMOVE]
Branch: 1 branch
BranchTrueFalseTotal
!defined($raw->[0]) || defined $raw->[2] ? : 1667226 634786 2302012
Condition100%3/3
not defined $raw->[0] or defined $raw->[2]
l!l&&r!l&&!r
1225769441457634786
MC/DC100%2/2
not defined $raw->[0] or defined $raw->[2]
not defined $raw->[0] defined $raw->[2]
Truth table100%3/3
not(A) or B
A= not defined $raw->[0]B= defined $raw->[2]
ABresult
1X1
011
000
211 ? ({}, 0)
212 : ($seen, $no_mill + 1);
213  
214 2302012 Game::Merrills::Rules::apply($position, $turn, $raw);
215 2302012 my $key;
216 2302012 ▶ if (!$position->[HAND_WHITE] && !$position->[HAND_BLACK]) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($position->[24] or $position->[25]) 1130841 1171171 2302012
Condition100%3/3
$position->[24] or $position->[25]
l!l&&r!l&&!r
1123763474081130841
MC/DC100%2/2
$position->[24] or $position->[25]
$position->[24] $position->[25]
Truth table100%3/3
A or B
A= $position->[24]B= $position->[25]
ABresult
1X1
011
000
217 1130841 $key = join '', @{$position}[ 0 .. 23 ], $next;
218 1130841 $child_seen->{$key}++;
219 }
220  
221 2302012 my $score = -$self->_search(
222 $state, $position, $next, $depth, $alpha, $beta, $ply, $extension,
223 $child_quiet, $child_seen, $key
224 );
225  
226 2302012 ▶ if (defined $key) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $key) 1130841 1171171 2302012
227 1130841 ▶ delete $child_seen->{$key} unless --$child_seen->{$key};
Branch: 1 branch
BranchTrueFalseTotal
unless --$child_seen->{$key} 1128198 2643 1130841
228 }
229 2302012 Game::Merrills::Rules::unapply($position, $turn, $raw);
230 2302012 return $score;
231 }
232  
233 2302012 ▶sub _search {
Subroutine _search: called CC=33 SCAR=35.0
234 2302012 my ($self, $state, $position, $turn, $depth, $alpha, $beta, $ply,
235 $extension, $no_mill, $seen, $key) = @_;
236  
237 2302012 $state->{nodes}++;
238 2302012 ▶ if ($state->{nodes} >= $state->{budget}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($state->{"nodes"} >= $state->{"budget"}) 135 2301877 2302012
239 135 $state->{aborted} = 1;
240 135 return 0;
241 }
242  
243 2301877 my $value = $VALUE{$turn};
244 2301877 ▶ my $men = $position->[ $value > 0 ? HAND_WHITE : HAND_BLACK ];
Branch: 1 branch
BranchTrueFalseTotal
$value > 0 ? : 1043263 1258614 2301877
245 2301877 $men += grep { $_ == $value } @{$position}[ 0 .. 23 ];
246 2301877 ▶ return -WIN() + $ply if $men < 3;
Branch: 1 branch
BranchTrueFalseTotal
if $men < 3 172230 2129647 2301877
247  
248 2129647 ▶ return 0 if defined $key && ($seen->{$key} || 0) >= 3;
Branch: 1 branch
BranchTrueFalseTotal
if defined $key and ($seen->{$key} || 0) >= 3 346 2129301 2129647
Condition80%4/5
defined $key and ($seen->{$key} || 0) >= 3
!ll&&!rl&&r
1171108958193346
$seen->{$key} || 0
l!l
9585390
MC/DC50%1/2
defined $key and ($seen->{$key} || 0) >= 3
defined $key $seen->{$key}
Truth table66%2/3
A and B
A= defined $keyB= $seen->{$key}
ABresult
0X0
100
111
249 2129301 ▶ return 0 if $state->{limit} && $no_mill >= $state->{limit};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"limit"} and $no_mill >= $state->{"limit"} 30 2129271 2129301
Condition66%2/3
$state->{"limit"} and $no_mill >= $state->{"limit"}
!ll&&!rl&&r
0212927130
MC/DC50%1/2
$state->{"limit"} and $no_mill >= $state->{"limit"}
$state->{"limit"} $no_mill >= $state->{"limit"}
Truth table66%2/3
A and B
A= $state->{"limit"}B= $no_mill >= $state->{"limit"}
ABresult
0X0
100
111
250  
251 2129271 ▶ return $self->_quiesce(
Branch: 1 branch
BranchTrueFalseTotal
if $depth <= 0 1704987 424284 2129271
252 $state, $position, $turn, $alpha, $beta, $ply, $extension, $no_mill, $seen
253 ) if $depth <= 0;
254  
255 424284 my $slot = pack('c26', @{$position}) . $turn;
256 424284 ▶ my $entry = $self->transposition ? $state->{table}{$slot} : undef;
Branch: 1 branch
BranchTrueFalseTotal
$self->transposition ? : 416818 7466 424284
257 424284 my $table_move;
258 424284 ▶ if ($entry) {
Branch: 1 branch
BranchTrueFalseTotal
if ($entry) 155367 268917 424284
259 155367 $table_move = $entry->[3];
260 155367 ▶ if ($entry->[0] >= $depth && abs($entry->[1]) < WIN - 100) {
Branch: 1 branch
BranchTrueFalseTotal
if ($entry->[0] >= $depth and abs $entry->[1] < 9900) 84741 70626 155367
Condition100%3/3
$entry->[0] >= $depth and abs $entry->[1] < 9900
!ll&&!rl&&r
515531907384741
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
261 84741 ▶ return $entry->[1] if $entry->[2] == EXACT;
Branch: 1 branch
BranchTrueFalseTotal
if $entry->[2] == 0 2782 81959 84741
262 81959 ▶ return $entry->[1] if $entry->[2] == LOWER && $entry->[1] >= $beta;
Branch: 1 branch
BranchTrueFalseTotal
if $entry->[2] == 1 and $entry->[1] >= $beta 76907 5052 81959
Condition100%3/3
$entry->[2] == 1 and $entry->[1] >= $beta
!ll&&!rl&&r
3878117476907
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
263 5052 ▶ return $entry->[1] if $entry->[2] == UPPER && $entry->[1] <= $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $entry->[2] == -1 and $entry->[1] <= $alpha 3344 1708 5052
Condition100%3/3
$entry->[2] == -1 and $entry->[1] <= $alpha
!ll&&!rl&&r
11745343344
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
264 }
265 }
266  
267 341251 my $moves = Game::Merrills::Rules::generate($position, $turn, $state->{flying});
268 341251 ▶ return -WIN() + $ply unless @{$moves};
Branch: 1 branch
BranchTrueFalseTotal
unless @{$moves;} 14 341237 341251
269  
270 341237 my $original = $alpha;
271 341237 my ($best_score, $best_move) = (-INFINITY(), undef);
272 341237 for my $raw (@{ $self->_ordered($state, $moves, $ply, $table_move) }) {
273 1531437 my $score = $self->_child(
274 $state, $position, $turn, $raw,
275 $depth - 1, -$beta, -$alpha, $ply + 1, $extension, $no_mill, $seen
276 );
277 1531437 ▶ return 0 if $state->{aborted};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"aborted"} 218 1531219 1531437
278  
279 1531219 ▶ if ($score > $best_score) {
Branch: 1 branch
BranchTrueFalseTotal
if ($score > $best_score) 453210 1078009 1531219
280 453210 ($best_score, $best_move) = ($score, $raw);
281 453210 ▶ $alpha = $score if $score > $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $score > $alpha 362431 90779 453210
282 }
283 1531219 ▶ next if $alpha < $beta;
Branch: 1 branch
BranchTrueFalseTotal
if $alpha < $beta 1256941 274278 1531219
284  
285 274278 my $name = _name($raw);
286 274278 $state->{history}{$name} += $depth * $depth;
287 274278 ▶ my $killers = $state->{killers}[$ply] ||= [];
Condition100%2/2
$state->{"killers"}[$ply] ||= []
l!l
2731221156
MC/DC100%1/1
$state->{"killers"}[$ply] ||= []
$state->{"killers"}[$ply]
Truth table100%2/2
A
A= $state->{"killers"}[$ply]
Aresult
11
00
288 108138 unshift @{$killers}, $name
289 274278 ▶ unless @{$killers} && $killers->[0] eq $name;
Branch: 1 branch
BranchTrueFalseTotal
unless @{$killers;} and $killers->[0] eq $name 108138 166140 274278
Condition100%3/3
@{$killers;} and $killers->[0] eq $name
!ll&&!rl&&r
1156106982166140
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
290 274278 ▶ pop @{$killers} while @{$killers} > 2;
Branch: 1 branch
BranchTrueFalseTotal
@{$killers;} > 2 and do { pop @{$killers;} } 105840 274278 380118
291 274278 last;
292 }
293  
294 341019 ▶ if ($self->transposition) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->transposition) 333553 7466 341019
295 333553 ▶ my $flag = $best_score <= $original ? UPPER
Branch: 2 branches
BranchTrueFalseTotal
$best_score <= $original ? : 33505 300048 333553
$best_score >= $beta ? : 268083 31965 300048
296 : $best_score >= $beta ? LOWER
297 : EXACT;
298 $state->{table}{$slot} = [
299 $depth, $best_score, $flag,
300 333553 ▶ $best_move && [ @{$best_move} ]
Condition50%1/2
$best_move && [@{$best_move;}]
!ll
0333553
MC/DC0%0/1
$best_move && [@{$best_move;}]
$best_move
Truth table50%1/2
A
A= $best_move
Aresult
00
11
301 ];
302 }
303 341019 return $best_score;
304 }
305  
306 1704987 ▶sub _quiesce {
Subroutine _quiesce: called CC=11 SCAR=24.0
307 1704987 my ($self, $state, $position, $turn, $alpha, $beta, $ply, $extension,
308 $no_mill, $seen) = @_;
309  
310 return -WIN() + $ply
311 1704987 ▶ unless Game::Merrills::Rules::has_move($position, $turn, $state->{flying});
Branch: 1 branch
BranchTrueFalseTotal
unless Game::Merrills::Rules::has_move($position, $turn, $state->{"flying"}) 112 1704875 1704987
312  
313 1704875 my $stand = _evaluate($position, $turn, $state->{flying});
314 1704875 ▶ return $stand if $extension >= MAX_EXTENSION || $stand >= $beta;
Branch: 1 branch
BranchTrueFalseTotal
if $extension >= 2 or $stand >= $beta 1042486 662389 1704875
Condition100%3/3
$extension >= 2 or $stand >= $beta
l!l&&r!l&&!r
77707964779662389
MC/DC100%2/2
$extension >= 2 or $stand >= $beta
$extension >= 2 $stand >= $beta
Truth table100%3/3
A or B
A= $extension >= 2B= $stand >= $beta
ABresult
1X1
011
000
315  
316 12330296 my @captures = grep { defined $_->[RM_REMOVE] }
317 662389 @{ Game::Merrills::Rules::generate($position, $turn, $state->{flying}) };
318 662389 ▶ return $stand unless @captures;
Branch: 1 branch
BranchTrueFalseTotal
unless @captures 387431 274958 662389
319  
320 274958 my $best = $stand;
321 274958 ▶ $alpha = $stand if $stand > $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $stand > $alpha 136778 138180 274958
322 274958 for my $raw (@captures) {
323 706660 my $score = $self->_child(
324 $state, $position, $turn, $raw,
325 0, -$beta, -$alpha, $ply + 1, $extension + 1, $no_mill, $seen
326 );
327 706660 ▶ return 0 if $state->{aborted};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"aborted"} 74 706586 706660
328 706586 ▶ $best = $score if $score > $best;
Branch: 1 branch
BranchTrueFalseTotal
if $score > $best 378699 327887 706586
329 706586 ▶ $alpha = $score if $score > $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $score > $alpha 297064 409522 706586
330 706586 ▶ last if $alpha >= $beta;
Branch: 1 branch
BranchTrueFalseTotal
if $alpha >= $beta 186625 519961 706586
331 }
332 274884 return $best;
333 }
334  
335 345214 ▶sub _ordered {
Subroutine _ordered: called CC=12 SCAR=24.9
336 345214 my ($self, $state, $moves, $ply, $table_move) = @_;
337 345214 ▶ my $wanted = $table_move ? _name($table_move) : '';
Branch: 1 branch
BranchTrueFalseTotal
$table_move ? : 72334 272880 345214
338 345214 ▶ my $killers = $state->{killers}[$ply] || [];
Condition100%2/2
$state->{'killers'}[$ply] || []
l!l
32288922325
MC/DC100%1/1
$state->{'killers'}[$ply] || []
$state->{'killers'}[$ply]
Truth table100%2/2
A
A= $state->{'killers'}[$ply]
Aresult
11
00
339 345214 my $history = $state->{history};
340  
341 345214 my @scored;
342 345214 for my $i (0 .. $#{$moves}) {
343 6216453 my $raw = $moves->[$i];
344 6216453 my $name = _name($raw);
345 6216453 my $score = 0;
346 6216453 ▶ $score += 1_000_000 if $name eq $wanted;
Branch: 1 branch
BranchTrueFalseTotal
if $name eq $wanted 72334 6144119 6216453
347 6216453 ▶ $score += 1_000 + (10 * $raw->[RM_CLOSES]) if defined $raw->[RM_REMOVE];
Branch: 1 branch
BranchTrueFalseTotal
if defined $raw->[2] 756318 5460135 6216453
348 6216453 ▶ $score += 400 if @{$killers} && $killers->[0] eq $name;
Branch: 1 branch
BranchTrueFalseTotal
if @{$killers;} and $killers->[0] eq $name 225014 5991439 6216453
Condition100%3/3
@{$killers;} and $killers->[0] eq $name
!ll&&!rl&&r
3534565637983225014
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
349 6216453 ▶ $score += 300 if @{$killers} > 1 && $killers->[1] eq $name;
Branch: 1 branch
BranchTrueFalseTotal
if @{$killers;} > 1 and $killers->[1] eq $name 183742 6032711 6216453
Condition100%3/3
@{$killers;} > 1 and $killers->[1] eq $name
!ll&&!rl&&r
4730425559669183742
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
350 6216453 ▶ $score += $history->{$name} || 0;
Condition100%2/2
$history->{$name} || 0
l!l
22176223998831
MC/DC100%1/1
$history->{$name} || 0
$history->{$name}
Truth table100%2/2
A
A= $history->{$name}
Aresult
11
00
351 6216453 push @scored, [ $score, $i, $raw ];
352 }
353 return [
354 345214 ▶ map { $_->[2] } sort { $b->[0] <=> $a->[0] || $a->[1] <=> $b->[1] } @scored
Condition66%2/3
$Game::Merrills::Bot::b->[0] <=> $Game::Merrills::Bot::a->[0] || $Game::Merrills::Bot::a->[1] <=> $Game::Merrills::Bot::b->[1]
l!l&&r!l&&!r
832853363129450
MC/DC0%0/2
$Game::Merrills::Bot::b->[0] <=> $Game::Merrills::Bot::a->[0] || $Game::Merrills::Bot::a->[1] <=> $Game::Merrills::Bot::b->[1]
$Game::Merrills::Bot::b->[0] <=> $Game::Merrills::Bot::a->[0] $Game::Merrills::Bot::a->[1] <=> $Game::Merrills::Bot::b->[1]
Truth table66%2/3
A || B
A= $Game::Merrills::Bot::b->[0] <=> $Game::Merrills::Bot::a->[0]B= $Game::Merrills::Bot::a->[1] <=> $Game::Merrills::Bot::b->[1]
ABresult
1X1
011
000
355 ];
356 }
357  
358 2335 ▶sub _pv {
Subroutine _pv: called CC=7 SCAR=19.5
359 2335 my ($self, $state, $position, $turn, $first) = @_;
360 2335 my @pv;
361 my @undo;
362  
363 2335 my $raw = $first;
364 2335 ▶ while (@pv < MAX_PV) {
Branch: 1 branch
BranchTrueFalseTotal
if (@pv < 20) 6186 3 6189
365 6186 ▶ unless ($raw) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($raw) 3875 2311 6186
366 3875 ▶ my $entry = $state->{table}{ pack('c26', @{$position}) . $turn } or last;
Branch: 1 branch
BranchTrueFalseTotal
my $entry = $state->{"table"}{pack("c26", @{$position;}) . $turn} or last 1543 2332 3875
367 1543 ▶ $raw = $entry->[3] or last;
Branch: 1 branch
BranchTrueFalseTotal
$raw = $entry->[3] or last 1543 0 1543
368 }
369 3854 my $name = _name($raw);
370 62195 last unless grep { _name($_) eq $name }
371 3854 ▶ @{ Game::Merrills::Rules::generate($position, $turn, $state->{flying}) };
Branch: 1 branch
BranchTrueFalseTotal
unless grep {_name($_) eq $name;} @{Game::Merrills::Rules::generate($position, $turn, $state->{"flying"});} 0 3854 3854
372 3854 push @pv, _notation($raw);
373 3854 Game::Merrills::Rules::apply($position, $turn, $raw);
374 3854 push @undo, [ $turn, $raw ];
375 3854 $turn = $OTHER{$turn};
376 3854 undef $raw;
377 }
378 2335 ▶ Game::Merrills::Rules::unapply($position, @{ pop @undo }) while @undo;
Branch: 1 branch
BranchTrueFalseTotal
@undo and do { Game::Merrills::Rules::unapply($position, @{pop @undo;}) } 3854 2335 6189
379 2335 return \@pv;
380 }
381  
382 51403 ▶sub _jitter {
Subroutine _jitter: called CC=2 SCAR=6.9
383 51403 my ($seed, $ply, $raw) = @_;
384 51403 my $string = $seed . ':' . $ply . ':' . _name($raw);
385 51403 my $hash = 0;
386 51403 $hash = (($hash * 33) + ord) % 65_521 for split //, $string;
387 51403 return $hash % 25;
388 }
389  
390 1704880 ▶sub _evaluate {
Subroutine _evaluate: called CC=23 SCAR=31.4
391 1704880 my ($position, $turn, $flying) = @_;
392 1704880 my %hand = (1 => $position->[HAND_WHITE], -1 => $position->[HAND_BLACK]);
393 1704880 my %score = (1 => 0, -1 => 0);
394 1704880 my %count = (1 => 0, -1 => 0);
395 1704880 for my $point (0 .. 23) {
396 40917120 ▶ $count{ $position->[$point] }++ if $position->[$point];
Branch: 1 branch
BranchTrueFalseTotal
if $position->[$point] 16178904 24738216 40917120
397 }
398 1704880 ▶ my $placing = $hand{1} || $hand{-1};
Condition100%3/3
$hand{'1'} || $hand{'-1'}
l!l&&r!l&&!r
93423642063728581
MC/DC100%2/2
$hand{'1'} || $hand{'-1'}
$hand{'1'} $hand{'-1'}
Truth table100%3/3
A || B
A= $hand{'1'}B= $hand{'-1'}
ABresult
1X1
011
000
399  
400 1704880 my @open;
401 1704880 for my $mill (@{$MILLS}) {
402 27278080 my ($one, $two, $three) = @{$position}[ @{$mill} ];
403 27278080 my $sum = $one + $two + $three;
404 27278080 ▶ next unless ($sum == 2 || $sum == -2) && !($one && $two && $three);
Branch: 1 branch
BranchTrueFalseTotal
unless $sum == 2 || $sum == -2 and not $one && $two && $three 25278625 1999455 27278080
Condition83%10/12
$sum == 2 || $sum == -2 and not $one && $two && $three
!ll&&!rl&&r
2527862501999455
$sum == 2 or $sum == -2
l!l&&r!l&&!r
976693102276225278625
$one && $two && $three
!ll&&!rl&&r
12023977970580
$one and $two
!ll&&!rl&&r
538618663779797058
MC/DC40%2/5
$sum == 2 || $sum == -2 and not $one && $two && $three
$sum == 2 $sum == -2 $one $two $three
Truth table77%7/9
A or B and not(C and D && E)
A= $sum == 2B= $sum == -2C= $oneD= $twoE= $three
ABCDEresult
00XXX0
1X1110
011110
1X0XX1
1X10X1
1X1101
010XX1
0110X1
011101
405 1999455 my ($empty) = grep { !$position->[$_] } @{$mill};
406 1999455 ▶ push @open, [ $sum > 0 ? 1 : -1, $empty, $mill ];
Branch: 1 branch
BranchTrueFalseTotal
$sum > 0 ? : 976693 1022762 1999455
407 }
408  
409 1704880 for my $two (@open) {
410 1999455 my ($side, $empty, $mill) = @{$two};
411 1999455 $score{$side} += $OPEN_TWO;
412 1999455 ▶ if ($hand{$side}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($hand{$side}) 809630 1189825 1999455
413 809630 $score{$side} += $REACH;
414 809630 next;
415 }
416 1189825 ▶ if ($flying && $count{$side} == 3) {
Branch: 1 branch
BranchTrueFalseTotal
if ($flying and $count{$side} == 3) 169000 1020825 1189825
Condition100%3/3
$flying and $count{$side} == 3
!ll&&!rl&&r
2101020615169000
MC/DC100%2/2
$flying and $count{$side} == 3
$flying $count{$side} == 3
Truth table100%3/3
A and B
A= $flyingB= $count{$side} == 3
ABresult
0X0
100
111
417 169000 $score{$side} += $REACH;
418 169000 next;
419 }
420 1020825 my $reach = 0;
421 1020825 for my $near (@{ $ADJACENT->[$empty] }) {
422 2892468 ▶ next unless $position->[$near] == $side;
Branch: 1 branch
BranchTrueFalseTotal
unless $position->[$near] == $side 977861 1914607 2892468
423 1914607 ▶ next if grep { $_ == $near } @{$mill};
Branch: 1 branch
BranchTrueFalseTotal
if grep {$_ == $near;} @{$mill;} 1455047 459560 1914607
424 459560 $reach = 1;
425 }
426 1020825 ▶ $score{$side} += $REACH if $reach;
Branch: 1 branch
BranchTrueFalseTotal
if $reach 402882 617943 1020825
427 }
428  
429 1704880 for my $point (0 .. 23) {
430 40917120 ▶ my $side = $position->[$point] or next;
Branch: 1 branch
BranchTrueFalseTotal
my $side = $position->[$point] or next 16178904 24738216 40917120
431 16178904 ▶ if ($placing) {
Branch: 1 branch
BranchTrueFalseTotal
if ($placing) 8607400 7571504 16178904
432 8607400 $score{$side} += $JUNCTION * (@{ $ADJACENT->[$point] } - 2);
433 8607400 next;
434 }
435 7571504 my $free = grep { !$position->[$_] } @{ $ADJACENT->[$point] };
436 7571504 $score{$side} += $MOBILITY * $free;
437 }
438  
439 1704880 $score{$_} += $MAN * ($count{$_} + $hand{$_}) for 1, -1;
440  
441 1704880 my $value = $VALUE{$turn};
442 1704880 return $score{$value} - $score{ -$value };
443 }
444  
445 74 1;
446  
447 __END__
« blib/lib/Game/Merrills/Terminal.pm ↑ Summary blib/lib/Game/Merrills/Notation.pm »