| 1 | package Game::Checkers::Bot; | ||||||||||||||||||||||||||||||||||||||||||
| 2 | |||||||||||||||||||||||||||||||||||||||||||
| 3 | 15 | ▶ | use strict; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 4 | 15 | ▶ | use warnings; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 5 | |||||||||||||||||||||||||||||||||||||||||||
| 6 | 15 | ▶ | use Object::Proto::Sugar -types; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 7 | 15 | ▶ | use Game::Checkers::Squares; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 8 | 15 | ▶ | use Game::Checkers::Notation; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 9 | 15 | ▶ | use Game::Checkers::Rules; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 10 | 15 | ▶ | use Game::Checkers::Move; | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 11 | |||||||||||||||||||||||||||||||||||||||||||
| 12 | 15 | our $VERSION = '0.03'; | |||||||||||||||||||||||||||||||||||||||||
| 13 | |||||||||||||||||||||||||||||||||||||||||||
| 14 | 15 | ▶ | use constant { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 15 | 15 | MATE => 10_000, | |||||||||||||||||||||||||||||||||||||||||
| 16 | INFINITY => 1_000_000, | ||||||||||||||||||||||||||||||||||||||||||
| 17 | MAX_EXTENSION => 8, | ||||||||||||||||||||||||||||||||||||||||||
| 18 | MAX_PV => 20, | ||||||||||||||||||||||||||||||||||||||||||
| 19 | NO_PROGRESS_PLIES => 80, | ||||||||||||||||||||||||||||||||||||||||||
| 20 | EXACT => 0, | ||||||||||||||||||||||||||||||||||||||||||
| 21 | LOWER => 1, | ||||||||||||||||||||||||||||||||||||||||||
| 22 | UPPER => -1, | ||||||||||||||||||||||||||||||||||||||||||
| 23 | 15 | }; | |||||||||||||||||||||||||||||||||||||||||
| 24 | |||||||||||||||||||||||||||||||||||||||||||
| 25 | 15 | ▶ | use constant { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 26 | 15 | RM_FROM => Game::Checkers::Move::RM_FROM, | |||||||||||||||||||||||||||||||||||||||||
| 27 | RM_TO => Game::Checkers::Move::RM_TO, | ||||||||||||||||||||||||||||||||||||||||||
| 28 | RM_PROMOTED => Game::Checkers::Move::RM_PROMOTED, | ||||||||||||||||||||||||||||||||||||||||||
| 29 | RM_PATH => Game::Checkers::Move::RM_PATH, | ||||||||||||||||||||||||||||||||||||||||||
| 30 | RM_CAPTURES => Game::Checkers::Move::RM_CAPTURES, | ||||||||||||||||||||||||||||||||||||||||||
| 31 | RM_KING => Game::Checkers::Move::RM_KING, | ||||||||||||||||||||||||||||||||||||||||||
| 32 | 15 | }; | |||||||||||||||||||||||||||||||||||||||||
| 33 | |||||||||||||||||||||||||||||||||||||||||||
| 34 | 15 | our (%WEIGHT, %LEVEL); | |||||||||||||||||||||||||||||||||||||||||
| 35 | |||||||||||||||||||||||||||||||||||||||||||
| 36 | # has runs at compile time, and so does anything a level table is read by, so | ||||||||||||||||||||||||||||||||||||||||||
| 37 | # these are built here rather than in the file body | ||||||||||||||||||||||||||||||||||||||||||
| 38 | 15 | ▶ | BEGIN { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 39 | 15 | %WEIGHT = ( | |||||||||||||||||||||||||||||||||||||||||
| 40 | man => 100, | ||||||||||||||||||||||||||||||||||||||||||
| 41 | king => 160, | ||||||||||||||||||||||||||||||||||||||||||
| 42 | advance => 4, | ||||||||||||||||||||||||||||||||||||||||||
| 43 | back_rank => 8, | ||||||||||||||||||||||||||||||||||||||||||
| 44 | centre => 4, | ||||||||||||||||||||||||||||||||||||||||||
| 45 | edge => -6, | ||||||||||||||||||||||||||||||||||||||||||
| 46 | mobility => 2, | ||||||||||||||||||||||||||||||||||||||||||
| 47 | trapped_king => -20, | ||||||||||||||||||||||||||||||||||||||||||
| 48 | chase => -2, | ||||||||||||||||||||||||||||||||||||||||||
| 49 | ); | ||||||||||||||||||||||||||||||||||||||||||
| 50 | |||||||||||||||||||||||||||||||||||||||||||
| 51 | 15 | %LEVEL = ( | |||||||||||||||||||||||||||||||||||||||||
| 52 | 1 => { depth => 2, nodes => 300, jitter => 1 }, | ||||||||||||||||||||||||||||||||||||||||||
| 53 | 2 => { depth => 4, nodes => 2_000, jitter => 1 }, | ||||||||||||||||||||||||||||||||||||||||||
| 54 | 3 => { depth => 7, nodes => 20_000, jitter => 0 }, | ||||||||||||||||||||||||||||||||||||||||||
| 55 | 4 => { depth => 10, nodes => 120_000, jitter => 0 }, | ||||||||||||||||||||||||||||||||||||||||||
| 56 | 5 => { depth => 13, nodes => 600_000, jitter => 0 }, | ||||||||||||||||||||||||||||||||||||||||||
| 57 | ); | ||||||||||||||||||||||||||||||||||||||||||
| 58 | } | ||||||||||||||||||||||||||||||||||||||||||
| 59 | |||||||||||||||||||||||||||||||||||||||||||
| 60 | 15 | my $ROW = \@Game::Checkers::Squares::ROW; | |||||||||||||||||||||||||||||||||||||||||
| 61 | 15 | my $COL = \@Game::Checkers::Squares::COL; | |||||||||||||||||||||||||||||||||||||||||
| 62 | 15 | my $STEP = \@Game::Checkers::Squares::STEP; | |||||||||||||||||||||||||||||||||||||||||
| 63 | 15 | my $JUMP_OVER = \@Game::Checkers::Squares::JUMP_OVER; | |||||||||||||||||||||||||||||||||||||||||
| 64 | 15 | my $JUMP_TO = \@Game::Checkers::Squares::JUMP_TO; | |||||||||||||||||||||||||||||||||||||||||
| 65 | |||||||||||||||||||||||||||||||||||||||||||
| 66 | 15 | my @DIRS = @Game::Checkers::Squares::DIRS; | |||||||||||||||||||||||||||||||||||||||||
| 67 | |||||||||||||||||||||||||||||||||||||||||||
| 68 | 15 | my %FORWARD = ( | |||||||||||||||||||||||||||||||||||||||||
| 69 | 1 => [Game::Checkers::Squares::SE(), Game::Checkers::Squares::SW()], | ||||||||||||||||||||||||||||||||||||||||||
| 70 | -1 => [Game::Checkers::Squares::NE(), Game::Checkers::Squares::NW()], | ||||||||||||||||||||||||||||||||||||||||||
| 71 | ); | ||||||||||||||||||||||||||||||||||||||||||
| 72 | |||||||||||||||||||||||||||||||||||||||||||
| 73 | has level => ( | ||||||||||||||||||||||||||||||||||||||||||
| 74 | is => 'rw', | ||||||||||||||||||||||||||||||||||||||||||
| 75 | isa => Int, | ||||||||||||||||||||||||||||||||||||||||||
| 76 | default => 3 | ||||||||||||||||||||||||||||||||||||||||||
| 77 | 15 | ); | |||||||||||||||||||||||||||||||||||||||||
| 78 | |||||||||||||||||||||||||||||||||||||||||||
| 79 | has seed => ( | ||||||||||||||||||||||||||||||||||||||||||
| 80 | is => 'rw', | ||||||||||||||||||||||||||||||||||||||||||
| 81 | isa => Int, | ||||||||||||||||||||||||||||||||||||||||||
| 82 | default => 0 | ||||||||||||||||||||||||||||||||||||||||||
| 83 | 15 | ); | |||||||||||||||||||||||||||||||||||||||||
| 84 | |||||||||||||||||||||||||||||||||||||||||||
| 85 | has transposition => ( | ||||||||||||||||||||||||||||||||||||||||||
| 86 | is => 'rw', | ||||||||||||||||||||||||||||||||||||||||||
| 87 | isa => Bool, | ||||||||||||||||||||||||||||||||||||||||||
| 88 | default => 1 | ||||||||||||||||||||||||||||||||||||||||||
| 89 | 15 | ); | |||||||||||||||||||||||||||||||||||||||||
| 90 | |||||||||||||||||||||||||||||||||||||||||||
| 91 | has last_search => ( | ||||||||||||||||||||||||||||||||||||||||||
| 92 | is => 'rw' | ||||||||||||||||||||||||||||||||||||||||||
| 93 | 15 | ); | |||||||||||||||||||||||||||||||||||||||||
| 94 | |||||||||||||||||||||||||||||||||||||||||||
| 95 | 1221 | ▶ | sub choose { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
choose: called CC=13 SCAR=26.0
Pod
documented
| |||||||||||||||||||||||||||||||||||||||||||
| 96 | 1221 | my ($self, $game) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 97 | 1221 | ▶ | return undef if $game->result; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 98 | |||||||||||||||||||||||||||||||||||||||||||
| 99 | 1220 | my $legal = $game->legal_moves; | |||||||||||||||||||||||||||||||||||||||||
| 100 | 1220 | ▶ | return undef unless @{$legal}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 101 | |||||||||||||||||||||||||||||||||||||||||||
| 102 | 1220 | ▶ | if (@{$legal} == 1) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 103 | 175 | $self->last_search({ | |||||||||||||||||||||||||||||||||||||||||
| 104 | depth => 0, | ||||||||||||||||||||||||||||||||||||||||||
| 105 | nodes => 0, | ||||||||||||||||||||||||||||||||||||||||||
| 106 | score => undef, | ||||||||||||||||||||||||||||||||||||||||||
| 107 | forced => 1, | ||||||||||||||||||||||||||||||||||||||||||
| 108 | move => $legal->[0]->notation, | ||||||||||||||||||||||||||||||||||||||||||
| 109 | pv => [$legal->[0]->notation] | ||||||||||||||||||||||||||||||||||||||||||
| 110 | }); | ||||||||||||||||||||||||||||||||||||||||||
| 111 | 175 | return $legal->[0]; | |||||||||||||||||||||||||||||||||||||||||
| 112 | } | ||||||||||||||||||||||||||||||||||||||||||
| 113 | |||||||||||||||||||||||||||||||||||||||||||
| 114 | 1045 | ▶ | my $spec = $LEVEL{$self->level} | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 115 | or die 'level must be 1 .. 5, got ' . $self->level; | ||||||||||||||||||||||||||||||||||||||||||
| 116 | |||||||||||||||||||||||||||||||||||||||||||
| 117 | 1045 | my $position = [@{$game->board->position}]; | |||||||||||||||||||||||||||||||||||||||||
| 118 | 1045 | my $turn = $game->turn; | |||||||||||||||||||||||||||||||||||||||||
| 119 | my $state = { | ||||||||||||||||||||||||||||||||||||||||||
| 120 | nodes => 0, | ||||||||||||||||||||||||||||||||||||||||||
| 121 | budget => $spec->{nodes}, | ||||||||||||||||||||||||||||||||||||||||||
| 122 | jitter => $spec->{jitter}, | ||||||||||||||||||||||||||||||||||||||||||
| 123 | 1045 | table => {}, | |||||||||||||||||||||||||||||||||||||||||
| 124 | history => {}, | ||||||||||||||||||||||||||||||||||||||||||
| 125 | killers => [], | ||||||||||||||||||||||||||||||||||||||||||
| 126 | seen => $self->_seen($game), | ||||||||||||||||||||||||||||||||||||||||||
| 127 | aborted => 0 | ||||||||||||||||||||||||||||||||||||||||||
| 128 | }; | ||||||||||||||||||||||||||||||||||||||||||
| 129 | |||||||||||||||||||||||||||||||||||||||||||
| 130 | 1045 | my ($best, $score, $reached); | |||||||||||||||||||||||||||||||||||||||||
| 131 | 1045 | for my $depth (1 .. $spec->{depth}) { | |||||||||||||||||||||||||||||||||||||||||
| 132 | 3917 | ▶ | last if $state->{nodes} > $state->{budget}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 133 | 3917 | $state->{aborted} = 0; | |||||||||||||||||||||||||||||||||||||||||
| 134 | 3917 | my ($iteration_score, $move) = $self->_root( | |||||||||||||||||||||||||||||||||||||||||
| 135 | $state, $position, $turn, $depth, $game->no_progress, $game->ply | ||||||||||||||||||||||||||||||||||||||||||
| 136 | ); | ||||||||||||||||||||||||||||||||||||||||||
| 137 | 3917 | ▶ | last if $state->{aborted} || !$move; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
$state->{"aborted"} or not $move
MC/DC50%1/2
$state->{"aborted"} or not $move
$state->{"aborted"}
not $move
Truth table66%2/3
A or not(B)
A= $state->{"aborted"}B= not $move
| |||||||||||||||||||||||||||||||||||||||||||
| 138 | 3465 | ($best, $score, $reached) = ($move, $iteration_score, $depth); | |||||||||||||||||||||||||||||||||||||||||
| 139 | } | ||||||||||||||||||||||||||||||||||||||||||
| 140 | |||||||||||||||||||||||||||||||||||||||||||
| 141 | my $notation = $best | ||||||||||||||||||||||||||||||||||||||||||
| 142 | ? Game::Checkers::Notation::format_move({ | ||||||||||||||||||||||||||||||||||||||||||
| 143 | squares => $best->[RM_PATH], | ||||||||||||||||||||||||||||||||||||||||||
| 144 | 1045 | ▶ | jump => scalar @{$best->[RM_CAPTURES]} | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 145 | }) | ||||||||||||||||||||||||||||||||||||||||||
| 146 | : $legal->[0]->notation; | ||||||||||||||||||||||||||||||||||||||||||
| 147 | |||||||||||||||||||||||||||||||||||||||||||
| 148 | $self->last_search({ | ||||||||||||||||||||||||||||||||||||||||||
| 149 | depth => $reached || 0, | ||||||||||||||||||||||||||||||||||||||||||
| 150 | nodes => $state->{nodes}, | ||||||||||||||||||||||||||||||||||||||||||
| 151 | 1045 | ▶ | score => $score, | ||||||||||||||||||||||||||||||||||||||||
|
Condition50%1/2
$reached || 0
MC/DC0%0/1
$reached || 0
$reached
Truth table50%1/2
A
A= $reached
| |||||||||||||||||||||||||||||||||||||||||||
| 152 | forced => 0, | ||||||||||||||||||||||||||||||||||||||||||
| 153 | move => $notation, | ||||||||||||||||||||||||||||||||||||||||||
| 154 | pv => $self->_pv($state, $position, $turn, $best) | ||||||||||||||||||||||||||||||||||||||||||
| 155 | }); | ||||||||||||||||||||||||||||||||||||||||||
| 156 | |||||||||||||||||||||||||||||||||||||||||||
| 157 | # the move handed back is the one out of the game's own legal list, so a | ||||||||||||||||||||||||||||||||||||||||||
| 158 | # caller may compare it by reference as well as by notation | ||||||||||||||||||||||||||||||||||||||||||
| 159 | 1045 | for my $move (@{$legal}) { | |||||||||||||||||||||||||||||||||||||||||
| 160 | 4189 | ▶ | return $move if $move->notation eq $notation; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 161 | } | ||||||||||||||||||||||||||||||||||||||||||
| 162 | 0 | return $legal->[0]; | |||||||||||||||||||||||||||||||||||||||||
| 163 | } | ||||||||||||||||||||||||||||||||||||||||||
| 164 | |||||||||||||||||||||||||||||||||||||||||||
| 165 | 1045 | ▶ | sub _seen { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_seen: called CC=3 SCAR=11.0
| |||||||||||||||||||||||||||||||||||||||||||
| 166 | 1045 | my ($self, $game) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 167 | 1045 | my ($position, $turn) = | |||||||||||||||||||||||||||||||||||||||||
| 168 | Game::Checkers::Notation::position_from_fen($game->fen); | ||||||||||||||||||||||||||||||||||||||||||
| 169 | 1045 | my %seen = (_key($position, $turn) => 1); | |||||||||||||||||||||||||||||||||||||||||
| 170 | 1045 | for my $move (@{$game->history}) { | |||||||||||||||||||||||||||||||||||||||||
| 171 | 38316 | Game::Checkers::Rules::apply($position, $move->to_raw); | |||||||||||||||||||||||||||||||||||||||||
| 172 | 38316 | ▶ | $turn = $turn eq 'black' ? 'white' : 'black'; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 173 | 38316 | $seen{_key($position, $turn)}++; | |||||||||||||||||||||||||||||||||||||||||
| 174 | } | ||||||||||||||||||||||||||||||||||||||||||
| 175 | 1045 | return \%seen; | |||||||||||||||||||||||||||||||||||||||||
| 176 | } | ||||||||||||||||||||||||||||||||||||||||||
| 177 | |||||||||||||||||||||||||||||||||||||||||||
| 178 | 2982597 | ▶ | sub _key { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_key: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||||||||||
| 179 | 2982597 | my ($position, $turn) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 180 | 2982597 | return pack('c32', @{$position}[1 .. 32]) . $turn; | |||||||||||||||||||||||||||||||||||||||||
| 181 | } | ||||||||||||||||||||||||||||||||||||||||||
| 182 | |||||||||||||||||||||||||||||||||||||||||||
| 183 | 3917 | ▶ | sub _root { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_root: called CC=12 SCAR=24.9
| |||||||||||||||||||||||||||||||||||||||||||
| 184 | 3917 | my ($self, $state, $position, $turn, $depth, $no_progress, $ply) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 185 | 3917 | my $moves = Game::Checkers::Rules::generate($position, $turn); | |||||||||||||||||||||||||||||||||||||||||
| 186 | 3917 | ▶ | return (undef, undef) unless @{$moves}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 187 | |||||||||||||||||||||||||||||||||||||||||||
| 188 | 3917 | ▶ | my $forced = @{$moves->[0][RM_CAPTURES]} ? 1 : 0; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 189 | 3917 | ▶ | my ($child_depth, $child_extension) = $forced | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 190 | ? ($depth, 1) | ||||||||||||||||||||||||||||||||||||||||||
| 191 | : ($depth - 1, 0); | ||||||||||||||||||||||||||||||||||||||||||
| 192 | |||||||||||||||||||||||||||||||||||||||||||
| 193 | 3917 | my $alpha = -INFINITY(); | |||||||||||||||||||||||||||||||||||||||||
| 194 | 3917 | my ($best, $best_score); | |||||||||||||||||||||||||||||||||||||||||
| 195 | 3917 | for my $raw (@{$self->_ordered($state, $moves, 0, undef)}) { | |||||||||||||||||||||||||||||||||||||||||
| 196 | # a move that fails low comes back as a bound rather than a score, and | ||||||||||||||||||||||||||||||||||||||||||
| 197 | # a bound plus a jitter is how a losing move gets chosen. So when the | ||||||||||||||||||||||||||||||||||||||||||
| 198 | # jitter is on every root move is searched with the full window and the | ||||||||||||||||||||||||||||||||||||||||||
| 199 | # scores it is added to are all exact. | ||||||||||||||||||||||||||||||||||||||||||
| 200 | 25886 | ▶ | my $bound = $state->{jitter} ? -INFINITY() : $alpha; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 201 | 25886 | my $score = $self->_child( | |||||||||||||||||||||||||||||||||||||||||
| 202 | $state, $position, $turn, $raw, | ||||||||||||||||||||||||||||||||||||||||||
| 203 | $child_depth, -INFINITY(), -$bound, 1, $child_extension, $no_progress | ||||||||||||||||||||||||||||||||||||||||||
| 204 | ); | ||||||||||||||||||||||||||||||||||||||||||
| 205 | 25886 | ▶ | return (undef, undef) if $state->{aborted}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 206 | |||||||||||||||||||||||||||||||||||||||||||
| 207 | 25434 | ▶ | $score += _jitter($self->seed, $ply, $raw) if $state->{jitter}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 208 | |||||||||||||||||||||||||||||||||||||||||||
| 209 | 25434 | ▶ | if (!defined $best_score || $score > $best_score) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
not defined $best_score or $score > $best_score
MC/DC100%2/2
not defined $best_score or $score > $best_score
not defined $best_score
$score > $best_score
Truth table100%3/3
not(A) or B
A= not defined $best_scoreB= $score > $best_score
| |||||||||||||||||||||||||||||||||||||||||||
| 210 | 9343 | ($best, $best_score) = ($raw, $score); | |||||||||||||||||||||||||||||||||||||||||
| 211 | 9343 | ▶ | $alpha = $score if $score > $alpha && !$state->{jitter}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
$score > $alpha and not $state->{"jitter"}
MC/DC50%1/2
$score > $alpha and not $state->{"jitter"}
$score > $alpha
not $state->{"jitter"}
Truth table66%2/3
A and not(B)
A= $score > $alphaB= not $state->{"jitter"}
| |||||||||||||||||||||||||||||||||||||||||||
| 212 | } | ||||||||||||||||||||||||||||||||||||||||||
| 213 | } | ||||||||||||||||||||||||||||||||||||||||||
| 214 | 3465 | return ($best_score, $best); | |||||||||||||||||||||||||||||||||||||||||
| 215 | } | ||||||||||||||||||||||||||||||||||||||||||
| 216 | |||||||||||||||||||||||||||||||||||||||||||
| 217 | 1469108 | ▶ | sub _child { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_child: called CC=4 SCAR=13.9
| |||||||||||||||||||||||||||||||||||||||||||
| 218 | 1469108 | my ($self, $state, $position, $turn, $raw, $depth, $alpha, $beta, $ply, | |||||||||||||||||||||||||||||||||||||||||
| 219 | $extension, $no_progress) = @_; | ||||||||||||||||||||||||||||||||||||||||||
| 220 | |||||||||||||||||||||||||||||||||||||||||||
| 221 | 1469108 | ▶ | my $next = $turn eq 'black' ? 'white' : 'black'; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 222 | 1469108 | ▶ | my $progress = Game::Checkers::Rules::progress($raw) ? 0 : $no_progress + 1; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 223 | |||||||||||||||||||||||||||||||||||||||||||
| 224 | 1469108 | Game::Checkers::Rules::apply($position, $raw); | |||||||||||||||||||||||||||||||||||||||||
| 225 | 1469108 | my $key = _key($position, $next); | |||||||||||||||||||||||||||||||||||||||||
| 226 | 1469108 | $state->{seen}{$key}++; | |||||||||||||||||||||||||||||||||||||||||
| 227 | |||||||||||||||||||||||||||||||||||||||||||
| 228 | 1469108 | my $score = -$self->_search( | |||||||||||||||||||||||||||||||||||||||||
| 229 | $state, $position, $next, $depth, $alpha, $beta, $ply, $extension, $progress | ||||||||||||||||||||||||||||||||||||||||||
| 230 | ); | ||||||||||||||||||||||||||||||||||||||||||
| 231 | |||||||||||||||||||||||||||||||||||||||||||
| 232 | 1469108 | ▶ | delete $state->{seen}{$key} unless --$state->{seen}{$key}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 233 | 1469108 | Game::Checkers::Rules::unapply($position, $raw); | |||||||||||||||||||||||||||||||||||||||||
| 234 | 1469108 | return $score; | |||||||||||||||||||||||||||||||||||||||||
| 235 | } | ||||||||||||||||||||||||||||||||||||||||||
| 236 | |||||||||||||||||||||||||||||||||||||||||||
| 237 | 1469108 | ▶ | sub _search { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_search: called CC=34 SCAR=35.3
| |||||||||||||||||||||||||||||||||||||||||||
| 238 | 1469108 | my ($self, $state, $position, $turn, $depth, $alpha, $beta, $ply, | |||||||||||||||||||||||||||||||||||||||||
| 239 | $extension, $no_progress) = @_; | ||||||||||||||||||||||||||||||||||||||||||
| 240 | |||||||||||||||||||||||||||||||||||||||||||
| 241 | 1469108 | $state->{nodes}++; | |||||||||||||||||||||||||||||||||||||||||
| 242 | 1469108 | ▶ | if ($state->{nodes} >= $state->{budget}) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 243 | 452 | $state->{aborted} = 1; | |||||||||||||||||||||||||||||||||||||||||
| 244 | 452 | return 0; | |||||||||||||||||||||||||||||||||||||||||
| 245 | } | ||||||||||||||||||||||||||||||||||||||||||
| 246 | |||||||||||||||||||||||||||||||||||||||||||
| 247 | 1468656 | my $key = _key($position, $turn); | |||||||||||||||||||||||||||||||||||||||||
| 248 | 1468656 | ▶ | return 0 if ($state->{seen}{$key} || 0) >= 3; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition50%1/2
$state->{'seen'}{$key} || 0
MC/DC0%0/1
$state->{'seen'}{$key} || 0
$state->{'seen'}{$key}
Truth table50%1/2
A
A= $state->{'seen'}{$key}
| |||||||||||||||||||||||||||||||||||||||||||
| 249 | 1468548 | ▶ | return 0 if $no_progress >= NO_PROGRESS_PLIES; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 250 | |||||||||||||||||||||||||||||||||||||||||||
| 251 | 1468548 | ▶ | my $entry = $self->transposition ? $state->{table}{$key} : undef; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 252 | 1468548 | my $table_move; | |||||||||||||||||||||||||||||||||||||||||
| 253 | 1468548 | ▶ | if ($entry) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 254 | 213699 | $table_move = $entry->[3]; | |||||||||||||||||||||||||||||||||||||||||
| 255 | 213699 | ▶ | if ($entry->[0] >= $depth && abs($entry->[1]) < MATE - 100) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$entry->[0] >= $depth and abs $entry->[1] < 9900
MC/DC100%2/2
$entry->[0] >= $depth and abs $entry->[1] < 9900
$entry->[0] >= $depth
abs $entry->[1] < 9900
Truth table100%3/3
A and B
A= $entry->[0] >= $depthB= abs $entry->[1] < 9900
| |||||||||||||||||||||||||||||||||||||||||||
| 256 | 50284 | ▶ | return $entry->[1] if $entry->[2] == EXACT; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 257 | 45235 | ▶ | return $entry->[1] if $entry->[2] == LOWER && $entry->[1] >= $beta; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$entry->[2] == 1 and $entry->[1] >= $beta
MC/DC100%2/2
$entry->[2] == 1 and $entry->[1] >= $beta
$entry->[2] == 1
$entry->[1] >= $beta
Truth table100%3/3
A and B
A= $entry->[2] == 1B= $entry->[1] >= $beta
| |||||||||||||||||||||||||||||||||||||||||||
| 258 | 14105 | ▶ | return $entry->[1] if $entry->[2] == UPPER && $entry->[1] <= $alpha; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$entry->[2] == -1 and $entry->[1] <= $alpha
MC/DC100%2/2
$entry->[2] == -1 and $entry->[1] <= $alpha
$entry->[2] == -1
$entry->[1] <= $alpha
Truth table100%3/3
A and B
A= $entry->[2] == -1B= $entry->[1] <= $alpha
| |||||||||||||||||||||||||||||||||||||||||||
| 259 | } | ||||||||||||||||||||||||||||||||||||||||||
| 260 | } | ||||||||||||||||||||||||||||||||||||||||||
| 261 | |||||||||||||||||||||||||||||||||||||||||||
| 262 | 1423703 | my $moves = Game::Checkers::Rules::generate($position, $turn); | |||||||||||||||||||||||||||||||||||||||||
| 263 | 1423703 | ▶ | return -MATE() + $ply unless @{$moves}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 264 | |||||||||||||||||||||||||||||||||||||||||||
| 265 | 1415102 | ▶ | my $forced = @{$moves->[0][RM_CAPTURES]} ? 1 : 0; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 266 | 1415102 | ▶ | my $extend = $forced && $extension < MAX_EXTENSION ? 1 : 0; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$forced and $extension < 8
MC/DC100%2/2
$forced and $extension < 8
$forced
$extension < 8
Truth table100%3/3
A and B
A= $forcedB= $extension < 8
| |||||||||||||||||||||||||||||||||||||||||||
| 267 | 1415102 | ▶ | return _evaluate($position, $turn) if $depth <= 0 && !$extend; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$depth <= 0 and not $extend
MC/DC100%2/2
$depth <= 0 and not $extend
$depth <= 0
not $extend
Truth table100%3/3
A and not(B)
A= $depth <= 0B= not $extend
| |||||||||||||||||||||||||||||||||||||||||||
| 268 | |||||||||||||||||||||||||||||||||||||||||||
| 269 | 701599 | ▶ | my ($child_depth, $child_extension) = $extend | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 270 | ? ($depth, $extension + 1) | ||||||||||||||||||||||||||||||||||||||||||
| 271 | : ($depth - 1, $extension); | ||||||||||||||||||||||||||||||||||||||||||
| 272 | |||||||||||||||||||||||||||||||||||||||||||
| 273 | 701599 | my $original = $alpha; | |||||||||||||||||||||||||||||||||||||||||
| 274 | 701599 | my ($best_score, $best_move) = (-INFINITY(), undef); | |||||||||||||||||||||||||||||||||||||||||
| 275 | 701599 | for my $raw (@{$self->_ordered($state, $moves, $ply, $table_move)}) { | |||||||||||||||||||||||||||||||||||||||||
| 276 | 1443222 | my $score = $self->_child( | |||||||||||||||||||||||||||||||||||||||||
| 277 | $state, $position, $turn, $raw, | ||||||||||||||||||||||||||||||||||||||||||
| 278 | $child_depth, -$beta, -$alpha, $ply + 1, $child_extension, $no_progress | ||||||||||||||||||||||||||||||||||||||||||
| 279 | ); | ||||||||||||||||||||||||||||||||||||||||||
| 280 | 1443222 | ▶ | return 0 if $state->{aborted}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 281 | |||||||||||||||||||||||||||||||||||||||||||
| 282 | 1440714 | ▶ | if ($score > $best_score) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 283 | 836870 | ($best_score, $best_move) = ($score, $raw); | |||||||||||||||||||||||||||||||||||||||||
| 284 | 836870 | ▶ | $alpha = $score if $score > $alpha; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 285 | } | ||||||||||||||||||||||||||||||||||||||||||
| 286 | 1440714 | ▶ | next if $alpha < $beta; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 287 | |||||||||||||||||||||||||||||||||||||||||||
| 288 | 408854 | my $name = $raw->[RM_FROM] . '-' . $raw->[RM_TO]; | |||||||||||||||||||||||||||||||||||||||||
| 289 | 408854 | $state->{history}{$name} += $depth * $depth; | |||||||||||||||||||||||||||||||||||||||||
| 290 | 408854 | ▶ | my $killers = $state->{killers}[$ply] ||= []; | ||||||||||||||||||||||||||||||||||||||||
|
Condition100%2/2
$state->{"killers"}[$ply] ||= []
MC/DC100%1/1
$state->{"killers"}[$ply] ||= []
$state->{"killers"}[$ply]
Truth table100%2/2
A
A= $state->{"killers"}[$ply]
| |||||||||||||||||||||||||||||||||||||||||||
| 291 | 306978 | unshift @{$killers}, $name | |||||||||||||||||||||||||||||||||||||||||
| 292 | 408854 | ▶ | unless @{$killers} && $killers->[0] eq $name; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
@{$killers;} and $killers->[0] eq $name
MC/DC100%2/2
@{$killers;} and $killers->[0] eq $name
@{$killers;}
$killers->[0] eq $name
Truth table100%3/3
A and B
A= @{$killers;}B= $killers->[0] eq $name
| |||||||||||||||||||||||||||||||||||||||||||
| 293 | 408854 | ▶ | pop @{$killers} while @{$killers} > 2; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 294 | 408854 | last; | |||||||||||||||||||||||||||||||||||||||||
| 295 | } | ||||||||||||||||||||||||||||||||||||||||||
| 296 | |||||||||||||||||||||||||||||||||||||||||||
| 297 | 699091 | ▶ | if ($self->transposition) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 298 | 697795 | ▶ | my $flag = $best_score <= $original ? UPPER | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||||||||||||||||
| 299 | : $best_score >= $beta ? LOWER | ||||||||||||||||||||||||||||||||||||||||||
| 300 | : EXACT; | ||||||||||||||||||||||||||||||||||||||||||
| 301 | $state->{table}{$key} = [ | ||||||||||||||||||||||||||||||||||||||||||
| 302 | $depth, $best_score, $flag, | ||||||||||||||||||||||||||||||||||||||||||
| 303 | 697795 | ▶ | $best_move && [@{$best_move}] | ||||||||||||||||||||||||||||||||||||||||
|
Condition50%1/2
$best_move && [@{$best_move;}]
MC/DC0%0/1
$best_move && [@{$best_move;}]
$best_move
Truth table50%1/2
A
A= $best_move
| |||||||||||||||||||||||||||||||||||||||||||
| 304 | ]; | ||||||||||||||||||||||||||||||||||||||||||
| 305 | } | ||||||||||||||||||||||||||||||||||||||||||
| 306 | 699091 | return $best_score; | |||||||||||||||||||||||||||||||||||||||||
| 307 | } | ||||||||||||||||||||||||||||||||||||||||||
| 308 | |||||||||||||||||||||||||||||||||||||||||||
| 309 | 705516 | ▶ | sub _ordered { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_ordered: called CC=13 SCAR=25.6
| |||||||||||||||||||||||||||||||||||||||||||
| 310 | 705516 | my ($self, $state, $moves, $ply, $table_move) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 311 | my $wanted = $table_move | ||||||||||||||||||||||||||||||||||||||||||
| 312 | 705516 | ▶ | ? join('.', @{$table_move->[RM_PATH]}) | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 313 | : ''; | ||||||||||||||||||||||||||||||||||||||||||
| 314 | 705516 | ▶ | my $killers = $state->{killers}[$ply] || []; | ||||||||||||||||||||||||||||||||||||||||
|
Condition100%2/2
$state->{'killers'}[$ply] || []
MC/DC100%1/1
$state->{'killers'}[$ply] || []
$state->{'killers'}[$ply]
Truth table100%2/2
A
A= $state->{'killers'}[$ply]
| |||||||||||||||||||||||||||||||||||||||||||
| 315 | 705516 | my $history = $state->{history}; | |||||||||||||||||||||||||||||||||||||||||
| 316 | |||||||||||||||||||||||||||||||||||||||||||
| 317 | 705516 | my @scored; | |||||||||||||||||||||||||||||||||||||||||
| 318 | 705516 | for my $raw (@{$moves}) { | |||||||||||||||||||||||||||||||||||||||||
| 319 | 2267639 | my $name = $raw->[RM_FROM] . '-' . $raw->[RM_TO]; | |||||||||||||||||||||||||||||||||||||||||
| 320 | 2267639 | my $score = 0; | |||||||||||||||||||||||||||||||||||||||||
| 321 | 2267639 | ▶ | $score += 1_000_000 if $wanted && join('.', @{$raw->[RM_PATH]}) eq $wanted; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$wanted and join(".", @{$raw->[3];}) eq $wanted
MC/DC100%2/2
$wanted and join(".", @{$raw->[3];}) eq $wanted
$wanted
join(".", @{$raw->[3];}) eq $wanted
Truth table100%3/3
A and B
A= $wantedB= join(".", @{$raw->[3];}) eq $wanted
| |||||||||||||||||||||||||||||||||||||||||||
| 322 | 2267639 | ▶ | $score += 1_000 + (10 * scalar @{$raw->[RM_CAPTURES]}) if @{$raw->[RM_CAPTURES]}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 323 | 2267639 | ▶ | $score += 500 if $raw->[RM_PROMOTED]; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 324 | 2267639 | ▶ | $score += 400 if @{$killers} && $killers->[0] eq $name; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
@{$killers;} and $killers->[0] eq $name
MC/DC100%2/2
@{$killers;} and $killers->[0] eq $name
@{$killers;}
$killers->[0] eq $name
Truth table100%3/3
A and B
A= @{$killers;}B= $killers->[0] eq $name
| |||||||||||||||||||||||||||||||||||||||||||
| 325 | 2267639 | ▶ | $score += 300 if @{$killers} > 1 && $killers->[1] eq $name; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
@{$killers;} > 1 and $killers->[1] eq $name
MC/DC100%2/2
@{$killers;} > 1 and $killers->[1] eq $name
@{$killers;} > 1
$killers->[1] eq $name
Truth table100%3/3
A and B
A= @{$killers;} > 1B= $killers->[1] eq $name
| |||||||||||||||||||||||||||||||||||||||||||
| 326 | 2267639 | ▶ | $score += $history->{$name} || 0; | ||||||||||||||||||||||||||||||||||||||||
|
Condition100%2/2
$history->{$name} || 0
MC/DC100%1/1
$history->{$name} || 0
$history->{$name}
Truth table100%2/2
A
A= $history->{$name}
| |||||||||||||||||||||||||||||||||||||||||||
| 327 | 2267639 | push @scored, [$score, $raw]; | |||||||||||||||||||||||||||||||||||||||||
| 328 | } | ||||||||||||||||||||||||||||||||||||||||||
| 329 | 705516 | return [map { $_->[1] } sort { $b->[0] <=> $a->[0] } @scored]; | |||||||||||||||||||||||||||||||||||||||||
| 330 | } | ||||||||||||||||||||||||||||||||||||||||||
| 331 | |||||||||||||||||||||||||||||||||||||||||||
| 332 | 1045 | ▶ | sub _pv { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_pv: called CC=8 SCAR=20.8
| |||||||||||||||||||||||||||||||||||||||||||
| 333 | 1045 | my ($self, $state, $position, $turn, $first) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 334 | 1045 | my @pv; | |||||||||||||||||||||||||||||||||||||||||
| 335 | my @undo; | ||||||||||||||||||||||||||||||||||||||||||
| 336 | |||||||||||||||||||||||||||||||||||||||||||
| 337 | # the root is searched outside the table, so the line starts with the move | ||||||||||||||||||||||||||||||||||||||||||
| 338 | # choose settled on and the table carries it from there | ||||||||||||||||||||||||||||||||||||||||||
| 339 | 1045 | my $raw = $first; | |||||||||||||||||||||||||||||||||||||||||
| 340 | 1045 | ▶ | while (@pv < MAX_PV) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 341 | 6517 | ▶ | unless ($raw) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 342 | 5472 | ▶ | my $entry = $state->{table}{_key($position, $turn)} or last; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 343 | 4427 | ▶ | $raw = $entry->[3] or last; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 344 | } | ||||||||||||||||||||||||||||||||||||||||||
| 345 | 5472 | my $legal = Game::Checkers::Rules::generate($position, $turn); | |||||||||||||||||||||||||||||||||||||||||
| 346 | 5472 | my $path = join '.', @{$raw->[RM_PATH]}; | |||||||||||||||||||||||||||||||||||||||||
| 347 | 5472 | ▶ | last unless grep { join('.', @{$_->[RM_PATH]}) eq $path } @{$legal}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 348 | push @pv, Game::Checkers::Notation::format_move({ | ||||||||||||||||||||||||||||||||||||||||||
| 349 | squares => $raw->[RM_PATH], | ||||||||||||||||||||||||||||||||||||||||||
| 350 | 5472 | jump => scalar @{$raw->[RM_CAPTURES]} | |||||||||||||||||||||||||||||||||||||||||
| 351 | }); | ||||||||||||||||||||||||||||||||||||||||||
| 352 | 5472 | Game::Checkers::Rules::apply($position, $raw); | |||||||||||||||||||||||||||||||||||||||||
| 353 | 5472 | push @undo, $raw; | |||||||||||||||||||||||||||||||||||||||||
| 354 | 5472 | ▶ | $turn = $turn eq 'black' ? 'white' : 'black'; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 355 | 5472 | undef $raw; | |||||||||||||||||||||||||||||||||||||||||
| 356 | } | ||||||||||||||||||||||||||||||||||||||||||
| 357 | 1045 | ▶ | Game::Checkers::Rules::unapply($position, pop @undo) while @undo; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 358 | 1045 | return \@pv; | |||||||||||||||||||||||||||||||||||||||||
| 359 | } | ||||||||||||||||||||||||||||||||||||||||||
| 360 | |||||||||||||||||||||||||||||||||||||||||||
| 361 | 24251 | ▶ | sub _jitter { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_jitter: called CC=2 SCAR=6.9
| |||||||||||||||||||||||||||||||||||||||||||
| 362 | 24251 | my ($seed, $ply, $raw) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 363 | 24251 | my $string = $seed . ':' . $ply . ':' . join '.', @{$raw->[RM_PATH]}; | |||||||||||||||||||||||||||||||||||||||||
| 364 | 24251 | my $hash = 0; | |||||||||||||||||||||||||||||||||||||||||
| 365 | 24251 | $hash = (($hash * 33) + ord) % 65_521 for split //, $string; | |||||||||||||||||||||||||||||||||||||||||
| 366 | 24251 | return $hash % 25; | |||||||||||||||||||||||||||||||||||||||||
| 367 | } | ||||||||||||||||||||||||||||||||||||||||||
| 368 | |||||||||||||||||||||||||||||||||||||||||||
| 369 | 713503 | ▶ | sub _evaluate { | ||||||||||||||||||||||||||||||||||||||||
|
Subroutine
_evaluate: called CC=53 SCAR=39.7
| |||||||||||||||||||||||||||||||||||||||||||
| 370 | 713503 | my ($position, $turn) = @_; | |||||||||||||||||||||||||||||||||||||||||
| 371 | 713503 | my $score = 0; | |||||||||||||||||||||||||||||||||||||||||
| 372 | 713503 | my (%men, %kings, %back, %mobility, @kings, @pieces); | |||||||||||||||||||||||||||||||||||||||||
| 373 | |||||||||||||||||||||||||||||||||||||||||||
| 374 | 713503 | for my $square (1 .. 32) { | |||||||||||||||||||||||||||||||||||||||||
| 375 | 22832096 | ▶ | my $value = $position->[$square] or next; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 376 | 9226775 | ▶ | my $sign = $value > 0 ? 1 : -1; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 377 | 9226775 | ▶ | my $king = abs($value) == 2 ? 1 : 0; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 378 | 9226775 | my $row = $ROW->[$square]; | |||||||||||||||||||||||||||||||||||||||||
| 379 | 9226775 | my $col = $COL->[$square]; | |||||||||||||||||||||||||||||||||||||||||
| 380 | |||||||||||||||||||||||||||||||||||||||||||
| 381 | 9226775 | ▶ | push @{$pieces[$sign > 0 ? 0 : 1]}, $square; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 382 | 9226775 | ▶ | if ($king) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 383 | 1006974 | $kings{$sign}++; | |||||||||||||||||||||||||||||||||||||||||
| 384 | 1006974 | $score += $sign * $WEIGHT{king}; | |||||||||||||||||||||||||||||||||||||||||
| 385 | 1006974 | ▶ | push @{$kings[$sign > 0 ? 0 : 1]}, $square; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 386 | } else { | ||||||||||||||||||||||||||||||||||||||||||
| 387 | 8219801 | $men{$sign}++; | |||||||||||||||||||||||||||||||||||||||||
| 388 | 8219801 | $score += $sign * $WEIGHT{man}; | |||||||||||||||||||||||||||||||||||||||||
| 389 | 8219801 | ▶ | $score += $sign * $WEIGHT{advance} * ($sign > 0 ? $row : 7 - $row); | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 390 | 8219801 | ▶ | $score += $sign * $WEIGHT{edge} if $col == 0 || $col == 7; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$col == 0 or $col == 7
MC/DC100%2/2
$col == 0 or $col == 7
$col == 0
$col == 7
Truth table100%3/3
A or B
A= $col == 0B= $col == 7
| |||||||||||||||||||||||||||||||||||||||||||
| 391 | 8219801 | ▶ | $back{$sign}++ if ($sign > 0 ? $row : 7 - $row) == 0; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||||||||||||||||
| 392 | } | ||||||||||||||||||||||||||||||||||||||||||
| 393 | 9226775 | ▶ | $score += $sign * $WEIGHT{centre} if $col == 3 || $col == 4; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$col == 3 or $col == 4
MC/DC100%2/2
$col == 3 or $col == 4
$col == 3
$col == 4
Truth table100%3/3
A or B
A= $col == 3B= $col == 4
| |||||||||||||||||||||||||||||||||||||||||||
| 394 | |||||||||||||||||||||||||||||||||||||||||||
| 395 | # moves available to this piece, counted without expanding a jump | ||||||||||||||||||||||||||||||||||||||||||
| 396 | # sequence: a cheap stand in for mobility that costs four lookups | ||||||||||||||||||||||||||||||||||||||||||
| 397 | 9226775 | my $moves = 0; | |||||||||||||||||||||||||||||||||||||||||
| 398 | 9226775 | my $base = $square * 4; | |||||||||||||||||||||||||||||||||||||||||
| 399 | 9226775 | ▶ | for my $dir ($king ? @DIRS : @{$FORWARD{$sign}}) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 400 | 20467498 | my $step = $STEP->[$base + $dir]; | |||||||||||||||||||||||||||||||||||||||||
| 401 | 20467498 | ▶ | $moves++ if $step && !$position->[$step]; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$step and not $position->[$step]
MC/DC100%2/2
$step and not $position->[$step]
$step
not $position->[$step]
Truth table100%3/3
A and not(B)
A= $stepB= not $position->[$step]
| |||||||||||||||||||||||||||||||||||||||||||
| 402 | 20467498 | ▶ | my $landing = $JUMP_TO->[$base + $dir] or next; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 403 | 14038561 | ▶ | next if $position->[$landing]; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 404 | 8508710 | ▶ | my $victim = $position->[$JUMP_OVER->[$base + $dir]] or next; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 405 | 2674293 | ▶ | $moves++ if ($victim > 0 ? 1 : -1) != $sign; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||||||||||||||||
| 406 | } | ||||||||||||||||||||||||||||||||||||||||||
| 407 | 9226775 | $mobility{$sign} += $moves; | |||||||||||||||||||||||||||||||||||||||||
| 408 | 9226775 | ▶ | $score += $sign * $WEIGHT{trapped_king} if $king && !$moves; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$king and not $moves
MC/DC100%2/2
$king and not $moves
$king
not $moves
Truth table100%3/3
A and not(B)
A= $kingB= not $moves
| |||||||||||||||||||||||||||||||||||||||||||
| 409 | } | ||||||||||||||||||||||||||||||||||||||||||
| 410 | |||||||||||||||||||||||||||||||||||||||||||
| 411 | # a home row is worth holding only while there is a man that could crown | ||||||||||||||||||||||||||||||||||||||||||
| 412 | 713503 | ▶ | $score += $WEIGHT{back_rank} * ($back{1} || 0) if $men{-1}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%2/2
$back{'1'} || 0
MC/DC100%1/1
$back{'1'} || 0
$back{'1'}
Truth table100%2/2
A
A= $back{'1'}
| |||||||||||||||||||||||||||||||||||||||||||
| 413 | 713503 | ▶ | $score -= $WEIGHT{back_rank} * ($back{-1} || 0) if $men{1}; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%2/2
$back{'-1'} || 0
MC/DC100%1/1
$back{'-1'} || 0
$back{'-1'}
Truth table100%2/2
A
A= $back{'-1'}
| |||||||||||||||||||||||||||||||||||||||||||
| 414 | 713503 | ▶ | $score += $WEIGHT{mobility} * (($mobility{1} || 0) - ($mobility{-1} || 0)); | ||||||||||||||||||||||||||||||||||||||||
|
Condition100%4/4
$mobility{'1'} || 0
$mobility{'-1'} || 0
MC/DC100%1/1
$mobility{'1'} || 0
$mobility{'1'}
MC/DC100%1/1
$mobility{'-1'} || 0
$mobility{'-1'}
Truth table100%2/2
A
A= $mobility{'1'}
Truth table100%2/2
A
A= $mobility{'-1'}
| |||||||||||||||||||||||||||||||||||||||||||
| 415 | |||||||||||||||||||||||||||||||||||||||||||
| 416 | 713503 | ▶ | my $total = ($men{1} || 0) + ($kings{1} || 0) + ($men{-1} || 0) + ($kings{-1} || 0); | ||||||||||||||||||||||||||||||||||||||||
|
Condition100%8/8
$men{'1'} || 0
$kings{'1'} || 0
$men{'-1'} || 0
$kings{'-1'} || 0
MC/DC100%1/1
$men{'1'} || 0
$men{'1'}
MC/DC100%1/1
$kings{'1'} || 0
$kings{'1'}
MC/DC100%1/1
$men{'-1'} || 0
$men{'-1'}
MC/DC100%1/1
$kings{'-1'} || 0
$kings{'-1'}
Truth table100%2/2
A
A= $men{'1'}
Truth table100%2/2
A
A= $kings{'1'}
Truth table100%2/2
A
A= $men{'-1'}
Truth table100%2/2
A
A= $kings{'-1'}
| |||||||||||||||||||||||||||||||||||||||||||
| 417 | 713503 | ▶ | if ($total <= 6 && $total) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
$total <= 6 and $total
MC/DC50%1/2
$total <= 6 and $total
$total <= 6
$total
Truth table66%2/3
A and B
A= $total <= 6B= $total
| |||||||||||||||||||||||||||||||||||||||||||
| 418 | 112995 | ▶ | my $black = ($men{1} || 0) * $WEIGHT{man} + ($kings{1} || 0) * $WEIGHT{king}; | ||||||||||||||||||||||||||||||||||||||||
|
Condition100%4/4
$men{'1'} || 0
$kings{'1'} || 0
MC/DC100%1/1
$men{'1'} || 0
$men{'1'}
MC/DC100%1/1
$kings{'1'} || 0
$kings{'1'}
Truth table100%2/2
A
A= $men{'1'}
Truth table100%2/2
A
A= $kings{'1'}
| |||||||||||||||||||||||||||||||||||||||||||
| 419 | 112995 | ▶ | my $white = ($men{-1} || 0) * $WEIGHT{man} + ($kings{-1} || 0) * $WEIGHT{king}; | ||||||||||||||||||||||||||||||||||||||||
|
Condition100%4/4
$men{'-1'} || 0
$kings{'-1'} || 0
MC/DC100%1/1
$men{'-1'} || 0
$men{'-1'}
MC/DC100%1/1
$kings{'-1'} || 0
$kings{'-1'}
Truth table100%2/2
A
A= $men{'-1'}
Truth table100%2/2
A
A= $kings{'-1'}
| |||||||||||||||||||||||||||||||||||||||||||
| 420 | 112995 | ▶ | my $stronger = $black > $white ? 0 : $white > $black ? 1 : undef; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||||||||||||||||
| 421 | 112995 | ▶ | if (defined $stronger && $kings[$stronger]) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
defined $stronger and $kings[$stronger]
MC/DC100%2/2
defined $stronger and $kings[$stronger]
defined $stronger
$kings[$stronger]
Truth table100%3/3
A and B
A= defined $strongerB= $kings[$stronger]
| |||||||||||||||||||||||||||||||||||||||||||
| 422 | 67010 | my $distance = 0; | |||||||||||||||||||||||||||||||||||||||||
| 423 | 67010 | for my $king (@{$kings[$stronger]}) { | |||||||||||||||||||||||||||||||||||||||||
| 424 | 126449 | ▶ | for my $enemy (@{$pieces[$stronger ? 0 : 1] || []}) { | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition50%1/2
$pieces[$stronger ? 0 : 1] || []
MC/DC0%0/1
$pieces[$stronger ? 0 : 1] || []
$pieces[$stronger ? 0 : 1]
Truth table50%1/2
A
A= $pieces[$stronger ? 0 : 1]
| |||||||||||||||||||||||||||||||||||||||||||
| 425 | 220151 | my $rows = abs($ROW->[$king] - $ROW->[$enemy]); | |||||||||||||||||||||||||||||||||||||||||
| 426 | 220151 | my $cols = abs($COL->[$king] - $COL->[$enemy]); | |||||||||||||||||||||||||||||||||||||||||
| 427 | 220151 | ▶ | $distance += $rows > $cols ? $rows : $cols; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 428 | } | ||||||||||||||||||||||||||||||||||||||||||
| 429 | } | ||||||||||||||||||||||||||||||||||||||||||
| 430 | 67010 | ▶ | $score += ($stronger ? -1 : 1) * $WEIGHT{chase} * $distance; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 431 | } | ||||||||||||||||||||||||||||||||||||||||||
| 432 | } | ||||||||||||||||||||||||||||||||||||||||||
| 433 | |||||||||||||||||||||||||||||||||||||||||||
| 434 | 713503 | ▶ | return $turn eq 'black' ? $score : -$score; | ||||||||||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||||||||||
| 435 | } | ||||||||||||||||||||||||||||||||||||||||||
| 436 | |||||||||||||||||||||||||||||||||||||||||||
| 437 | 15 | 1; | |||||||||||||||||||||||||||||||||||||||||
| 438 | |||||||||||||||||||||||||||||||||||||||||||
| 439 | __END__ | ||||||||||||||||||||||||||||||||||||||||||