Skip to content

Kestrel 3.1

Choose a tag to compare

@Alon-Berg Alon-Berg released this 07 Nov 21:06
· 19 commits to main since this release

Kestrel 3.1

More search threads and a much larger hash, for computers with many cores. The network, the search, the evaluation and the time management are those of 3.0: with one thread Kestrel 3.1 plays exactly like 3.0 (the same depth-12 bench, 859,322 nodes; 24 test positions searched to depth 16 (13.1 million nodes), and with go nodes 30000, give identical nodes, scores, best moves and principal variations in the release builds of both).

What is new compared with 3.0

  • Threads up to 128 (3.0: 8). The search code is compiled once per thread, so every thread owns its tables (history, correction history, position, ...) as in 3.0; there are now 128 copies, made from the 3.0 source by scripts/make_threads.py, which checks that all copies are identical. The default is still 1 thread. A launcher thread starts the helper threads (about 50 - 100 microseconds each, 6 - 14 ms for 127 helpers) while the main search already runs: the first info line comes after 0.6 ms (median) with 128 threads, as with one thread (0.5 ms). After stop the 127 helpers need 11 ms (median, 20 ms at most) to finish.
  • Hash up to 1,048,576 MB (3.0: 4096). The table size is still a power of two (a request is rounded down: 24,000 MB gives a table of 16,384 MB). On Windows and Linux a request above three quarters of the installed memory is cut to that size, with an info string line, so that a mistyped value cannot page the computer to death; if the operating system refuses an allocation the engine still falls back to smaller tables and now says so. Big tables are cleared by many threads: 16 GB are allocated and zeroed in about 1 s and ucinewgame clears them in about 1 s (one clearing thread: 4.6 s and 4.4 s on the same computer).
  • A node limit counts the main thread only. go nodes N and UCI_LimitStrength used to stop as soon as any thread had searched N nodes. With several threads the first helper got there before the main thread had finished depth 1, and the best-ordered move was played (in a won queen-and-knight against king ending, the stalemating move: 3.0 with 8 threads in 37 of 40 tries). Now only the main thread's count ends the search; the nodes of the info lines (all threads) can be larger than N. For a limited-strength engine use one thread.
  • Short move times with many threads. In 3.0 think() started all helper threads before the main search began: 127 threads take 6 - 14 ms on a computer with enough processors and 35 - 100 ms and more with fewer processors than threads or a busy computer, which with a hard limit of 45 ms (go movetime 60) was most or all of the time, and the first time check of a thread runs at node 0, so a search whose hard limit had passed by then ended without any result and the best-ordered legal move was played. On a quiet 22-processor laptop, in a won queen ending in which a quiet king move is stalemate (visible from depth 2 on), 31 of 60 such searches with 128 threads (5 of 60 with 64 threads) ended before depth 1; with only a rule that a time limit cannot end a search before depth 1 has completed, 18 of 60 stopped at depth 1 and played the stalemating move (64 threads: 3 of 60). Now a launcher thread starts the helpers and the main search begins at once, and a time limit cannot end a search before depth 1 has completed: 0 of 60 at 64 and at 128 threads, last depth 12 (median), and 0 of 30 with 24 busy programs competing for the processors. The code of 3.0 is the same, but 3.0 starts at most 7 helpers. stop and node limits are not affected, and with one thread nothing changes. tests/breakers.py --threads 64 found the problem; new test: tests/depth1_test.py.
  • Windows: starting the helpers when there are more threads than processors. The launcher thread runs at a higher priority than the search. With more threads than processors the helpers that were already running kept it waiting: starting 127 helpers took 2.6 s (median) on a 22-processor laptop and up to 20 s in a build without this, 35 ms (108 ms at most) with it, and the main search no longer waits for it at all.
  • Smaller memory footprint at few threads. ucinewgame clears the tables of the search copies that were started since the last clear only; the pawn table of every copy starts as zeros and is no longer stored in the executable. The Windows x86-64-v3 exe is 81.6 MB (3.0: 88.4 MB). Every search copy reserves 6.3 MB of address space, so the process commits about 0.84 GB when idle against 79 MB for 3.0; a one-thread game uses about the same resident memory as in 3.0 (97 MB against 67 MB with a 16 MB hash).

