Evaluation Functions

01From rules to a number

Every example on this page uses light cycles, the game behind CodinGame's Tron Battle. Each player steers a cycle around a grid, the cycle leaves a solid trail behind it, and a player who drives into a trail, a wall or the edge of the board is out. The last cycle moving wins. On CodinGame the grid is 30×20, a battle has two to four players, they move one at a time, and each move must arrive in under 100 ms.^[1] The 2010 Google AI Challenge used the same game with both players moving at once, so two heads could crash into the same cell on the same turn.^[2] The demos here use two players, turn by turn, on smaller boards so they run fast.

A first light-cycle bot is usually a list of rules. Rule one: move toward the side with the most open space. Rule two: don't move next to the opponent's head, because it could cut you off. Each rule makes sense alone. Now put the biggest open area right beside the opponent. Rule one says go, rule two says stay away, and the bot does whatever the rule you happened to write first says, whatever the position looks like.

An evaluation function settles the argument with arithmetic. It looks at a position and returns one number: how good that position is for you, where higher is better. Each thing it measures is a feature, and each feature gets a weight that says how much it counts. The score is the weighted sum.

Written out, the score of a position is a sum with one term per feature:

In words: measure each feature in the position, multiply each one by its weight, and add the results. A bigger total means a better position for the player you're scoring for.

With an evaluation, choosing a move is mechanical. For each legal move, play it on a copy of the board, score the copy, and keep the move with the highest score. That loop is the greedy bot of section 06. The same function sits at the bottom of the searches in Phase 3: alpha-beta (page 5) scores the position at the end of every line of play it looks at, and it looks at a lot of them. Janzert's 2010 Tron bot searched about 30,000 positions per turn at the start of a game on an open 15×15 map, on his own machine.^[3] So an evaluation has to be fast as well as right.

02What to measure

Which numbers should go into the sum? Anything you can compute quickly that tends to be higher in the positions you go on to win. Light-cycle evaluations, like many others, are built from a few recurring kinds of feature, with the details depending on the game.

Two habits keep the sum honest. First, score from one player's side. Territory and mobility work as "mine minus theirs". A shared quantity such as the distance between the heads has no sides, so its weight says whether closeness helps you. A search then treats the opponent's view of a position as your score with the sign flipped: whatever helps you hurts them by the same amount. Page 5 relies on that, so one search function can play both sides.

