| 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
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 67 | 1196 | ▶ | return undef unless defined $colour; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 68 | 1195 | ▶ | return undef unless defined $game->turn && $game->turn eq $colour; | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
defined $game->turn and $game->turn eq $colour
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
| |||||||||||||||||||||||||||||
| 69 | |||||||||||||||||||||||||||||
| 70 | 1194 | my $legal = $game->legal($colour); | |||||||||||||||||||||||||||
| 71 | 1194 | ▶ | return undef unless @$legal; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 72 | 1194 | ▶ | return $legal->[0] if @$legal == 1; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 73 | |||||||||||||||||||||||||||||
| 74 | return $self->_open($game, $colour, $legal) | ||||||||||||||||||||||||||||
| 75 | 1111 | ▶ | if $game->phase eq 'opening' && !$LEVEL{ $self->level }{book}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
$game->phase eq "opening" and not $LEVEL{$self->level}{"book"}
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"}
| |||||||||||||||||||||||||||||
| 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 // "?"
MC/DC0%0/1
$colour // "?"
$colour
Truth table50%1/2
A
A= $colour
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 115 | 2657 | ($best, $value, $depth_reached) = ($square, $score, $depth); | |||||||||||||||||||||||||||
| 116 | 2657 | ▶ | last if $state->{nodes} >= $state->{budget}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 137 | 20785 | ▶ | if ($score > $alpha) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 153 | |||||||||||||||||||||||||||||
| 154 | 92749 | my @moves = Game::Reversi::Board->legal_moves($board, $colour); | |||||||||||||||||||||||||||
| 155 | |||||||||||||||||||||||||||||
| 156 | 92749 | ▶ | if (!@moves) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 157 | 224 | ▶ | return $self->_leaf($state, $board, $colour) if $passes; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 167 | 324689 | ▶ | return $beta if $score >= $beta; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 168 | 262005 | ▶ | $alpha = $score if $score > $alpha; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 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
| |||||||||||||||||||||||||||||
| 186 | 6036696 | ▶ | $score += $cell eq $me ? $WEIGHT[$square] : -$WEIGHT[$square]; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 187 | } | ||||||||||||||||||||||||||||
| 188 | |||||||||||||||||||||||||||||
| 189 | $score -= $MOBILITY * scalar(Game::Reversi::Board->legal_moves($board, $them)) | ||||||||||||||||||||||||||||
| 190 | 247084 | ▶ | if $state->{setting}{mobility}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 191 | |||||||||||||||||||||||||||||
| 192 | 247084 | ▶ | $score += ($count->{$me} - $count->{$them}) * ($ENDGAME - $empty) | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 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
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
| |||||||||||||||||||||||||||||
| 201 | } | ||||||||||||||||||||||||||||
| 202 | |||||||||||||||||||||||||||||
| 203 | 5 | 1; | |||||||||||||||||||||||||||
| 204 | |||||||||||||||||||||||||||||
| 205 | __END__ | ||||||||||||||||||||||||||||