Difference between revisions of "Pattern Matching"

From Robowiki
Jump to navigation Jump to search
m ("most" instead of "any other" advanced targeting)
m (linked to terminology)
 
(9 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 +
{{Wikipedia}} {{Generalize|targeting|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.
 
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.
  
Line 19: Line 20:
 
== External links ==
 
== External links ==
  
* [http://web.archive.org/web/20040213005719/http://realj.com/robots/MogBot.html#aiming David Mold's description of MogBot's targeting algorithm]
+
* [http://web.archive.org/web/20040213005719/http://www.realj.com/robots/MogBot.html#aiming David Mold's description of MogBot's targeting algorithm]
 
* [http://web.archive.org/web/20040301161952/www-106.ibm.com/developerworks/library/j-pattrec.html Secrets from the Robocode masters: Advanced targeting -- Pattern recognition]
 
* [http://web.archive.org/web/20040301161952/www-106.ibm.com/developerworks/library/j-pattrec.html Secrets from the Robocode masters: Advanced targeting -- Pattern recognition]
  
 
== See also ==
 
== See also ==
  
* [[SymbolicPatternMatching]]
+
* [[Symbolic Pattern Matching]]
* [[FoldedPatternMatcher]]
+
* [[Folded Pattern Matcher]]
* [[Single-Tick Pattern Matching]]
+
* [[oldwiki:PatternMatching/SingleTick|Single-Tick Pattern Matching]]
* [[PatternMatcher Challenge]]
+
* [[Pattern Matcher Challenge]]
 +
* [[Sequential Prediction]]
  
 
[[Category:Advanced Targeting Strategies]]
 
[[Category:Advanced Targeting Strategies]]
[[Category:Targeting]]
+
[[Category:Log-Based Targeting]]
 +
[[Category:Terminology]]

Latest revision as of 19:48, 24 June 2012

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