Dynamic Clustering

Origins

Dynamic Clustering was coined and pioneered by ABC. It was refined by the RoboWiki community, including the authors of Chalk, Diamond, and other k-nearest-neighbor bots.

Fixed segmentation asks a bot author to choose every bucket boundary before the battle starts. Dynamic Clustering keeps the original situations instead. When the gun needs an answer, it finds the recorded situations that most resemble the one in front of it.

The name is historical. In Robocode, Dynamic Clustering is usually a k-nearest-neighbor search with density estimation, not k-means clustering.

A situation becomes a point

At fire time, record a state vector alongside the eventual outcome of its wave. A small first vector might contain normalized distance, lateral velocity, advancing velocity, and distance to the nearest wall. When the wave reaches the enemy, attach its observed GuessFactor to that same record.

For a current state $q$ and a recorded state $p$, a common squared similarity distance is $d^2(p,q) = \sum_i w_i(p_i-q_i)^2$. Here $p_i$ and $q_i$ are values on axis $i$, and $w_i$ is that axis's weight. Normalize axes first, or a value measured in hundreds of units will drown out velocity.

The current battle state selects nearby recorded states in a multi-dimensional data space.

From neighbors to an aiming angle

Choose the $k$ closest records, then let their outcomes vote for a GuessFactor. A kernel gives close neighbors more weight than merely similar ones. The resulting peak becomes the firing angle in the same way as a GuessFactor gun.

on wave break:
    log.add(state captured when the wave was fired, observedGuessFactor)

when aiming:
    current = makeState(scan)
    neighbors = k records with the smallest weightedDistance(current, record.state)
    bestFactor = densityPeak(neighbors, record.guessFactor, record.distance)
    aim at directBearing + bestFactor * maximumEscapeAngle

Keeping the complete records is the advantage. A new axis or a different weight changes the comparison without discarding old wave outcomes. It is also the cost: a poor state representation still produces poor neighbors.

Data, speed, and fallbacks

Early in a round there may be too few records to make a useful neighborhood. Fall back to a broad GuessFactor buffer or a simpler gun until the log grows. Keep data per enemy, and consider decaying or capping old samples when an opponent changes behavior.

A direct scan through every record is clear and often good enough for a small log. Long battles make that search expensive. A k-d tree organizes the state points so nearest-neighbor queries can avoid much of the log, but it is an optimization to add after the brute-force version has been tested.

More axes are not automatically better

Each added axis makes an exact match rarer. Add only measurements that separate real movement choices, then test the change across enough rounds to distinguish an improvement from luck.

Platform notes

The state search, wave timing, and bullet speed are the same idea in classic Robocode and Tank Royale. Store headings and bearings in one internal convention before building a state or converting the final firing angle: classic Robocode uses compass-style angles, while Tank Royale uses mathematical angles. Tank Royale's published physics also confirms the shared maximum speed of 8 units per turn and bullet-speed rule.

Further Reading

• Dynamic Clustering - RoboWiki (classic Robocode)
• Dynamic Clustering Tutorial - RoboWiki (classic Robocode)
• kd-tree - RoboWiki (classic Robocode)
• Physics - Tank Royale documentation