Difference between revisions of "Dynamic Clustering"
(rewrite, hope someone can write better than me) |
(Various additions/corrections/wikipedialinks/etc) |
||
| Line 1: | Line 1: | ||
| − | Dynamic clustering is a technique to find | + | '''Dynamic clustering''' is a technique to find entries in your [[Category:Log-Based Algorithms|log]] similar to the current situation. Essentialy, it is a [[wikipedia:K-nearest neighbor algorithm|K-nearest neighbor algorithm]], and not actually [[wikipedia:Cluster analysis|clustering]] at all. Despite this midnomer, the term "Dynamic Clustering" has stuck with the robocode community. |
| − | + | The ideas is to record a "state" (or termed "situation") for each entry in your log. The state can contain any data that you seem valuable, such as [[lateral velocity]], [[advancing velocity]], or [[enemy distance]]. Save this along with your data. Then to use the day, you find a "distance" between current state and past states. Distance can be [[wikipedia:Euclidean distance|Euclidian]] (<code>sqrt(sqr(dist1 - dist2) + sqr(lat1 - lat2))</code>) or another way, such as [[wikipedia:Manhattan distance|Manhattan distance]]. Find some number of entries with the lowest distance, and use them for targeting. | |
| + | |||
| + | The earliest method doing this, was by iterating through the log and calculating the distance for each log entry. If you have a large log this is very slow. More recently [[Kd-Tree|Kd-Trees]] have been used. [[User:Corbos|Corbos]] was the first one to mention them in [[Robowiki]], which caught the interest of [[User:Chase-san|Chase-san]] and [[User:Simonton|Simonton]]. As of now, Simonton's Kd-tree implementations is one of faster ones. | ||
=== Bot using this technique === | === Bot using this technique === | ||
| Line 13: | Line 15: | ||
== See Also == | == See Also == | ||
* [[Visit Count Stats]] | * [[Visit Count Stats]] | ||
| − | * [[ | + | * [[Kd-Tree]] |
| + | |||
| + | [[Category:Log-Based Algorithms]] | ||
Revision as of 19:13, 26 April 2009
Dynamic clustering is a technique to find entries in your similar to the current situation. Essentialy, it is a K-nearest neighbor algorithm, and not actually clustering at all. Despite this midnomer, the term "Dynamic Clustering" has stuck with the robocode community.
The ideas is to record a "state" (or termed "situation") for each entry in your log. The state can contain any data that you seem valuable, such as lateral velocity, advancing velocity, or enemy distance. Save this along with your data. Then to use the day, you find a "distance" between current state and past states. Distance can be Euclidian (sqrt(sqr(dist1 - dist2) + sqr(lat1 - lat2))) or another way, such as Manhattan distance. Find some number of entries with the lowest distance, and use them for targeting.
The earliest method doing this, was by iterating through the log and calculating the distance for each log entry. If you have a large log this is very slow. More recently Kd-Trees have been used. Corbos was the first one to mention them in Robowiki, which caught the interest of Chase-san and Simonton. As of now, Simonton's Kd-tree implementations is one of faster ones.
Bot using this technique
- Tron & Shadow: First tow bots using this technique. This technique used to called "Trons Gun", but later renamed.
- Chalk: First dynamic clustering bot that released with source code.
- DCBot: A simplified version of gun using by earlier version of Tron and Shadow.
- Lukious & Firebird & Hydra: Dynamic Clustering version of Dookious, Phoenix, WaveSerpent respectively.
- Horizon & RougeDC & YersiniaPestis: Newer dynamic clustering bots.
- X2 & Ali & DrussGT: These bots use Dynamic Clustering only for their gun.
