Plisco/Engine/Tree.pm

filter: Statementstmt 80.3% 645 / 803 Branchbran 67.6% 288 / 426 Conditioncond 67.2% 117 / 174 MC/DCmcdc 48.5% 49 / 101 Subroutinesub 87.7% 43 / 49 Podpod 0.0% 0 / 15 totaltotal 72.8% 1142 / 1568 CC 286 SCAR 50.0
CC
286
Cov
75%
alphabeta
350.9
tbRootProbe
135.5
quiesce
44.5
CRAP 147.7
↑ Summary Plisco/Tablebase.pm »
1 #! /bin/false
2  
3 # Copyright (C) 2021-2026 Guido Flohr <guido.flohr@cantanea.com>,
4 # all rights reserved.
5  
6 # This program is free software. It comes without any warranty, to
7 # the extent permitted by applicable law. You can redistribute it
8 # and/or modify it under the terms of the Do What the Fuck You Want
9 # to Public License, Version 2, as published by Sam Hocevar. See
10 # http://www.wtfpl.net/ for more details.
11  
12 package Chess::Plisco::Engine::Tree;
13 8 $Chess::Plisco::Engine::Tree::VERSION = 'v1.0.3';
14 8 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
15 8 ▶use integer;
Subroutine BEGIN: called CC=1 SCAR=0.0
16  
17 8 ▶use Locale::TextDomain ('Chess-Plisco');
Subroutine BEGIN: called CC=1 SCAR=0.0
18 8 ▶use List::Util qw(min);
Subroutine BEGIN: called CC=1 SCAR=0.0
19  
20 8 ▶use Chess::Plisco qw(:all);
Subroutine BEGIN: called CC=1 SCAR=0.0
21 # Macros from Chess::Plisco::Macro are already expanded here!
22 8 ▶use Chess::Plisco::Engine::Position qw(CP_POS_REVERSIBLE_CLOCK CP_POS_POPCOUNT);
Subroutine BEGIN: called CC=1 SCAR=0.0
23 8 ▶use Chess::Plisco::Engine::Constants;
Subroutine BEGIN: called CC=1 SCAR=0.0
24  
25 8 ▶use Time::HiRes qw(tv_interval ualarm gettimeofday);
Subroutine BEGIN: called CC=1 SCAR=0.0
26  
27 8 ▶use constant DEBUG => $ENV{DEBUG_PLISCO_TREE};
Subroutine BEGIN: called CC=1 SCAR=0.0
28  
29 8 ▶use constant CP_POS_SIGNATURE => Chess::Plisco::Engine::Position::CP_POS_SIGNATURE();
Subroutine BEGIN: called CC=1 SCAR=0.0
30 8 ▶use constant CP_POS_REVERSIBLE_CLOCK => Chess::Plisco::Engine::Position::CP_POS_REVERSIBLE_CLOCK();
Subroutine BEGIN: called CC=1 SCAR=0.0
31  
32 8 ▶use Chess::Plisco::Engine::TranspositionTable;
Subroutine BEGIN: called CC=1 SCAR=0.0
33  
34 # These values get stored in the upper 32 bits of a moves so that they are
35 # searched first.
36 8 ▶use constant MOVE_ORDERING_PV => 1 << 62;
Subroutine BEGIN: called CC=1 SCAR=0.0
37 8 ▶use constant MOVE_ORDERING_TT => 1 << 61;
Subroutine BEGIN: called CC=1 SCAR=0.0
38  
39 8 ▶use constant SAFETY_MARGIN => 300;
Subroutine BEGIN: called CC=1 SCAR=0.0
40 8 ▶use constant UALARM_INTERVAL => 500 * SAFETY_MARGIN;
Subroutine BEGIN: called CC=1 SCAR=0.0
41  
42 8 ▶use constant WDL_LOSS => -2;
Subroutine BEGIN: called CC=1 SCAR=0.0
43 8 ▶use constant WDL_BLESSED_LOSS => -1;
Subroutine BEGIN: called CC=1 SCAR=0.0
44 8 ▶use constant WDL_DRAW => 0;
Subroutine BEGIN: called CC=1 SCAR=0.0
45 8 ▶use constant WDL_CURSED_WIN => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
46 8 ▶use constant WDL_WIN => 2;
Subroutine BEGIN: called CC=1 SCAR=0.0
47  
48 # For all combinations of promotion piece and captured piece, calculate a
49 # value suitable for sorting. We choose the raw material balance minus the
50 # piece that moves. That way, captures that the queen makes are less
51 # "attractive" than captures that the rook makes.
52 8 my @move_values = (0) x 369;
53  
54  
55 # MVV-LVA values. Looked up via the captured and moving piece ($move & 0x3f).
56 8 my @mvv_lva;
57  
58 # Usually only queen promotions and sometimes promotions to a knight are
59 # interesting. This mask is used to filter them out.
60 8 ▶use constant GOOD_PROMO_MASK => (1 << (CP_QUEEN)) | (1 << (CP_KNIGHT));
Subroutine BEGIN: called CC=1 SCAR=0.0
61  
62 8 my ($self_tb_cardinality, $self_tb_probe_depth);
63  
64 355 ▶sub new {
Subroutine new: called CC=3 SCAR=11.0
Pod undocumented
65 355 my ($class, %options) = @_;
66  
67 355 my $position = $options{position};
68 355 my $signatures = $options{signatures};
69  
70 # Make sure that the reversible clock does not look beyond the known
71 # positions. This will simplify the detection of a draw by repetition.
72 355 ▶ if ($position->[CP_POS_REVERSIBLE_CLOCK] >= @$signatures) {
Branch: 1 branch
BranchTrueFalseTotal
if ($position->[15] >= @$signatures) 8 347 355
73 8 $position->[CP_POS_REVERSIBLE_CLOCK] = @$signatures - 1;
74 }
75  
76 8 ▶ no integer;
Subroutine BEGIN: called CC=1 SCAR=0.0
77  
78 355 my @killers = map { [] } 0 .. MAX_PLY - 1;
79 my $self = {
80 position => $position,
81 signatures => $signatures,
82 history_length => -1 + scalar @$signatures,
83 tt => $options{tt},
84 watcher => $options{watcher},
85 0 ▶ info => $options{info} || sub {},
Subroutine __ANON__: not called CC=1 SCAR=0.0
86 book => $options{book},
87 book_depth => $options{book_depth},
88 killers => \@killers,
89 cutoff_moves => [[], []], # History heuristic, one slot for each side.
90 average_score => -INF,
91 previous_average_score => INF,
92 iter_scores => [],
93 previous_time_reduction => 0.85,
94 root_moves => {},
95 total_best_move_changes => 0,
96 tb => $options{tb},
97 tb_cardinality => $options{tb_cardinality},
98 tb_probe_depth => $options{tb_probe_depth},
99 tb_probe_limit => $options{tb_probe_limit},
100 tb_50_move_rule => $options{tb_50_move_rule},
101 tb_7 => $options{tb_7},
102 tb_3 => $options{tb_3},
103 355 ▶ tb_hits => 0,
Condition33%1/3
$options{'info'} || sub { }
l!l&&r!l&&!r
35500
MC/DC0%0/2
$options{'info'} || sub { }
$options{'info'} sub { }
Truth table33%1/3
A || B
A= $options{'info'}B= sub { }
ABresult
1X1
011
000
104 tb_root_hit => 0,
105 };
106  
107 355 $self_tb_cardinality = $options{tb_cardinality};
108 355 $self_tb_probe_depth = $options{tb_probe_depth};
109  
110 355 bless $self, $class;
111 }
112  
113 2752455 ▶sub checkTime {
Subroutine checkTime: called CC=12 SCAR=27.0
Pod undocumented
114 2752455 my ($self) = @_;
115  
116 8 ▶ no integer;
Subroutine BEGIN: called CC=1 SCAR=0.0
117  
118 # Remember whether we are currently pondering. If a "ponderhit" was
119 # returned, the engine object will reset the ponder flag and also reset
120 # the start time to now. If that happens, we should skip this
121 # recalibration of the nodes to the next time control because the ETA will
122 # be zero or close to 0.
123 2752455 my $was_ponder = $self->{ponder};
124  
125 # It is important to check for input before checking the time control. If
126 # another "go" command has been received, the engine object will request
127 # us to stop immediately. When this search terminates, the engine will
128 # immediately resume with the next search.
129 2752455 $self->{watcher}->check($self);
130 2752455 ▶ if ($self->{stop_requested}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"stop_requested"}) 0 2752455 2752455
131 0 die "PLISCO_ABORTED\n";
132 }
133  
134 2752455 my $elapsed = 1000 * tv_interval($self->{start_time});
135  
136 # Taken from Stockfish: Start printing the current move after 0.5 s.
137 # Otherwise the output is getting messy in the beginning. Stockfish is
138 # using 3 s but we are slower.
139 2752455 ▶ if ($elapsed > 500) {
Branch: 1 branch
BranchTrueFalseTotal
if ($elapsed > 500) 2752446 9 2752455
140 2752446 $self->{print_current_move} = 1;
141 }
142  
143 2752455 my $nodes = $self->{nodes};
144  
145 # FIXME! It is probably better to look at the current nps, not the
146 # overall nps.
147 2752455 ▶ my $nps = $elapsed ? (1000 * $nodes / $elapsed) : 10000;
Branch: 1 branch
BranchTrueFalseTotal
$elapsed ? : 2752455 0 2752455
148  
149 2752455 my $max_nodes_to_tc = $nps >> 2;
150  
151 2752455 ▶ if ($self->{ponder}) {
Branch: 3 branches
BranchTrueFalseTotal
if ($self->{'ponder'}) { } 0 2752455 2752455
elsif ($self->{'max_depth'}) { } 2752449 6 2752455
elsif ($self->{'max_nodes'}) { } 0 6 6
152 # We have to be quick enough to stop. On the other hand, pondering
153 # is not effective, if we invoke the time control function too often.
154 0 $self->{nodes_to_tc} = $nodes + $nps >> 4;
155 } elsif ($self->{max_depth}) {
156 2752449 $self->{nodes_to_tc} = $nodes + $max_nodes_to_tc;
157 } elsif ($self->{max_nodes}) {
158 0 ▶ if ($nodes + $max_nodes_to_tc < $self->{max_nodes}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($nodes + $max_nodes_to_tc < $self->{'max_nodes'}) { } 0 0 0
159 0 $self->{nodes_to_tc} = $nodes + $max_nodes_to_tc;
160 } else {
161 0 $self->{nodes_to_tc} = $self->{max_nodes};
162 }
163 } else {
164 8 ▶ use integer;
Subroutine BEGIN: called CC=1 SCAR=0.0
165  
166 6 my $allocated = $self->{maximum};
167 6 my $eta = $allocated - $elapsed;
168 6 ▶ if ($eta < SAFETY_MARGIN) {
Branch: 1 branch
BranchTrueFalseTotal
if ($eta < 300) 1 5 6
169 1 die "PLISCO_ABORTED\n";
170 }
171  
172 # How many nodes should we check until the next time control?
173 # We want to roughly do at least 4 time checks per second to keep the
174 # application responsive.
175 5 my $max_nodes = $nps >> 2;
176  
177 # Re-calibrate the number of nodes to the next time control.
178 #
179 # But do not do this when the uci engine object has just received
180 # a "ponderhit" command. It has then reset our start time to the
181 # current time and has removed the ponder flag. That is why we have
182 # remembered it at the start of this routine.
183 #
184 # If we have less than about one second left, we gradually reduce
185 # the batch size so that we do not overuse the allocated time.
186 #
187 # We can expect to process $eta * $nps / 1000 nodes in the remaining
188 # time. In order to play safe, should the performance suddenly drop,
189 # we divide that number by 8. A division by 1000 is roughly a
190 # right shift of 10, a division by 4 a right-shift by 2. We can
191 # therefore just right-shift the product by 13.
192 5 ▶ if (!($was_ponder && !$self->{ponder})) {
Branch: 1 branch
BranchTrueFalseTotal
if (not $was_ponder && !$self->{"ponder"}) 5 0 5
Condition33%1/3
$was_ponder && !$self->{'ponder'}
!ll&&!rl&&r
500
MC/DC0%0/2
$was_ponder && !$self->{'ponder'}
$was_ponder !$self->{'ponder'}
Truth table33%1/3
A && not(B)
A= $was_ponderB= !$self->{'ponder'}
ABresult
0X0
100
111
193 5 my $dyn_nodes = ($eta * $nps) >> 13;
194  
195 5 ▶ my $nodes_to_go = ($max_nodes < $dyn_nodes) ? $max_nodes : $dyn_nodes;
Branch: 1 branch
BranchTrueFalseTotal
$max_nodes < $dyn_nodes ? : 0 5 5
196 5 $self->{nodes_to_tc} = $nodes + $nodes_to_go;
197 }
198 }
199 }
200  
201 0 ▶sub debug {
Subroutine debug: not called CC=1 SCAR=6.9
Pod undocumented
202 0 my ($self, $msg) = @_;
203  
204 0 chomp $msg;
205 0 print STDERR "DEBUG $msg\n";
206  
207 0 return 1;
208 }
209  
210 0 ▶sub indent {
Subroutine indent: not called CC=1 SCAR=6.9
Pod undocumented
211 0 my ($self, $ply, $msg) = @_;
212  
213 0 chomp $msg;
214 0 my $indent = '..' x ($ply - 1);
215 0 $self->debug("[$ply/$self->{depth}] $indent$msg");
216 }
217  
218 2008 ▶sub printPV {
Subroutine printPV: called CC=15 SCAR=29.1
Pod undocumented
219 2008 my ($self, $pline) = @_;
220  
221 8 ▶ no integer;
Subroutine BEGIN: called CC=1 SCAR=0.0
222 2008 my $position = $self->{start};
223 2008 ▶ my $score = $self->{score} // 0;
Condition100%2/2
$self->{"score"} // 0
l!l
20062
MC/DC100%1/1
$self->{"score"} // 0
$self->{"score"}
Truth table100%2/2
A
A= $self->{"score"}
Aresult
11
00
224 2008 my $mate_in;
225 2008 ▶ if ($score >= MATE - MAX_PLY) {
Branch: 2 branches
BranchTrueFalseTotal
if ($score >= 31754) { } 971 1037 2008
elsif ($score <= -31754) { } 0 1037 1037
226 8 ▶ use integer;
Subroutine BEGIN: called CC=1 SCAR=0.0
227 971 $mate_in = (MATE - $score) >> 1;
228 } elsif ($score <= (-MATE + MAX_PLY)) {
229 8 ▶ use integer;
Subroutine BEGIN: called CC=1 SCAR=0.0
230 0 $mate_in = -((-(-MATE - $score)) >> 1);
231 }
232  
233 2008 ▶ my $nodes = $self->{nodes} // 1;
Condition100%2/2
$self->{"nodes"} // 1
l!l
20062
MC/DC100%1/1
$self->{"nodes"} // 1
$self->{"nodes"}
Truth table100%2/2
A
A= $self->{"nodes"}
Aresult
11
00
234 2008 my $elapsed = tv_interval($self->{start_time});
235 2008 ▶ my $nps = $elapsed ? (int(0.5 + $nodes / $elapsed)) : 0;
Branch: 1 branch
BranchTrueFalseTotal
$elapsed ? : 2008 0 2008
236 2008 ▶ if ($self->{tb_root_hit} && !$mate_in) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"tb_root_hit"} and not $mate_in) 0 2008 2008
Condition33%1/3
$self->{"tb_root_hit"} and not $mate_in
!ll&&!rl&&r
200800
MC/DC0%0/2
$self->{"tb_root_hit"} and not $mate_in
$self->{"tb_root_hit"} not $mate_in
Truth table33%1/3
A and not(B)
A= $self->{"tb_root_hit"}B= not $mate_in
ABresult
0X0
100
111
237 0 $score = $self->{tb_outcome};
238 }
239 2008 ▶ my $scorestr = $mate_in ? "mate $mate_in" : "cp $score";
Branch: 1 branch
BranchTrueFalseTotal
$mate_in ? : 971 1037 2008
240 2008 my $pv = join ' ', $position->movesCoordinateNotation(@$pline);
241 2008 my $time = int(0.5 + (1000 * $elapsed));
242 2008 ▶ my $hashfull = $self->{tt}->hashfull // 0;
Condition50%1/2
$self->{"tt"}->hashfull // 0
l!l
20080
MC/DC0%0/1
$self->{"tt"}->hashfull // 0
$self->{"tt"}->hashfull
Truth table50%1/2
A
A= $self->{"tt"}->hashfull
Aresult
11
00
243 2008 ▶ my $depth = $self->{depth} // 1;
Condition50%1/2
$self->{"depth"} // 1
l!l
20080
MC/DC0%0/1
$self->{"depth"} // 1
$self->{"depth"}
Truth table50%1/2
A
A= $self->{"depth"}
Aresult
11
00
244 2008 ▶ my $seldepth = $self->{seldepth} // $depth;
Condition66%2/3
$self->{"seldepth"} // $depth
l!l&&r!l&&!r
200620
MC/DC0%0/2
$self->{"seldepth"} // $depth
$self->{"seldepth"} $depth
Truth table66%2/3
A // B
A= $self->{"seldepth"}B= $depth
ABresult
1X1
011
000
245 2008 ▶ my $tbhits = $self->{tb_hits} // 0;
Condition50%1/2
$self->{"tb_hits"} // 0
l!l
20080
MC/DC0%0/1
$self->{"tb_hits"} // 0
$self->{"tb_hits"}
Truth table50%1/2
A
A= $self->{"tb_hits"}
Aresult
11
00
246 2008 $self->{info}->("depth $depth seldepth $seldepth"
247 . " score $scorestr nodes $nodes nps $nps hashfull $hashfull"
248 . " tbhits $self->{tb_hits} time $time pv $pv");
249 2008 ▶ if ($self->{__debug}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"__debug"}) 0 2008 2008
250 0 ▶ $self->{info}->("tt_hits $self->{tt_hits}") if $self->{__debug};
Branch: 1 branch
BranchTrueFalseTotal
if $self->{"__debug"} 0 0 0
251 }
252 }
253  
254 # Make them invokable without a method call.
255 sub quiesce;
256  
257  
258  
259 1153191 ▶sub alphabeta {
Subroutine alphabeta: called CC=116 SCAR=58.6
Pod undocumented
260 1153191 my ($self, $ply, $depth, $alpha, $beta, $pline, $node_type, $cut_node,
261 $tt_pvs, $min_probe_ply) = @_;
262  
263 1153191 ▶ if ($self->{nodes} >= $self->{nodes_to_tc}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"nodes"} >= $self->{"nodes_to_tc"}) 1151020 2171 1153191
264 1151020 $self->checkTime;
265 }
266  
267 1153190 my $pv_node = $node_type != NON_PV_NODE;
268  
269 1153190 ▶ if ($depth <= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($depth <= 0) 784075 369115 1153190
270 784075 ▶ return quiesce($self, $ply, $alpha, $beta, $pv_node ? PV_NODE : NON_PV_NODE, $min_probe_ply);
Branch: 1 branch
BranchTrueFalseTotal
$pv_node ? : 33787 750288 784075
271 }
272  
273 369115 ▶ $depth = ((($depth) < (MAX_PLY - 1)) ? ($depth) : (MAX_PLY - 1));
Branch: 1 branch
BranchTrueFalseTotal
$depth < 245 ? : 369115 0 369115
274  
275 369115 my $root_node = $node_type == ROOT_NODE;
276 369115 ▶ my $all_node = !($pv_node || $cut_node);
Condition100%3/3
$pv_node || $cut_node
l!l&&r!l&&!r
2611730387439124
MC/DC100%2/2
$pv_node || $cut_node
$pv_node $cut_node
Truth table100%3/3
A || B
A= $pv_nodeB= $cut_node
ABresult
1X1
011
000
277  
278 369115 my $position = $self->{position};
279  
280 369115 if (DEBUG) {
281 my $hex_signature = sprintf '%016x', $position->[CP_POS_SIGNATURE];
282 my $line = join ' ', @{$self->{line}};
283 my $fen = $position->toFEN;
284 my $node_type_name = NODE_TYPES->[$node_type];
285 $self->indent($ply, "alphabeta<$node_type_name>: alpha = $alpha, beta = $beta, line: $line,"
286 . " depth: $depth, sig: $hex_signature $fen");
287 }
288  
289 369115 ▶ if ($position->[CP_POS_HALFMOVE_CLOCK] >= 100) {
Branch: 1 branch
BranchTrueFalseTotal
if ($position->[11] >= 100) 0 369115 369115
290 0 if (DEBUG) {
291 $self->indent($ply, "draw detected");
292 }
293 0 return DRAW;
294 }
295  
296 # Check draw by repetition. FIXME! Try to find near repetitions with
297 # cuckoo tables.
298 #
299 # We know that the reversible clock is never pointing beyond the known
300 # positions/signatures because that gets adjusted in the constructor.
301 369115 my $signatures = $self->{signatures};
302 369115 my $signature = $position->[CP_POS_SIGNATURE];
303 369115 ▶ if ($ply > 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($ply > 1) 368388 727 369115
304 368388 my $rc = $position->[CP_POS_REVERSIBLE_CLOCK];
305 368388 my $history_length = $self->{history_length};
306 368388 my $signature_slot = $history_length + $ply;
307 368388 my $max_back = $signature_slot - $rc - 1;
308 368388 ▶ for (my $n = $signature_slot - 5; $n >= $max_back; $n -= 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n >= $max_back) 373 368384 368757
309 373 ▶ if ($signatures->[$n] == $signature) {
Branch: 1 branch
BranchTrueFalseTotal
if ($signatures->[$n] == $signature) 4 369 373
310 4 if (DEBUG) {
311 $self->indent($ply, "3-fold repetition");
312 }
313 4 return DRAW;
314 }
315 }
316 }
317  
318 # Transposition table lookup.
319 369111 my $tt = $self->{tt};
320 369111 if (DEBUG) {
321 my $hex_sig = sprintf '%016x', $signature;
322 $self->indent($ply, "TT probe $hex_sig \@depth $depth, alpha = $alpha, beta = $beta");
323 }
324 369111 my ($tt_hit, $tt_depth, $tt_bound, $tt_move, $tt_value, $tt_eval,
325 $tt_pv, @tt_address) = $tt->probe($signature);
326  
327 369111 ▶ $tt_move = 0 if ($root_node || !$tt_hit);
Branch: 1 branch
BranchTrueFalseTotal
if $root_node or not $tt_hit 294520 74591 369111
Condition100%3/3
$root_node or not $tt_hit
l!l&&r!l&&!r
72729379374591
MC/DC100%2/2
$root_node or not $tt_hit
$root_node not $tt_hit
Truth table100%3/3
A or not(B)
A= $root_nodeB= not $tt_hit
ABresult
1X1
011
000
328 0 ▶ $tt_value = (do { if ($tt_value >= VALUE_TB_WIN_IN_MAX_PLY) { if ($tt_value >= MATE_IN_MAX_PLY && MATE - $tt_value > 100 - $position->[CP_POS_HALFMOVE_CLOCK]) { VALUE_TB_WIN_IN_MAX_PLY - 1 } elsif (VALUE_TB_WIN_IN_MAX_PLY - $tt_value > 100 - $position->[CP_POS_HALFMOVE_CLOCK]) { VALUE_TB_WIN_IN_MAX_PLY - 1 } else { $tt_value - $ply; } } elsif ($tt_value <= VALUE_TB_LOSS_IN_MAX_PLY) { if ($tt_value <= MATED_IN_MAX_PLY && MATE + $tt_value > 100 - $position->[CP_POS_HALFMOVE_CLOCK]) { VALUE_TB_LOSS_IN_MAX_PLY + 1; } elsif (VALUE_TB_LOSS_IN_MAX_PLY + $tt_value > 100 - $position->[CP_POS_HALFMOVE_CLOCK]) { VALUE_TB_LOSS_IN_MAX_PLY + 1; } else { $tt_value + $ply; } } else { $tt_value; }})
Branch: 7 branches
BranchTrueFalseTotal
if $tt_hit and defined $tt_value 74972 294139 369111
if ($tt_value >= 31507) { } 4992 69980 74972
elsif ($tt_value <= -31507) { } 3118 66862 69980
if ($tt_value >= 31754 and 32000 - $tt_value > 100 - $position->[11]) { } 0 4992 4992
elsif (31507 - $tt_value > 100 - $position->[11]) { } 0 4992 4992
if ($tt_value <= -31754 and 32000 + $tt_value > 100 - $position->[11]) { } 0 3118 3118
elsif (-31507 + $tt_value > 100 - $position->[11]) { } 0 3118 3118
Condition44%4/9
$tt_hit and defined $tt_value
!ll&&!rl&&r
294139074972
$tt_value >= 31754 and 32000 - $tt_value > 100 - $position->[11]
!ll&&!rl&&r
049920
$tt_value <= -31754 and 32000 + $tt_value > 100 - $position->[11]
!ll&&!rl&&r
031180
MC/DC50%1/2
$tt_hit and defined $tt_value
$tt_hit defined $tt_value
MC/DC0%0/2
$tt_value >= 31754 and 32000 - $tt_value > 100 - $position->[11]
$tt_value >= 31754 32000 - $tt_value > 100 - $position->[11]
MC/DC0%0/2
$tt_value <= -31754 and 32000 + $tt_value > 100 - $position->[11]
$tt_value <= -31754 32000 + $tt_value > 100 - $position->[11]
Truth table66%2/3
A and B
A= $tt_hitB= defined $tt_value
ABresult
0X0
100
111
Truth table33%1/3
A and B
A= $tt_value >= 31754B= 32000 - $tt_value > 100 - $position->[11]
ABresult
0X0
100
111
Truth table33%1/3
A and B
A= $tt_value <= -31754B= 32000 + $tt_value > 100 - $position->[11]
ABresult
0X0
100
111
329 if $tt_hit && defined $tt_value;
330 369111 ▶ $tt_pvs->[$ply] = $pv_node || ($tt_hit && $tt_pv);
Condition100%6/6
$pv_node || $tt_hit && $tt_pv
l!l&&r!l&&!r
261152093340903
$tt_hit and $tt_pv
!ll&&!rl&&r
276591643122093
MC/DC100%3/3
$pv_node || $tt_hit && $tt_pv
$pv_node $tt_hit $tt_pv
Truth table100%4/4
A || B and C
A= $pv_nodeB= $tt_hitC= $tt_pv
ABCresult
1XX1
0111
00X0
0100
331 369111 ▶ my $pv_hit = $tt_hit && $tt_pv;
Condition100%3/3
$tt_hit && $tt_pv
!ll&&!rl&&r
294139677607212
MC/DC100%2/2
$tt_hit && $tt_pv
$tt_hit $tt_pv
Truth table100%3/3
A && B
A= $tt_hitB= $tt_pv
ABresult
0X0
100
111
332  
333 369111 ▶ if ($tt_hit && defined $tt_value && $tt_depth >= $depth) {
Branch: 1 branch
BranchTrueFalseTotal
if ($tt_hit and defined $tt_value and $tt_depth >= $depth) 45624 323487 369111
Condition83%5/6
$tt_hit and defined $tt_value and $tt_depth >= $depth
!ll&&!rl&&r
2941392934845624
$tt_hit and defined $tt_value
!ll&&!rl&&r
294139074972
MC/DC66%2/3
$tt_hit and defined $tt_value and $tt_depth >= $depth
$tt_hit defined $tt_value $tt_depth >= $depth
Truth table75%3/4
A and B and C
A= $tt_hitB= defined $tt_valueC= $tt_depth >= $depth
ABCresult
0XX0
10X0
1100
1111
334 # FIXME! Actually, there is no need for a TT move.
335 45624 ▶ if ($tt_move
Branch: 1 branch
BranchTrueFalseTotal
if ($tt_move and $tt_bound == 3 || $tt_bound == 2 && $tt_value >= $beta || $tt_bound == 1 && $tt_value <= $alpha) 35977 9647 45624
Condition100%15/15
$tt_move and $tt_bound == 3 || $tt_bound == 2 && $tt_value >= $beta || $tt_bound == 1 && $tt_value <= $alpha
!ll&&!rl&&r
7886176135977
$tt_bound == 3 or $tt_bound == 2 and $tt_value >= $beta or $tt_bound == 1 and $tt_value <= $alpha
l!l&&r!l&&!r
35912651761
$tt_bound == 3 or $tt_bound == 2 and $tt_value >= $beta
l!l&&r!l&&!r
467354451826
$tt_bound == 2 and $tt_value >= $beta
!ll&&!rl&&r
398142835445
$tt_bound == 1 and $tt_value <= $alpha
!ll&&!rl&&r
142833365
MC/DC83%5/6
$tt_move and $tt_bound == 3 || $tt_bound == 2 && $tt_value >= $beta || $tt_bound == 1 && $tt_value <= $alpha
$tt_move $tt_bound == 3 $tt_bound == 2 $tt_value >= $beta $tt_bound == 1 $tt_value <= $alpha
Truth table66%6/9
A and B or C and D or E and F
A= $tt_moveB= $tt_bound == 3C= $tt_bound == 2D= $tt_value >= $betaE= $tt_bound == 1F= $tt_value <= $alpha
ABCDEFresult
0XXXXX0
100X0X0
100X100
10100X0
1010100
11XXXX1
1011XX1
100X111
1010111
336 && ($tt_bound == BOUND_EXACT
337 || ($tt_bound == BOUND_LOWER && $tt_value >= $beta)
338 || ($tt_bound == BOUND_UPPER && $tt_value <= $alpha))) {
339 35977 ++$self->{tt_hits};
340 35977 ▶ if ($ply == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($ply == 1) 0 35977 35977
341 0 @$pline = ($tt_move);
342 0 $self->{score} = $tt_value;
343 }
344  
345 35977 if (DEBUG) {
346 my $hex_sig = sprintf '%016x', $signature;
347 my $cn = $position->moveCoordinateNotation($tt_move);
348 my $type = BOUND_TYPES->[$tt_bound];
349 my $is_pv_hit = $pv_hit ? 'true' : 'false';
350 $self->indent($ply, "TT hit for $hex_sig, value $tt_value ($type), TT depth $tt_depth, PV hit: $is_pv_hit, best move $cn");
351 }
352  
353 35977 return $tt_value;
354 }
355 }
356  
357 # Probe endgame tablebase.
358 333134 my $best_value = -INF;
359 333134 ▶ if ($ply >= $min_probe_ply) {
Branch: 1 branch
BranchTrueFalseTotal
if ($ply >= $min_probe_ply) 0 333134 333134
360 0 my $pieces_count = $position->[CP_POS_POPCOUNT];
361 0 ▶ if ($min_probe_ply > 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($min_probe_ply > 1) 0 0 0
362 0 ▶ if ($pieces_count <= $self_tb_cardinality) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pieces_count <= $self_tb_cardinality) { } 0 0 0
363 0 $min_probe_ply = 1;
364 } else {
365 0 $min_probe_ply = $ply + $pieces_count - $self_tb_cardinality;
366 0 goto TB_PROBE_DONE;
367 }
368 }
369  
370 0 ▶ if ($position->[CP_POS_HALFMOVE_CLOCK] == 0
Branch: 1 branch
BranchTrueFalseTotal
if ($position->[11] == 0 and not $position->[20] and $pieces_count < $self_tb_cardinality || $depth >= $self_tb_probe_depth) 0 0 0
Condition0%0/9
$position->[11] == 0 and not $position->[20] and $pieces_count < $self_tb_cardinality || $depth >= $self_tb_probe_depth
!ll&&!rl&&r
000
$position->[11] == 0 and not $position->[20]
!ll&&!rl&&r
000
$pieces_count < $self_tb_cardinality or $depth >= $self_tb_probe_depth
l!l&&r!l&&!r
000
MC/DC0%0/4
$position->[11] == 0 and not $position->[20] and $pieces_count < $self_tb_cardinality || $depth >= $self_tb_probe_depth
$position->[11] == 0 not $position->[20] $pieces_count < $self_tb_cardinality $depth >= $self_tb_probe_depth
Truth table0%0/5
A and not(B) and C or D
A= $position->[11] == 0B= not $position->[20]C= $pieces_count < $self_tb_cardinalityD= $depth >= $self_tb_probe_depth
ABCDresult
0XXX0
10XX0
11000
111X1
11011
371 && !$position->[CP_POS_CASTLING_RIGHTS]
372 && ($pieces_count < $self_tb_cardinality
373 || $depth >= $self_tb_probe_depth)) {
374 0 my $tb = $self->{tb};
375 0 my $wdl;
376
377 0 eval {
378 0 ▶ local $SIG{ALRM} = sub { $self->checkTime };
Subroutine __ANON__: not called CC=1 SCAR=6.9
379  
380 0 ualarm UALARM_INTERVAL, UALARM_INTERVAL;
381 0 $wdl = $tb->safeProbeWdl($position);
382 0 ualarm 0;
383 };
384 0 ▶ if ($@) {
Branch: 1 branch
BranchTrueFalseTotal
if ($@) 0 0 0
385 # Time used up. Disable all tablebase lookups, and go on with
386 # a regular search.
387 0 $self_tb_cardinality = 0;
388 0 ualarm 0;
389 }
390  
391 0 ▶ if (defined $wdl) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $wdl) 0 0 0
392 0 if (DEBUG) {
393 $self->indent($ply, "tablebase hit, WDL: $wdl\n");
394 }
395  
396 0 ++$self->{tb_hits};
397  
398 0 ▶ my $draw_score = $self->{tb_50_move_rule} ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
$self->{'tb_50_move_rule'} ? : 0 0 0
399 0 my $tb_value = VALUE_TB - $ply;
400  
401 0 my ($value, $tt_type);
402 0 ▶ if ($wdl < -$draw_score) {
Branch: 2 branches
BranchTrueFalseTotal
if ($wdl < -$draw_score) { } 0 0 0
elsif ($wdl > $draw_score) { } 0 0 0
403 0 $value = -$tb_value;
404 0 $tt_type = BOUND_UPPER;
405 } elsif ($wdl > $draw_score) {
406 0 $value = $tb_value;
407 0 $tt_type = BOUND_LOWER;
408 } else {
409 0 $value = DRAW + 2 * $wdl * $draw_score;
410 0 $tt_type = BOUND_EXACT;
411 }
412  
413 0 ▶ if ($tt_type == BOUND_EXACT
Branch: 2 branches
BranchTrueFalseTotal
if ($tt_type == 3 or $tt_type == 2 ? $value >= $beta : $value <= $alpha) 0 0 0
$tt_type == 2 ? : 0 0 0
Condition0%0/3
$tt_type == 3 or $tt_type == 2 ? $value >= $beta : $value <= $alpha
l!l&&r!l&&!r
000
MC/DC0%0/2
$tt_type == 3 or $tt_type == 2 ? $value >= $beta : $value <= $alpha
$tt_type == 3 $tt_type == 2 ? $value >= $beta : $value <= $alpha
Truth table0%0/3
A or B
A= $tt_type == 3B= $tt_type == 2 ? $value >= $beta : $value <= $alpha
ABresult
1X1
011
000
414 || ($tt_type == BOUND_LOWER ? $value >= $beta : $value <= $alpha)) {
415 0 if (DEBUG) {
416 my $tt_type_name = BOUND_TYPES->[$tt_type];
417 my $tt_value = (do { (($value >= VALUE_TB_WIN_IN_MAX_PLY) ? $value + $ply : ($value <= VALUE_TB_LOSS_IN_MAX_PLY) ? $value - $ply : $value);});
418 $self->indent($ply, "store value $ply \@depth $depth with bound type $tt_type_name");
419 }
420 $tt->store(
421 @tt_address, # Address.
422 $signature, # Zobrist key.
423 0 ▶ (do { (($value >= VALUE_TB_WIN_IN_MAX_PLY) ? $value + $ply : ($value <= VALUE_TB_LOSS_IN_MAX_PLY) ? $value - $ply : $value);}), # score, mate distance adjusted.
Branch: 2 branches
BranchTrueFalseTotal
$value >= 31507 ? : 0 0 0
$value <= -31507 ? : 0 0 0
424 $tt_pvs->[-1], # PV flag.
425 $tt_type, # BOUND_EXACT/TT_SCORE_ALPHA/TT_SCORE_LOWER.
426 $depth, # Depth searched.
427 0, # Best move at this node.
428 );
429  
430 0 return $value;
431 }
432  
433 0 ▶ if ($pv_node && $tt_type == BOUND_LOWER) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pv_node and $tt_type == 2) 0 0 0
Condition0%0/3
$pv_node and $tt_type == 2
!ll&&!rl&&r
000
MC/DC0%0/2
$pv_node and $tt_type == 2
$pv_node $tt_type == 2
Truth table0%0/3
A and B
A= $pv_nodeB= $tt_type == 2
ABresult
0X0
100
111
434 0 $best_value = $value;
435 0 if (DEBUG && $best_value > $alpha) {
436 $self->indent($ply, "raise alpha to tablebase value $best_value");
437 }
438 0 ▶ $alpha = ((($alpha) > ($best_value)) ? ($alpha) : ($best_value));
Branch: 1 branch
BranchTrueFalseTotal
$alpha > $best_value ? : 0 0 0
439 }
440 }
441 }
442 }
443 TB_PROBE_DONE:
444  
445 333134 my @moves;
446 333134 my $pv_move;
447 333134 my $cutoff_moves = $self->{cutoff_moves}->[$position->[CP_POS_TO_MOVE]];
448 333134 ▶ if ($root_node) {
Branch: 2 branches
BranchTrueFalseTotal
if ($root_node) { } 727 332407 333134
elsif ($depth >= 5) { } 0 332407 332407
449 727 @moves = @{$self->{ordered_root_moves}};
450 727 $pv_move = $moves[0];
451 } elsif ($depth >= 5) {
452 # Use the same move ordering as for root moves.
453 0 ▶ $pv_move = $pline->[$ply - 1] if @$pline >= $ply;
Branch: 1 branch
BranchTrueFalseTotal
if @$pline >= $ply 0 0 0
454 0 @moves = $self->orderRootMoves($position, $depth, $ply, $pv_move, $position->pseudoLegalMoves);
455 } else {
456 332407 @moves = $position->pseudoLegalMoves;
457  
458 332407 ▶ $pv_move = $pline->[$ply - 1] if @$pline >= $ply;
Branch: 1 branch
BranchTrueFalseTotal
if @$pline >= $ply 0 332407 332407
459 332407 my (@pv, @tt, @promotions, @checks, @good_captures, @k1, @k2, @k3, @quiet, @bad_captures);
460 332407 my $killers = $self->{killers}->[$ply];
461 332407 my $k1 = $killers->[0];
462 332407 my $k2 = $killers->[1];
463 332407 ▶ my $k3 = $ply > 1 ? $self->{killers}->[$ply - 2]->[0] : 0;
Branch: 1 branch
BranchTrueFalseTotal
$ply > 1 ? : 332407 0 332407
464 332407 ▶ if ($depth >= 4) {
Branch: 1 branch
BranchTrueFalseTotal
if ($depth >= 4) { } 215 332192 332407
465 # Light sorting.
466 215 my %good_captures;
467 215 foreach my $move (@moves) {
468 5338 ▶ if (((($move) & 0x1fffc0) == (($pv_move) & 0x1fffc0))) {
Branch: 7 branches
BranchTrueFalseTotal
if (($move & 2097088) == ($pv_move & 2097088)) { } 0 5338 5338
elsif (($move & 2097088) == ($tt_move & 2097088)) { } 197 5141 5338
elsif (my $promote = $move >> 6 & 7) { } 311 4830 5141
elsif ($move >> 3 & 7) { } 909 3921 4830
elsif ($move == $k1) { } 122 3799 3921
elsif ($move == $k2) { } 0 3799 3799
elsif ($move == $k3) { } 0 3799 3799
469 0 push @pv, $move;
470 } elsif (((($move) & 0x1fffc0) == (($tt_move) & 0x1fffc0))) {
471 197 push @tt, $move;
472 } elsif (my $promote = ((($move) >> 6) & 0x7)) {
473 311 ▶ if ((GOOD_PROMO_MASK >> $promote) & 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (36 >> $promote & 1) { } 131 180 311
474 131 push @promotions, $move;
475 } else {
476 180 push @quiet, $move;
477 }
478 } elsif (((($move) >> 3) & 0x7)) {
479 909 my $see = $position->SEE($move);
480 909 ▶ if ($see >= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($see >= 0) { } 750 159 909
481 750 $good_captures{$move} = $position->SEE($move);
482 } else {
483 159 push @bad_captures, $move;
484 }
485 } elsif ($move == $k1) {
486 122 $k1[0] = $move;
487 } elsif ($move == $k2) {
488 0 $k2[0] = $move;
489 } elsif ($move == $k3) {
490 0 $k3[0] = $move;
491 } else {
492 3799 push @quiet, $move;
493 }
494 }
495 215 ▶ @good_captures = sort { $good_captures{$b} <=> $good_captures{$a} || $b <=> $a } keys %good_captures;
Condition66%2/3
$good_captures{$b} <=> $good_captures{$a} || $b <=> $a
l!l&&r!l&&!r
5013190
MC/DC0%0/2
$good_captures{$b} <=> $good_captures{$a} || $b <=> $a
$good_captures{$b} <=> $good_captures{$a} $b <=> $a
Truth table66%2/3
A || B
A= $good_captures{$b} <=> $good_captures{$a}B= $b <=> $a
ABresult
1X1
011
000
496 215 ▶ @bad_captures = sort { $mvv_lva[$b] <=> $mvv_lva[$a] || $b <=> $a } @bad_captures;
Condition33%1/3
$mvv_lva[$b] <=> $mvv_lva[$a] || $b <=> $a
l!l&&r!l&&!r
0470
MC/DC0%0/2
$mvv_lva[$b] <=> $mvv_lva[$a] || $b <=> $a
$mvv_lva[$b] <=> $mvv_lva[$a] $b <=> $a
Truth table33%1/3
A || B
A= $mvv_lva[$b] <=> $mvv_lva[$a]B= $b <=> $a
ABresult
1X1
011
000
497 } else {
498 # Minimal sorting.
499 332192 foreach my $move (@moves) {
500 11093430 ▶ if (((($move) & 0x1fffc0) == (($pv_move) & 0x1fffc0))) {
Branch: 7 branches
BranchTrueFalseTotal
if (($move & 2097088) == ($pv_move & 2097088)) { } 0 11093430 11093430
elsif (($move & 2097088) == ($tt_move & 2097088)) { } 13451 11079979 11093430
elsif (my $promote = $move >> 6 & 7) { } 106927 10973052 11079979
elsif ($move >> 3 & 7) { } 1392588 9580464 10973052
elsif ($move == $k1) { } 33982 9546482 9580464
elsif ($move == $k2) { } 10516 9535966 9546482
elsif ($move == $k3) { } 28014 9507952 9535966
501 0 push @pv, $move;
502 } elsif (((($move) & 0x1fffc0) == (($tt_move) & 0x1fffc0))) {
503 13451 push @tt, $move;
504 } elsif (my $promote = ((($move) >> 6) & 0x7)) {
505 106927 ▶ if ((GOOD_PROMO_MASK >> $promote) & 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (36 >> $promote & 1) { } 52531 54396 106927
506 52531 push @promotions, $move;
507 } else {
508 54396 push @quiet, $move;
509 }
510 } elsif (((($move) >> 3) & 0x7)) {
511 1392588 push @good_captures, $move;
512 } elsif ($move == $k1) {
513 33982 $k1[0] = $move;
514 } elsif ($move == $k2) {
515 10516 $k2[0] = $move;
516 } elsif ($move == $k3) {
517 28014 $k3[0] = $move;
518 } else {
519 9507952 push @quiet, $move;
520 }
521 }
522 332192 @good_captures = sort { $mvv_lva[$b & 0x3f] <=> $mvv_lva[$a & 0x3f] } @good_captures;
523 }
524  
525 # Apply history bonus and malus to all quiet moves. We store the bonuses
526 # in the upper 32 bits so that we can do a simple integer sort.
527 332407 foreach my $move (@quiet) {
528 9566327 $move |= (($cutoff_moves->[($move & 0x1ffe00) >> 9]) << 32);
529 }
530 332407 @quiet = sort { $b <=> $a } @quiet;
531  
532 332407 @moves = (@pv, @tt, @promotions, @checks, @good_captures, @k1, @k2, @k3, @quiet, @bad_captures);
533 }
534  
535 333134 my $legal = 0;
536 333134 my $moveno = 0;
537 333134 my $pv_found;
538 333134 my $is_null_window = $beta - $alpha == 1;
539 333134 my $best_move = 0;
540 333134 ▶ my $print_current_move = $ply == 1 && $self->{print_current_move};
Condition100%3/3
$ply == 1 && $self->{'print_current_move'}
!ll&&!rl&&r
33240716711
MC/DC100%2/2
$ply == 1 && $self->{'print_current_move'}
$ply == 1 $self->{'print_current_move'}
Truth table100%3/3
A && B
A= $ply == 1B= $self->{'print_current_move'}
ABresult
0X0
100
111
541 333134 my $signature_slot = $self->{history_length} + $ply;
542 333134 my @check_info = $position->inCheck;
543 333134 my @backup = @$position;
544 333134 foreach my $move (@moves) {
545 3145444 ▶ next if !$position->checkPseudoLegalMove($move, @check_info);
Branch: 1 branch
BranchTrueFalseTotal
unless $position->checkPseudoLegalMove($move, @check_info) 2313016 832428 3145444
546 832428 my @line;
547 832428 $position->move($move, 1);
548 832428 $signatures->[$signature_slot] = $position->[CP_POS_SIGNATURE];
549 832428 my $nodes_before = $self->{nodes}++;
550 832428 ▶ $self->printCurrentMove($move, $legal) if $print_current_move;
Branch: 1 branch
BranchTrueFalseTotal
if $print_current_move 25819 806609 832428
551 832428 my $score;
552 832428 if (DEBUG) {
553 my $cn = $position->moveCoordinateNotation($move);
554 $self->indent($ply, "move $cn: start search");
555 push @{$self->{line}}, $cn;
556 }
557 832428 ▶ if ($pv_found) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pv_found) { } 48132 784296 832428
558 48132 if (DEBUG) {
559 $self->indent($ply, "null window search");
560 }
561 48132 $score = -alphabeta($self, $ply + 1, $depth - 1,
562 -$alpha - 1, -$alpha, \@line, NON_PV_NODE, 1, $tt_pvs, $min_probe_ply);
563 48131 ▶ if (($score > $alpha) && ($score < $beta)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($score > $alpha and $score < $beta) 1715 46416 48131
Condition100%3/3
$score > $alpha and $score < $beta
!ll&&!rl&&r
458465701715
MC/DC100%2/2
$score > $alpha and $score < $beta
$score > $alpha $score < $beta
Truth table100%3/3
A and B
A= $score > $alphaB= $score < $beta
ABresult
0X0
100
111
564 1715 if (DEBUG) {
565 $self->indent($ply, "value $score outside null window, re-search");
566 }
567 1715 undef @line;
568 1715 $score = -alphabeta($self, $ply + 1, $depth - 1,
569 -$beta, -$alpha, \@line, NON_PV_NODE, 0, $tt_pvs, $min_probe_ply);
570 }
571 } else {
572 784296 if (DEBUG) {
573 $self->indent($ply, "recurse normal search");
574 }
575 784296 ▶ $score = -alphabeta($self, $ply + 1, $depth - 1, -$beta, -$alpha,
Branch: 1 branch
BranchTrueFalseTotal
$pv_node ? : 36904 747392 784296
576 \@line, $pv_node ? PV_NODE : NON_PV_NODE, 0, $tt_pvs,
577 $min_probe_ply);
578 }
579  
580 832425 ++$legal;
581 832425 ++$moveno;
582 832425 if (DEBUG) {
583 my $cn = $position->moveCoordinateNotation($move);
584 $self->indent($ply, "move $cn: value $score");
585 }
586 832425 @$position = @backup;
587 832425 if (DEBUG) {
588 pop @{$self->{line}};
589 }
590 832425 my $root_move;
591 832425 ▶ if ($node_type == ROOT_NODE) {
Branch: 1 branch
BranchTrueFalseTotal
if ($node_type == 0) 26091 806334 832425
592 26091 $root_move = $self->{root_moves}->{$move & 0xffff_ffff};
593 # The constants for the time management are taken from Stockfish
594 # and they use their own units which seem to be 3.5-4.0 centipawns.
595 $root_move->{average_score} =
596 26091 ▶ $root_move->{average_score} != -INF ? ($score + $root_move->{average_score}) >> 1 : $score;
Branch: 1 branch
BranchTrueFalseTotal
$root_move->{'average_score'} != -32001 ? : 10732 15359 26091
597 $root_move->{mean_squared_score} = $root_move->{mean_squared_score} != -INF * INF
598 26091 ▶ ? ($score * abs($score) + $root_move->{mean_squared_score}) / 2
Branch: 1 branch
BranchTrueFalseTotal
$root_move->{'mean_squared_score'} != -1024064001 ? : 10732 15359 26091
599 : $score * abs($score);
600 26091 $root_move->{move_effort} += $self->{nodes} - $nodes_before;
601 26091 ▶ ++$self->{total_best_move_changes} if $score > $best_value && $score > $alpha && $legal > 1;
Branch: 1 branch
BranchTrueFalseTotal
if $score > $best_value and $score > $alpha and $legal > 1 735 25356 26091
Condition100%6/6
$score > $best_value and $score > $alpha and $legal > 1
!ll&&!rl&&r
24640716735
$score > $best_value and $score > $alpha
!ll&&!rl&&r
24626141451
MC/DC100%3/3
$score > $best_value and $score > $alpha and $legal > 1
$score > $best_value $score > $alpha $legal > 1
Truth table100%4/4
A and B and C
A= $score > $best_valueB= $score > $alphaC= $legal > 1
ABCresult
0XX0
10X0
1100
1111
602 }
603 832425 ▶ if ($score > $best_value) {
Branch: 1 branch
BranchTrueFalseTotal
if ($score > $best_value) 345505 486920 832425
604 345505 $best_value = $score;
605  
606 345505 ▶ if ($score > $alpha) {
Branch: 1 branch
BranchTrueFalseTotal
if ($score > $alpha) 266528 78977 345505
607 266528 $best_move = $move;
608  
609 266528 $pv_found = 1;
610 266528 @$pline = ($move, @line);
611 266528 ▶ if ($node_type == ROOT_NODE) {
Branch: 1 branch
BranchTrueFalseTotal
if ($node_type == 0) 1451 265077 266528
612 1451 $self->{score} = $score;
613 1451 $self->printPV($pline);
614 }
615  
616 266528 ▶ if ($score < $beta) {
Branch: 1 branch
BranchTrueFalseTotal
if ($score < $beta) { } 6286 260242 266528
617 6286 $alpha = $score;
618 6286 if (DEBUG) {
619 $self->indent($ply, "raise alpha to $alpha");
620 }
621 } else {
622 260242 if (DEBUG) {
623 my $hex_sig = sprintf '%016x', $signature;
624 my $cn = $position->moveCoordinateNotation($move);
625 $self->indent($ply, "$cn fail high ($score >= $beta), store $score(BOUND_LOWER) \@depth $depth for $hex_sig");
626 }
627  
628 # Quiet move failing high?
629 260242 ▶ if (!((($move) >> 3) & 0x7)
Branch: 1 branch
BranchTrueFalseTotal
unless ($move >> 3 & 7 or ($move & 2097088) == ($pv_move & 2097088) or ($move & 2097088) == ($tt_move & 2097088)) 71122 189120 260242
Condition100%6/6
$move >> 3 & 7 or ($move & 2097088) == ($pv_move & 2097088) or ($move & 2097088) == ($tt_move & 2097088)
l!l&&r!l&&!r
186375274571122
$move >> 3 & 7 or ($move & 2097088) == ($pv_move & 2097088)
l!l&&r!l&&!r
1863215473867
MC/DC100%3/3
$move >> 3 & 7 or ($move & 2097088) == ($pv_move & 2097088) or ($move & 2097088) == ($tt_move & 2097088)
$move >> 3 & 7 ($move & 2097088) == ($pv_move & 2097088) ($move & 2097088) == ($tt_move & 2097088)
Truth table100%4/4
A or B or C
A= $move >> 3 & 7B= ($move & 2097088) == ($pv_move & 2097088)C= ($move & 2097088) == ($tt_move & 2097088)
ABCresult
1XX1
01X1
0011
0000
630 && !((($move) & 0x1fffc0) == (($pv_move) & 0x1fffc0))
631 && !((($move) & 0x1fffc0) == (($tt_move) & 0x1fffc0))) {
632 71122 if (DEBUG) {
633 my $cn = $position->moveCoordinateNotation($move);
634 $self->indent($ply, "$cn is quiet and becomes new killer move");
635 }
636  
637 71122 my $killers = $self->{killers}->[$ply];
638 71122 ($killers->[0], $killers->[1]) = ($move, $killers->[0]);
639  
640 # The history bonus should only be given to real quiet
641 # moves, not bad captures. Later, when we also give
642 # maluses, we still want to give the malus to all
643 # previously searched quiet moves.
644  
645 # This is the from and to square as one single integer.
646 71122 my $from_to = ($move & 0x1ffe00) >> 9;
647  
648 71122 $cutoff_moves->[$from_to] += $depth * $depth;
649 71122 if (DEBUG) {
650 my $bonus = $depth * $depth;
651 my $cn = $position->moveCoordinateNotation($move);
652 $self->indent($ply, "$cn is quiet and gets history bonus $bonus");
653 }
654 }
655  
656 260242 last;
657 }
658 }
659 }
660 }
661  
662 333131 my $tt_type;
663 333131 ▶ if (!$legal) {
Branch: 3 branches
BranchTrueFalseTotal
if (not $legal) { } 29623 303508 333131
elsif ($best_value >= $beta) { } 260242 43266 303508
elsif ($best_move and $pv_node) { } 2607 40659 43266
664 # Mate or stalemate.
665 29623 ▶ if ($position->inCheck) {
Branch: 1 branch
BranchTrueFalseTotal
if ($position->inCheck) { } 29622 1 29623
666 29622 $best_value = -MATE + $ply;
667 } else {
668 1 $best_value = DRAW;
669 }
670 29623 $tt_type = BOUND_EXACT;
671 29623 ▶ $depth = (((MAX_PLY - 1) < ($depth + 6)) ? (MAX_PLY - 1) : ($depth + 6));
Branch: 1 branch
BranchTrueFalseTotal
245 < $depth + 6 ? : 0 29623 29623
672 29623 if (DEBUG) {
673 $self->indent($ply, "mate/stalemate, score: $best_value");
674 }
675 } elsif ($best_value >= $beta) {
676 260242 $tt_type = BOUND_LOWER;
677 ▶ } elsif ($best_move && $pv_node) {
Condition100%3/3
$best_move and $pv_node
!ll&&!rl&&r
3926613932607
MC/DC100%2/2
$best_move and $pv_node
$best_move $pv_node
Truth table100%3/3
A and B
A= $best_moveB= $pv_node
ABresult
0X0
100
111
678 2607 $tt_type = BOUND_EXACT;
679 } else {
680 40659 $tt_type = BOUND_UPPER;
681 }
682  
683 333131 if (DEBUG) {
684 my $hex_sig = sprintf '%016x', $signature;
685 if ($is_null_window && $tt_type == BOUND_EXACT) {
686 $self->indent($ply, "returning best value $best_value without tt store for $hex_sig");
687 } else {
688 my $type;
689 if ($tt_type == BOUND_UPPER) {
690 $type = 'BOUND_UPPER';
691 } elsif ($tt_type == BOUND_LOWER) {
692 $type = 'BOUND_LOWER';
693 } else {
694 $type = 'BOUND_EXACT';
695 }
696 my $value = (do { (($best_value >= VALUE_TB_WIN_IN_MAX_PLY) ? $best_value + $ply : ($best_value <= VALUE_TB_LOSS_IN_MAX_PLY) ? $best_value - $ply : $best_value);});
697 $self->indent($ply, "returning best value $best_value, store $value ($type) \@depth $depth for $hex_sig");
698 }
699 }
700  
701 # Taken from Stockfish: If no good move is found and the previous position
702 # was ttPv, then the previous opponent move is probably good and the new
703 # position is added to the search tree.
704 333131 ▶ if ($best_value <= $alpha) {
Branch: 1 branch
BranchTrueFalseTotal
if ($best_value <= $alpha) 53552 279579 333131
705 53552 ▶ $tt_pvs->[-1] = $tt_pvs->[-1] || $tt_pvs->[-2];
Condition100%3/3
$tt_pvs->[-1] || $tt_pvs->[-2]
l!l&&r!l&&!r
912455043878
MC/DC100%2/2
$tt_pvs->[-1] || $tt_pvs->[-2]
$tt_pvs->[-1] $tt_pvs->[-2]
Truth table100%3/3
A || B
A= $tt_pvs->[-1]B= $tt_pvs->[-2]
ABresult
1X1
011
000
706 }
707  
708 $tt->store(
709 @tt_address, # Address.
710 $signature, # Zobrist key.
711 333131 ▶ (do { (($best_value >= VALUE_TB_WIN_IN_MAX_PLY) ? $best_value + $ply : ($best_value <= VALUE_TB_LOSS_IN_MAX_PLY) ? $best_value - $ply : $best_value);}), # score, mate distance adjusted.
Branch: 3 branches
BranchTrueFalseTotal
unless $is_null_window and $tt_type == 3 306171 26960 333131
$best_value >= 31507 ? : 8671 297500 306171
$best_value <= -31507 ? : 29107 268393 297500
Condition100%3/3
$is_null_window and $tt_type == 3
!ll&&!rl&&r
2862927754226960
MC/DC100%2/2
$is_null_window and $tt_type == 3
$is_null_window $tt_type == 3
Truth table100%3/3
A and B
A= $is_null_windowB= $tt_type == 3
ABresult
0X0
100
111
712 $tt_pvs->[-1], # PV flag.
713 $tt_type, # BOUND_EXACT/TT_SCORE_ALPHA/TT_SCORE_LOWER.
714 $depth, # Depth searched.
715 $best_move # Best move at this node.
716 ) if !($is_null_window && $tt_type == BOUND_EXACT);
717  
718 333131 return $best_value;
719 }
720  
721 1603230 ▶sub quiesce {
Subroutine quiesce: called CC=40 SCAR=38.0
Pod undocumented
722 1603230 my ($self, $ply, $alpha, $beta, $node_type, $min_probe_ply) = @_;
723  
724 1603230 ▶ if ($self->{nodes} >= $self->{nodes_to_tc}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"nodes"} >= $self->{"nodes_to_tc"}) 1601435 1795 1603230
725 1601435 $self->checkTime;
726 }
727  
728 1603230 my $pv_node = $node_type != NON_PV_NODE;
729  
730 1603230 ▶ $self->{seldepth} = ((($ply) > ($self->{seldepth})) ? ($ply) : ($self->{seldepth}));
Branch: 1 branch
BranchTrueFalseTotal
$ply > $self->{'seldepth'} ? : 3751 1599479 1603230
731  
732 1603230 my $position = $self->{position};
733  
734 1603230 if (DEBUG) {
735 my $hex_signature = sprintf '%016x', $position->[CP_POS_SIGNATURE];
736 my $line = join ' ', @{$self->{line}};
737 my $fen = $position->fen;
738 $self->indent($ply, "quiescence: alpha = $alpha, beta = $beta, line: $line,"
739 . " sig: $hex_signature $fen");
740 }
741  
742 # Expand the search, when in check.
743 1603230 ▶ if ($position->inCheck) {
Branch: 1 branch
BranchTrueFalseTotal
if ($position->inCheck) 318321 1284909 1603230
744 318321 if (DEBUG) {
745 $self->indent($ply, "quiescence check extension");
746 }
747  
748 318321 ▶ return alphabeta($self, $ply, 1, $alpha, $beta, [], $node_type,
Condition100%3/3
!$pv_node && $beta == $alpha + 1
!ll&&!rl&&r
222736184289864
MC/DC100%2/2
!$pv_node && $beta == $alpha + 1
!$pv_node $beta == $alpha + 1
Truth table100%3/3
not(A) && B
A= !$pv_nodeB= $beta == $alpha + 1
ABresult
0X0
100
111
749 !$pv_node && $beta == $alpha + 1, [$pv_node], $min_probe_ply);
750 }
751  
752 1284909 my $tt = $self->{tt};
753 1284909 my $signature = $position->[CP_POS_SIGNATURE];
754 1284909 my ($tt_hit, $tt_depth, $tt_bound, $tt_move, $tt_value, $tt_eval,
755 $tt_pv, @tt_address) = $tt->probe($signature);
756  
757 0 ▶ $tt_value = (do { if ($tt_value >= VALUE_TB_WIN_IN_MAX_PLY) { if ($tt_value >= MATE_IN_MAX_PLY && MATE - $tt_value > 100 - $position->[CP_POS_HALFMOVE_CLOCK]) { VALUE_TB_WIN_IN_MAX_PLY - 1 } elsif (VALUE_TB_WIN_IN_MAX_PLY - $tt_value > 100 - $position->[CP_POS_HALFMOVE_CLOCK]) { VALUE_TB_WIN_IN_MAX_PLY - 1 } else { $tt_value - $ply; } } elsif ($tt_value <= VALUE_TB_LOSS_IN_MAX_PLY) { if ($tt_value <= MATED_IN_MAX_PLY && MATE + $tt_value > 100 - $position->[CP_POS_HALFMOVE_CLOCK]) { VALUE_TB_LOSS_IN_MAX_PLY + 1; } elsif (VALUE_TB_LOSS_IN_MAX_PLY + $tt_value > 100 - $position->[CP_POS_HALFMOVE_CLOCK]) { VALUE_TB_LOSS_IN_MAX_PLY + 1; } else { $tt_value + $ply; } } else { $tt_value; }})
Branch: 7 branches
BranchTrueFalseTotal
if $tt_hit and defined $tt_value 209567 1075342 1284909
if ($tt_value >= 31507) { } 5189 204378 209567
elsif ($tt_value <= -31507) { } 0 204378 204378
if ($tt_value >= 31754 and 32000 - $tt_value > 100 - $position->[11]) { } 0 5189 5189
elsif (31507 - $tt_value > 100 - $position->[11]) { } 0 5189 5189
if ($tt_value <= -31754 and 32000 + $tt_value > 100 - $position->[11]) { } 0 0 0
elsif (-31507 + $tt_value > 100 - $position->[11]) { } 0 0 0
Condition33%3/9
$tt_hit and defined $tt_value
!ll&&!rl&&r
10753420209567
$tt_value >= 31754 and 32000 - $tt_value > 100 - $position->[11]
!ll&&!rl&&r
051890
$tt_value <= -31754 and 32000 + $tt_value > 100 - $position->[11]
!ll&&!rl&&r
000
MC/DC50%1/2
$tt_hit and defined $tt_value
$tt_hit defined $tt_value
MC/DC0%0/2
$tt_value >= 31754 and 32000 - $tt_value > 100 - $position->[11]
$tt_value >= 31754 32000 - $tt_value > 100 - $position->[11]
MC/DC0%0/2
$tt_value <= -31754 and 32000 + $tt_value > 100 - $position->[11]
$tt_value <= -31754 32000 + $tt_value > 100 - $position->[11]
Truth table66%2/3
A and B
A= $tt_hitB= defined $tt_value
ABresult
0X0
100
111
Truth table33%1/3
A and B
A= $tt_value >= 31754B= 32000 - $tt_value > 100 - $position->[11]
ABresult
0X0
100
111
Truth table0%0/3
A and B
A= $tt_value <= -31754B= 32000 + $tt_value > 100 - $position->[11]
ABresult
0X0
100
111
758 if $tt_hit && defined $tt_value;
759  
760 # Early TT cutoff.
761 1284909 ▶ if (!$pv_node && $tt_depth >= DEPTH_QUIESCENCE
Branch: 2 branches
BranchTrueFalseTotal
if (not $pv_node and $tt_depth >= 0 and defined $tt_value and $tt_bound & ($tt_value >= $beta ? 2 : 1)) 32389 1252520 1284909
$tt_value >= $beta ? : 5162 30538 35700
Condition100%9/9
not $pv_node and $tt_depth >= 0 and defined $tt_value and $tt_bound & ($tt_value >= $beta ? 2 : 1)
!ll&&!rl&&r
1249209331132389
not $pv_node and $tt_depth >= 0 and defined $tt_value
!ll&&!rl&&r
239697100951235700
not $pv_node and $tt_depth >= 0
!ll&&!rl&&r
870951526021045212
MC/DC100%4/4
not $pv_node and $tt_depth >= 0 and defined $tt_value and $tt_bound & ($tt_value >= $beta ? 2 : 1)
not $pv_node $tt_depth >= 0 defined $tt_value $tt_bound & ($tt_value >= $beta ? 2 : 1)
Truth table100%5/5
not(A) and B and C and D
A= not $pv_nodeB= $tt_depth >= 0C= defined $tt_valueD= $tt_bound & ($tt_value >= $beta ? 2 : 1)
ABCDresult
0XXX0
10XX0
110X0
11100
11111
762 && defined $tt_value
763 && ($tt_bound & ($tt_value >= $beta ? BOUND_LOWER : BOUND_UPPER))) {
764 32389 return $tt_value;
765 }
766  
767 # Compute best available stand-pat value
768 1252520 my $best_value = $position->evaluate;
769 1252520 if (DEBUG) {
770 $self->indent($ply, "static evaluation: $best_value");
771 }
772  
773 1252520 ▶ if ($best_value >= $beta) {
Branch: 1 branch
BranchTrueFalseTotal
if ($best_value >= $beta) 969112 283408 1252520
774 # FIXME! Reduce branching here!
775 969112 if (DEBUG) {
776 my $hex_sig = sprintf '%016x', $signature;
777 if ($tt_hit) {
778 $self->indent($ply, "quiescence standing pat ($best_value >= $beta) without tt store for $hex_sig");
779 } else {
780 $self->indent($ply, "quiescence standing pat ($best_value >= $beta), store no move value $best_value (BOUND_LOWER) \@depth 0 for $hex_sig");
781 }
782 }
783  
784 969112 ▶ if (!$tt_hit) {
Branch: 1 branch
BranchTrueFalseTotal
if (not $tt_hit) { } 806947 162165 969112
785 $tt->store(
786 @tt_address,
787 $signature,
788 806947 ▶ (do { (($best_value >= VALUE_TB_WIN_IN_MAX_PLY) ? $best_value + $ply : ($best_value <= VALUE_TB_LOSS_IN_MAX_PLY) ? $best_value - $ply : $best_value);}),
Branch: 2 branches
BranchTrueFalseTotal
$best_value >= 31507 ? : 0 806947 806947
$best_value <= -31507 ? : 0 806947 806947
789 0,
790 BOUND_LOWER,
791 DEPTH_UNSEARCHED,
792 0,
793 );
794 } else {
795 162165 $best_value = $tt_value;
796 }
797  
798 969112 return $best_value;
799 }
800  
801 283408 ▶ if ($best_value > $alpha) {
Branch: 1 branch
BranchTrueFalseTotal
if ($best_value > $alpha) 8450 274958 283408
802 8450 $alpha = $best_value;
803 }
804  
805 # FIXME! Jump over all the expensive stuff following if there are no
806 # moves.
807 283408 my @moves = $position->pseudoLegalAttacks; # or goto SKIP_MOVE_LOOP ...
808  
809 283408 my (@tt, @promotions, @checks, %captures);
810 283408 foreach my $move (@moves) {
811 1278071 ▶ if (((($move) & 0x1fffc0) == (($tt_move) & 0x1fffc0))) {
Branch: 3 branches
BranchTrueFalseTotal
if (($move & 2097088) == ($tt_move & 2097088)) { } 7247 1270824 1278071
elsif (36 >> ($move >> 6 & 7) & 1) { } 76603 1194221 1270824
elsif ($position->moveGivesCheck($move)) { } 221560 972661 1194221
812 7247 push @tt, $move;
813 } elsif ((GOOD_PROMO_MASK >> (((($move) >> 6) & 0x7))) & 1) {
814 # Skip underpromotions in quiescence.
815 76603 push @promotions, $move;
816 } elsif ($position->moveGivesCheck($move)) { # FIXME! Too expensive?
817 221560 push @checks, $move;
818 } else {
819 # info depth 10 seldepth 37 score cp 6 nodes 46676164 nps 39461 hashfull 500 tbhits 0 time 1182841 pv e2e4 e7e5 c2c3 g8f6 g1f3 f8e7 f3e5 f6e4 d1g4 e4g5
820 # bestmove e2e4 ponder e7e5
821  
822 972661 my $see = $position->SEE($move);
823 972661 ▶ $captures{$move} = $see if $see >= -80;
Branch: 1 branch
BranchTrueFalseTotal
if $see >= -80 763101 209560 972661
824 }
825 }
826  
827 283408 ▶ my @captures = sort { $captures{$b} <=> $captures{$a} || $b <=> $a } keys %captures;
Condition66%2/3
$captures{$b} <=> $captures{$a} || $b <=> $a
l!l&&r!l&&!r
5767352793760
MC/DC0%0/2
$captures{$b} <=> $captures{$a} || $b <=> $a
$captures{$b} <=> $captures{$a} $b <=> $a
Truth table66%2/3
A || B
A= $captures{$b} <=> $captures{$a}B= $b <=> $a
ABresult
1X1
011
000
828 283408 @moves = (@tt, @promotions, @checks, @captures);
829  
830 283408 my $signatures = $self->{signatures};
831 283408 my $signature_slot = $self->{history_length} + $ply;
832 283408 my @check_info = $position->inCheck;
833 283408 my @backup = @$position;
834  
835 283408 my $legal = 0;
836 283408 my $best_move = 0;
837 283408 foreach my $move (@moves) {
838 921522 ▶ next if !$position->checkPseudoLegalMove($move, @check_info);
Branch: 1 branch
BranchTrueFalseTotal
unless $position->checkPseudoLegalMove($move, @check_info) 102367 819155 921522
839 819155 $position->move($move, 1);
840 819155 $signatures->[$signature_slot] = $position->[CP_POS_SIGNATURE];
841 819155 if (DEBUG) {
842 my $cn = $position->moveCoordinateNotation($move);
843 push @{$self->{line}}, $cn;
844 $self->indent($ply, "move $cn: start quiescence search");
845 }
846 819155 ++$self->{nodes};
847 819155 ++$legal;
848 819155 if (DEBUG) {
849 $self->indent($ply, "recurse quiescence search");
850 }
851 819155 my $score = -quiesce($self, $ply + 1, -$beta, -$alpha, $node_type, $min_probe_ply);
852 819155 if (DEBUG) {
853 my $cn = $position->moveCoordinateNotation($move);
854 $self->indent($ply, "move $cn: value: $score");
855 pop @{$self->{line}};
856 }
857 819155 @$position = @backup;
858 819155 ▶ if ($score > $best_value) {
Branch: 1 branch
BranchTrueFalseTotal
if ($score > $best_value) 328153 491002 819155
859 328153 $best_value = $score;
860  
861 328153 ▶ if ($score > $alpha) {
Branch: 1 branch
BranchTrueFalseTotal
if ($score > $alpha) 51284 276869 328153
862 51284 $best_move = $move;
863  
864 51284 ▶ if ($score < $beta) {
Branch: 1 branch
BranchTrueFalseTotal
if ($score < $beta) { } 5200 46084 51284
865 5200 if (DEBUG) {
866 $self->indent($ply, "raise quiescence alpha to $alpha");
867 }
868 5200 $alpha = $score;
869 } else {
870 46084 if (DEBUG) {
871 my $hex_sig = sprintf '%016x', $signature;
872 my $cn = $position->moveCoordinateNotation($move);
873 $self->indent($ply, "$cn quiescence fail high ($score >= $beta), store $score (BOUND_LOWER) \@depth 0 for $hex_sig");
874 }
875  
876 46084 last;
877 }
878 }
879 }
880 }
881  
882 283408 ▶ my $tt_type = $best_value >= $beta ? BOUND_LOWER : BOUND_UPPER;
Branch: 1 branch
BranchTrueFalseTotal
$best_value >= $beta ? : 46084 237324 283408
883 $tt->store(
884 @tt_address, # Address.
885 $signature, # Zobrist key.
886 283408 ▶ (do { (($best_value >= VALUE_TB_WIN_IN_MAX_PLY) ? $best_value + $ply : ($best_value <= VALUE_TB_LOSS_IN_MAX_PLY) ? $best_value - $ply : $best_value);}), # score, mate distance adjusted.
Branch: 2 branches
BranchTrueFalseTotal
$best_value >= 31507 ? : 25049 258359 283408
$best_value <= -31507 ? : 0 258359 258359
Condition100%3/3
$tt_hit && $tt_pv
!ll&&!rl&&r
268395150085
MC/DC100%2/2
$tt_hit && $tt_pv
$tt_hit $tt_pv
Truth table100%3/3
A && B
A= $tt_hitB= $tt_pv
ABresult
0X0
100
111
887 $tt_hit && $tt_pv, # PV flag.
888 $tt_type, # BOUND_EXACT/BOUND_UPPER/BOUND_LOWER.
889 DEPTH_QUIESCENCE, # Depth searched.
890 $best_move # Best move at this node.
891 );
892 283408 if (DEBUG) {
893 my $hex_sig = sprintf '%016x', $signature;
894 my $type = BOUND_TYPES->[$tt_type];
895 $self->indent($ply, "returning best value (quiescence) $best_value, store ($type) for $hex_sig");
896 }
897  
898 283408 return $best_value;
899 }
900  
901 347 ▶sub rootSearch {
Subroutine rootSearch: called CC=30 SCAR=35.5
Pod undocumented
902 347 my ($self, $pline) = @_;
903  
904 347 $self->{nodes} = 0;
905  
906 347 my $position = $self->{position};
907  
908 347 ▶ my $max_depth = $self->{max_depth} || (MAX_PLY - 1);
Condition100%2/2
$self->{'max_depth'} || 245
l!l
3452
MC/DC100%1/1
$self->{'max_depth'} || 245
$self->{'max_depth'}
Truth table100%2/2
A
A= $self->{'max_depth'}
Aresult
11
00
909 347 my $depth = $self->{depth} = 0;
910 347 $self->{seldepth} = 0;
911 347 my $score = $self->{score} = 0;
912  
913 347 my @line = @$pline;
914  
915 347 my $last_best_move;
916 347 my $last_best_move_depth = 0;
917 347 my $search_again_counter = 0;
918  
919 # Checking whether a tablebase probe is elegible is relatively expensive.
920 # But we know that the popcount of the position can only decrease by
921 # one per ply. So we pre-calculate the minimum ply, where a probe makes
922 # sense. If we hit that limit during the search, we re-evaluate. That
923 # reduces the number of checks to a minimum. If we have a cardinality
924 # of 7, then we start even thinking a about probing at ply 26.
925 347 my $min_probe_ply = INF;
926 347 ▶ if ($self_tb_cardinality > 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self_tb_cardinality > 2) 0 347 347
927 0 my $popcount = $position->[CP_POS_POPCOUNT];
928 0 ▶ if ($popcount <= $self_tb_cardinality) {
Branch: 1 branch
BranchTrueFalseTotal
if ($popcount <= $self_tb_cardinality) { } 0 0 0
929 0 $min_probe_ply = 2;
930 } else {
931 0 $min_probe_ply = 1 + $popcount - $self_tb_cardinality;
932 }
933 }
934  
935 347 if (DEBUG) {
936 my $fen = $position->toFEN;
937 $self->debug("Searching $fen");
938 }
939 347 eval {
940 347 ▶ DEEPENING: while (++$depth <= $max_depth) {
Branch: 1 branch
BranchTrueFalseTotal
if (++$depth <= $max_depth) 555 345 900
941 8 ▶ no integer;
Subroutine BEGIN: called CC=1 SCAR=0.0
942  
943 # When the aspiration window changes, the PV move should be
944 # brought to the front and the order of all other moves must
945 # remain unchanged. Therefore, we order the moves just once.
946 555 $self->{ordered_root_moves} = [$self->orderRootMoves($position, 1, $depth, 0, keys %{$self->{root_moves}})];
947  
948 # Age out instability.
949 555 $self->{total_best_move_changes} /= 2;
950  
951 555 $self->{depth} = $depth;
952 555 if (DEBUG) {
953 $self->debug("Deepening to depth $depth");
954 $self->{line} = [];
955 }
956  
957 # The upper 32 bits of the move can be abused by the move ordering.
958 555 my $pv_move = $line[0] & 0xffff_ffff;
959 555 my $delta = 15 + abs $self->{root_moves}->{$pv_move}->{mean_squared_score} / 8000;
960 555 my $avg = $self->{root_moves}->{$pv_move}->{average_score};
961 #stop "pv mean squared score: $self->{root_moves}->{$pv_move}->{mean_squared_score}\n";
962 #warn "pv average score: $self->{root_moves}->{$pv_move}->{average_score}\n";
963 555 ▶ my $alpha = int(((($avg - $delta) > (-INF)) ? ($avg - $delta) : (-INF)));
Branch: 1 branch
BranchTrueFalseTotal
$avg - $delta > -32001 ? : 156 399 555
964 555 ▶ my $beta = int(((($avg + $delta) < (+INF)) ? ($avg + $delta) : (+INF)));
Branch: 1 branch
BranchTrueFalseTotal
$avg + $delta < 32001 ? : 156 399 555
965  
966 555 my $failed_high_count = 0;
967 555 while (1) {
968 727 my @tt_pvs;
969 #warn "DEPTH $depth: delta: $delta avg: $avg alpha: $alpha beta: $beta\n";
970 727 $score = $self->alphabeta(1, $depth, $alpha, $beta, \@line,
971 ROOT_NODE, 0, \@tt_pvs, $min_probe_ply);
972 #warn " best value: $score\n";
973 726 if (DEBUG) {
974 $self->debug("Score at depth $depth: $score");
975 }
976  
977 # Mate found?
978 726 ▶ if (($score >= MATE - $depth) || ($score <= -(MATE - $depth))) {
Branch: 1 branch
BranchTrueFalseTotal
if ($score >= 32000 - $depth or $score <= -(32000 - $depth)) 0 726 726
Condition33%1/3
$score >= 32000 - $depth or $score <= -(32000 - $depth)
l!l&&r!l&&!r
00726
MC/DC0%0/2
$score >= 32000 - $depth or $score <= -(32000 - $depth)
$score >= 32000 - $depth $score <= -(32000 - $depth)
Truth table33%1/3
A or B
A= $score >= 32000 - $depthB= $score <= -(32000 - $depth)
ABresult
1X1
011
000
979 0 $self->printPV(\@line);
980 0 last DEEPENING;
981 }
982  
983 726 ▶ if ($score <= $alpha) {
Branch: 2 branches
BranchTrueFalseTotal
if ($score <= $alpha) { } 8 718 726
elsif ($score >= $beta) { } 164 554 718
984 8 $beta = $alpha;
985 8 ▶ $alpha = int(((($score - $delta) > (-INF)) ? ($score - $delta) : (-INF)));
Branch: 1 branch
BranchTrueFalseTotal
$score - $delta > -32001 ? : 8 0 8
986 8 if (DEBUG) {
987 $self->debug("Failed low, must re-search with alpha=$alpha and beta=$beta");
988 }
989 8 $failed_high_count = 0;
990 } elsif ($score >= $beta) {
991 164 ▶ $alpha = int(((($beta - $delta) > ($alpha)) ? ($beta - $delta) : ($alpha)));
Branch: 1 branch
BranchTrueFalseTotal
$beta - $delta > $alpha ? : 85 79 164
992 164 ▶ $beta = int(((($score + $delta) < (+INF)) ? ($score + $delta) : (+INF)));
Branch: 1 branch
BranchTrueFalseTotal
$score + $delta < 32001 ? : 92 72 164
993 164 if (DEBUG) {
994 $self->debug("Failed high, must re-search with alpha=$alpha and beta=$beta");
995 }
996 164 ++$failed_high_count;
997 } else {
998 554 last;
999 }
1000
1001 172 $delta *= 5;
1002  
1003 # Bring the PV move to the front and keep the rest of the
1004 # move ordering unchanged.
1005 172 my $pv_move = $line[0];
1006 $self->{ordered_root_moves} = [
1007 $pv_move,
1008 172 grep { $_ ne $pv_move } @{$self->{ordered_root_moves}},
1009 ];
1010 }
1011  
1012 554 $self->printPV(\@line);
1013  
1014 554 ▶ if ($self->{use_time_management}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"use_time_management"}) 5 549 554
1015 5 my $iter_idx = ($depth - 1) & 3;
1016  
1017 8 ▶ no integer;
Subroutine BEGIN: called CC=1 SCAR=0.0
1018  
1019 5 my $root_move = $self->{root_moves}->{$line[0] & 0xffff_ffff};
1020 5 my $best_value = $root_move->{score};
1021  
1022 my $falling_eval = (11.85 + 2.24 * ($root_move->{previous_average_score} - $best_value)
1023 5 + 0.93 * ($self->{iter_scores}->[$iter_idx] - $best_value)) / 100.0;
1024 5 ▶ $falling_eval = ($falling_eval) < (0.57) ? (0.57) : ($falling_eval) > (1.70) ? (1.70) : ($falling_eval);
Branch: 2 branches
BranchTrueFalseTotal
$falling_eval < 0.57 ? : 0 5 5
$falling_eval > 1.7 ? : 5 0 5
1025 5 ▶ if ($line[0] != $last_best_move) {
Branch: 1 branch
BranchTrueFalseTotal
if ($line[0] != $last_best_move) 2 3 5
1026 2 $last_best_move_depth = $depth;
1027 }
1028  
1029 # Idea: Try to move the center based on the average completed
1030 # search depth. But the average search depth should probably
1031 # be aged out.
1032 # my $depth_scale = $self->{avg_completed_depth} / 40.0; # SF baseline
1033 # my $center = $last_best_move_depth + 12.15 * $depth_scale;
1034 5 my $k = 0.51; # FIXME! Lower that to 0.25?
1035 5 my $center = $last_best_move_depth + 12.15; # Divide by 4.25?
1036  
1037 5 my $time_reduction = 0.66 + 0.85 / (0.98 + exp(-$k * ($depth - $center)));
1038 5 my $reduction = (1.43 + $self->{previous_time_reduction}) / (2.28 * $time_reduction);
1039 5 my $best_move_instability = 1.02 + 2.14 * $self->{total_best_move_changes};
1040 5 ▶ my $nodes_effort = $root_move->{move_effort} * 100000 / (((1) > ($self->{nodes})) ? (1) : ($self->{nodes}));
Branch: 1 branch
BranchTrueFalseTotal
1 > $self->{'nodes'} ? : 0 5 5
1041  
1042 # The original value is 93340. But we will not reach that
1043 # with only safe prunings.
1044 5 ▶ my $high_best_move_effort = $nodes_effort >= 30000 ? 0.76 : 1.0;
Branch: 1 branch
BranchTrueFalseTotal
$nodes_effort >= 30000 ? : 1 4 5
1045  
1046 5 my $total_time = $self->{optimum} * $falling_eval * $reduction
1047 * $best_move_instability * $high_best_move_effort;
1048  
1049 5 my $elapsed = 1000 * tv_interval($self->{start_time});
1050  
1051 5 ▶ if ($elapsed > ((($total_time) < ($self->{maximum})) ? ($total_time) : ($self->{maximum}))) {
Branch: 3 branches
BranchTrueFalseTotal
if ($elapsed > ($total_time < $self->{'maximum'} ? $total_time : $self->{'maximum'})) { } 0 5 5
elsif (not $self->{'ponder'}) { } 5 0 5
$total_time < $self->{'maximum'} ? : 3 2 5
1052 0 ▶ if (!$self->{ponder}) {
Branch: 1 branch
BranchTrueFalseTotal
unless ($self->{"ponder"}) 0 0 0
1053 0 last;
1054 }
1055 } elsif (!$self->{ponder}) {
1056 # Stockfish sets the threshold to half of the total time.
1057 # We use less.
1058 #
1059 # Current best: 0.25
1060 # Values 0.5, 0.375, 0.3125 all failed SPRTs.
1061 5 ▶ if ($elapsed > $total_time >> 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($elapsed > $total_time >> 2) 1 4 5
1062 1 last;
1063 }
1064 }
1065  
1066 4 $root_move->{previous_average_score} = $root_move->{average_score};
1067 4 $self->{previous_time_reduction} = $time_reduction;
1068 4 $last_best_move = $line[0];
1069 4 $self->{iter_scores}->[$iter_idx] = $best_value;
1070 }
1071 }
1072 };
1073 347 ▶ if ($@) {
Branch: 1 branch
BranchTrueFalseTotal
if ($@) 1 346 347
1074 1 ▶ if ($@ ne "PLISCO_ABORTED\n") {
Branch: 1 branch
BranchTrueFalseTotal
if ($@ ne "PLISCO_ABORTED\n") 0 1 1
1075 0 $self->{info}->(__"Error: exception raised: $@");
1076 }
1077 1 $self->printPV(\@line);
1078 }
1079  
1080 347 ▶ if ($self->{maximum} && !$self->{ponderhit}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"maximum"} and not $self->{"ponderhit"}) 2 345 347
Condition66%2/3
$self->{"maximum"} and not $self->{"ponderhit"}
!ll&&!rl&&r
34502
MC/DC50%1/2
$self->{"maximum"} and not $self->{"ponderhit"}
$self->{"maximum"} not $self->{"ponderhit"}
Truth table66%2/3
A and not(B)
A= $self->{"maximum"}B= not $self->{"ponderhit"}
ABresult
0X0
100
111
1081 2 my $elapsed = 1000 * tv_interval($self->{start_time});
1082 2 ▶ if ($elapsed > $self->{maximum}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($elapsed > $self->{"maximum"}) 0 2 2
1083 0 $self->{info}->(__"Error: used $elapsed ms instead of $self->{maximum} ms.");
1084 }
1085 }
1086  
1087 347 @$pline = @line;
1088 }
1089  
1090 555 ▶sub orderRootMoves {
Subroutine orderRootMoves: called CC=19 SCAR=30.4
Pod undocumented
1091 555 my ($self, $position, $depth, $ply, $pv_move, @moves) = @_;
1092  
1093 555 ▶ if ($self->{tb_hit} && $depth == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"tb_hit"} and $depth == 1) 0 555 555
Condition33%1/3
$self->{"tb_hit"} and $depth == 1
!ll&&!rl&&r
55500
MC/DC0%0/2
$self->{"tb_hit"} and $depth == 1
$self->{"tb_hit"} $depth == 1
Truth table33%1/3
A and B
A= $self->{"tb_hit"}B= $depth == 1
ABresult
0X0
100
111
1094 0 my $root_moves = $self->{root_moves};
1095 0 @moves = sort { $root_moves->{$a} <=> $root_moves->{$b} } @moves;
1096 }
1097  
1098 555 my $signature = $self->{position}->[CP_POS_SIGNATURE];
1099  
1100 555 my $tt = $self->{tt};
1101 555 my ($tt_hit, $tt_depth, $tt_bound, $tt_move, $tt_value, $tt_eval,
1102 $tt_pv, @tt_address) = $tt->probe($signature);
1103 555 ▶ $tt_move = 0 if !$tt_hit;
Branch: 1 branch
BranchTrueFalseTotal
unless $tt_hit 346 209 555
1104  
1105 555 my (@pv, @tt, @promotions, @checks, @good_captures, @k1, @k2, @k3, @quiet, @bad_captures);
1106 555 my $killers = $self->{killers}->[$ply];
1107 555 my $k1 = $killers->[0];
1108 555 my $k2 = $killers->[1];
1109 555 ▶ my $k3 = $ply > 1 ? $self->{killers}->[$ply - 2]->[0] : 0;
Branch: 1 branch
BranchTrueFalseTotal
$ply > 1 ? : 208 347 555
1110  
1111 555 my %good_captures;
1112 555 foreach my $move (@moves) {
1113 24455 ▶ if (((($move) & 0x1fffc0) == (($pv_move) & 0x1fffc0))) {
Branch: 8 branches
BranchTrueFalseTotal
if (($move & 2097088) == ($pv_move & 2097088)) { } 0 24455 24455
elsif (($move & 2097088) == ($tt_move & 2097088)) { } 209 24246 24455
elsif (my $promote = $move >> 6 & 7) { } 259 23987 24246
elsif ($position->moveGivesCheck($move)) { } 3952 20035 23987
elsif ($move >> 3 & 7) { } 2085 17950 20035
elsif ($move == $k1) { } 1 17949 17950
elsif ($move == $k2) { } 1 17948 17949
elsif ($move == $k3) { } 0 17948 17948
1114 0 push @tt, $move;
1115 } elsif (((($move) & 0x1fffc0) == (($tt_move) & 0x1fffc0))) {
1116 209 push @tt, $move;
1117 } elsif (my $promote = ((($move) >> 6) & 0x7)) {
1118 259 ▶ if ((GOOD_PROMO_MASK >> $promote) & 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (36 >> $promote & 1) { } 129 130 259
1119 129 push @promotions, $move;
1120 } else {
1121 130 push @quiet, $move;
1122 }
1123 } elsif ($position->moveGivesCheck($move)) {
1124 3952 push @checks, $move;
1125 } elsif (((($move) >> 3) & 0x7)) {
1126 2085 my $see = $position->SEE($move);
1127 2085 ▶ if ($see >= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($see >= 0) { } 1437 648 2085
1128 1437 $good_captures{$move} = $position->SEE($move);
1129 } else {
1130 648 push @bad_captures, $move;
1131 }
1132 } elsif ($move == $k1) {
1133 1 $k1[0] = $move;
1134 } elsif ($move == $k2) {
1135 1 $k2[0] = $move;
1136 } elsif ($move == $k3) {
1137 0 $k3[0] = $move;
1138 } else {
1139 17948 push @quiet, $move;
1140 }
1141 }
1142 555 ▶ @good_captures = sort { $good_captures{$b} <=> $good_captures{$a} || $b <=> $a } keys %good_captures;
Condition66%2/3
$good_captures{$b} <=> $good_captures{$a} || $b <=> $a
l!l&&r!l&&!r
9586400
MC/DC0%0/2
$good_captures{$b} <=> $good_captures{$a} || $b <=> $a
$good_captures{$b} <=> $good_captures{$a} $b <=> $a
Truth table66%2/3
A || B
A= $good_captures{$b} <=> $good_captures{$a}B= $b <=> $a
ABresult
1X1
011
000
1143 555 ▶ @bad_captures = sort { $mvv_lva[$b] <=> $mvv_lva[$a] || $b <=> $a } @bad_captures;
Condition33%1/3
$mvv_lva[$b] <=> $mvv_lva[$a] || $b <=> $a
l!l&&r!l&&!r
04600
MC/DC0%0/2
$mvv_lva[$b] <=> $mvv_lva[$a] || $b <=> $a
$mvv_lva[$b] <=> $mvv_lva[$a] $b <=> $a
Truth table33%1/3
A || B
A= $mvv_lva[$b] <=> $mvv_lva[$a]B= $b <=> $a
ABresult
1X1
011
000
1144  
1145 # Apply history bonus and malus to all quiet moves. We store the bonuses
1146 # in the upper 32 bits so that we can do a simple integer sort.
1147 555 my $cutoff_moves = $self->{cutoff_moves}->[$position->[CP_POS_TO_MOVE]];
1148 555 foreach my $move (@quiet) {
1149 18078 $move |= (($cutoff_moves->[($move & 0x1ffe00) >> 9]) << 32);
1150 }
1151 555 @quiet = sort { $b <=> $a } @quiet;
1152  
1153 555 return @pv, @tt, @promotions, @checks, @good_captures, @k1, @k2, @k3, @quiet, @bad_captures;
1154 }
1155  
1156  
1157  
1158 0 ▶sub outputMoveEfforts {
Subroutine outputMoveEfforts: not called CC=3 SCAR=24.8
Pod undocumented
1159 0 my ($self) = @_;
1160  
1161 0 my $sum = 0;
1162 0 ▶ my $all_nodes = $self->{nodes} || 1;
Condition0%0/2
$self->{'nodes'} || 1
l!l
00
MC/DC0%0/1
$self->{'nodes'} || 1
$self->{'nodes'}
Truth table0%0/2
A
A= $self->{'nodes'}
Aresult
11
00
1163 0 foreach my $move (sort { $self->{root_moves}->{$b}->{move_effort} <=> $self->{root_moves}->{$a}->{move_effort} } keys %{$self->{root_moves}}) {
1164 0 my $san = $self->{position}->SAN($move);
1165 0 my $nodes = $self->{root_moves}->{$move}->{move_effort};
1166 0 $sum += $nodes;
1167 0 my $effort = int(0.5 + (100000 * $nodes / $all_nodes));
1168 0 $self->{info}->("Move effort $san: $effort ($nodes nodes)");
1169 }
1170  
1171 0 $self->{info}->("Move effort sum: $sum");
1172 }
1173  
1174 25821 ▶sub printCurrentMove {
Subroutine printCurrentMove: called CC=1 SCAR=0.0
Pod undocumented
1175 25821 my ($self, $move, $moveno) = @_;
1176  
1177 8 ▶ no integer;
Subroutine BEGIN: called CC=1 SCAR=0.0
1178  
1179 25821 my $position = $self->{position};
1180 25821 my $cn = $position->moveCoordinateNotation($move);
1181 25821 my $elapsed = int(1000 * tv_interval($self->{start_time}));
1182  
1183 25821 $moveno += 1;
1184 25821 $self->{info}->("depth $self->{depth} currmove $cn currmovenumber $moveno"
1185 . " time $elapsed");
1186 }
1187  
1188 349 ▶sub think {
Subroutine think: called CC=15 SCAR=33.9
Pod undocumented
1189 349 my ($self) = @_;
1190  
1191 349 my $position = $self->{position};
1192 349 $self->{start} = $position->copy;
1193 349 my @legal = $position->legalMoves;
1194 349 ▶ if (!@legal) {
Branch: 2 branches
BranchTrueFalseTotal
if (not @legal) { } 0 349 349
elsif (1 == @legal) { } 2 347 349
1195 0 my $state = $position->gameOver;
1196 0 ▶ if ($state & (CP_GAME_WHITE_WINS | CP_GAME_BLACK_WINS)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($state & 6) { } 0 0 0
1197 0 $self->{info}->("depth 0 score mate 0");
1198 } else {
1199 0 $self->{info}->("depth 0 score cp 0");
1200 }
1201  
1202 0 return;
1203 } elsif (1 == @legal) {
1204 # This is not good if in ponder mode because there will be no move to
1205 # ponder on. Try to at least get a ponder move from the transposition
1206 # table.
1207 2 my $move = $legal[0];
1208 2 $self->{depth} = 1;
1209 2 $self->printCurrentMove($move, 1);
1210 2 my $ponder_move = $self->getPonderMove($move);
1211 2 $self->printPV([$move]);
1212  
1213 2 ▶ if (defined $ponder_move) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $ponder_move) { } 0 2 2
1214 0 return $move, $ponder_move;
1215 } else {
1216 2 return $move;
1217 }
1218 }
1219  
1220 # Initialize root moves.
1221 347 foreach my $move (@legal) {
1222 15359 $self->{root_moves}->{$move} = {
1223 move_effort => 0,
1224 score => -INF,
1225 previous_score => -INF,
1226 average_score => -INF,
1227 previous_average_score => -INF,
1228 mean_squared_score => -INF * INF,
1229 };
1230 }
1231  
1232 347 ▶ if ($self->{book} && $self->{history_length} < $self->{book_depth}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"book"} and $self->{"history_length"} < $self->{"book_depth"}) 0 347 347
Condition33%1/3
$self->{"book"} and $self->{"history_length"} < $self->{"book_depth"}
!ll&&!rl&&r
34700
MC/DC0%0/2
$self->{"book"} and $self->{"history_length"} < $self->{"book_depth"}
$self->{"book"} $self->{"history_length"} < $self->{"book_depth"}
Truth table33%1/3
A and B
A= $self->{"book"}B= $self->{"history_length"} < $self->{"book_depth"}
ABresult
0X0
100
111
1233 0 my $notation = $self->{book}->pickMove($position);
1234 0 ▶ if ($notation) {
Branch: 1 branch
BranchTrueFalseTotal
if ($notation) 0 0 0
1235 0 my $move = eval { $position->parseMove($notation) };
1236 0 ▶ return $move if $move;
Branch: 1 branch
BranchTrueFalseTotal
if $move 0 0 0
1237 }
1238 }
1239  
1240 # Check for tablebase hit.
1241 347 eval {
1242 0 ▶ local $SIG{ALRM} = sub { $self->checkTime };
Subroutine __ANON__: not called CC=1 SCAR=1.2
1243 347 ualarm UALARM_INTERVAL, UALARM_INTERVAL;
1244 347 $self->tbRankRootMoves;
1245 347 ualarm 0;
1246 };
1247 347 ▶ if ($@) {
Branch: 1 branch
BranchTrueFalseTotal
if ($@) 0 347 347
1248 0 ualarm 0;
1249 }
1250  
1251 # There must always be a valid move in the line.
1252 347 my @line = ($legal[0]);
1253  
1254 347 $self->{thinking} = 1;
1255 347 $self->{tt_hits} = 0;
1256 347 $self->{tt}->newSearch;
1257  
1258 347 ▶ if ($self->{debug}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"debug"}) 0 347 347
1259 0 $self->{info}->("allocated time: $self->{optimum} .. $self->{maximum}");
1260 }
1261  
1262 347 $self->rootSearch(\@line);
1263  
1264 347 delete $self->{thinking};
1265  
1266 # Avoid printing the PV or the best move if the search was cancelled.
1267 # Otherwise, the GUI may be confused. This can actually not happen
1268 # when everybody follows the convention that a "stop" is sent to
1269 # cancel a ponder but we reset the flag in the "stop" handler and are
1270 # good for both cases.
1271 347 ▶ return if $self->{cancelled};
Branch: 1 branch
BranchTrueFalseTotal
if $self->{"cancelled"} 0 347 347
1272  
1273 347 ▶ if (!@line) {
Branch: 1 branch
BranchTrueFalseTotal
unless (@line) 0 347 347
1274 # Search has returned no move.
1275 0 $self->{info}->("Error: pick a random move because of search failure.");
1276 0 $line[0] = $legal[int rand @legal];
1277 }
1278  
1279 347 my $ponder_move = $self->getPonderMove(@line);
1280  
1281 347 ▶ if (defined $ponder_move) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $ponder_move) { } 98 249 347
1282 98 return $line[0], $line[1];
1283 } else {
1284 249 return $line[0];
1285 }
1286 }
1287  
1288 349 ▶sub getPonderMove {
Subroutine getPonderMove: called CC=4 SCAR=13.9
Pod undocumented
1289 349 my ($self, @line) = @_;
1290  
1291 349 ▶ return if !@line;
Branch: 1 branch
BranchTrueFalseTotal
unless @line 0 349 349
1292  
1293 349 ▶ return $line[1] if @line > 1;
Branch: 1 branch
BranchTrueFalseTotal
if @line > 1 98 251 349
1294  
1295 251 my $pos = $self->{position}->copy;
1296  
1297 # Play our move.
1298 251 $pos->move($line[0]);
1299  
1300 # And now try to find an entry in the transposition table.
1301 251 my $signature = $pos->[CP_POS_SIGNATURE];
1302 251 my $tt = $self->{tt};
1303 251 my $tt_move;
1304 251 if (DEBUG) {
1305 $self->debug("probing transposition table for ponder move");
1306 }
1307 # We're not interested in the value.
1308 251 $tt->probe($signature, 1, MAX_PLY + 1, 0, 0, \$tt_move);
1309  
1310 251 if (DEBUG) {
1311 if ($tt_move) {
1312 my $cn = $pos->moveCoordinateNotation($tt_move);
1313 #$self->debug("best move: $cn");
1314 }
1315 }
1316  
1317 251 ▶ return $tt_move if $tt_move;
Branch: 1 branch
BranchTrueFalseTotal
if $tt_move 0 251 251
1318 }
1319  
1320 353 ▶sub tbRankRootMoves {
Subroutine tbRankRootMoves: called CC=8 SCAR=24.1
Pod undocumented
1321 353 my ($self) = @_;
1322  
1323 353 my $tb = $self->{tb};
1324  
1325 353 $self->{tb_root_hit} = 0;
1326  
1327 # Limit probe depth to 0 if table piece count too small.
1328 353 ▶ if ($self->{tb_probe_limit} > $self->{tb_cardinality}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"tb_probe_limit"} > $self->{"tb_cardinality"}) 2 351 353
1329 2 $self->{tb_probe_limit} = $self->{tb_cardinality};
1330 2 $self->{tb_probe_depth} = 0;
1331 }
1332  
1333 353 my $pos = $self->{position};
1334
1335 353 ▶ if (!$pos->[CP_POS_CASTLING_RIGHTS]
Branch: 1 branch
BranchTrueFalseTotal
if (not $pos->[20] and $pos->[19] <= $self->{"tb_probe_limit"}) 6 347 353
Condition100%3/3
not $pos->[20] and $pos->[19] <= $self->{"tb_probe_limit"}
!ll&&!rl&&r
33446
MC/DC100%2/2
not $pos->[20] and $pos->[19] <= $self->{"tb_probe_limit"}
not $pos->[20] $pos->[19] <= $self->{"tb_probe_limit"}
Truth table100%3/3
not(A) and B
A= not $pos->[20]B= $pos->[19] <= $self->{"tb_probe_limit"}
ABresult
0X0
100
111
1336 && $pos->[CP_POS_POPCOUNT] <= $self->{tb_probe_limit}) {
1337 6 ▶ if ($self->{use_time_management}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"use_time_management"}) 0 6 6
1338 0 my $min_time = $self->{tb_7} / (5 ^ (7 - $pos->[CP_POS_POPCOUNT]));
1339 0 ▶ if ($min_time < $self->{tb_3}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($min_time < $self->{"tb_3"}) 0 0 0
1340 0 $min_time = $self->{tb_3};
1341 }
1342 0 ▶ if ($self->{maximum} < $min_time) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{"maximum"} < $min_time) 0 0 0
1343 0 return;
1344 }
1345 }
1346 6 ▶ $self->{tb_root_hit} = 1 if $self->tbRootProbe;
Branch: 1 branch
BranchTrueFalseTotal
if $self->tbRootProbe 6 0 6
1347 }
1348 }
1349  
1350 6 ▶sub tbRootProbe {
Subroutine tbRootProbe: called CC=32 SCAR=49.1
Pod undocumented
1351 6 my ($self) = @_;
1352  
1353 6 my $pos = $self->{position}->copy;
1354  
1355 6 my $tb = $self->{tb};
1356  
1357 # Probe for the outcome of the game.
1358 6 my $wdl = $tb->safeProbeWdl($pos);
1359 6 ▶ return if !defined $wdl;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $wdl 0 6 6
1360  
1361 6 my $wdl_sign = $wdl <=> 0;
1362  
1363 # First determine whether we are winning or losing.
1364 6 my $winning = $wdl > 0;
1365 6 ▶ if ($wdl == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($wdl == 0) 0 6 6
1366 # In case of a draw, we want to escape there, if we are behind.
1367 0 my $static_eval = $pos->evaluate;
1368 0 $winning = $static_eval > 0;
1369 }
1370  
1371 # Pass 1. Probe all root moves.
1372 6 my $root_moves = $self->{root_moves};
1373 6 my @backup = @$pos;
1374  
1375 # Pass 2.
1376 # Discard all moves that change the outcome of the game. They cannot be
1377 # part of the PV.
1378 #
1379 # We want to order the moves by the DTZ of the position after the move
1380 # has been made.
1381 6 foreach my $move (keys %{$root_moves}) {
1382 134 my $san = $pos->SAN($move);
1383 134 $pos->move($move);
1384  
1385 134 $root_moves->{$move}->{tb_wdl} = $tb->safeProbeWdl($pos);
1386 # We consider a missing WDL table a configuration error.
1387 134 ▶ return if !defined $root_moves->{$move}->{tb_wdl};
Branch: 1 branch
BranchTrueFalseTotal
unless defined $root_moves->{$move}{"tb_wdl"} 0 134 134
1388  
1389 134 ▶ if (($root_moves->{$move}->{tb_wdl} <=> 0) != -$wdl_sign) {
Branch: 1 branch
BranchTrueFalseTotal
if (($root_moves->{$move}{"tb_wdl"} <=> 0) != -$wdl_sign) 42 92 134
1390 42 delete $root_moves->{$move};
1391 42 goto UNDO_MOVE;
1392 }
1393  
1394 # First, get mate, stalemate out of the way.
1395 92 my @legal = $pos->legalMoves;
1396 92 ▶ if (!@legal) {
Branch: 1 branch
BranchTrueFalseTotal
unless (@legal) 0 92 92
1397 0 ▶ if ($pos->inCheck || !$winning) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pos->inCheck or not $winning) { } 0 0 0
Condition0%0/3
$pos->inCheck or not $winning
l!l&&r!l&&!r
000
MC/DC0%0/2
$pos->inCheck or not $winning
$pos->inCheck not $winning
Truth table0%0/3
A or not(B)
A= $pos->inCheckB= not $winning
ABresult
1X1
011
000
1398 # We have found a mate or stalemate. Our single-threaded
1399 # engine cannot be used for multiPV analysys. We can just as
1400 # well bypass the search altogether and return the winning
1401 # move.
1402 0 $self->{root_moves} = { $move => $self->{root_moves}->{$move} };
1403 0 return;
1404 } else {
1405 # A stalemate but we are winning.
1406 0 delete $root_moves->{$move};
1407 0 goto UNDO_MOVE;
1408 }
1409 }
1410  
1411 # Does the move result in a draw by insufficient material?
1412 92 ▶ if ($pos->insufficientMaterial) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pos->insufficientMaterial) 0 92 92
1413 0 ▶ if ($winning) {
Branch: 1 branch
BranchTrueFalseTotal
if ($winning) { } 0 0 0
1414 # Don't even consider that move.
1415 0 delete $root_moves->{$move};
1416 0 goto UNDO_MOVE;
1417 } else {
1418 # Force playing this move.
1419 0 $self->{root_moves} = { $move => $self->{root_moves}->{$move} };
1420 0 return;
1421 }
1422 }
1423  
1424 # If the probe fails, treat all moves equally.
1425 92 ▶ my $dtz = -$tb->safeProbeDtz($pos) // 0;
Condition50%1/2
-$tb->safeProbeDtz($pos) // 0
l!l
920
MC/DC0%0/1
-$tb->safeProbeDtz($pos) // 0
-$tb->safeProbeDtz($pos)
Truth table50%1/2
A
A= -$tb->safeProbeDtz($pos)
Aresult
11
00
1426  
1427 # We will later try to filter out moves that will result in an
1428 # unwanted draw by the 50-move-rule.
1429 92 my $hmc = $pos->[CP_POS_HALFMOVE_CLOCK];
1430  
1431 92 ▶ if ($hmc == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($hmc == 0) { } 0 92 92
1432 # The current move is a pawn push or capture. The DTZ is that
1433 # of the next endgame phase. Compared to the DTZ before that, it will
1434 # make a leap and is useless for move ordering. Therefore, we
1435 # use the DTZ from the position before which was -1, -101, 0, 1, or
1436 # 101. However, the position before hasn't been probed. But we can
1437 # deduce the value from the WDL:
1438 0 $dtz = (-67 * $wdl * $wdl * $wdl + 269 * $wdl) >> 1;
1439 } else {
1440 # We have already handled stalemate and draw because of
1441 # insufficient material. Now check the draws that have to be
1442 # claimed.
1443  
1444 # Check for draw by 3-fold repetition. Unlike the normal
1445 # search, the root search has to check that this is really
1446 # the 3rd repetition.
1447 92 my $signature = $pos->[CP_POS_SIGNATURE];
1448 92 my @repetitions = grep { $_ == $signature } @{$self->{signatures}};
1449 92 my $is_draw = @repetitions > 1;
1450  
1451 92 $root_moves->{$move}->{tb_draw} = $is_draw;
1452  
1453 # Correct the DTZ by 1 and apply the offset for the first move.
1454 92 ▶ if ($dtz > 0) {
Branch: 2 branches
BranchTrueFalseTotal
if ($dtz > 0) { } 92 0 92
elsif ($dtz < 0) { } 0 0 0
1455 92 ++$dtz;
1456 } elsif ($dtz < 0) {
1457 0 --$dtz;
1458 }
1459  
1460 92 ▶ if ($is_draw) {
Branch: 1 branch
BranchTrueFalseTotal
if ($is_draw) { } 0 92 92
1461 0 $root_moves->{$move}->{tb_rank} = 0;
1462 } else {
1463 92 $root_moves->{$move}->{tb_rank} = $dtz;
1464 }
1465 }
1466  
1467 92 $root_moves->{$move}->{tb_abs_dtz} = $hmc - 1 + abs $dtz;
1468  
1469 134 UNDO_MOVE: @$pos = @backup; # Undo move.
1470 }
1471  
1472 6 ▶ if ($self->{tb_50_move_rule}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->{'tb_50_move_rule'}) { } 6 0 6
1473 6 my (@drawing, @rule50, @other);
1474 6 foreach my $move (keys %{$root_moves}) {
1475 92 my $root_move = $root_moves->{$move};
1476  
1477 92 ▶ if ($root_move->{tb_rank} == 0) {
Branch: 2 branches
BranchTrueFalseTotal
if ($root_move->{'tb_rank'} == 0) { } 0 92 92
elsif ($root_move->{'tb_abs_dtz'} > 100) { } 86 6 92
1478 0 push @drawing, $move;
1479 } elsif ($root_move->{tb_abs_dtz} > 100) {
1480 86 push @rule50, $move;
1481 } else {
1482 6 push @other, $move;
1483 }
1484 }
1485  
1486 6 ▶ if ($winning) {
Branch: 1 branch
BranchTrueFalseTotal
if ($winning) { } 6 0 6
1487 6 ▶ if (@other) {
Branch: 1 branch
BranchTrueFalseTotal
if (@other) { } 4 2 6
1488 4 delete @{$root_moves}{@drawing};
1489 4 delete @{$root_moves}{@rule50};
1490 } else {
1491 2 my $min_dtz = min map { $root_moves->{$_}->{tb_abs_dtz }} keys %$root_moves;
1492 2 foreach my $move (keys %$root_moves) {
1493 36 ▶ delete $root_moves->{$move} if $root_moves->{$move}->{tb_abs_dtz} != $min_dtz;
Branch: 1 branch
BranchTrueFalseTotal
if $root_moves->{$move}{"tb_abs_dtz"} != $min_dtz 34 2 36
1494 }
1495 }
1496 } else {
1497 0 ▶ if (@drawing) {
Branch: 1 branch
BranchTrueFalseTotal
if (@drawing) 0 0 0
1498 0 delete @{$root_moves}{@other};
1499 }
1500 }
1501 6 ▶ $self->{tb_outcome} = $wdl == WDL_WIN ? 20000 : $wdl == WDL_LOSS ? -20000 : 0;
Branch: 2 branches
BranchTrueFalseTotal
$wdl == 2 ? : 6 0 6
$wdl == -2 ? : 0 0 0
1502 } else {
1503 0 my (@drawing, @other) = @_;
1504  
1505 0 foreach my $move (keys %{$root_moves}) {
1506 0 my $root_move = $root_moves->{$move};
1507 0 ▶ if ($root_move->{tb_rank} == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($root_move->{'tb_rank'} == 0) { } 0 0 0
1508 0 push @drawing, $move;
1509 } else {
1510 0 push @other, $move;
1511 }
1512 }
1513  
1514 0 ▶ if ($winning) {
Branch: 1 branch
BranchTrueFalseTotal
if ($winning) { } 0 0 0
1515 0 ▶ if (@other) {
Branch: 1 branch
BranchTrueFalseTotal
if (@other) 0 0 0
1516 0 delete @{$root_moves}{@drawing};
1517 }
1518 } else {
1519 0 ▶ if (@drawing) {
Branch: 1 branch
BranchTrueFalseTotal
if (@drawing) 0 0 0
1520 0 delete @{$root_moves}{@other};
1521 }
1522 }
1523 0 $self->{tb_outcome} = 20000 * $wdl_sign;
1524 }
1525  
1526 6 return $self;
1527 }
1528  
1529 # Fill the lookup table for the move values.
1530 8 foreach my $mover (CP_PAWN .. CP_KING) {
1531 48 my @piece_values = (
1532 0,
1533 CP_PAWN_VALUE,
1534 CP_KNIGHT_VALUE,
1535 CP_BISHOP_VALUE,
1536 CP_ROOK_VALUE,
1537 CP_QUEEN_VALUE,
1538 );
1539  
1540 48 foreach my $victim (CP_NO_PIECE, CP_PAWN .. CP_QUEEN) {
1541 288 my $index = ($victim << 6) | ($mover << 3);
1542 288 ▶ my $value = $victim ? ($piece_values[$victim] - $mover) : 0;
Branch: 1 branch
BranchTrueFalseTotal
$victim ? : 240 48 288
1543 288 $move_values[$index] = $value;
1544 288 ▶ my $key = (CP_PIECE_CHARS->[0]->[$victim] || ' ') . CP_PIECE_CHARS->[0]->[$mover];
Condition100%2/2
[['', 'P', 'N', 'B', 'R', 'Q', 'K'], ['', 'p', 'n', 'b', 'r', 'q', 'k']]->[0][$victim] || ' '
l!l
24048
MC/DC100%1/1
[['', 'P', 'N', 'B', 'R', 'Q', 'K'], ['', 'p', 'n', 'b', 'r', 'q', 'k']]->[0][$victim] || ' '
[['', 'P', 'N', 'B', 'R', 'Q', 'K'], ['', 'p', 'n', 'b', 'r', 'q', 'k']]->[0][$victim]
Truth table100%2/2
A
A= [['', 'P', 'N', 'B', 'R', 'Q', 'K'], ['', 'p', 'n', 'b', 'r', 'q', 'k']]->[0][$victim]
Aresult
11
00
1545 288 ▶ if ($mover == CP_PAWN) {
Branch: 1 branch
BranchTrueFalseTotal
if ($mover == 1) 48 240 288
1546 48 foreach my $promote (CP_KNIGHT .. CP_QUEEN) {
1547 192 $move_values[$index | $promote]
1548 = $value + $piece_values[$promote] - CP_PAWN_VALUE;
1549 192 my $pc = CP_PIECE_CHARS->[0]->[$promote];
1550 192 my $pvalue = $value + $piece_values[$promote] - CP_PAWN_VALUE;
1551 }
1552 }
1553 }
1554 }
1555  
1556 8 my @mvv_lva_values = (
1557 0, CP_PAWN_VALUE, CP_KNIGHT_VALUE, CP_BISHOP_VALUE,
1558 CP_ROOK_VALUE, CP_QUEEN_VALUE, 2 * CP_QUEEN_VALUE,
1559 );
1560 8 foreach my $victim (CP_PAWN .. CP_QUEEN) {
1561 40 foreach my $attacker (CP_PAWN .. CP_KING) {
1562 240 $mvv_lva[($victim << 3) | $attacker] =
1563 100 * $mvv_lva_values[$victim] - $mvv_lva_values[$attacker];
1564 240 my $idx = ($victim << 3) | $attacker;
1565 }
1566 }
1567  
1568 8 1;
↑ Summary Plisco/Tablebase.pm »