[Computer Chess] How many Elo is a megabyte worth? I built a clock that can measure it

Every engine author has a feeling for what a bigger hash table is worth. I wanted a number, so I built a clock that could give me one.

The short version, for one alpha-beta engine at 100 ms a move (a shogi engine; the smaller chess sample is further down):

About 5 MiB of history tables was worth more than four times the thinking time. Sixteen times the hash table was inside the error bars.

I don't think this is a law of nature. I think it is one engine at one speed, and I would like you to try to break it. The rest of this post is how the measurement works, what it does not show, and how to run it on your own engine.

The clock: count instructions, not seconds

Measuring small effects with a wall clock is hard. Hardware differs, servers get busy, and time losses add noise that has nothing to do with the engine.

So I removed the wall clock. Before an engine runs, its WebAssembly is rewritten so that every executed instruction is counted. go movetime 100 means 4 billion instructions. clock_time_get returns a virtual time built from that count, so an engine that watches the clock works unchanged.

• The same game is produced on a phone, a laptop and a server.
• A timeout is a fact you can replay, not a busy machine.
• A faster CPU does not search deeper. Only the code does.

In the 1,039 games behind this post there were no time losses, no illegal moves and no crashes.

The exchange rate between memory and time

With a clock like that, "half the thinking time" is exact: half the instructions. So I could measure the price of time directly, by playing the same build against itself.

Halving time costs more the less of it you have: about 200 Elo from 100 to 50 ms, and over 300 from 25 to 12.5 ms.

Then I varied memory and kept time fixed. A simple additive model (Elo = time term + configuration term) fits all the games, and adding interaction terms did not improve the fit. That is what gives an exchange rate: the history tables' roughly +570 Elo equals about 4.5x thinking time. The bigger hash table's +37 equals about ten milliseconds.

What this does not show

Please read these before quoting the table.

• It is one engine, and it plays shogi. It is a conventional iterative-deepening alpha-beta searcher, but it is not your engine. The shogi sample is 935 games.
• "History off" is a blunt switch. It also disables the search corrections that depend on those tables. Read it as "all history-driven machinery", not move ordering alone.
• The hash table does not saturate at this speed. At 25 to 100 ms this search does not fill it. At longer time controls I would expect a different answer.
• The 16 MiB build is 35 MiB in total, which is above the arena's 32 MiB cap. I lifted the cap to measure it.
• The chess sample is small. 104 games, many of them draws. Time mattered less than in shogi (100 ms vs 50 ms: +44 Elo). With memory charged as described below, hash tables of 128 KiB, 1 MiB and 16 MiB were all inside the error bars (±140).
• Instruction counts are not seconds. Division and square root are counted heavier, but caches are not modelled, and a SIMD instruction counts as one. A 16 MiB table that misses the cache on real hardware looks better here than it should, and it still did not pay.

Why I measured it: memory pays rent

If you only limit time, memory is free, and the winning move is to fill everything with tables. I wanted small engines to be the point, so in the arena I run, memory is charged from the same clock.

The measurement above is how I chose that curve. Under it, the build with a 1 MiB hash table (62 ms usable) scored +63 ±98 against the build with 4 MiB (53 ms usable), and the 35 MiB build (33 ms usable) lost 182 ±110. Memory that earns its strength survives. Memory taken for its own sake does not.

So the question for your engine becomes concrete: which of your tables would you keep if each megabyte cost you milliseconds?

Run it on your own engine

The referee is a single file with the same checks, rules and instruction clock as the server. Your engine needs to be a WASI command (Rust wasm32-wasip1, or C and C++ with wasi-sdk), single-threaded, speaking UCI.

ARENA=https://tinyai.run curl -sf $ARENA/tools/arena.mjs -o arena.mjs node arena.mjs check engine.wasm node arena.mjs play small-hash.wasm --opponent big-hash.wasm --games 40 

Build your engine twice with different table sizes and play them. The games run under the arena's rules, rent included. If your result contradicts mine, that is the reply I am hoping for.

No engine yet? There is a starter: one dependency-free Rust file (MIT) with legal move generation, iterative-deepening alpha-beta and a simple evaluation, about 90 KB built. The manual starts from an empty folder.

The arena

The clock and the rent are the rules of tinyai.run, a rated ladder for small chess and shogi engines.

• WASM up to 4 MiB, data up to 8 MiB, memory up to 32 MiB, 100 ms a move.
• UCI with uci, isready, position and go movetime 100 only. Every game is a fresh process.
• Engines are private by default, and the arena never hands out a submitted WASM. Please submit only code you have the right to submit, and credit the engine yours builds on.
• Ratings are on the arena's own scale. They are not comparable to CCRL or TCEC, and this is not a replacement for either.

It opened on November 11. The first outside author arrived 14 hours later with a shogi engine that lost 47 of its first 49 games, came back two hours later with a new version, and won 10 of the next 37. The same author's chess engine is 99 KiB and uses under 1 MiB, so it pays no rent at all.

The chess ladder is nearly empty: the anchor, the gate engine and that one engine. The first 32 authors through the gate get a permanent GEN-0 mark. Seat #1 is taken.

The full contract is in the spec. The tradition of tiny engines is far older than this site (micro-Max and Toledo Nanochess did more with a few kilobytes than most of us do with megabytes), and I would rather be corrected by people from it than be wrong quietly.