Play It Forward & Sequential Prediction

Origins

Play It Forward was developed and documented by the RoboWiki community as a faster way to turn a logged situation into a firing angle. Sequential Prediction comes from outside Robocode: Fri Mommersteeg of the Eindhoven University of Technology published its linear-time matching algorithm in Game Programming Wisdom (2002), and the RoboWiki community adapted it for pattern-matching guns.

A GuessFactor gun needs an angle for every situation in its log. The direct way to get one is a virtual bullet: place a shot at a candidate angle, then check its position against the enemy every turn until it either hits or passes by. Test a fan of candidate angles and the cost multiplies with each one. These two techniques cut that cost from two different directions.

One replay instead of a fan of bullets

Play It Forward stores the same kind of frame as Pattern Matching: heading difference and velocity, rather than an absolute heading or a raw velocity delta, which holds up better across headings and avoids extra bounds-checking. To score a past situation, start from the enemy's recorded position, heading, and velocity at that tick, then step forward using the frames that actually followed it in the log, exactly as they happened. Stop once the bullet's travel time for that firing power runs out, and the endpoint converts directly into the angle that would have hit.

No candidate angle is ever tested. The enemy's own recorded path is the only path replayed, so one pass produces the exact answer that a fan of virtual bullets could only approximate by trial.

Play It Forward replays the enemy's own logged path once, instead of testing a fan of candidate angles.

Fast PIF: a rotation instead of repeated trigonometry

A direct replay still calls sine and cosine once per simulated tick, and that adds up across a long log. Fast PIF rotates and translates the battlefield so the situation's starting heading lines up with a fixed reference direction before the replay begins. The stored frames then advance the point using plain addition, with no per-tick trigonometry, and only the final predicted point needs one rotation and translation back into real battlefield coordinates. The replay produces the same angle either way. Fast PIF only removes repeated work.

Sequential Prediction: the best match in one pass

Pattern matching needs the best, usually longest, matching sequence before it can replay anything, and comparing the newest frames against every earlier window costs more with each tick added to the log. Sequential Prediction finds the longest match ending at every position in a single linear pass instead.

The idea rests on one fact: the match ending at the newest frame is one longer than the match that ended the last time the previous frame's value appeared, provided the same frame followed it. Track, for each frame value, where it last occurred and how long a match ended there. If the frame now following that repeated value matches the current one, extend it by one. Otherwise, the match at this tick resets to one.

lastMatchLength = map from frame value to its match length at its most recent occurrence
lastSeen = map from frame value to the tick it most recently occurred at

for each new frame f at tick t:
    previous = frame at tick t - 1
    if lastSeen[previous] exists and frameAt(lastSeen[previous] + 1) == f:
        matchLength[t] = lastMatchLength[previous] + 1
    else:
        matchLength[t] = 1
    lastMatchLength[f] = matchLength[t]
    lastSeen[f] = t

Turn rate tops out at $10 - 0.75|v|$ degrees per turn and speed is capped at 8 units per turn, so each frame quantizes into a small alphabet of discrete heading-difference and velocity values, exactly what a symbol-matching algorithm like this one needs. Because it reports every match length it finds in a single pass rather than only the longest one, a gun can feed several pattern lengths into a virtual-gun array at once instead of committing to one window size ahead of time.

Platform notes

The log, the replay, and the matching algorithm depend only on movement rules that classic Robocode and Tank Royale share. Store heading differences in one consistent internal convention and convert only at the boundary, since classic Robocode headings are compass-style while Tank Royale headings are mathematical.

Further Reading

• Play It Forward - RoboWiki (classic Robocode)
• Sequential Prediction - RoboWiki (classic Robocode)
• Pattern Matching - RoboWiki (classic Robocode)
• Physics - Tank Royale documentation