Difference between revisions of "Pattern Matching"

From Robowiki
Jump to navigation Jump to search
(→‎See also: new method for pattern matching (very fast))
m (→‎See also: Edited link to pattern matcher challenge)
Line 28: Line 28:
 
* [[FoldedPatternMatcher]]
 
* [[FoldedPatternMatcher]]
 
* [[Single-Tick Pattern Matching]]
 
* [[Single-Tick Pattern Matching]]
* [[PatternMatcher Challenge]]
+
* [[Pattern Matcher Challenge]]
 
* [[Sequential Prediction]]
 
* [[Sequential Prediction]]
  
 
[[Category:Advanced Targeting Strategies]]
 
[[Category:Advanced Targeting Strategies]]
 
[[Category:Log-Based Targeting]]
 
[[Category:Log-Based Targeting]]

Revision as of 00:33, 19 January 2010

Wikipedia
Wikipedia has an article about:
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

See also