Strength with more threads

On my laptop (22 logical processors) 8 threads score +123 ± 24 Elo against 1 thread of the same build at 10 s + 0.1 s per game (200 games with a development build: 85 won, 17 lost, 98 drawn) and +108 ± 38 Elo with the release exe (100 games: 38 won, 8 lost, 54 drawn); all games finished normally. More threads than the computer has processors do not help: 64 and 128 threads on the same 22 processors scored +11 ± 71 and +11 ± 57 against 1 thread (32 games each), and the 128-thread engine lost one game on time. Use at most as many threads as there are logical processors, and raise Move Overhead to 50 - 100 ms with 64 or more threads. I could not test a computer with many more processors.

Lazy SMP does not scale linearly. On this laptop (6 performance cores with two threads each, 8 efficiency cores, 2 low-power cores; 76 MB of network weights that all threads read) the nodes per second grow 2.9 times with 8 threads and 3.7 times with 20, and the time to reach a fixed depth does not shrink, because every thread runs slower when the others are busy. Counted in nodes, the search needs 1.4 / 1.8 / 3.0 / 3.7 / 4.4 times as many nodes in total to finish depth 20 with 2 / 4 / 8 / 16 / 20 threads, and 5.1 / 7.3 / 9.2 times with 32 / 64 / 128 threads (these three on 22 processors); if every thread ran as fast as a thread of the one-thread search, the time to depth would shrink by about 1.4 / 2.3 / 2.6 / 4.4 / 4.5 / 6.3 / 8.8 / 14 times with 2 / 4 / 8 / 16 / 20 / 32 / 64 / 128 threads. Raw results: logs/threads_3_1.txt.

What did not change

The network (the file of 3.0), the search, the evaluation, the time management, Syzygy support and every other option. The strength of 3.0 against 2.3 (+130 ± 8 Elo, one thread) holds for 3.1 with one thread; see the notes of 3.0.

Which file do I need?

File For
Kestrel-3.1-windows-x86-64-v3.zip Windows 64-bit, AVX2 + BMI2 CPUs (recommended)
Kestrel-3.1-windows-x86-64-v2.zip Windows 64-bit, SSE4.2 + POPCNT CPUs
Kestrel-3.1-windows-x86-64.zip Windows 64-bit, any CPU
Kestrel-3.1-linux-x86-64-v3.tar.gz Linux x86-64, AVX2 + BMI2 CPUs
Kestrel-3.1-linux-x86-64-v2.tar.gz Linux x86-64, SSE4.2 + POPCNT CPUs
Kestrel-3.1-linux-x86-64.tar.gz Linux x86-64, any CPU
Kestrel-3.1-linux-arm64.tar.gz Linux ARM64
Kestrel-3.1-macos-x86-64.tar.gz macOS, Intel Macs
Kestrel-3.1-macos-arm64.tar.gz macOS, Apple Silicon (M1 and newer)

The three Windows builds are also attached as plain .exe files (same program as in the zips; a plain exe has no opening book: put claude_book.txt next to it and switch OwnBook on if you want it). kestrel_net_3_1.bin is the network alone (the same file as kestrel_net_3_0.bin; needed only to build from source or to load with EvalFile).

Only the x86-64-v3 builds have the AVX2 evaluation code (CPU with AVX2 and BMI2: most PCs since 2015). The v2 and generic builds work on older CPUs but are about 37 % slower.

