Reversi/Bot.pm

filter: Statementstmt 100% 113 / 113 Branchbran 97.8% 45 / 46 Conditioncond 63.6% 7 / 11 MC/DCmcdc 28.5% 2 / 7 Subroutinesub 100% 17 / 17 Podpod 66.6% 2 / 3 totaltotal 94.4% 186 / 197 CC 32 SCAR 17.1
CC
32
Cov
97%
choose
9.1
_alphabeta
9.0
_leaf
7.0
CRAP 5.5
« Reversi/Notation.pm ↑ Summary Reversi/Rules.pm »
1 package Game::Reversi::Bot;
2  
3 9 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 9 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
5  
6 9 ▶use Object::Proto::Sugar -types;
Subroutine BEGIN: called CC=1 SCAR=0.0
7  
8 9 ▶use Digest::SHA ();
Subroutine BEGIN: called CC=1 SCAR=0.0
9  
10 9 ▶use Game::Reversi::Board;
Subroutine BEGIN: called CC=1 SCAR=0.0
11 9 ▶use Game::Reversi::Move;
Subroutine BEGIN: called CC=1 SCAR=0.0
12 9 ▶use Game::Reversi::Opening;
Subroutine BEGIN: called CC=1 SCAR=0.0
13  
14 9 our $VERSION = '0.04';
15  
16 9 my @WEIGHT = (
17 120, -20, 20, 5, 5, 20, -20, 120,
18 -20, -40, -5, -5, -5, -5, -40, -20,
19 20, -5, 15, 3, 3, 15, -5, 20,
20 5, -5, 3, 3, 3, 3, -5, 5,
21 5, -5, 3, 3, 3, 3, -5, 5,
22 20, -5, 15, 3, 3, 15, -5, 20,
23 -20, -40, -5, -5, -5, -5, -40, -20,
24 120, -20, 20, 5, 5, 20, -20, 120,
25 );
26  
27 9 our $MOBILITY = 5;
28  
29 9 our $ENDGAME = 20;
30  
31 9 my %LEVEL = (
32 1 => { nodes => 60, mobility => 0, exact => 0, depth => 1 },
33 2 => { nodes => 400, mobility => 0, exact => 6, depth => 3 },
34 3 => { nodes => 1500, mobility => 1, exact => 8, depth => 5 },
35 4 => { nodes => 5000, mobility => 1, exact => 9, depth => 8 },
36 5 => { nodes => 8000, mobility => 1, exact => 10, depth => 14, book => 0 },
37 );
38  
39 42 ▶sub levels { return sort { $a <=> $b } keys %LEVEL }
Subroutine levels: called CC=1 SCAR=0.0
Pod documented
40  
41 has level => (
42 is => 'ro',
43 isa => Int,
44 default => 3
45 9 );
46  
47 has seed => (
48 is => 'ro',
49 default => 0
50 9 );
51  
52 has last_search => (
53 is => 'rw',
54 isa => Any
55 9 );
56  
57 158 ▶sub BUILD {
Subroutine BUILD: called CC=2 SCAR=6.9
Pod undocumented
58 158 my ($self) = @_;
59 die 'Game::Reversi::Bot: there is no level ' . $self->level
60 158 ▶ unless $LEVEL{ $self->level };
Branch: 1 branch
BranchTrueFalseTotal
unless $LEVEL{$self->level} 2 156 158
61 156 return $self;
62 }
63  
64 1420 ▶sub choose {
Subroutine choose: called CC=9 SCAR=22.1
Pod documented
65 1420 my ($self, $game, $colour) = @_;
66 1420 ▶ return undef unless $game->status eq 'active';
Branch: 1 branch
BranchTrueFalseTotal
unless $game->status eq "active" 2 1418 1420
67 1418 ▶ return undef unless defined $colour;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $colour 1 1417 1418
68 1417 ▶ return undef unless defined $game->turn && $game->turn eq $colour;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $game->turn and $game->turn eq $colour 1 1416 1417
Condition66%2/3
defined $game->turn and $game->turn eq $colour
!ll&&!rl&&r
011416
MC/DC50%1/2
defined $game->turn and $game->turn eq $colour
defined $game->turn $game->turn eq $colour
Truth table66%2/3
A and B
A= defined $game->turnB= $game->turn eq $colour
ABresult
0X0
100
111
69  
70 1416 my $legal = $game->legal($colour);
71 1416 ▶ return undef unless @$legal;
Branch: 1 branch
BranchTrueFalseTotal
unless @$legal 0 1416 1416
72 1416 ▶ return $legal->[0] if @$legal == 1;
Branch: 1 branch
BranchTrueFalseTotal
if @$legal == 1 98 1318 1416
73  
74 return $self->_open($game, $colour, $legal)
75 1318 ▶ if $game->phase eq 'opening' && !$LEVEL{ $self->level }{book};
Branch: 1 branch
BranchTrueFalseTotal
if $game->phase eq "opening" and not $LEVEL{$self->level}{"book"} 160 1158 1318
Condition66%2/3
$game->phase eq "opening" and not $LEVEL{$self->level}{"book"}
!ll&&!rl&&r
11580160
MC/DC50%1/2
$game->phase eq "opening" and not $LEVEL{$self->level}{"book"}
$game->phase eq "opening" not $LEVEL{$self->level}{"book"}
Truth table66%2/3
A and not(B)
A= $game->phase eq "opening"B= not $LEVEL{$self->level}{"book"}
ABresult
0X0
100
111
76  
77 1158 return $self->_search($game, $colour, $legal);
78 }
79  
80 160 ▶sub _open {
Subroutine _open: called CC=1 SCAR=0.0
81 160 my ($self, $game, $colour, $legal) = @_;
82 my $key = join '|', $self->_seed($colour), scalar @$legal,
83 160 join ',', map { $_->square } @$legal;
84 160 my $word = unpack 'N', Digest::SHA::sha256($key);
85 160 $self->last_search({ nodes => 0, depth => 0, opening => 1 });
86 160 return $legal->[ $word % scalar @$legal ];
87 }
88  
89 160 ▶sub _seed {
Subroutine _seed: called CC=2 SCAR=7.2
90 160 my ($self, $colour) = @_;
91 160 ▶ return unpack 'H16',
Condition50%1/2
$colour // "?"
l!l
1600
MC/DC0%0/1
$colour // "?"
$colour
Truth table50%1/2
A
A= $colour
Aresult
11
00
92 Digest::SHA::sha256('reversi-bot:' . $self->seed . ':' . ($colour // '?'));
93 }
94  
95 1158 ▶sub _search {
Subroutine _search: called CC=4 SCAR=13.9
96 1158 my ($self, $game, $colour, $legal) = @_;
97 1158 my $setting = $LEVEL{ $self->level };
98 1158 my $board = $game->board;
99  
100 1158 my @ordered = $self->_order($board, $colour, [ map { $_->square } @$legal ]);
101 1158 my %move_of = map { $_->square => $_ } @$legal;
102  
103 my $state = {
104 nodes => 0, over_budget => 0,
105 1158 budget => $setting->{nodes}, setting => $setting,
106 };
107  
108 1158 my $best = $ordered[0];
109 1158 my $depth_reached = 0;
110 1158 my $value;
111  
112 1158 for my $depth (1 .. $setting->{depth}) {
113 3286 my ($square, $score) = $self->_root($state, $board, $colour, $depth, \@ordered);
114 3286 ▶ last unless defined $square;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $square 123 3163 3286
115 3163 ($best, $value, $depth_reached) = ($square, $score, $depth);
116 3163 ▶ last if $state->{nodes} >= $state->{budget};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"nodes"} >= $state->{"budget"} 2 3161 3163
117  
118 3161 @ordered = ($best, grep { $_ != $best } @ordered);
119 }
120  
121 $self->last_search({
122 1158 nodes => $state->{nodes}, depth => $depth_reached,
123 value => $value, opening => 0,
124 });
125 1158 return $move_of{$best};
126 }
127  
128 3286 ▶sub _root {
Subroutine _root: called CC=4 SCAR=13.9
129 3286 my ($self, $state, $board, $colour, $depth, $ordered) = @_;
130 3286 my ($best, $alpha) = (undef, -1e9);
131  
132 3286 for my $square (@$ordered) {
133 24486 my $after = Game::Reversi::Board->apply($board, $square, $colour);
134 24486 my $score = -$self->_alphabeta($state, $after, Game::Reversi::Board->other($colour),
135 $depth - 1, -1e9, -$alpha, 0);
136 24486 ▶ return (undef, undef) if $state->{over_budget};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"over_budget"} 123 24363 24486
137 24363 ▶ if ($score > $alpha) {
Branch: 1 branch
BranchTrueFalseTotal
if ($score > $alpha) 5385 18978 24363
138 5385 ($alpha, $best) = ($score, $square);
139 }
140 }
141 3163 return ($best, $alpha);
142 }
143  
144 372964 ▶sub _alphabeta {
Subroutine _alphabeta: called CC=9 SCAR=22.0
145 372964 my ($self, $state, $board, $colour, $depth, $alpha, $beta, $passes) = @_;
146  
147 372964 ▶ if (++$state->{nodes} > $state->{budget}) {
Branch: 1 branch
BranchTrueFalseTotal
if (++$state->{"nodes"} > $state->{"budget"}) 123 372841 372964
148 123 $state->{over_budget} = 1;
149 123 return 0;
150 }
151  
152 372841 ▶ return $self->_leaf($state, $board, $colour) if $depth <= 0;
Branch: 1 branch
BranchTrueFalseTotal
if $depth <= 0 274429 98412 372841
153  
154 98412 my @moves = Game::Reversi::Board->legal_moves($board, $colour);
155  
156 98412 ▶ if (!@moves) {
Branch: 1 branch
BranchTrueFalseTotal
unless (@moves) 264 98148 98412
157 264 ▶ return $self->_leaf($state, $board, $colour) if $passes;
Branch: 1 branch
BranchTrueFalseTotal
if $passes 68 196 264
158 196 return -$self->_alphabeta($state, $board, Game::Reversi::Board->other($colour),
159 $depth, -$beta, -$alpha, 1);
160 }
161  
162 98148 for my $square ($self->_order($board, $colour, \@moves)) {
163 348282 my $after = Game::Reversi::Board->apply($board, $square, $colour);
164 348282 my $score = -$self->_alphabeta($state, $after, Game::Reversi::Board->other($colour),
165 $depth - 1, -$beta, -$alpha, 0);
166 348282 ▶ return 0 if $state->{over_budget};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"over_budget"} 374 347908 348282
167 347908 ▶ return $beta if $score >= $beta;
Branch: 1 branch
BranchTrueFalseTotal
if $score >= $beta 66221 281687 347908
168 281687 ▶ $alpha = $score if $score > $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $score > $alpha 35503 246184 281687
169 }
170 31553 return $alpha;
171 }
172  
173 274497 ▶sub _leaf {
Subroutine _leaf: called CC=7 SCAR=19.5
174 274497 my ($self, $state, $board, $me) = @_;
175 274497 my $them = Game::Reversi::Board->other($me);
176 274497 my $empty = Game::Reversi::Board->empties($board);
177 274497 my $count = Game::Reversi::Board->count($board);
178  
179 return ($count->{$me} - $count->{$them}) * 100
180 274497 ▶ if $empty <= $state->{setting}{exact};
Branch: 1 branch
BranchTrueFalseTotal
if $empty <= $state->{"setting"}{"exact"} 6568 267929 274497
181  
182 267929 my $score = 0;
183 267929 for my $square (0 .. 63) {
184 17147456 my $cell = $board->[$square];
185 17147456 ▶ next unless defined $cell;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $cell 10510340 6637116 17147456
186 6637116 ▶ $score += $cell eq $me ? $WEIGHT[$square] : -$WEIGHT[$square];
Branch: 1 branch
BranchTrueFalseTotal
$cell eq $me ? : 3117782 3519334 6637116
187 }
188  
189 $score -= $MOBILITY * scalar(Game::Reversi::Board->legal_moves($board, $them))
190 267929 ▶ if $state->{setting}{mobility};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"setting"}{"mobility"} 141024 126905 267929
191  
192 267929 ▶ $score += ($count->{$me} - $count->{$them}) * ($ENDGAME - $empty)
Branch: 1 branch
BranchTrueFalseTotal
if $empty < $Game::Reversi::Bot::ENDGAME 28348 239581 267929
193 if $empty < $ENDGAME;
194  
195 267929 return $score;
196 }
197  
198 99306 ▶sub _order {
Subroutine _order: called CC=2 SCAR=7.0
199 99306 my ($self, $board, $colour, $squares) = @_;
200 99306 ▶ return sort { $WEIGHT[$b] <=> $WEIGHT[$a] || $a <=> $b } @$squares;
Condition66%2/3
$WEIGHT[$b] <=> $WEIGHT[$a] || $a <=> $b
l!l&&r!l&&!r
10941545576240
MC/DC0%0/2
$WEIGHT[$b] <=> $WEIGHT[$a] || $a <=> $b
$WEIGHT[$b] <=> $WEIGHT[$a] $a <=> $b
Truth table66%2/3
A || B
A= $WEIGHT[$b] <=> $WEIGHT[$a]B= $a <=> $b
ABresult
1X1
011
000
201 }
202  
203 9 1;
204  
205 __END__
« Reversi/Notation.pm ↑ Summary Reversi/Rules.pm »