Second, mind the scales. Features come in different units, and the weights convert them. On a 30×20 board the territory margin can swing by hundreds of cells, while open neighbors runs from 0 to 3 once the cycle is moving (it can't turn back into its own trail). With a weight of 1 on each, open neighbors only decides between moves whose territory is equal, which may be exactly what you want: a tie-breaker. If you meant it to matter more, its weight has to be much bigger.

03Count the cells you reach first

A light-cycle game usually turns on one moment: the trails wall the two cycles off from each other. From then on each player can only fill its own region, and whoever has more room lasts longer. Before that moment, the most useful number is a forecast of how the free cells will be split. A simple forecast: each cell belongs to whoever can get there first.

That forecast is called Voronoi territory. Andy Sloane (a1k0n), who won the 2010 Google AI Challenge, described it as "for each spot on the map, find whether player 1 can reach it before player 2 does or vice versa", and noted that everyone in the contest who had read the forums was already using it.^[4] His starting evaluation added up the cells on each side and subtracted.

Reaching first is a question about distances around walls, and a breadth-first search (BFS) answers it. Start at a head and explore outward in rings: first every free cell one move away, then every free cell two moves away, and so on. The first time the search reaches a cell, the ring number is the shortest route to it around every wall and trail. One BFS from your head and one from the opponent's give two distances for every free cell. Graph Traversal builds BFS step by step if you want the details.

1. Run a BFS from your head. It records how many moves you need to reach every free cell. Trails, walls and both heads block it.
2. Run a BFS from the opponent's head. Same search, other start.
3. Compare the two distances for each free cell. The smaller one owns the cell. Equal distances are a tie and count for nobody, and so does a cell neither head can reach.
4. Subtract. Your cells minus the opponent's cells is the territory margin.

Each BFS visits a free cell at most once and checks its four neighbors, so on CodinGame's 600-cell board one evaluation costs a few thousand simple steps. The ties need one more thought in a game where players move in turn. Of two players the same distance from a cell, the one to move gets there first. Some bots award ties that way. The widget and the code on this page leave ties neutral, which is simpler and close enough for a first evaluation.

Cell counts treat every territory of the same size as equally good, and they aren't. Thirty cells in a 6×5 room leave plenty of ways to fill them. Thirty cells strung along a one-cell corridor leave one way through, and the opponent can cut the corridor in half. A second count tells them apart: for each cell in a territory, how many of its neighbors are open. a1k0n added that count after his bot kept cluttering its own space with aimless early moves, and noted that it led to "automatic wall-hugging behavior when all else was equal".^[4] Each link between two of your cells is counted twice that way, once from each end.

a1k0n then fitted the two weights to data. He took 11,691 games played by the top 100 players of the time, found the turn in each where the players were separated, estimated how many more moves each could have made from there, and used linear regression to choose the two weights: the values that made a weighted sum of the cell and open-neighbor differences on the turns before predict that difference most closely. The fit gave 0.055 per cell and 0.194 per open-neighbor count, so one open neighbor is worth about 3.5 cells. He called the model "pretty far from absolutely great, and only a little predictive", and it still improved his bot in his own tests.^[4]

04Where the count lies

The Chamber board breaks the Voronoi count. Purple "owns" 54 cells to green's 39, a margin of +15, and purple loses. A cycle can never pass through the same cell twice, and purple's head is the only connection between its two rooms. Moving into one room loses the other for good.

A free cell like that, whose loss splits the free space into separate pieces, is an articulation point. The regions it separates are often called chambers. The plain count adds up every chamber a player could reach, but a cycle that enters a chamber through a one-cell door can't come back out the same way, so at most one path of chambers is ever filled.

Finding every articulation point takes a single depth-first search over the free cells, in time proportional to the number of cells plus links between them. Hopcroft and Tarjan published that algorithm in 1973.^[5] As the search goes deeper it records, for each cell, how far back up the current path the cells below it can reach by some other route. If nothing below a cell can get back above it, that cell is an articulation point. Three bots from the 2010 contest built on articulation points in different ways:

• a1k0n split each territory into chambers at its articulation points and valued a territory by the best single path through them, so the evaluation could tell that a player must choose between rooms. He called this "probably the contest-winning idea"; by his recollection it beat his previous version 12–1.^[4]
• Janzert, fifth in the contest,^[6] built a tree of 2-connected chambers in each territory and backed up an upper bound on the space a player can fill from the leaves to the root.^[3]
• dhartmei, 80th, used chambers once the players were separated: from the current room, try walking to each reachable articulation point, recurse into the room behind it, and keep the longest result, stopping early once the count beats the opponent's.^[6]

The upper bound Janzert mentions comes from a checkerboard. Color the board like one: every move goes from one color to the other, so a path alternates colors. a1k0n credits the idea to dmj on the contest forums: "if a given space has a lot more 'red' squares than 'black' squares, the surplus 'red' squares will necessarily be wasted."^[4] A room with 20 cells of one color and 12 of the other lets you fill at most 25 of its 32 cells: the 12 scarce ones, and at most one more of the common color than that.

05Wins, losses and separated boards

An evaluation is a guess about the future. A crashed opponent isn't a guess: the game is over. If a win scores like an ordinary good position, a bot can prefer a big territory margin to the move that ends the game in its favor.

The fix is to score finished games with a constant far outside the range of any guess. On a 30×20 board the territory margin can't exceed 600 cells, so with weights near 1 a win worth 1,000,000 can't be confused with any position the evaluation scores. A loss scores the negative.

Two wins shouldn't tie with each other either, and neither should two losses. A win in 3 moves and a win in 9 aren't equally good: the longer one gives the opponent six more chances to escape, and a search that scores them the same can keep choosing a win that never arrives. Subtract the number of moves until the game ends. Then the bot takes the fastest win, and when every move loses it picks the slowest loss, which leaves the most room for an opponent's mistake.

Separated boards sit in between. Once the trails divide the players, nothing either does can affect the other, and the winner is whoever can fill more cells. That count is far more reliable than a Voronoi forecast, so it deserves a bigger weight. After a separation a1k0n scored a position as 1,000 × (his region's size − the opponent's), with the factor of 1,000 there "to reward certainty in an endgame vs. heuristic positional value".^[4] Raw region sizes overcount for the reason in section 04, and Janzert's bot used its chamber bound on separated regions as well.^[3]

Turn order matters at separation too. In CodinGame's version players move one at a time, so with equal fillable space the player who has to move first runs out first: it makes its last move, the opponent makes its last move, and then it has nowhere to go. A tie in space is a loss for the player to move. In the 2010 contest both players moved at once, and the same position was a draw.

06A one-ply greedy bot

With an evaluation in hand, the simplest complete bot needs one loop. A ply is one move by one player, and a greedy bot takes whatever scores best right now. A one-ply greedy bot looks at its own next move and nothing after it.

1. List the legal moves. A move into a trail, a wall or off the board is a crash, so it never gets scored.
2. Play each move on a copy of the board. Mark the new head cell as taken and move the head.
3. Evaluate the copy. Use the weighted features, from your side.
4. Keep the best. Undo the move, and if its score beats the best so far, remember it. Break ties in a fixed order so the bot is deterministic.

The widget pits that bot against a flood-fill bot, which moves wherever the most cells stay reachable from its head and ignores the opponent. A flood fill is a search that counts every free cell connected to a start cell. The greedy bot uses the formula from the worked example in section 01, with a third feature added: the Manhattan distance between the two heads, which is columns apart plus rows apart.

The interval in the readout is a Wilson interval: the range of true scoring rates that could plausibly have produced this many points in 200 games. Measuring Bot Strength covers it properly. For now, read it as an error bar.

A one-ply bot ignores the opponent's reply. It will happily drive into a corridor because the move looks good this turn, and the opponent then closes the corridor behind it. Page 5 looks further. Still, a one-ply evaluation can go a long way when the evaluation is good. In 2017 the CodinGame player Xavier_F reported reaching Legend in Tron Battle with Python and no search at all: each move was scored by a weighted mix of his own remaining space, each opponent's space, the Voronoi conflict points and the articulation points. He had tried Monte Carlo tree search and alpha-beta first, and concluded that Python was probably the wrong language for either under CodinGame's time limit.^[7] That's one player's report about one game, but it shows how much the evaluation carries.

A common question at this point: if the computer does the searching, where is the skill, and shouldn't everyone's bots end up the same? Most of the skill is in the evaluation. The search that page 5 wraps around it is a few dozen lines of textbook code. What separates bots is what the evaluation measures, how its weights were chosen, which traps it knows about (like the one-cell door in section 04), how it scores endings, and how carefully each change was measured. In 2010 the Voronoi count was common knowledge on the contest forums, and a1k0n called the chamber rule he added on top of it probably the contest-winning idea.^[4]

07Tune the weights by tournament

Weights start as guesses. The usual way to improve them is to change one, play the new version against the old one, and keep the change if it wins. Doing that over and over is hill climbing. The weak spot is the word "wins": a short tournament is a noisy measurement.

A local tournament here means a series of games between two versions of your bot on your own machine, on many different maps. Each map is played twice with the bots swapping starts, so a lucky start cancels out. The trouble is the number of games.

The cure is to check every kept change on held-out games: maps the tuning never saw, many more of them, both seats. The tournament's own score is biased upward by the act of choosing, and a fresh measurement isn't.

The left panel shows the claims: at K = 10 every kept change looks like a big win, because only the lucky tournaments get kept. The right panel shows that bigger tournaments didn't find more real gains in these runs; in run 1 each K found exactly one. A bigger K buys an accurate claim and fewer harmful changes. At K = 200 the claim lands within a few points of the held-out score, and a change that truly scores 45% passes a 10-game test 26% of the time but a 200-game test only 7% of the time.

Tournaments aren't the only way to set weights. a1k0n fitted his by regression on recorded games, as section 03 describes. Either way, measure the final version on maps you never tuned on. Page 9 covers how many games a decision needs and why separate tuning and test maps matter so much.

08Territory and a greedy move in code

These complete programs count Voronoi territory with two breadth-first searches, score a position with the three weighted features from the greedy widget, and choose a one-ply greedy move. Their main functions check boards whose answers you can count by hand: the corridor A...B (one cell each and a tie in the middle), the figure's board from section 03 (2, 2 and 3 ties, with the unreachable column belonging to no one), and the widget's Chamber board, where A counts 54 cells and 87 links to B's 39 and 63, exactly what the widget's kernel reports. They also check that the greedy bot picks the bigger room on the Chamber board, that a distance weight of −1 makes it step toward the opponent, and that a walled-in head has no move to return. Both programs use the same names, so you can read them side by side.

// Voronoi territory with two breadth-first searches, and a one-ply greedy bot, on a grid.
#include <array>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>

constexpr int kUnreached = -1;
constexpr std::array<int, 4> kStepX{0, 1, 0, -1};  // up, right, down, left
constexpr std::array<int, 4> kStepY{-1, 0, 1, 0};

struct Grid {
    int width = 0, height = 0;
    std::vector<bool> blocked;  // walls, trails and both heads
    std::array<int, 2> head{};  // cell index (y * width + x) of each player's head
};

// '#' is a wall, 'A' and 'B' are the two heads, '.' is a free cell.
Grid parse(const std::vector<std::string>& rows) {
    Grid grid;
    grid.height = static_cast<int>(rows.size());
    grid.width = static_cast<int>(rows[0].size());
    for (int y = 0; y < grid.height; ++y)
        for (int x = 0; x < grid.width; ++x) {
            const char symbol = rows[y][x];
            grid.blocked.push_back(symbol != '.');
            if (symbol == 'A') grid.head[0] = y * grid.width + x;
            if (symbol == 'B') grid.head[1] = y * grid.width + x;
        }
    return grid;
}

// The cell one step from `cell` in `direction`, or -1 if the step leaves the board.
int neighbor(const Grid& grid, int cell, int direction) {
    const int x = cell % grid.width + kStepX[direction];
    const int y = cell / grid.width + kStepY[direction];
    if (x < 0 || y < 0 || x >= grid.width || y >= grid.height) return -1;
    return y * grid.width + x;
}

// Breadth-first search from one head: how many moves it takes to reach each free cell.
std::vector<int> distancesFrom(const Grid& grid, int start) {
    std::vector<int> distance(grid.blocked.size(), kUnreached);
    std::vector<int> queue{start};  // cells in the order they were first reached
    distance[start] = 0;
    for (std::size_t next = 0; next < queue.size(); ++next) {
        const int cell = queue[next];
        for (int direction = 0; direction < 4; ++direction) {
            const int target = neighbor(grid, cell, direction);
            if (target < 0 || grid.blocked[target] || distance[target] != kUnreached) continue;
            distance[target] = distance[cell] + 1;  // first visit is the shortest route
            queue.push_back(target);
        }
    }
    return distance;
}

struct Territory {
    int mine = 0, theirs = 0, ties = 0;  // free cells each side reaches first, and draws
    int myEdges = 0, theirEdges = 0;     // side-by-side pairs of cells owned by one side
};

// Who reaches each free cell first? Ties, and cells nobody can reach, count for neither side.
Territory countTerritory(const Grid& grid, int me) {
    const std::vector<int> mine = distancesFrom(grid, grid.head[me]);
    const std::vector<int> theirs = distancesFrom(grid, grid.head[1 - me]);
    std::vector<int> owner(grid.blocked.size(), -1);  // 0 me, 1 them, -1 nobody
    Territory territory;
    for (std::size_t cell = 0; cell < owner.size(); ++cell) {
        if (grid.blocked[cell]) continue;
        const bool iReach = mine[cell] != kUnreached, theyReach = theirs[cell] != kUnreached;
        if (iReach && (!theyReach || mine[cell] < theirs[cell])) { owner[cell] = 0; ++territory.mine; }
        else if (theyReach && (!iReach || theirs[cell] < mine[cell])) { owner[cell] = 1; ++territory.theirs; }
        else if (iReach) ++territory.ties;  // both arrive on the same move
    }
    // Look right and down from every owned cell, so each pair is counted once.
    for (int cell = 0; cell < static_cast<int>(owner.size()); ++cell) {
        if (owner[cell] < 0) continue;
        for (int direction : {1, 2}) {
            const int other = neighbor(grid, cell, direction);
            if (other < 0 || owner[other] != owner[cell]) continue;
            if (owner[cell] == 0) ++territory.myEdges; else ++territory.theirEdges;
        }
    }
    return territory;
}

struct Weights { double territory = 1, openNeighbours = 0, distance = 0; };

// How good the position is for `me`: a weighted sum of three features.
double evaluate(const Grid& grid, int me, const Weights& weights) {
    const Territory territory = countTerritory(grid, me);
    int open = 0;  // free cells next to my head: room for my next move
    for (int direction = 0; direction < 4; ++direction) {
        const int cell = neighbor(grid, grid.head[me], direction);
        if (cell >= 0 && !grid.blocked[cell]) ++open;
    }
    const int dx = grid.head[0] % grid.width - grid.head[1] % grid.width;
    const int dy = grid.head[0] / grid.width - grid.head[1] / grid.width;
    return weights.territory * (territory.mine - territory.theirs)
         + weights.openNeighbours * open
         + weights.distance * (std::abs(dx) + std::abs(dy));
}

// One ply: try each legal move, score the position it leads to, keep the best (the first on a tie).
int chooseMove(Grid grid, int me, const Weights& weights) {
    int bestMove = -1;
    double bestScore = 0;
    const int from = grid.head[me];
    for (int direction = 0; direction < 4; ++direction) {
        const int to = neighbor(grid, from, direction);
        if (to < 0 || grid.blocked[to]) continue;        // a crash is never worth scoring
        grid.blocked[to] = true;  grid.head[me] = to;    // make the move on this copy...
        const double score = evaluate(grid, me, weights);
        grid.blocked[to] = false; grid.head[me] = from;  // ...and take it back
        if (bestMove < 0 || score > bestScore) { bestMove = direction; bestScore = score; }
    }
    return bestMove;  // -1 when every move crashes
}

int main() {
    // A corridor: each head reaches one cell first, and the middle cell is a tie.
    const Territory corridor = countTerritory(parse({"A...B"}), 0);
    assert(corridor.mine == 1 && corridor.theirs == 1 && corridor.ties == 1);

    // Walls, and a column on the right that nobody can reach: it counts for no one.
    const Territory pocket = countTerritory(parse({"A..#.", "...#.", "..B#."}), 0);
    assert(pocket.mine == 2 && pocket.theirs == 2 && pocket.ties == 3);

    // The widget's Chamber board: A counts 54 cells to B's 39, but its head is the only door
    // between a 30-cell room and a 24-cell room.
    const Grid chamber = parse({"......#........",
                                "......#........",
                                "......#...B....",
                                "......#........",
                                "......#........",
                                "###A###########",
                                "......#########",
                                "......#########",
                                "......#########",
                                "......#########"});
    const Territory rooms = countTerritory(chamber, 0);
    assert(rooms.mine == 54 && rooms.theirs == 39 && rooms.ties == 0);
    assert(rooms.myEdges == 87 && rooms.theirEdges == 63);
    // One ply ahead, the greedy bot takes the bigger room: up keeps 29 cells, down keeps 23.
    assert(chooseMove(chamber, 0, Weights{}) == 0);

    // With only a distance weight of -1 ("get closer"), A steps right, toward B.
    assert(chooseMove(parse({".....", "A...B", "....."}), 0, Weights{0, 0, -1}) == 1);

    // Walled in on every side: there is no legal move to return.
    assert(chooseMove(parse({"#A#", "###"}), 0, Weights{}) == -1);
    std::puts("all territory and greedy checks passed");
}

// Voronoi territory with two breadth-first searches, and a one-ply greedy bot, on a grid.
const UNREACHED: i32 = -1;
const STEP_X: [i32; 4] = [0, 1, 0, -1]; // up, right, down, left
const STEP_Y: [i32; 4] = [-1, 0, 1, 0];

#[derive(Clone)]
struct Grid {
    width: i32,
    height: i32,
    blocked: Vec<bool>, // walls, trails and both heads
    head: [usize; 2],   // cell index (y * width + x) of each player's head
}

// '#' is a wall, 'A' and 'B' are the two heads, '.' is a free cell.
fn parse(rows: &[&str]) -> Grid {
    let mut grid = Grid { width: rows[0].len() as i32, height: rows.len() as i32, blocked: Vec::new(), head: [0; 2] };
    for (y, row) in rows.iter().enumerate() {
        for (x, symbol) in row.chars().enumerate() {
            grid.blocked.push(symbol != '.');
            if symbol == 'A' { grid.head[0] = y * rows[0].len() + x; }
            if symbol == 'B' { grid.head[1] = y * rows[0].len() + x; }
        }
    }
    grid
}

// The cell one step from `cell` in `direction`, or None if the step leaves the board.
fn neighbor(grid: &Grid, cell: usize, direction: usize) -> Option<usize> {
    let x = cell as i32 % grid.width + STEP_X[direction];
    let y = cell as i32 / grid.width + STEP_Y[direction];
    if x < 0 || y < 0 || x >= grid.width || y >= grid.height { return None; }
    Some((y * grid.width + x) as usize)
}

// Breadth-first search from one head: how many moves it takes to reach each free cell.
fn distances_from(grid: &Grid, start: usize) -> Vec<i32> {
    let mut distance = vec![UNREACHED; grid.blocked.len()];
    let mut queue = vec![start]; // cells in the order they were first reached
    distance[start] = 0;
    let mut next = 0;
    while next < queue.len() {
        let cell = queue[next];
        next += 1;
        for direction in 0..4 {
            let Some(target) = neighbor(grid, cell, direction) else { continue };
            if grid.blocked[target] || distance[target] != UNREACHED { continue; }
            distance[target] = distance[cell] + 1; // first visit is the shortest route
            queue.push(target);
        }
    }
    distance
}

#[derive(Default)]
struct Territory {
    mine: i32, theirs: i32, ties: i32,  // free cells each side reaches first, and draws
    my_edges: i32, their_edges: i32,    // side-by-side pairs of cells owned by one side
}

// Who reaches each free cell first? Ties, and cells nobody can reach, count for neither side.
fn count_territory(grid: &Grid, me: usize) -> Territory {
    let mine = distances_from(grid, grid.head[me]);
    let theirs = distances_from(grid, grid.head[1 - me]);
    let mut owner = vec![-1; grid.blocked.len()]; // 0 me, 1 them, -1 nobody
    let mut territory = Territory::default();
    for cell in 0..owner.len() {
        if grid.blocked[cell] { continue; }
        let (i_reach, they_reach) = (mine[cell] != UNREACHED, theirs[cell] != UNREACHED);
        if i_reach && (!they_reach || mine[cell] < theirs[cell]) { owner[cell] = 0; territory.mine += 1; }
        else if they_reach && (!i_reach || theirs[cell] < mine[cell]) { owner[cell] = 1; territory.theirs += 1; }
        else if i_reach { territory.ties += 1; } // both arrive on the same move
    }
    // Look right and down from every owned cell, so each pair is counted once.
    for cell in 0..owner.len() {
        if owner[cell] < 0 { continue; }
        for direction in [1, 2] {
            let Some(other) = neighbor(grid, cell, direction) else { continue };
            if owner[other] != owner[cell] { continue; }
            if owner[cell] == 0 { territory.my_edges += 1; } else { territory.their_edges += 1; }
        }
    }
    territory
}

struct Weights { territory: f64, open_neighbours: f64, distance: f64 }

// How good the position is for `me`: a weighted sum of three features.
fn evaluate(grid: &Grid, me: usize, weights: &Weights) -> f64 {
    let territory = count_territory(grid, me);
    let open = (0..4) // free cells next to my head: room for my next move
        .filter_map(|direction| neighbor(grid, grid.head[me], direction))
        .filter(|&cell| !grid.blocked[cell])
        .count();
    let dx = grid.head[0] as i32 % grid.width - grid.head[1] as i32 % grid.width;
    let dy = grid.head[0] as i32 / grid.width - grid.head[1] as i32 / grid.width;
    weights.territory * f64::from(territory.mine - territory.theirs)
        + weights.open_neighbours * open as f64
        + weights.distance * f64::from(dx.abs() + dy.abs())
}

// One ply: try each legal move, score the position it leads to, keep the best (the first on a tie).
fn choose_move(grid: &Grid, me: usize, weights: &Weights) -> Option<usize> {
    let mut grid = grid.clone();
    let mut best: Option<(usize, f64)> = None;
    let from = grid.head[me];
    for direction in 0..4 {
        let Some(to) = neighbor(&grid, from, direction) else { continue };
        if grid.blocked[to] { continue; }                 // a crash is never worth scoring
        grid.blocked[to] = true;  grid.head[me] = to;     // make the move on this copy...
        let score = evaluate(&grid, me, weights);
        grid.blocked[to] = false; grid.head[me] = from;   // ...and take it back
        if best.map_or(true, |(_, best_score)| score > best_score) { best = Some((direction, score)); }
    }
    best.map(|(direction, _)| direction) // None when every move crashes
}

fn main() {
    let default = Weights { territory: 1.0, open_neighbours: 0.0, distance: 0.0 };
    // A corridor: each head reaches one cell first, and the middle cell is a tie.
    let corridor = count_territory(&parse(&["A...B"]), 0);
    assert!(corridor.mine == 1 && corridor.theirs == 1 && corridor.ties == 1);

    // Walls, and a column on the right that nobody can reach: it counts for no one.
    let pocket = count_territory(&parse(&["A..#.", "...#.", "..B#."]), 0);
    assert!(pocket.mine == 2 && pocket.theirs == 2 && pocket.ties == 3);

    // The widget's Chamber board: A counts 54 cells to B's 39, but its head is the only door
    // between a 30-cell room and a 24-cell room.
    let chamber = parse(&["......#........",
                          "......#........",
                          "......#...B....",
                          "......#........",
                          "......#........",
                          "###A###########",
                          "......#########",
                          "......#########",
                          "......#########",
                          "......#########"]);
    let rooms = count_territory(&chamber, 0);
    assert!(rooms.mine == 54 && rooms.theirs == 39 && rooms.ties == 0);
    assert!(rooms.my_edges == 87 && rooms.their_edges == 63);
    // One ply ahead, the greedy bot takes the bigger room: up keeps 29 cells, down keeps 23.
    assert_eq!(choose_move(&chamber, 0, &default), Some(0));

    // With only a distance weight of -1 ("get closer"), A steps right, toward B.
    let closer = Weights { territory: 0.0, open_neighbours: 0.0, distance: -1.0 };
    assert_eq!(choose_move(&parse(&[".....", "A...B", "....."]), 0, &closer), Some(1));

    // Walled in on every side: there is no legal move to return.
    assert_eq!(choose_move(&parse(&["#A#", "###"]), 0, &default), None);
    println!("all territory and greedy checks passed");
}

09Where evaluations go wrong

Scoring from the wrong side. Every term must be measured from the same side: one fixed player, or the player to move, but the same one everywhere. Mixing the two in one function is a classic bug, and it hides well because half the positions still score sensibly.

One feature swamping the rest. A raw distance of up to 48 steps (on a 30×20 board) next to an open-neighbor count of 0 to 3 means the distance decides everything unless its weight is small. Check the range of each weighted term as well as the weights.

Trusting the count on a board with doors. Voronoi territory assumes every owned cell is usable. A one-cell door between rooms, as on the Chamber board, breaks that. If your bot loses games where it led on territory, look for articulation points first.

An evaluation that's too slow. Two BFS passes over 600 cells are cheap once and slow when a search runs them tens of thousands of times a turn. Allocate the buffers once and reuse them, and time the evaluation alone before blaming the search. Fast Bots covers the techniques.

Tuning and testing on the same maps. Weights chosen because they won on some maps are partly fitted to those maps. The only fair test of the final version is on maps no decision ever looked at.

10What's next

The greedy bot sees one move ahead and treats the opponent as if it will never reply. Minimax and Alpha-Beta puts this evaluation at the bottom of a search that asks what the opponent will answer, and what you answer to that, several moves deep. It covers pruning, move ordering, answering before the 100 ms deadline, and what to assume when three or four players share the board.

11Sources

Widget readouts are computed in the page from the displayed boards and seeded games; they are not CodinGame results.

1. CodinGame. Tron Battle, puzzle statement (first league), read 2026-10-30. The 30×20 grid, battles of 2 to 4 cycles, players moving in turn, the 100 ms limit per turn, and a defeated player's trail disappearing.
2. University of Waterloo Computer Science Club, 2010. Google AI Challenge: problem description (Internet Archive copy). Simultaneous moves, and a tie when both players enter the same cell.
3. Brian Haskin (Janzert), 2010. Janzert's Tron Bots, Information Page. His alpha-beta bot crAB: about 30,000 nodes and 7 moves of lookahead per turn early on an open 15×15 map on his machine, Voronoi territory, and a tree of 2-connected chambers with a checkerboard upper bound.
4. Andy Sloane (a1k0n), 2010. Google AI Challenge post-mortem. The Voronoi heuristic, open-neighbor counting, the regression weights (0.055 and 0.194 from 11,691 games), the checkerboard argument, articulation points and the battlefront chamber rule, and the 1,000 × region-size endgame score.
5. John Hopcroft and Robert Tarjan, 1973. Algorithm 447: Efficient Algorithms for Graph Manipulation, Communications of the ACM 16(6): 372–378 (scan). Finding articulation points with one depth-first search in linear time.
6. Daniel Hartmeier (dhartmei), 2010. maxsteps: visiting chambers, from his Tron server page, which also lists the 2010 contest write-ups with their final ranks. Recursing over articulation points once the players are separated, with early cut-offs.
7. Xavier_F, 2017. Post #34 in "Tron Battle (aka Line Racing) multiplayer challenge discussion", CodinGame forum, 26 November 2017. Reaching Legend in Python with a weighted one-move scoring function and no search.