What fuel is
The platform counts every instruction a bot runs. A unit that runs out stops mid-turn and carries on next round, one round late.
How the worst case is computed
The proof reads the compiled program, the exact file the platform meters. It never runs a game. It adds up the cost of every path a turn can take.
The fourth rule is what makes it work. A search loop has no fixed length, so no checker can bound it. But a loop that first asks “do I still have k fuel?” can never spend past the budget, however many times it runs. So the bot can search as deep as a turn allows and still be proved.
A guard in the bot
struct arrival {
static constexpr std::uint64_t k = 10156;
…
};
…
if (!world::fits<guard::arrival>()) return;
The step after it runs only with 10,156 fuel left. Nobody picks that number: after each change, one command raises every guard that falls short to the least value that still proves.
- Change the bot
- prove --raise
- Thresholds rewritten
- Proved, or the path that isn't
Designing code to a budget
The proof became a design tool. Once a build is analysed it answers in 0.02 seconds what one function costs at worst, how much fuel is left when it starts, and which path is the dearest.
Proved worst case of one call, by function, 13 Nov
Two rewrites it guided
- Before
- After
Proof and measurement, side by side
I asked for both: the worst case any game could cost, and what each function really spent in a played game.
| The proof | The meter | |
|---|---|---|
| Answers | the worst any game could cost | what this game did cost |
| Reads | the compiled program | one played game, function by function |
| Checked by | fuzzing its charges against the platform's own | 8,664 turns summing to the platform's count exactly |
| Speed | 0.02 s a question, once analysed | 3 to 6 s a game |
Four days from idea to proof
- I ask for it“Every decision branch is going to fit within the fuel.” Agents start the design three minutes later.
- First version, in Python5,085 lines, reviewed eight times the same day.
- Rewritten in C++Same answers on 114 of 115 test programs. On my first bot, 64 seconds became 2.6.
- The bot proves for the first timeThat morning it had failed for 86 reasons.
- Every guard gets a nameFrom 7 Nov one command sets their thresholds after each change.
- Proof at release, not at every testTests then started their first games in 5.6 seconds instead of 13.6.
Did it matter?
Turns out of fuel, per 100,000 played online
Two of the top three teams ran out of fuel over a hundred times more often. Mine never had to wonder.
What I’d keep
A proof is slower to live with than a test: at its worst, a single threshold raise took 2 h 46. Running it at release instead of at every test kept its guarantee and gave the speed back.
- 13 Nov, 06:11
- 13 Nov, 10:54
On the last day I had agents make the code cheaper instead of adding more guards: in under five hours, cut-short decisions fell from 3.2% of turns to 0.2%.