Skip to content
Thomas Fairhurst
Chapters

Chapter 09 · Fuel

A proof that no turn runs out

Every unit gets 100,000 units of compute a turn. I didn't want to test for that limit, so I had agents build a tool that proves the bot can never cross it, in any game state.

100,000fuel a unit gets each turn
146guards in the final bot, each threshold set by the proof
0turns out of fuel in the live version's 1,402 archived games

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.

1fuel an instructioncounted by the platform's meter
100ka turn200k on the first turn, 10M in the draft
0left overthe unit freezes until next round

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.

a + bone fuel an instruction, added along a path
max(a, b)a branch counts its dearer side
n × bodya loop with a bound the proof can see
budget − k + tailan open-ended loop, behind a guard that needs k fuel left

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

fight_end
17,961
value::fight_read
15,533
value::own_chance
10,563
steps_back
9,284
tactic::value_of
7,404
fight_sides
5,677
race_pass
5,207
strike_first
4,743

Two rewrites it guided

Walking four camp groups, worst case
45,205
3,803
One step's neighbour reads
4,690
560
  • 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 proofThe meter
Answersthe worst any game could costwhat this game did cost
Readsthe compiled programone played game, function by function
Checked byfuzzing its charges against the platform's own8,664 turns summing to the platform's count exactly
Speed0.02 s a question, once analysed3 to 6 s a game

Four days from idea to proof

  1. I ask for it“Every decision branch is going to fit within the fuel.” Agents start the design three minutes later.
  2. First version, in Python5,085 lines, reviewed eight times the same day.
  3. Rewritten in C++Same answers on 114 of 115 test programs. On my first bot, 64 seconds became 2.6.
  4. The bot proves for the first timeThat morning it had failed for 86 reasons.
  5. Every guard gets a nameFrom 7 Nov one command sets their thresholds after each change.
  6. 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

Intercontinental Fishladder #1
0
Claudus Maximus
0
stellar best girltop 3
126
Mitetop 3
242

Two of the top three teams ran out of fuel over a hundred times more often. Mine never had to wonder.

Once the proof had made fuel safe, I could spend it: from 10 Nov the live bot ran its guards at 60% of the proved thresholds, which played 4.9 Elo better at a cost of about 0.6 turns per 100,000.

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.

Turns with a decision cut short for fuel
3.2%
0.2%
Guards
121
101
Longest function, in lines
677
290
  • 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%.