Dominoes/Bot.pm

filter: Statementstmt 83.3% 10 / 12 Branchbran n/a Conditioncond n/a MC/DCmcdc n/a Subroutinesub 100% 4 / 4 Podpod n/a totaltotal 87.5% 14 / 16 CC 1 SCAR 0.7
CC
1
Cov
83%
BEGIN
1.3
BEGIN
1.0
BEGIN
1.0
CRAP 1.1
« Dominoes/Tile.pm ↑ Summary Dominoes/Notation.pm »
1 package Game::Dominoes::Bot;
2  
3 1 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 1 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
5  
6 1 ▶use Digest::SHA ();
Subroutine BEGIN: called CC=1 SCAR=0.0
7 0 ▶use Object::Proto::Sugar -types;
Subroutine BEGIN: called CC=1 SCAR=2.6
8  
9 use Game::Dominoes::Hand;
10 use Game::Dominoes::Rules;
11 use Game::Dominoes::Scoring;
12 use Game::Dominoes::Set;
13  
14 our $VERSION = '0.04';
15  
16 our %LEVEL = (
17 1 => { worlds => 0, depth => 0, shape => 0 },
18 2 => { worlds => 0, depth => 0, shape => 1 },
19 3 => { worlds => 24, depth => 8, shape => 1 },
20 4 => { worlds => 40, depth => 12, shape => 1 },
21 5 => { worlds => 64, depth => 16, shape => 1 },
22 );
23  
24 our $SAMPLE_TRIES = 40;
25  
26 has level => (is => 'ro', isa => Int, default => 3);
27 has seed => (is => 'ro', isa => Int, default => 0);
28 has last_search => (is => 'rw', isa => HashRef, default => {});
29  
30 sub BUILD {
31 my ($self) = @_;
32 die 'Game::Dominoes::Bot: level must be 1 to 5' unless $LEVEL{ $self->level };
33 return $self;
34 }
35  
36 sub levels { return { %LEVEL } }
37  
38 sub _stream {
39 my ($self, $key) = @_;
40 my ($counter, @words) = (0);
41 return sub {
42 unless (@words) {
43 @words = unpack 'N8',
44 Digest::SHA::sha256($self->seed . '|' . $key . '|' . $counter++);
45 }
46 return shift @words;
47 };
48 }
49  
50 sub _public_key {
51 my ($self, $view) = @_;
52 my @parts = (
53 $view->{seat}, $view->{players}, $view->{hand_number},
54 $view->{turn} // '-', $view->{boneyard},
55 join(',', map { $_ . ':' . $view->{counts}{$_} } sort keys %{ $view->{counts} }),
56 join(',', map { $_ . ':' . $view->{scores}{$_} } sort keys %{ $view->{scores} }),
57 join(',', map { $_->stringify } @{ $view->{layout}->tiles }),
58 join(',', @{ $view->{ends} }),
59 join(',', map { $_->stringify } @{ $view->{hand} || [] }),
60 );
61 return join '|', @parts;
62 }
63  
64 sub _shuffle {
65 my ($list, $next) = @_;
66 for (my $i = $#$list; $i > 0; $i--) {
67 my $n = $i + 1;
68 my $limit = int(4294967296 / $n) * $n;
69 my $word;
70 do { $word = $next->() } while $word >= $limit;
71 my $j = $word % $n;
72 @{$list}[ $i, $j ] = @{$list}[ $j, $i ];
73 }
74 return $list;
75 }
76  
77 sub _unseen {
78 my ($self, $view) = @_;
79 my %seen;
80 $seen{ $_->id } = 1 for @{ $view->{layout}->tiles };
81 $seen{ $_->id } = 1 for @{ $view->{hand} || [] };
82 return [ grep { !$seen{ $_->id } } @{ Game::Dominoes::Set::tiles() } ];
83 }
84  
85 sub _sample {
86 my ($self, $view, $next) = @_;
87  
88 my $unseen = $self->_unseen($view);
89 my @others = grep { $_ ne $view->{seat} } sort keys %{ $view->{counts} };
90 my $deductions = $view->{deductions} || {};
91  
92 my $best;
93 for my $try (1 .. $SAMPLE_TRIES) {
94 my @pool = @$unseen;
95 _shuffle(\@pool, $next);
96  
97 my (%hands, $bad);
98 for my $seat (@others) {
99 my $want = $view->{counts}{$seat};
100 my @take = splice @pool, 0, $want;
101 $hands{$seat} = \@take;
102 next unless $deductions->{$seat} && keys %{ $deductions->{$seat} };
103 for my $tile (@take) {
104 next unless $deductions->{$seat}{ $tile->high }
105 || $deductions->{$seat}{ $tile->low };
106 $bad = 1;
107 last;
108 }
109 last if $bad;
110 }
111  
112 my $world = { hands => \%hands, boneyard => [@pool] };
113 $best = $world unless $best;
114 return $world unless $bad;
115 }
116  
117 return $best;
118 }
119  
120 sub _rollout {
121 my ($self, $view, $world, $first, $depth) = @_;
122  
123 my $seat = $view->{seat};
124 my $layout = $view->{layout}->clone;
125 my %hand = (
126 $seat => Game::Dominoes::Hand->new(tiles => [ @{ $view->{hand} || [] } ]),
127 map { $_ => Game::Dominoes::Hand->new(tiles => [ @{ $world->{hands}{$_} } ]) }
128 keys %{ $world->{hands} },
129 );
130 my @yard = @{ $world->{boneyard} };
131  
132 $hand{$seat}->remove($first->{tile});
133 $layout->place($first->{tile}, $first->{arm});
134 my $score = Game::Dominoes::Scoring::score_for(
135 Game::Dominoes::Scoring::count($layout), $view->{scale}
136 );
137 return $score + _out_bonus($view, \%hand, $seat) if $hand{$seat}->is_empty;
138  
139 my @seats = sort { $a <=> $b } keys %hand;
140 my $at = 0;
141 $at++ while $at < $#seats && $seats[$at] != $seat;
142  
143 for my $ply (1 .. $depth) {
144 $at = ($at + 1) % @seats;
145 my $who = $seats[$at];
146 my $moves = Game::Dominoes::Rules::candidates($layout, $hand{$who});
147  
148 unless (@$moves) {
149 while (@yard) {
150 $hand{$who}->add(shift @yard);
151 $moves = Game::Dominoes::Rules::candidates($layout, $hand{$who});
152 last if @$moves;
153 }
154 next unless @$moves;
155 }
156  
157 my $best = $moves->[0];
158 my $best_points = -1;
159 for my $move (@$moves) {
160 my $points = Game::Dominoes::Rules::score_of(
161 $layout, $move->{tile}, $move->{arm}, $view->{scale}
162 );
163 next unless $points > $best_points;
164 ($best, $best_points) = ($move, $points);
165 }
166  
167 $hand{$who}->remove($best->{tile});
168 $layout->place($best->{tile}, $best->{arm});
169 my $points = Game::Dominoes::Scoring::score_for(
170 Game::Dominoes::Scoring::count($layout), $view->{scale}
171 );
172 $score += $who eq $seat ? $points : -$points;
173 return $score + ($who eq $seat ? 1 : -1) * _out_bonus($view, \%hand, $who)
174 if $hand{$who}->is_empty;
175 }
176  
177 return $score - $hand{$seat}->pips / 5;
178 }
179  
180 sub _out_bonus {
181 my ($view, $hands, $who) = @_;
182 my $pips = 0;
183 $pips += $hands->{$_}->pips for grep { $_ ne $who } keys %$hands;
184 return Game::Dominoes::Scoring::bonus($pips, $view->{scale});
185 }
186  
187 sub _shape {
188 my ($self, $view, $move) = @_;
189 my $tile = $move->{tile};
190 return $tile->pips / 100 + ($tile->is_double ? 0.05 : 0);
191 }
192  
193 sub choose {
194 my ($self, $game, $seat) = @_;
195  
196 my $view = (ref $game eq 'HASH') ? $game : $game->view($seat);
197 return undef unless $view->{hand} && @{ $view->{hand} };
198  
199 my $hand = Game::Dominoes::Hand->new(tiles => [ @{ $view->{hand} } ]);
200 my $moves = Game::Dominoes::Rules::candidates($view->{layout}, $hand);
201 if (my $forced = $view->{forced}) {
202 $moves = [ grep { $_->{tile}->id == $forced->id } @$moves ];
203 }
204 return undef unless @$moves;
205  
206 my $level = $LEVEL{ $self->level };
207 my $key = $self->_public_key($view);
208  
209 my @scored;
210 for my $move (@$moves) {
211 my $points = Game::Dominoes::Rules::score_of(
212 $view->{layout}, $move->{tile}, $move->{arm}, $view->{scale}
213 );
214 push @scored, {
215 move => $move,
216 score => $points + ($level->{shape} ? $self->_shape($view, $move) : 0),
217 points => $points,
218 };
219 }
220  
221 my $worlds = 0;
222 if ($level->{worlds}) {
223 my $next = $self->_stream($key);
224 my @sampled = map { $self->_sample($view, $next) } 1 .. $level->{worlds};
225 $worlds = scalar @sampled;
226  
227 for my $candidate (@scored) {
228 my $total = 0;
229 $total += $self->_rollout($view, $_, $candidate->{move}, $level->{depth})
230 for @sampled;
231 $candidate->{score} = $total / $worlds;
232 }
233 }
234  
235 my @order = sort {
236 $b->{score} <=> $a->{score}
237 || $b->{move}{tile}->pips <=> $a->{move}{tile}->pips
238 || $a->{move}{tile}->id <=> $b->{move}{tile}->id
239 || $a->{move}{arm} cmp $b->{move}{arm}
240 } @scored;
241  
242 $self->last_search({
243 level => $self->level,
244 worlds => $worlds,
245 depth => $level->{depth},
246 considered => scalar @scored,
247 score => $order[0]{score},
248 points => $order[0]{points},
249 play => $order[0]{move},
250 });
251  
252 return $order[0]{move};
253 }
254  
255 1;
256  
257 __END__
« Dominoes/Tile.pm ↑ Summary Dominoes/Notation.pm »