blib/lib/Game/Oware/Bot.pm

filter: Statementstmt 98.5% 131 / 133 Branchbran 90.9% 40 / 44 Conditioncond 78.2% 18 / 23 MC/DCmcdc 60.0% 9 / 15 Subroutinesub 100% 19 / 19 Podpod 75.0% 3 / 4 totaltotal 92.4% 220 / 238 CC 37 SCAR 17.7
CC
37
Cov
94%
_alphabeta
10.2
_leaf
9.0
choose
7.1
CRAP 5.8
« blib/lib/Game/Oware/Terminal.pm ↑ Summary blib/lib/Game/Oware/Notation.pm »
1 package Game::Oware::Bot;
2  
3 16 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 16 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
5  
6 16 ▶use Object::Proto::Sugar -types;
Subroutine BEGIN: called CC=1 SCAR=0.0
7  
8 16 ▶use Digest::SHA ();
Subroutine BEGIN: called CC=1 SCAR=0.0
9  
10 16 ▶use Game::Oware::Board;
Subroutine BEGIN: called CC=1 SCAR=0.0
11 16 ▶use Game::Oware::Rules;
Subroutine BEGIN: called CC=1 SCAR=0.0
12 16 ▶use Game::Oware::Scoring;
Subroutine BEGIN: called CC=1 SCAR=0.0
13 16 ▶use Game::Oware::Variant ();
Subroutine BEGIN: called CC=1 SCAR=0.0
14  
15 16 our $VERSION = '0.04';
16  
17 16 our $STORE = 100;
18 16 our $MATERIAL = 2;
19 16 our $VULNERABLE = 5;
20 16 our $LOADED = 3;
21 16 our $TERMINAL = 1000;
22  
23 16 my %LEVEL = (
24 1 => { depth => 1, nodes => 500, blunder => 1 },
25 2 => { depth => 3, nodes => 4000, blunder => 1 },
26 3 => { depth => 5, nodes => 20000, blunder => 0 },
27 4 => { depth => 8, nodes => 120000, blunder => 0 },
28 5 => { depth => 11, nodes => 400000, blunder => 0 },
29 );
30  
31 has level => (
32 is => 'ro',
33 isa => Int,
34 default => 3
35 16 );
36  
37 has seed => (
38 is => 'ro',
39 isa => Str,
40 default => ''
41 16 );
42  
43 has last_search => (
44 is => 'rw',
45 isa => HashRef,
46 default => {}
47 16 );
48  
49 136 ▶sub BUILD {
Subroutine BUILD: called CC=2 SCAR=6.9
Pod undocumented
50 136 my ($self) = @_;
51 die 'Game::Oware::Bot: there is no level ' . $self->level
52 136 ▶ unless $LEVEL{ $self->level };
Branch: 1 branch
BranchTrueFalseTotal
unless $LEVEL{$self->level} 2 134 136
53 134 return $self;
54 }
55  
56 12 ▶sub levels { return sort { $a <=> $b } keys %LEVEL }
Subroutine levels: called CC=1 SCAR=0.0
Pod documented
57  
58 61 ▶sub setting_for {
Subroutine setting_for: called CC=2 SCAR=6.9
Pod documented
59 61 my ($class, $level) = @_;
60 61 ▶ die "Game::Oware::Bot: there is no level $level" unless $LEVEL{$level};
Branch: 1 branch
BranchTrueFalseTotal
unless $LEVEL{$level} 2 59 61
61 59 return { %{ $LEVEL{$level} } };
62 }
63  
64 2908 ▶sub choose {
Subroutine choose: called CC=7 SCAR=19.6
Pod documented
65 2908 my ($self, $game, $seat) = @_;
66  
67 2908 ▶ return undef unless $game->status eq 'active';
Branch: 1 branch
BranchTrueFalseTotal
unless $game->status eq "active" 1 2907 2908
68 2907 ▶ return undef unless defined $seat && $seat eq $game->turn;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $seat and $seat eq $game->turn 1 2906 2907
Condition66%2/3
defined $seat and $seat eq $game->turn
!ll&&!rl&&r
012906
MC/DC50%1/2
defined $seat and $seat eq $game->turn
defined $seat $seat eq $game->turn
Truth table66%2/3
A and B
A= defined $seatB= $seat eq $game->turn
ABresult
0X0
100
111
69  
70 2906 my $legal = $game->legal($seat);
71 2906 ▶ return undef unless @$legal;
Branch: 1 branch
BranchTrueFalseTotal
unless @$legal 0 2906 2906
72  
73 2906 $self->last_search({ depth => 0, nodes => 0, score => undef, move => $legal->[0] });
74 2906 ▶ return $legal->[0] if @$legal == 1;
Branch: 1 branch
BranchTrueFalseTotal
if @$legal == 1 647 2259 2906
75  
76 my $state = {
77 nodes => 0,
78 2259 setting => $LEVEL{ $self->level },
79 variant => $game->variant,
80 };
81  
82 2259 my @ranked = $self->_search($state, $game, $seat, $legal);
83 2259 my $pick = $self->_pick($state, $game, $seat, \@ranked);
84  
85 $self->last_search({
86 depth => $state->{depth} // 0,
87 nodes => $state->{nodes},
88 score => $ranked[0]{score},
89 2259 ▶ move => $pick,
Condition50%1/2
$state->{"depth"} // 0
l!l
22590
MC/DC0%0/1
$state->{"depth"} // 0
$state->{"depth"}
Truth table50%1/2
A
A= $state->{"depth"}
Aresult
11
00
90 });
91  
92 2259 return $pick;
93 }
94  
95 2259 ▶sub _search {
Subroutine _search: called CC=5 SCAR=16.1
96 2259 my ($self, $state, $game, $seat, $legal) = @_;
97  
98 2259 my @children = $self->_children($state, $game->board, $seat, $legal);
99 2259 my @ranked = map { { house => $_->{house}, score => 0 } } @children;
100  
101 2259 for my $depth (1 .. $state->{setting}{depth}) {
102 7045 ▶ last if $state->{nodes} >= $state->{setting}{nodes};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"nodes"} >= $state->{"setting"}{"nodes"} 0 7045 7045
103  
104 7045 my @round;
105 7045 $state->{spent} = 0;
106  
107 7045 for my $child (@children) {
108 my $score = -$self->_alphabeta($state, $child->{board},
109 24232 Game::Oware::Board->other($seat), $depth - 1,
110 -1_000_000, 1_000_000);
111 24232 push @round, { house => $child->{house}, score => $score };
112 }
113  
114 7045 ▶ last if $state->{spent};
Branch: 1 branch
BranchTrueFalseTotal
if $state->{"spent"} 0 7045 7045
115  
116 7045 @ranked = sort { $b->{score} <=> $a->{score} } @round;
117 7045 $state->{depth} = $depth;
118  
119 7045 my %order = map { $ranked[$_]{house} => $_ } 0 .. $#ranked;
120 7045 @children = sort { $order{ $a->{house} } <=> $order{ $b->{house} } } @children;
121 }
122  
123 2259 return @ranked;
124 }
125  
126 119180 ▶sub _children {
Subroutine _children: called CC=3 SCAR=11.0
127 119180 my ($self, $state, $board, $seat, $legal) = @_;
128  
129 119180 my @children;
130 119180 for my $house (@$legal) {
131 my ($next, $move) =
132 504365 Game::Oware::Rules->resolve($board, $house, $seat, $state->{variant});
133 504365 push @children, { house => $house, board => $next, taken => $move->taken };
134 }
135  
136 119180 ▶ return sort { $b->{taken} <=> $a->{taken} || $a->{house} <=> $b->{house} } @children;
Condition66%2/3
$Game::Oware::Bot::b->{'taken'} <=> $Game::Oware::Bot::a->{'taken'} || $Game::Oware::Bot::a->{'house'} <=> $Game::Oware::Bot::b->{'house'}
l!l&&r!l&&!r
1308685430800
MC/DC0%0/2
$Game::Oware::Bot::b->{'taken'} <=> $Game::Oware::Bot::a->{'taken'} || $Game::Oware::Bot::a->{'house'} <=> $Game::Oware::Bot::b->{'house'}
$Game::Oware::Bot::b->{'taken'} <=> $Game::Oware::Bot::a->{'taken'} $Game::Oware::Bot::a->{'house'} <=> $Game::Oware::Bot::b->{'house'}
Truth table66%2/3
A || B
A= $Game::Oware::Bot::b->{'taken'} <=> $Game::Oware::Bot::a->{'taken'}B= $Game::Oware::Bot::a->{'house'} <=> $Game::Oware::Bot::b->{'house'}
ABresult
1X1
011
000
137 }
138  
139 306302 ▶sub _alphabeta {
Subroutine _alphabeta: called CC=10 SCAR=23.2
140 306302 my ($self, $state, $board, $seat, $depth, $alpha, $beta) = @_;
141  
142 306302 $state->{nodes}++;
143  
144 306302 ▶ return $self->_final($board, $seat)
Branch: 1 branch
BranchTrueFalseTotal
if "Game::Oware::Scoring"->target_reached($board) or "Game::Oware::Scoring"->is_draw($board) 763 305539 306302
Condition66%2/3
"Game::Oware::Scoring"->target_reached($board) or "Game::Oware::Scoring"->is_draw($board)
l!l&&r!l&&!r
7630305539
MC/DC50%1/2
"Game::Oware::Scoring"->target_reached($board) or "Game::Oware::Scoring"->is_draw($board)
"Game::Oware::Scoring"->target_reached($board) "Game::Oware::Scoring"->is_draw($board)
Truth table66%2/3
A or B
A= "Game::Oware::Scoring"->target_reached($board)B= "Game::Oware::Scoring"->is_draw($board)
ABresult
1X1
011
000
145 if Game::Oware::Scoring->target_reached($board)
146 || Game::Oware::Scoring->is_draw($board);
147  
148 my @legal =
149 305539 Game::Oware::Rules->legal_moves($board, $seat, $state->{variant});
150  
151 305539 ▶ return $self->_final(Game::Oware::Scoring->sweep_to($board, $seat), $seat)
Branch: 1 branch
BranchTrueFalseTotal
unless @legal 25 305514 305539
152 unless @legal;
153  
154 305514 ▶ if ($state->{nodes} >= $state->{setting}{nodes}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($state->{"nodes"} >= $state->{"setting"}{"nodes"}) 0 305514 305514
155 0 $state->{spent} = 1;
156 0 return $self->_leaf($board, $seat);
157 }
158  
159 305514 ▶ return $self->_leaf($board, $seat) if $depth <= 0;
Branch: 1 branch
BranchTrueFalseTotal
if $depth <= 0 188593 116921 305514
160  
161 116921 my $best = -1_000_000;
162  
163 116921 for my $child ($self->_children($state, $board, $seat, \@legal)) {
164 my $score = -$self->_alphabeta($state, $child->{board},
165 282070 Game::Oware::Board->other($seat), $depth - 1, -$beta, -$alpha);
166  
167 282070 ▶ $best = $score if $score > $best;
Branch: 1 branch
BranchTrueFalseTotal
if $score > $best 147395 134675 282070
168 282070 ▶ $alpha = $score if $score > $alpha;
Branch: 1 branch
BranchTrueFalseTotal
if $score > $alpha 121552 160518 282070
169 282070 ▶ last if $alpha >= $beta;
Branch: 1 branch
BranchTrueFalseTotal
if $alpha >= $beta 60257 221813 282070
170 }
171  
172 116921 return $best;
173 }
174  
175 788 ▶sub _final {
Subroutine _final: called CC=1 SCAR=0.0
176 788 my ($self, $board, $seat) = @_;
177 788 my $captured = Game::Oware::Scoring->captured($board);
178 788 my $foe = Game::Oware::Board->other($seat);
179 788 return ($captured->{$seat} - $captured->{$foe}) * $TERMINAL;
180 }
181  
182 188593 ▶sub _leaf {
Subroutine _leaf: called CC=9 SCAR=22.0
183 188593 my ($self, $board, $seat) = @_;
184  
185 188593 my $foe = Game::Oware::Board->other($seat);
186 188593 my $captured = Game::Oware::Scoring->captured($board);
187  
188 188593 my $score = ($captured->{$seat} - $captured->{$foe}) * $STORE;
189  
190 188593 $score += (Game::Oware::Board->seeds_on_side($board, $seat)
191 - Game::Oware::Board->seeds_on_side($board, $foe)) * $MATERIAL;
192  
193 188593 my ($mine, $theirs, $loaded_mine, $loaded_theirs) = (0, 0, 0, 0);
194 188593 for my $house (Game::Oware::Board->houses_of($seat)) {
195 1131558 ▶ $mine++ if $board->[$house] == 1 || $board->[$house] == 2;
Branch: 1 branch
BranchTrueFalseTotal
if $board->[$house] == 1 or $board->[$house] == 2 358781 772777 1131558
Condition100%3/3
$board->[$house] == 1 or $board->[$house] == 2
l!l&&r!l&&!r
249655109126772777
MC/DC100%2/2
$board->[$house] == 1 or $board->[$house] == 2
$board->[$house] == 1 $board->[$house] == 2
Truth table100%3/3
A or B
A= $board->[$house] == 1B= $board->[$house] == 2
ABresult
1X1
011
000
196 1131558 ▶ $loaded_mine++ if $board->[$house] >= 12;
Branch: 1 branch
BranchTrueFalseTotal
if $board->[$house] >= 12 9948 1121610 1131558
197 }
198 188593 for my $house (Game::Oware::Board->houses_of($foe)) {
199 1131558 ▶ $theirs++ if $board->[$house] == 1 || $board->[$house] == 2;
Branch: 1 branch
BranchTrueFalseTotal
if $board->[$house] == 1 or $board->[$house] == 2 347578 783980 1131558
Condition100%3/3
$board->[$house] == 1 or $board->[$house] == 2
l!l&&r!l&&!r
229931117647783980
MC/DC100%2/2
$board->[$house] == 1 or $board->[$house] == 2
$board->[$house] == 1 $board->[$house] == 2
Truth table100%3/3
A or B
A= $board->[$house] == 1B= $board->[$house] == 2
ABresult
1X1
011
000
200 1131558 ▶ $loaded_theirs++ if $board->[$house] >= 12;
Branch: 1 branch
BranchTrueFalseTotal
if $board->[$house] >= 12 9596 1121962 1131558
201 }
202  
203 188593 $score -= ($mine - $theirs) * $VULNERABLE;
204 188593 $score += ($loaded_mine - $loaded_theirs) * $LOADED;
205  
206 188593 return $score;
207 }
208  
209 3556 ▶sub _draw {
Subroutine _draw: called CC=1 SCAR=0.0
210 3556 my ($self, $game, $seat, $range) = @_;
211 3556 my $ply = scalar @{ $game->log };
212 3556 my $hash = Digest::SHA::sha256_hex($self->seed . ':' . $seat . ':' . $ply);
213 3556 return hex(substr $hash, 0, 8) % $range;
214 }
215  
216 2259 ▶sub _pick {
Subroutine _pick: called CC=6 SCAR=17.9
217 2259 my ($self, $state, $game, $seat, $ranked) = @_;
218  
219 2259 my $best = $ranked->[0]{score};
220 2259 my @tied = grep { $_->{score} == $best } @$ranked;
221  
222 2259 ▶ unless ($state->{setting}{blunder}) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($state->{"setting"}{"blunder"}) 382 1877 2259
223 382 return $tied[ $self->_draw($game, $seat, scalar @tied) ]{house};
224 }
225  
226 1877 my $roll = $self->_draw($game, $seat, 100);
227 1877 ▶ return $ranked->[1]{house} if $roll < 25 && @$ranked > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $roll < 25 and @$ranked > 1 446 1431 1877
Condition66%2/3
$roll < 25 and @$ranked > 1
!ll&&!rl&&r
14310446
MC/DC50%1/2
$roll < 25 and @$ranked > 1
$roll < 25 @$ranked > 1
Truth table66%2/3
A and B
A= $roll < 25B= @$ranked > 1
ABresult
0X0
100
111
228 1431 ▶ return $ranked->[2]{house} if $roll < 35 && @$ranked > 2;
Branch: 1 branch
BranchTrueFalseTotal
if $roll < 35 and @$ranked > 2 140 1291 1431
Condition100%3/3
$roll < 35 and @$ranked > 2
!ll&&!rl&&r
124150140
MC/DC100%2/2
$roll < 35 and @$ranked > 2
$roll < 35 @$ranked > 2
Truth table100%3/3
A and B
A= $roll < 35B= @$ranked > 2
ABresult
0X0
100
111
229 1291 return $tied[ $self->_draw($game, $seat, scalar @tied) ]{house};
230 }
231  
232 16 1;
233  
234 __END__
« blib/lib/Game/Oware/Terminal.pm ↑ Summary blib/lib/Game/Oware/Notation.pm »