1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
* Minimax improvements
** DONE Alpha beta pruning
- Move ordering too
- Probably after iterative deepening
** DONE Score caching
** Move generation caching?
** DONE Iterative deepening
- Use results of previous searches for move ordering
** DONE Profile to see what needs optimization the most
- =cargo run --profile profiling -- bench 9= (add =--features search-stats= for counters)
- Profile: =perf record -e cycles:u -m 16 --call-graph dwarf target/profiling/tigers-and-sheep-rs bench 9=
(=-m 16= keeps the ring buffer under =perf_event_mlock_kb=, otherwise mmap fails)
- First profile, depth 9: 2056 ms, 2.05 M nodes, ~1.0 M nodes/s
| Where | Share |
|-------------------------------------------+--------------------------|
| Kernel: clock_gettime syscalls | 43% of wall time (sys) |
| SipHash for the cache HashMap | ~29% of user cycles |
| get_moves (2.0 calls/node, Vec each time) | ~22% of user cycles |
| minimax_uncached + inlined evaluate | ~29% of user cycles |
- The kernel time was not the HashMap's page faults, as first thought: the kernel had fallen back
from the TSC to the HPET clock source, so =Instant::now()= at every interior node was a real
syscall (=strace -c=: 99% of syscall time in clock_gettime). After a reboot it was back on TSC.
Check =/sys/devices/system/clocksource/clocksource0/current_clocksource= before comparing timings.
- Search: cache hit rate 29% (1.8 probes/node); 74% of cutoffs on the first move (63% in placement)
** DONE Speed-ups from the profile
All at depth 9 on the TSC clock source; scores and moves the same as the baseline at every step.
| Step | Time ms | Nodes | Nodes/s | 1st-move cutoffs |
|--------------------------------------------+---------+--------+---------+------------------|
| Baseline | 1205 | 2.05 M | 1.7 M | 72% |
| =has_moves= in =check_win= | 1045 | 2.05 M | 2.0 M | 72% |
| =TranspositionTable= (2^20 slots, 24 MB) | 650 | 2.07 M | 3.2 M | 72% |
| Jumps first, killer moves | 572 | 1.67 M | 2.9 M | 97% |
- Table: always-replace needed 2.82 M nodes at 2^20 slots (2.31 M even at 2^22), because the 1.5 M
leaf entries pushed out deeper ones. Two-slot buckets, one kept for the deepest entry, fixed it.
- Ordering: a =sort_by_key= cost ~26% of cycles and made it slower overall than no ordering;
=get_moves= now lists jumps first and the search rotates killers and the hint to the front instead.
- Killers on their own cut nodes 10% but made the opening search bigger (0.93 M -> 1.04 M nodes)
** DONE Symmetric cache
=minimax= looks positions up by =GameBoard::canonical= (smallest =key= of the 8 rotations and
reflections), storing best moves as played on the canonical board. Depth 9 on the HPET clock
source, so the times are only comparable with each other; moves and scores unchanged.
| Step | Time ms | Nodes | Nodes/s (stats build) |
|-------------------------+---------+--------+-----------------------|
| Before | 1170 | 1.67 M | 1.44 M |
| Canonical cache keys | 570 | 0.71 M | 1.24 M |
- The opening (fully symmetric) shrank most: 1.04 M -> 0.23 M nodes. Each probe now does 7 board
transforms of 10 row lookups each, which costs ~14% per node.
*** Next candidates
- Check the deadline every N nodes instead of at every node, so a slow clock source can't cost half the search
- =evaluate=: tiger moves and trapped tigers from bitmasks rather than =get_moves= + 25 =get()= calls
- Table lookups are now the top item (~28% of cycles), mostly cache misses into the 24 MB table
* Draws
* Neural player training
** DONE Tiger bias in self-play
Before the fix, tigers won ~97% of self-play games and the net only reached ~15-20% against
=ClaudePlayer= at depth 3. 200 games each, tigers/sheep/draws:
| Players | Random opening plies | eps | Result |
|-----------+----------------------+------+------------|
| Claude d3 | 10 | 0 | 78/22/100 |
| Claude d3 | 10 | 0.05 | 171/15/14 |
| Neural d3 | 4 | 0 | 197/0/3 |
- Random sheep moves usually hang a sheep, so eps exploration alone tilts games to the tigers, and
TD targets carried those wins back to the positions before the blunders.
- Fix: a position where a random move was played is labelled with its own search score, cutting
the TD chain. Neural d3, 4 random plies, eps 0 became 126/4/70, and against =ClaudePlayer= (100
games, depth 3) it went 12% at gen 5, 50% at gen 50, 50-62% at gens 60-100.
*** Next candidates
- Pick exploratory moves among near-best ones (softmax over root scores) rather than uniformly
- Sheep are still the weaker side: report the match score for each side separately
|
