Pattern Matching

This article only talks about Pattern Matching in the context of targeting. You can help RoboWiki by expanding it to apply to the general topic of learning algorithms.

A form of log-based targeting that tries to match the most recent series of enemy movements against a history of previous enemy movements. The most common form finds the closest match, then uses the movements immediately after that match to predict the enemy's future movements; other variations exist, as well.

Pattern matching was one of the most powerful targeting strategies in the early days of Robocode. It is the most powerful method among NanoBots and one of the best among MicroBots, as it can fit into far less code size than most advanced targeting strategies. While it continues to get attention from many bot authors, it is generally not a top targeting method among MegaBots.

How it works

There are many different pattern matching algorithms, but here is the pseudocode for a typical one, derived from David Mold's MogBot algorithm:

• Keep a log of enemy movements that stores the enemy's velocity and heading change each tick.
• When aiming, take the last 7 enemy movements and use this as your pattern (let's call it p, made up of p[0], p[1], ... , p[6]).
• Search through your history of enemy movements and find the series of 7 ticks that most closely matches p. For each position x in your search history:
  • Measure the difference between x and p[0], x + 1 and p[1], up through x + 6 and p[6]. This measurement could simply be abs(velocity1 - velocity2) + abs(turnRate1 - turnRate2) for each individual tick.
  • Sum these differences - the lower the result, the closer the match. Call this sum s.
  • Remember the lowest value of s and its position in the log.
• Once you have found the closest match, imagine that the enemy will move with the exact same series of movements that he did last time. Note the enemy's current position and heading, then iterate through the movements immediately after the match we found.
  • For each successive movement frame, move the enemy's position ahead by the past frame's velocity and then turn the enemy's heading by the past frame's heading.
  • Figure out how long it will take your bullet to get there and repeat the prediction that many times, then fire at that spot.

External links

• David Mold's description of MogBot's targeting algorithm
• Secrets from the Robocode masters: Advanced targeting -- Pattern recognition

See also

• Symbolic Pattern Matching
• Folded Pattern Matcher
• Single-Tick Pattern Matching
• Pattern Matcher Challenge
• Sequential Prediction