Status of each build

  • Windows: all three builds were run here; each gives the same depth-12 bench (859,322 nodes), so the plain code and the AVX2 code agree exactly, and the x86-64-v3 build plays exactly like the 3.0 build with one thread (24 positions to depth 16, 13.1 million nodes, and with go nodes 30000: identical nodes, scores, best moves and principal variations). Both black-box audits pass (83 of 83 and 31 of 31). All 20 test scripts of the repository (tests/) pass on the packaged x86-64-v3 exe, among them tests/breakers.py (807 checks) with 1, 8 and 64 threads and with 16 threads and tablebases (1207 checks), and tests/stress_stop.py with 16, 64 and 128 threads; the new tests/depth1_test.py passes too (128 threads, go movetime 60: every search searches, no stalemating move). The Syzygy test against python-chess (3-4-5 men): 1,500 positions, 0 mismatches; root filter 1,483 positions, 0 problems; search 60 positions, 0 problems; conversion 30 of 30 won endgames. The sanitizer verification of the release source (GCC and clang AddressSanitizer + UBSan builds, also with 4 threads) passed 30 of 30 checks; an AddressSanitizer + UBSan build of the release source with up to 128 threads passed 16 of 17 steps (thread stress at 2 to 128 threads, hash tests, the UCI fuzzer, tests/breakers.py --quick with 8 and 64 threads, ...); the one step that stops, tests/edge_test.py, stops at the two FEN-parser spots listed under Known limits.
  • Linux and macOS: compiled with Zig and checked for file format, but not run (I have no machine to run them on). The workflow in .github/workflows/verify-release.yml runs the published files on GitHub's Linux, macOS and Windows machines (bench, a UCI session, 128 threads with a 2 GB hash, the Syzygy test with the 3- and 4-men files, on Linux the whole test suite including 64 and 128 threads) and builds the source with AddressSanitizer and UBSan; the thread code of 3.1 runs on those systems for the first time there. The macOS Intel build is run by the workflow on GitHub's Intel Mac machine after the release is published (I have no Mac myself).
  • The exe is about 82 MB and is not code-signed; some virus scanners are suspicious of big unsigned programs (1.0 had a false positive, see docs/BUILDING.md).

Known limits

  • The threads are started and stopped for every search (a thread pool is not implemented): with 128 threads on a 22-processor laptop go movetime 60 took 50 ms in the median but once 328 ms in 60 searches, and about 0.8 s (median) when 24 other programs kept all processors busy; on a computer with 128 processors starting 127 threads takes about 14 ms. With a clock and many threads use a Move Overhead of at least 100 ms.
  • The hash size is a power of two (rounded down). Tables of 32 GB and more (2^31 entries) could not be run on the 31 GB computer where this was made; the index arithmetic is 64-bit everywhere. A big table costs nodes per second (4 KB pages: one thread 1.15 M nps with 64 MB, 0.95 M with 16 GB).
  • On macOS the engine does not know the installed memory and does not cut a Hash request.
  • Windows before Windows 11 / Server 2022 confines a process to one group of at most 64 logical processors; on a computer with more, threads beyond 64 would share those 64. Not tested.
  • Two undefined-behaviour spots of the FEN parser exist in 3.0 and 3.1 (a FEN with a rank that does not add up to eight files; a halfmove clock of 2^31 or more); they are not changed and matter only to a sanitizer build fed with malformed input.

Building from source

src/kestrel_3_1.cpp is generated from src/kestrel_3_0.cpp by scripts/make_threads.py (the 128-copy file is 4.1 MB; g++ -O3 needs about 136 s and 1.1 GB for it on a fast PC, 3.0 needed 16 s and 0.5 GB). It embeds the network with .incbin "kestrel_net.bin", which the assembler looks up in the current directory: download kestrel_net_3_1.bin from this release, save it as kestrel_net.bin in the folder where you run the compiler, then for example

g++ -std=c++17 -O3 -march=x86-64-v3 -static -pthread -DNDEBUG -o kestrel.exe path/to/src/kestrel_3_1.cpp

The network is not stored in the git history (76 MB per version); see docs/BUILDING.md for the other targets.