Difference between revisions of "Dynamic Clustering"

From Robowiki
Jump to navigation Jump to search
(copy and past content, cleaning later)
 
 
(15 intermediate revisions by 6 users not shown)
Line 1: Line 1:
−
Consider a history of the enemy state (log, array, whatever). For each entry you have multiple data on the enemy, like distance, speed, distance to wall, etc. Now, DynamicClustering consists in categorizing those entries into clusters, so that each cluster contains "similar" entries. "Similar" is defined by beeing close to each other, the measure of distance beeing the euclidian distance between entries: sqrt(sqr(dist1 - dist2) + sqr(speed1 - speed2) + ...). If you search Google for Clustering algorithms, you'll get lots of references to K-means clustering, which involves iteratively changing the centers of the clusters and reassigning each entry to it's new cluster. I tried it, it's very slow and I didn't manage to make it work good enough. My aproach is simpler, you just take the current entry and consider it the center of the cluster, then you find the N closest entries in the log and use them to decide where to shoot.
+
{{Wikipedia|K-nearest neighbor algorithm}}
 +
{{Youtube|eqlPbtO3rQY}}
 +
'''Dynamic clustering''' is a technique to find entries in your [[:Category:Log-Based Algorithms|log]] similar to the current situation. Essentially, it is a [[wikipedia:K-nearest neighbor algorithm|K-nearest neighbor algorithm]], and not actually [[wikipedia:Cluster analysis|clustering]] at all. Despite this misnomer, the term "Dynamic Clustering" has stuck with the Robocode community.
  
−
Now for the wheighting of each dimension. Each dimension can be wheighted by some factor. Those factors can be decided intuitively (is velocity more important than distance to wall?), by trial and error, or you can use some statistical entities to dynamically decide for you. I tried many ;), the latest beeing the entropy association between each dimension and the hitting GuessFactor (yes, I currently use GuessFactors in Shadow's gun ;)). Read more about it [http://www.library.cornell.edu/nr/bookcpdf/c14-4.pdf here].
+
The idea is to record a "state" (or termed "situation") for each entry in your log. The state can contain any data that you deem valuable, such as [[lateral velocity]], [[advancing velocity]], or [[enemy distance]]. Save this along with your data. Then to use the data, you find a "distance" between current state and past states. Distance can be [[wikipedia:Euclidean distance|Euclidian]] (<math>\sqrt{(dist1 - dist2)^2 + (lat1 - lat2)^2 + \cdots}</math>) or another way, such as [[wikipedia:Manhattan distance|Manhattan distance]] (<math>|dist1 - dist2| + |lat1 - lat2| + \cdots</math>). Find some number of entries with the lowest distance, and use them for targeting, movement, or whatever you like.
  
−
For a slightly simplified version of my DC gun used in [[Shadow]] and [[Tron]] see: [[DCBot]]
+
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]]s have been used. [[User:Corbos|Corbos]] was the first one to mention them on the [[RoboWiki]], which caught the interest of [[User:Chase-san|Chase-san]] and [[User:Simonton|Simonton]].
 +
 +
=== Bots using this technique ===
 +
* [[Tron]] & [[Shadow]]: First two bots using this technique. This technique used to be called "[[TronsGun|Trons Gun]]", but later it was renamed.
 +
* [[Chalk]]: First dynamic clustering bot that was released with [[Open Source|source code]].
 +
* [[DCBot]]: A simplified version of gun used 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.
 +
* Mini: [[CunobelinDC]], [[Foilist]]
 +
* Micro: [[MagicD3]], [[FoilistMicro]]
 +
 
 +
== See Also ==
 +
* [[Dynamic Clustering Tutorial]]
 +
* [[Visit Count Stats]]
 +
* [[kd-tree]]
 +
* [[TronsGun]] — the initial form of dynamic clustering
 +
 
 +
[[Category:Log-Based Algorithms]]

Latest revision as of 15:24, 6 April 2024

Wikipedia
Youtube
Youtube has a video of Dynamic Clustering in action: click here to watch

Dynamic clustering is a technique to find entries in your log similar to the current situation. Essentially, it is a K-nearest neighbor algorithm, and not actually clustering at all. Despite this misnomer, the term "Dynamic Clustering" has stuck with the Robocode community.

The idea is to record a "state" (or termed "situation") for each entry in your log. The state can contain any data that you deem valuable, such as lateral velocity, advancing velocity, or enemy distance. Save this along with your data. Then to use the data, you find a "distance" between current state and past states. Distance can be Euclidian (<math>\sqrt{(dist1 - dist2)^2 + (lat1 - lat2)^2 + \cdots}</math>) or another way, such as Manhattan distance (<math>|dist1 - dist2| + |lat1 - lat2| + \cdots</math>). Find some number of entries with the lowest distance, and use them for targeting, movement, or whatever you like.

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 on the RoboWiki, which caught the interest of Chase-san and Simonton.

Bots using this technique

See Also

Retrieved from "http://robowiki.net/w/index.php?title=Dynamic_Clustering&oldid=57807"