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 5 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 5 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
5  
6 5 ▶use Object::Proto::Sugar -types;
Subroutine BEGIN: called CC=1 SCAR=0.0
7  
8 5 ▶use Digest::SHA ();
Subroutine BEGIN: called CC=1 SCAR=0.0
9  
10 5 ▶use Game::Reversi::Board;
Subroutine BEGIN: called CC=1 SCAR=0.0
11 5 ▶use Game::Reversi::Move;
Subroutine BEGIN: called CC=1 SCAR=0.0
12 5 ▶use Game::Reversi::Opening;
Subroutine BEGIN: called CC=1 SCAR=0.0
13  
14 5 our $VERSION = '0.03';
15  
16 5 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 5 our $MOBILITY = 5;
28  
29 5 our $ENDGAME = 20;
30  
31 5 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 29 ▶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 5 );
46  
47 has seed => (
48 is => 'ro',
49 default => 0
50 5 );
51  
52 has last_search => (
53 is => 'rw',
54 isa => Any
55 5 );
56  
57 113 ▶sub BUILD {
Subroutine BUILD: called CC=2 SCAR=6.9
Pod undocumented
58 113 my ($self) = @_;
59 die 'Game::Reversi::Bot: there is no level ' . $self->level
60 113 ▶ unless $LEVEL{ $self->level };
Branch: 1 branch
BranchTrueFalseTotal
unless $LEVEL{$self->level} 2 111 113
61 111 return $self;
62 }
63  
64 1198 ▶sub choose {
Subroutine choose: called CC=9 SCAR=22.1
Pod documented
65 1198 my ($self, $game, $colour) = @_;
66 1198 ▶ return undef unless $game->status eq 'active';
Branch: 1 branch
BranchTrueFalseTotal
unless $game->status eq "active" 2 1196 1198
67 1196 ▶ return undef unless defined $colour;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $colour 1 1195 1196
68 1195 ▶ return undef unless defined $game->turn && $game->turn eq $colour;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $game->turn and $game->turn eq $colour 1 1194 1195
Condition66%2/3
defined $game->turn and $game->turn eq $colour
!ll&&!rl&&r
011194
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 1194 my $legal = $game->legal($colour);
71 1194 ▶ return undef unless @$legal;
Branch: 1 branch
BranchTrueFalseTotal
unless @$legal 0 1194 1194
72 1194 ▶ return $legal->[0] if @$legal == 1;
Branch: 1 branch
BranchTrueFalseTotal
if @$legal == 1 83 1111 1194
73  
74 return $self->_open($game, $colour, $legal)
75 1111 ▶ if $game->phase eq 'opening' && !$LEVEL{ $self->level }{book};
Branch: 1 branch
BranchTrueFalseTotal
if $game->phase eq "opening" and not $LEVEL{$self->level}{"book"} 129 982 1111
Condition66%2/3
$game->phase eq "opening" and not $LEVEL{$self->level}{"book"}
!ll&&!rl&&r
9820129
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 982 return $self->_search($game, $colour, $legal);
78 }
79  
80 129 ▶sub _open {
Subroutine _open: called CC=1 SCAR=0.0
81 129 my ($self, $game, $colour, $legal) = @_;
82 my $key = join '|', $self->_seed($colour), scalar @$legal,
83 129 join ',', map { $_->square } @$legal;
84 129 my $word = unpack 'N', Digest::SHA::sha256($key);
85 129 $self->last_search({ nodes => 0, depth => 0, opening => 1 });
86 129 return $legal->[ $word % scalar @$legal ];
87 }
88  
89 129 ▶sub _seed {
Subroutine _seed: called CC=2 SCAR=7.2
90 129 my ($self, $colour) = @_;
91 129 ▶ return unpack 'H16',
Condition50%1/2
$colour // "?"
l!l
1290
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 982 ▶sub _search {
Subroutine _search: called CC=4 SCAR=13.9
96 982 my ($self, $game, $colour, $legal) = @_;
97 982 my $setting = $LEVEL{ $self->level };
98 982 my $board = $game->board;
99  
100 982 my @ordered = $self->_order($board, $colour, [ map { $_->square } @$legal ]);
101 982 my %move_of = map { $_->square => $_ } @$legal;
102  
103 my $state = {
104 nodes => 0, over_budget => 0,
105 982 budget => $setting->{nodes}, setting => $setting,
106 };
107  
108 982 my $best = $ordered[0];
109 982 my $depth_reached = 0;
110 982 my $value;
111  
112 982 for my $depth (1 .. $setting->{depth}) {
113 2768 my ($square, $score) = $self->_root($state, $board, $colour, $depth, \@ordered);
114 2768 ▶ last unless defined $square;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $square 111 2657 2768
115 2657 ($best, $value, $depth_reached) = ($square, $score, $depth);
116 2657 ▶ last if $state->{nodes} >= $state->{budget};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"nodes"} >= $state->{"budget"} 2 2655 2657
117  
118 2655 @ordered = ($best, grep { $_ != $best } @ordered);
119 }
120  
121 $self->last_search({
122 982 nodes => $state->{nodes}, depth => $depth_reached,
123 value => $value, opening => 0,
124 });
125 982 return $move_of{$best};
126 }
127  
128 2768 ▶sub _root {
Subroutine _root: called CC=4 SCAR=13.9
129 2768 my ($self, $state, $board, $colour, $depth, $ordered) = @_;
130 2768 my ($best, $alpha) = (undef, -1e9);
131  
132 2768 for my $square (@$ordered) {
133 20896 my $after = Game::Reversi::Board->apply($board, $square, $colour);
134 20896 my $score = -$self->_alphabeta($state, $after, Game::Reversi::Board->other($colour),
135 $depth - 1, -1e9, -$alpha, 0);
136 20896 ▶ return (undef, undef) if $state->{over_budget};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"over_budget"} 111 20785 20896
137 20785 ▶ if ($score > $alpha) {
Branch: 1 branch
BranchTrueFalseTotal
if ($score > $alpha) 4567 16218 20785
138 4567 ($alpha, $best) = ($score, $square);
139 }
140 }
141 2657 return ($best, $alpha);
142 }
143  
144 346097 ▶sub _alphabeta {
Subroutine _alphabeta: called CC=9 SCAR=22.0
145 346097 my ($self, $state, $board, $colour, $depth, $alpha, $beta, $passes) = @_;
146  
147 346097 ▶ if (++$state->{nodes} > $state->{budget}) {
Branch: 1 branch
BranchTrueFalseTotal
if (++$state->{"nodes"} > $state->{"budget"}) 111 345986 346097
148 111 $state->{over_budget} = 1;
149 111 return 0;
150 }
151  
152 345986 ▶ return $self->_leaf($state, $board, $colour) if $depth <= 0;
Branch: 1 branch
BranchTrueFalseTotal
if $depth <= 0 253237 92749 345986
153  
154 92749 my @moves = Game::Reversi::Board->legal_moves($board, $colour);
155  
156 92749 ▶ if (!@moves) {
Branch: 1 branch
BranchTrueFalseTotal
unless (@moves) 224 92525 92749
157 224 ▶ return $self->_leaf($state, $board, $colour) if $passes;
Branch: 1 branch
BranchTrueFalseTotal
if $passes 62 162 224
158 162 return -$self->_alphabeta($state, $board, Game::Reversi::Board->other($colour),
159 $depth, -$beta, -$alpha, 1);
160 }
161  
162 92525 for my $square ($self->_order($board, $colour, \@moves)) {
163 325039 my $after = Game::Reversi::Board->apply($board, $square, $colour);
164 325039 my $score = -$self->_alphabeta($state, $after, Game::Reversi::Board->other($colour),
165 $depth - 1, -$beta, -$alpha, 0);
166 325039 ▶ return 0 if $state->{over_budget};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"over_budget"} 350 324689 325039
167 324689 ▶ return $beta if $score >= $beta;
Branch: 1 branch
BranchTrueFalseTotal
if $score >= $beta 62684 262005 324689
168 262005 ▶ $alpha = $score if $score > $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $score > $alpha 32788 229217 262005
169 }
170 29491 return $alpha;
171 }
172  
173 253299 ▶sub _leaf {
Subroutine _leaf: called CC=7 SCAR=19.5
174 253299 my ($self, $state, $board, $me) = @_;
175 253299 my $them = Game::Reversi::Board->other($me);
176 253299 my $empty = Game::Reversi::Board->empties($board);
177 253299 my $count = Game::Reversi::Board->count($board);
178  
179 return ($count->{$me} - $count->{$them}) * 100
180 253299 ▶ if $empty <= $state->{setting}{exact};
Branch: 1 branch
BranchTrueFalseTotal
if $empty <= $state->{"setting"}{"exact"} 6215 247084 253299
181  
182 247084 my $score = 0;
183 247084 for my $square (0 .. 63) {
184 15813376 my $cell = $board->[$square];
185 15813376 ▶ next unless defined $cell;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $cell 9776680 6036696 15813376
186 6036696 ▶ $score += $cell eq $me ? $WEIGHT[$square] : -$WEIGHT[$square];
Branch: 1 branch
BranchTrueFalseTotal
$cell eq $me ? : 2833091 3203605 6036696
187 }
188  
189 $score -= $MOBILITY * scalar(Game::Reversi::Board->legal_moves($board, $them))
190 247084 ▶ if $state->{setting}{mobility};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"setting"}{"mobility"} 141024 106060 247084
191  
192 247084 ▶ $score += ($count->{$me} - $count->{$them}) * ($ENDGAME - $empty)
Branch: 1 branch
BranchTrueFalseTotal
if $empty < $Game::Reversi::Bot::ENDGAME 25720 221364 247084
193 if $empty < $ENDGAME;
194  
195 247084 return $score;
196 }
197  
198 93507 ▶sub _order {
Subroutine _order: called CC=2 SCAR=7.0
199 93507 my ($self, $board, $colour, $squares) = @_;
200 93507 ▶ return sort { $WEIGHT[$b] <=> $WEIGHT[$a] || $a <=> $b } @$squares;
Condition66%2/3
$WEIGHT[$b] <=> $WEIGHT[$a] || $a <=> $b
l!l&&r!l&&!r
10167845162670
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 5 1;
204  
205 __END__
« Reversi/Notation.pm ↑ Summary Reversi/Rules.pm »