blib/lib/Game/Merrills/Bot.pm

filter: Statementstmt 100% 301 / 301 Branchbran 96.2% 154 / 160 Conditioncond 89.0% 81 / 91 MC/DCmcdc 77.3% 41 / 53 Subroutinesub 100% 24 / 24 Podpod 75.0% 3 / 4 totaltotal 95.4% 604 / 633 CC 128 SCAR 29.5
CC
128
Cov
97%
_search
33.0
_evaluate
33.0
choose
14.1
CRAP 19.1
↑ Summary blib/lib/Game/Merrills/Terminal.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::Points;
Subroutine __ANON__: called CC=1 SCAR=0.0
8 74 ▶use Game::Merrills::Notation;
Subroutine __ANON__: called CC=1 SCAR=0.0
9 74 ▶use Game::Merrills::Rules;
Subroutine __ANON__: called CC=1 SCAR=0.0
10 74 ▶use Game::Merrills::Move;
Subroutine __ANON__: called CC=1 SCAR=0.0
11  
12 74 our $VERSION = '0.01';
13  
14 74 ▶use constant {
Subroutine __ANON__: called CC=1 SCAR=0.0
15 74 WIN => 10_000,
16 INFINITY => 1_000_000,
17 MAX_EXTENSION => 2,
18 MAX_PV => 20,
19 EXACT => 0,
20 LOWER => 1,
21 UPPER => -1,
22 74 };
23  
24 74 ▶use constant {
Subroutine __ANON__: called CC=1 SCAR=0.0
25 74 RM_FROM => Game::Merrills::Move::RM_FROM,
26 RM_TO => Game::Merrills::Move::RM_TO,
27 RM_REMOVE => Game::Merrills::Move::RM_REMOVE,
28 RM_CLOSES => Game::Merrills::Move::RM_CLOSES,
29 HAND_WHITE => Game::Merrills::Rules::HAND_WHITE,
30 HAND_BLACK => Game::Merrills::Rules::HAND_BLACK,
31 74 };
32  
33 74 our (%LEVEL, $MAN, $MILL, $OPEN_TWO, $REACH, $RUNNING, $BLOCKED, $MOBILITY, $JUNCTION);
34  
35 74 ▶BEGIN {
Subroutine BEGIN: called CC=1 SCAR=0.0
36 74 %LEVEL = (
37 1 => { depth => 1, nodes => 300, jitter => 1 },
38 2 => { depth => 3, nodes => 3_000, jitter => 1 },
39 3 => { depth => 5, nodes => 20_000, jitter => 0 },
40 4 => { depth => 7, nodes => 100_000, jitter => 0 },
41 5 => { depth => 9, nodes => 400_000, jitter => 0 },
42 );
43  
44 74 $MAN = 100;
45 74 $MILL = 12;
46 74 $OPEN_TWO = 8;
47 74 $REACH = 10;
48 74 $RUNNING = 30;
49 74 $BLOCKED = 6;
50 74 $MOBILITY = 2;
51 74 $JUNCTION = 3;
52 }
53  
54 74 my %OTHER = (white => 'black', black => 'white');
55 74 my %VALUE = (white => 1, black => -1);
56  
57 74 my $ADJACENT = \@Game::Merrills::Points::ADJACENT;
58 74 my $MILLS = \@Game::Merrills::Points::MILLS;
59 74 my $MILLS_OF = \@Game::Merrills::Points::MILLS_OF;
60  
61 has level => (
62 is => 'ro',
63 isa => Int,
64 default => 3
65 74 );
66  
67 has seed => (
68 is => 'ro',
69 isa => Int,
70 default => 0
71 74 );
72  
73 has transposition => (
74 is => 'rw',
75 isa => Bool,
76 default => 1
77 74 );
78  
79 has last_search => (
80 is => 'rw'
81 74 );
82  
83 294 ▶sub BUILD {
Subroutine BUILD: called CC=4 SCAR=14.2
Pod undocumented
84 294 my ($self) = @_;
85 die 'level must be 1 .. 5, got ' . (defined $self->level ? "'" . $self->level . "'" : 'undef')
86 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
87 291 return $self;
88 }
89  
90 77 ▶sub levels {
Subroutine levels: called CC=1 SCAR=0.0
Pod documented
91 77 return sort { $a <=> $b } keys %LEVEL;
92 }
93  
94 15 ▶sub setting_for {
Subroutine setting_for: called CC=4 SCAR=13.9
Pod documented
95 15 my ($class, $level) = @_;
96 15 ▶ my $setting = defined $level ? $LEVEL{$level} : undef;
Branch: 1 branch
BranchTrueFalseTotal
defined $level ? : 14 1 15
97 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
98 11 return { %{$setting} };
99 }
100  
101 2278 ▶sub choose {
Subroutine choose: called CC=14 SCAR=26.4
Pod documented
102 2278 my ($self, $game) = @_;
103 2278 ▶ return undef if $game->result;
Branch: 1 branch
BranchTrueFalseTotal
if $game->result 2 2276 2278
104  
105 2276 my $legal = $game->legal_moves;
106 2276 ▶ return undef unless @{$legal};
Branch: 1 branch
BranchTrueFalseTotal
unless @{$legal;} 0 2276 2276
107  
108 2276 ▶ if (@{$legal} == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (@{$legal;} == 1) 12 2264 2276
109 12 $self->last_search({
110 depth => 0,
111 nodes => 0,
112 score => undef,
113 forced => 1,
114 move => $legal->[0]->notation,
115 pv => [ $legal->[0]->notation ]
116 });
117 12 return $legal->[0];
118 }
119  
120 2264 my $spec = $LEVEL{ $self->level };
121 2264 my $position = Game::Merrills::Rules::position($game->board);
122 2264 my $turn = $game->turn;
123 my $state = {
124 nodes => 0,
125 budget => $spec->{nodes},
126 jitter => $spec->{jitter},
127 2264 ▶ table => {},
Branch: 1 branch
BranchTrueFalseTotal
$game->flying ? : 2262 2 2264
Condition50%1/2
$Game::Merrills::NO_MILL_LIMIT || 0
l!l
22640
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
128 history => {},
129 killers => [],
130 flying => $game->flying ? 1 : 0,
131 limit => $Game::Merrills::NO_MILL_LIMIT || 0,
132 aborted => 0
133 };
134 2264 my $seen = { %{ $game->repetition } };
135  
136 2264 my ($best, $score, $reached);
137 2264 for my $depth (1 .. $spec->{depth}) {
138 3849 ▶ last if $state->{nodes} >= $state->{budget};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"nodes"} >= $state->{"budget"} 0 3849 3849
139 3849 $state->{aborted} = 0;
140 3849 my ($iteration_score, $move) = $self->_root(
141 $state, $position, $turn, $depth, $game->no_mill, $seen, $game->ply
142 );
143 3849 ▶ last if $state->{aborted} || !$move;
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"aborted"} or not $move 117 3732 3849
Condition66%2/3
$state->{"aborted"} or not $move
l!l&&r!l&&!r
11703732
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
144 3732 ($best, $score, $reached) = ($move, $iteration_score, $depth);
145 }
146  
147 2264 my $chosen = $legal->[0];
148 2264 ▶ if ($best) {
Branch: 1 branch
BranchTrueFalseTotal
if ($best) 2234 30 2264
149 2234 my $name = _name($best);
150 2234 for my $move (@{$legal}) {
151 16793 ▶ next unless _name($move->to_raw) eq $name;
Branch: 1 branch
BranchTrueFalseTotal
unless _name($move->to_raw) eq $name 14559 2234 16793
152 2234 $chosen = $move;
153 2234 last;
154 }
155 }
156  
157 $self->last_search({
158 depth => $reached || 0,
159 nodes => $state->{nodes},
160 2264 ▶ score => $score,
Condition100%2/2
$reached || 0
l!l
223430
MC/DC100%1/1
$reached || 0
$reached
Truth table100%2/2
A
A= $reached
Aresult
11
00
161 forced => 0,
162 move => $chosen->notation,
163 pv => $self->_pv($state, $position, $turn, $best)
164 });
165 2264 return $chosen;
166 }
167  
168 4724020 ▶sub _name {
Subroutine _name: called CC=2 SCAR=6.9
169 4724020 my ($raw) = @_;
170 4724020 ▶ return join '.', map { defined $_ ? $_ : '-' } @{$raw}[ RM_FROM, RM_TO, RM_REMOVE ];
Branch: 1 branch
BranchTrueFalseTotal
defined $_ ? : 6814267 7357793 14172060
171 }
172  
173 3694 ▶sub _notation {
Subroutine _notation: called CC=1 SCAR=0.0
174 3694 my ($raw) = @_;
175 3694 return Game::Merrills::Notation::format_move({
176 from => $raw->[RM_FROM],
177 to => $raw->[RM_TO],
178 remove => $raw->[RM_REMOVE],
179 });
180 }
181  
182 3849 ▶sub _root {
Subroutine _root: called CC=10 SCAR=23.0
183 3849 my ($self, $state, $position, $turn, $depth, $no_mill, $seen, $ply) = @_;
184 3849 my $moves = Game::Merrills::Rules::generate($position, $turn, $state->{flying});
185 3849 ▶ return (undef, undef) unless @{$moves};
Branch: 1 branch
BranchTrueFalseTotal
unless @{$moves;} 0 3849 3849
186  
187 3849 my $alpha = -INFINITY();
188 3849 my ($best, $best_score);
189 3849 for my $raw (@{ $self->_ordered($state, $moves, 0, undef) }) {
190 56360 ▶ my $bound = $state->{jitter} ? -INFINITY() : $alpha;
Branch: 1 branch
BranchTrueFalseTotal
$state->{'jitter'} ? : 45263 11097 56360
191 56360 my $score = $self->_child(
192 $state, $position, $turn, $raw,
193 $depth - 1, -INFINITY(), -$bound, 1, 0, $no_mill, $seen
194 );
195 56360 ▶ return (undef, undef) if $state->{aborted};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"aborted"} 117 56243 56360
196  
197 56243 ▶ $score += _jitter($self->seed, $ply, $raw) if $state->{jitter};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"jitter"} 45154 11089 56243
198  
199 56243 ▶ if (!defined $best_score || $score > $best_score) {
Branch: 1 branch
BranchTrueFalseTotal
if (not defined $best_score or $score > $best_score) 11234 45009 56243
Condition100%3/3
not defined $best_score or $score > $best_score
l!l&&r!l&&!r
3845738945009
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
200 11234 ($best, $best_score) = ($raw, $score);
201 11234 ▶ $alpha = $score if $score > $alpha && !$state->{jitter};
Branch: 1 branch
BranchTrueFalseTotal
if $score > $alpha and not $state->{"jitter"} 1847 9387 11234
Condition66%2/3
$score > $alpha and not $state->{"jitter"}
!ll&&!rl&&r
093871847
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
202 }
203 }
204 3732 return ($best_score, $best);
205 }
206  
207 1865744 ▶sub _child {
Subroutine _child: called CC=7 SCAR=19.5
208 1865744 my ($self, $state, $position, $turn, $raw, $depth, $alpha, $beta, $ply,
209 $extension, $no_mill, $seen) = @_;
210  
211 1865744 my $next = $OTHER{$turn};
212 1865744 ▶ my ($child_seen, $child_quiet) = !defined $raw->[RM_FROM] || defined $raw->[RM_REMOVE]
Branch: 1 branch
BranchTrueFalseTotal
!defined($raw->[0]) || defined $raw->[2] ? : 1574008 291736 1865744
Condition100%3/3
not defined $raw->[0] or defined $raw->[2]
l!l&&r!l&&!r
1225034348974291736
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
213 ? ({}, 0)
214 : ($seen, $no_mill + 1);
215  
216 1865744 Game::Merrills::Rules::apply($position, $turn, $raw);
217 1865744 my $key;
218 1865744 ▶ if (!$position->[HAND_WHITE] && !$position->[HAND_BLACK]) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($position->[24] or $position->[25]) 696260 1169484 1865744
Condition100%3/3
$position->[24] or $position->[25]
l!l&&r!l&&!r
112317946305696260
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
219 696260 $key = join '', @{$position}[ 0 .. 23 ], $next;
220 696260 $child_seen->{$key}++;
221 }
222  
223 1865744 my $score = -$self->_search(
224 $state, $position, $next, $depth, $alpha, $beta, $ply, $extension,
225 $child_quiet, $child_seen, $key
226 );
227  
228 1865744 ▶ if (defined $key) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $key) 696260 1169484 1865744
229 696260 ▶ delete $child_seen->{$key} unless --$child_seen->{$key};
Branch: 1 branch
BranchTrueFalseTotal
unless --$child_seen->{$key} 695183 1077 696260
230 }
231 1865744 Game::Merrills::Rules::unapply($position, $turn, $raw);
232 1865744 return $score;
233 }
234  
235 1865744 ▶sub _search {
Subroutine _search: called CC=33 SCAR=35.0
236 1865744 my ($self, $state, $position, $turn, $depth, $alpha, $beta, $ply,
237 $extension, $no_mill, $seen, $key) = @_;
238  
239 1865744 $state->{nodes}++;
240 1865744 ▶ if ($state->{nodes} >= $state->{budget}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($state->{"nodes"} >= $state->{"budget"}) 117 1865627 1865744
241 117 $state->{aborted} = 1;
242 117 return 0;
243 }
244  
245 1865627 my $value = $VALUE{$turn};
246 1865627 ▶ my $men = $position->[ $value > 0 ? HAND_WHITE : HAND_BLACK ];
Branch: 1 branch
BranchTrueFalseTotal
$value > 0 ? : 905896 959731 1865627
247 1865627 $men += grep { $_ == $value } @{$position}[ 0 .. 23 ];
248 1865627 ▶ return -WIN() + $ply if $men < 3;
Branch: 1 branch
BranchTrueFalseTotal
if $men < 3 84546 1781081 1865627
249  
250 1781081 ▶ return 0 if defined $key && ($seen->{$key} || 0) >= 3;
Branch: 1 branch
BranchTrueFalseTotal
if defined $key and ($seen->{$key} || 0) >= 3 101 1780980 1781081
Condition80%4/5
defined $key and ($seen->{$key} || 0) >= 3
!ll&&!rl&&r
1169423611557101
$seen->{$key} || 0
l!l
6116580
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
251 1780980 ▶ return 0 if $state->{limit} && $no_mill >= $state->{limit};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"limit"} and $no_mill >= $state->{"limit"} 30 1780950 1780980
Condition66%2/3
$state->{"limit"} and $no_mill >= $state->{"limit"}
!ll&&!rl&&r
0178095030
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
252  
253 1780950 ▶ return $self->_quiesce(
Branch: 1 branch
BranchTrueFalseTotal
if $depth <= 0 1484210 296740 1780950
254 $state, $position, $turn, $alpha, $beta, $ply, $extension, $no_mill, $seen
255 ) if $depth <= 0;
256  
257 296740 my $slot = pack('c26', @{$position}) . $turn;
258 296740 ▶ my $entry = $self->transposition ? $state->{table}{$slot} : undef;
Branch: 1 branch
BranchTrueFalseTotal
$self->transposition ? : 289349 7391 296740
259 296740 my $table_move;
260 296740 ▶ if ($entry) {
Branch: 1 branch
BranchTrueFalseTotal
if ($entry) 81176 215564 296740
261 81176 $table_move = $entry->[3];
262 81176 ▶ if ($entry->[0] >= $depth && abs($entry->[1]) < WIN - 100) {
Branch: 1 branch
BranchTrueFalseTotal
if ($entry->[0] >= $depth and abs $entry->[1] < 9900) 36411 44765 81176
Condition100%3/3
$entry->[0] >= $depth and abs $entry->[1] < 9900
!ll&&!rl&&r
41327343836411
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
263 36411 ▶ return $entry->[1] if $entry->[2] == EXACT;
Branch: 1 branch
BranchTrueFalseTotal
if $entry->[2] == 0 2164 34247 36411
264 34247 ▶ return $entry->[1] if $entry->[2] == LOWER && $entry->[1] >= $beta;
Branch: 1 branch
BranchTrueFalseTotal
if $entry->[2] == 1 and $entry->[1] >= $beta 29760 4487 34247
Condition100%3/3
$entry->[2] == 1 and $entry->[1] >= $beta
!ll&&!rl&&r
3427106029760
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
265 4487 ▶ return $entry->[1] if $entry->[2] == UPPER && $entry->[1] <= $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $entry->[2] == -1 and $entry->[1] <= $alpha 3048 1439 4487
Condition100%3/3
$entry->[2] == -1 and $entry->[1] <= $alpha
!ll&&!rl&&r
10603793048
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
266 }
267 }
268  
269 261768 my $moves = Game::Merrills::Rules::generate($position, $turn, $state->{flying});
270 261768 ▶ return -WIN() + $ply unless @{$moves};
Branch: 1 branch
BranchTrueFalseTotal
unless @{$moves;} 20 261748 261768
271  
272 261748 my $original = $alpha;
273 261748 my ($best_score, $best_move) = (-INFINITY(), undef);
274 261748 for my $raw (@{ $self->_ordered($state, $moves, $ply, $table_move) }) {
275 1142347 my $score = $self->_child(
276 $state, $position, $turn, $raw,
277 $depth - 1, -$beta, -$alpha, $ply + 1, $extension, $no_mill, $seen
278 );
279 1142347 ▶ return 0 if $state->{aborted};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"aborted"} 153 1142194 1142347
280  
281 1142194 ▶ if ($score > $best_score) {
Branch: 1 branch
BranchTrueFalseTotal
if ($score > $best_score) 358105 784089 1142194
282 358105 ($best_score, $best_move) = ($score, $raw);
283 358105 ▶ $alpha = $score if $score > $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $score > $alpha 286305 71800 358105
284 }
285 1142194 ▶ next if $alpha < $beta;
Branch: 1 branch
BranchTrueFalseTotal
if $alpha < $beta 939386 202808 1142194
286  
287 202808 my $name = _name($raw);
288 202808 $state->{history}{$name} += $depth * $depth;
289 202808 ▶ my $killers = $state->{killers}[$ply] ||= [];
Condition100%2/2
$state->{"killers"}[$ply] ||= []
l!l
2017211087
MC/DC100%1/1
$state->{"killers"}[$ply] ||= []
$state->{"killers"}[$ply]
Truth table100%2/2
A
A= $state->{"killers"}[$ply]
Aresult
11
00
290 67787 unshift @{$killers}, $name
291 202808 ▶ unless @{$killers} && $killers->[0] eq $name;
Branch: 1 branch
BranchTrueFalseTotal
unless @{$killers;} and $killers->[0] eq $name 67787 135021 202808
Condition100%3/3
@{$killers;} and $killers->[0] eq $name
!ll&&!rl&&r
108766700135021
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
292 202808 ▶ pop @{$killers} while @{$killers} > 2;
Branch: 1 branch
BranchTrueFalseTotal
@{$killers;} > 2 and do { pop @{$killers;} } 65627 202808 268435
293 202808 last;
294 }
295  
296 261595 ▶ if ($self->transposition) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->transposition) 254204 7391 261595
297 254204 ▶ my $flag = $best_score <= $original ? UPPER
Branch: 2 branches
BranchTrueFalseTotal
$best_score <= $original ? : 27066 227138 254204
$best_score >= $beta ? : 196680 30458 227138
298 : $best_score >= $beta ? LOWER
299 : EXACT;
300 $state->{table}{$slot} = [
301 $depth, $best_score, $flag,
302 254204 ▶ $best_move && [ @{$best_move} ]
Condition50%1/2
$best_move && [@{$best_move;}]
!ll
0254204
MC/DC0%0/1
$best_move && [@{$best_move;}]
$best_move
Truth table50%1/2
A
A= $best_move
Aresult
00
11
303 ];
304 }
305 261595 return $best_score;
306 }
307  
308 1484210 ▶sub _quiesce {
Subroutine _quiesce: called CC=11 SCAR=24.0
309 1484210 my ($self, $state, $position, $turn, $alpha, $beta, $ply, $extension,
310 $no_mill, $seen) = @_;
311  
312 return -WIN() + $ply
313 1484210 ▶ unless Game::Merrills::Rules::has_move($position, $turn, $state->{flying});
Branch: 1 branch
BranchTrueFalseTotal
unless Game::Merrills::Rules::has_move($position, $turn, $state->{"flying"}) 139 1484071 1484210
314  
315 1484071 my $stand = _evaluate($position, $turn, $state->{flying});
316 1484071 ▶ return $stand if $extension >= MAX_EXTENSION || $stand >= $beta;
Branch: 1 branch
BranchTrueFalseTotal
if $extension >= 2 or $stand >= $beta 876929 607142 1484071
Condition100%3/3
$extension >= 2 or $stand >= $beta
l!l&&r!l&&!r
79659797270607142
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
317  
318 9654902 my @captures = grep { defined $_->[RM_REMOVE] }
319 607142 @{ Game::Merrills::Rules::generate($position, $turn, $state->{flying}) };
320 607142 ▶ return $stand unless @captures;
Branch: 1 branch
BranchTrueFalseTotal
unless @captures 364681 242461 607142
321  
322 242461 my $best = $stand;
323 242461 ▶ $alpha = $stand if $stand > $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $stand > $alpha 118543 123918 242461
324 242461 for my $raw (@captures) {
325 667037 my $score = $self->_child(
326 $state, $position, $turn, $raw,
327 0, -$beta, -$alpha, $ply + 1, $extension + 1, $no_mill, $seen
328 );
329 667037 ▶ return 0 if $state->{aborted};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"aborted"} 85 666952 667037
330 666952 ▶ $best = $score if $score > $best;
Branch: 1 branch
BranchTrueFalseTotal
if $score > $best 356852 310100 666952
331 666952 ▶ $alpha = $score if $score > $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $score > $alpha 271051 395901 666952
332 666952 ▶ last if $alpha >= $beta;
Branch: 1 branch
BranchTrueFalseTotal
if $alpha >= $beta 160872 506080 666952
333 }
334 242376 return $best;
335 }
336  
337 265597 ▶sub _ordered {
Subroutine _ordered: called CC=12 SCAR=24.9
338 265597 my ($self, $state, $moves, $ply, $table_move) = @_;
339 265597 ▶ my $wanted = $table_move ? _name($table_move) : '';
Branch: 1 branch
BranchTrueFalseTotal
$table_move ? : 46204 219393 265597
340 265597 ▶ my $killers = $state->{killers}[$ply] || [];
Condition100%2/2
$state->{'killers'}[$ply] || []
l!l
24493320664
MC/DC100%1/1
$state->{'killers'}[$ply] || []
$state->{'killers'}[$ply]
Truth table100%2/2
A
A= $state->{'killers'}[$ply]
Aresult
11
00
341 265597 my $history = $state->{history};
342  
343 265597 my @scored;
344 265597 for my $i (0 .. $#{$moves}) {
345 4355241 my $raw = $moves->[$i];
346 4355241 my $name = _name($raw);
347 4355241 my $score = 0;
348 4355241 ▶ $score += 1_000_000 if $name eq $wanted;
Branch: 1 branch
BranchTrueFalseTotal
if $name eq $wanted 46204 4309037 4355241
349 4355241 ▶ $score += 1_000 + (10 * $raw->[RM_CLOSES]) if defined $raw->[RM_REMOVE];
Branch: 1 branch
BranchTrueFalseTotal
if defined $raw->[2] 461338 3893903 4355241
350 4355241 ▶ $score += 400 if @{$killers} && $killers->[0] eq $name;
Branch: 1 branch
BranchTrueFalseTotal
if @{$killers;} and $killers->[0] eq $name 177234 4178007 4355241
Condition100%3/3
@{$killers;} and $killers->[0] eq $name
!ll&&!rl&&r
3195943858413177234
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
351 4355241 ▶ $score += 300 if @{$killers} > 1 && $killers->[1] eq $name;
Branch: 1 branch
BranchTrueFalseTotal
if @{$killers;} > 1 and $killers->[1] eq $name 142295 4212946 4355241
Condition100%3/3
@{$killers;} > 1 and $killers->[1] eq $name
!ll&&!rl&&r
3947293818217142295
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
352 4355241 ▶ $score += $history->{$name} || 0;
Condition100%2/2
$history->{$name} || 0
l!l
17925712562670
MC/DC100%1/1
$history->{$name} || 0
$history->{$name}
Truth table100%2/2
A
A= $history->{$name}
Aresult
11
00
353 4355241 push @scored, [ $score, $i, $raw ];
354 }
355 return [
356 265597 ▶ 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
645050141012030
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
357 ];
358 }
359  
360 2264 ▶sub _pv {
Subroutine _pv: called CC=7 SCAR=19.5
361 2264 my ($self, $state, $position, $turn, $first) = @_;
362 2264 my @pv;
363 my @undo;
364  
365 2264 my $raw = $first;
366 2264 ▶ while (@pv < MAX_PV) {
Branch: 1 branch
BranchTrueFalseTotal
if (@pv < 20) 5957 1 5958
367 5957 ▶ unless ($raw) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($raw) 3723 2234 5957
368 3723 ▶ my $entry = $state->{table}{ pack('c26', @{$position}) . $turn } or last;
Branch: 1 branch
BranchTrueFalseTotal
my $entry = $state->{"table"}{pack("c26", @{$position;}) . $turn} or last 1460 2263 3723
369 1460 ▶ $raw = $entry->[3] or last;
Branch: 1 branch
BranchTrueFalseTotal
$raw = $entry->[3] or last 1460 0 1460
370 }
371 3694 my $name = _name($raw);
372 51828 last unless grep { _name($_) eq $name }
373 3694 ▶ @{ 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 3694 3694
374 3694 push @pv, _notation($raw);
375 3694 Game::Merrills::Rules::apply($position, $turn, $raw);
376 3694 push @undo, [ $turn, $raw ];
377 3694 $turn = $OTHER{$turn};
378 3694 undef $raw;
379 }
380 2264 ▶ Game::Merrills::Rules::unapply($position, @{ pop @undo }) while @undo;
Branch: 1 branch
BranchTrueFalseTotal
@undo and do { Game::Merrills::Rules::unapply($position, @{pop @undo;}) } 3694 2264 5958
381 2264 return \@pv;
382 }
383  
384 45218 ▶sub _jitter {
Subroutine _jitter: called CC=2 SCAR=6.9
385 45218 my ($seed, $ply, $raw) = @_;
386 45218 my $string = $seed . ':' . $ply . ':' . _name($raw);
387 45218 my $hash = 0;
388 45218 $hash = (($hash * 33) + ord) % 65_521 for split //, $string;
389 45218 return $hash % 25;
390 }
391  
392 1484076 ▶sub _evaluate {
Subroutine _evaluate: called CC=33 SCAR=35.0
393 1484076 my ($position, $turn, $flying) = @_;
394 1484076 my %hand = (1 => $position->[HAND_WHITE], -1 => $position->[HAND_BLACK]);
395 1484076 my %score = (1 => 0, -1 => 0);
396 1484076 my %count = (1 => 0, -1 => 0);
397 1484076 for my $point (0 .. 23) {
398 35617824 ▶ $count{ $position->[$point] }++ if $position->[$point];
Branch: 1 branch
BranchTrueFalseTotal
if $position->[$point] 15142434 20475390 35617824
399 }
400 1484076 ▶ my $placing = $hand{1} || $hand{-1};
Condition100%3/3
$hand{'1'} || $hand{'-1'}
l!l&&r!l&&!r
93402741377508672
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
401  
402 1484076 my (@closed, @open);
403 1484076 for my $mill (@{$MILLS}) {
404 23745216 my ($one, $two, $three) = @{$position}[ @{$mill} ];
405 23745216 my $sum = $one + $two + $three;
406 23745216 ▶ if ($sum == 3 || $sum == -3) {
Branch: 1 branch
BranchTrueFalseTotal
if ($sum == 3 or $sum == -3) 1585794 22159422 23745216
Condition100%3/3
$sum == 3 or $sum == -3
l!l&&r!l&&!r
82963975615522159422
MC/DC100%2/2
$sum == 3 or $sum == -3
$sum == 3 $sum == -3
Truth table100%3/3
A or B
A= $sum == 3B= $sum == -3
ABresult
1X1
011
000
407 1585794 ▶ my $side = $sum > 0 ? 1 : -1;
Branch: 1 branch
BranchTrueFalseTotal
$sum > 0 ? : 829639 756155 1585794
408 1585794 $score{$side} += $MILL;
409 1585794 $closed[$_] = $side for @{$mill};
410 1585794 next;
411 }
412 22159422 ▶ next unless ($sum == 2 || $sum == -2) && !($one && $two && $three);
Branch: 1 branch
BranchTrueFalseTotal
unless $sum == 2 || $sum == -2 and not $one && $two && $three 20358022 1801400 22159422
Condition83%10/12
$sum == 2 || $sum == -2 and not $one && $two && $three
!ll&&!rl&&r
2035802201801400
$sum == 2 or $sum == -2
l!l&&r!l&&!r
93629986510120358022
$one && $two && $three
!ll&&!rl&&r
10612887401120
$one and $two
!ll&&!rl&&r
498653562635740112
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
413 1801400 my ($empty) = grep { !$position->[$_] } @{$mill};
414 1801400 ▶ push @open, [ $sum > 0 ? 1 : -1, $empty, $mill ];
Branch: 1 branch
BranchTrueFalseTotal
$sum > 0 ? : 936299 865101 1801400
415 }
416  
417 1484076 for my $two (@open) {
418 1801400 my ($side, $empty, $mill) = @{$two};
419 1801400 $score{$side} += $OPEN_TWO;
420 1801400 ▶ if ($hand{$side}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($hand{$side}) 808725 992675 1801400
421 808725 $score{$side} += $REACH;
422 808725 next;
423 }
424 992675 ▶ if ($flying && $count{$side} == 3) {
Branch: 1 branch
BranchTrueFalseTotal
if ($flying and $count{$side} == 3) 44686 947989 992675
Condition100%3/3
$flying and $count{$side} == 3
!ll&&!rl&&r
21094777944686
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
425 44686 $score{$side} += $REACH;
426 44686 next;
427 }
428 947989 my ($reach, $running) = (0, 0);
429 947989 for my $near (@{ $ADJACENT->[$empty] }) {
430 2568579 ▶ next unless $position->[$near] == $side;
Branch: 1 branch
BranchTrueFalseTotal
unless $position->[$near] == $side 869079 1699500 2568579
431 1699500 ▶ next if grep { $_ == $near } @{$mill};
Branch: 1 branch
BranchTrueFalseTotal
if grep {$_ == $near;} @{$mill;} 1308906 390594 1699500
432 390594 $reach = 1;
433 390594 ▶ $running = 1 if ($closed[$near] || 0) == $side;
Branch: 1 branch
BranchTrueFalseTotal
if ($closed[$near] || 0) == $side 108654 281940 390594
Condition100%2/2
$closed[$near] || 0
l!l
108654281940
MC/DC100%1/1
$closed[$near] || 0
$closed[$near]
Truth table100%2/2
A
A= $closed[$near]
Aresult
11
00
434 }
435 947989 ▶ $score{$side} += $REACH if $reach;
Branch: 1 branch
BranchTrueFalseTotal
if $reach 378589 569400 947989
436 947989 ▶ $score{$side} += $RUNNING if $running;
Branch: 1 branch
BranchTrueFalseTotal
if $running 108620 839369 947989
437 }
438  
439 1484076 for my $point (0 .. 23) {
440 35617824 ▶ my $side = $position->[$point] or next;
Branch: 1 branch
BranchTrueFalseTotal
my $side = $position->[$point] or next 15142434 20475390 35617824
441 15142434 ▶ if ($placing) {
Branch: 1 branch
BranchTrueFalseTotal
if ($placing) 8593871 6548563 15142434
442 8593871 $score{$side} += $JUNCTION * (@{ $ADJACENT->[$point] } - 2);
443 8593871 next;
444 }
445 6548563 my $free = grep { !$position->[$_] } @{ $ADJACENT->[$point] };
446 6548563 $score{$side} += $MOBILITY * $free;
447 6548563 ▶ $score{$side} -= $BLOCKED unless $free || ($flying && $count{$side} == 3);
Branch: 1 branch
BranchTrueFalseTotal
unless $free or $flying and $count{$side} == 3 1535399 5013164 6548563
Condition100%6/6
$free or $flying and $count{$side} == 3
l!l&&r!l&&!r
4958394547701535399
$flying and $count{$side} == 3
!ll&&!rl&&r
4153539554770
MC/DC100%3/3
$free or $flying and $count{$side} == 3
$free $flying $count{$side} == 3
Truth table100%4/4
A or B and C
A= $freeB= $flyingC= $count{$side} == 3
ABCresult
1XX1
0111
00X0
0100
448 }
449  
450 1484076 $score{$_} += $MAN * ($count{$_} + $hand{$_}) for 1, -1;
451  
452 1484076 my $value = $VALUE{$turn};
453 1484076 return $score{$value} - $score{ -$value };
454 }
455  
456 74 1;
457  
458 __END__
↑ Summary blib/lib/Game/Merrills/Terminal.pm »