Difference between revisions of "BestPSpace"

From Robowiki
Jump to navigation Jump to search
m (removing "Targeting" category)
m (Fix layout)
 
Line 7: Line 7:
 
Albert described this targeting method on the RoboWiki in 2003:
 
Albert described this targeting method on the RoboWiki in 2003:
  
<blockquote>
 
<p>
 
 
BestPSpace is the method of [[Targeting]] used by LauLectrik 1.2. There may be other bots that use it under other names.
 
BestPSpace is the method of [[Targeting]] used by LauLectrik 1.2. There may be other bots that use it under other names.
</p><p>
+
 
 
The system tries to overcome the problems [[PatternMatching]], [[GuessFactorTargeting]], and [[VirtualBullets]] have:
 
The system tries to overcome the problems [[PatternMatching]], [[GuessFactorTargeting]], and [[VirtualBullets]] have:
</p><p>
+
 
 
* Pattern matchers have trouble predicting movement when the enemy behaviour has no clear pattern, or when future behaviour is not related to previous observations. It seems to happen with many top bots, and that's why the VB method seems to work better against them.
 
* Pattern matchers have trouble predicting movement when the enemy behaviour has no clear pattern, or when future behaviour is not related to previous observations. It seems to happen with many top bots, and that's why the VB method seems to work better against them.
</p><p>
+
 
 
* VB bots calculate the best relative bearing to fire at, based on previously collected data. For simple movements, this works fine. However, lately some top bots have appeared that create a movement that has a flat bearing probability function. The bearing probability function for these bots looks like:
 
* VB bots calculate the best relative bearing to fire at, based on previously collected data. For simple movements, this works fine. However, lately some top bots have appeared that create a movement that has a flat bearing probability function. The bearing probability function for these bots looks like:
</p><p>
+
 
+probability for a given distance.
+
  +probability for a given distance.
+
+
  +
+
+
  +
+*********
+
  +*********
+*********
+
  +*********
+*********
+
  +*********
========== bearing
+
  ========== bearing
</p><p>
+
 
 
BestPSpace tries to overcome it by mapping the right bearing to hit to multiple variables. It creates N probability spaces, each classified by a group of variables. For example:
 
BestPSpace tries to overcome it by mapping the right bearing to hit to multiple variables. It creates N probability spaces, each classified by a group of variables. For example:
</p><p>
+
 
+ SPACE 1: probability for a given distance.
+
  + SPACE 1: probability for a given distance.
+
+
  +
+
+
  +
+*********
+
  +*********
+*********
+
  +*********
+*********
+
  +*********
========== bearing
+
  ========== bearing
</p><p>
+
 
+ SPACE 2: probability for a given accumulated time moving in a certain direction.
+
  + SPACE 2: probability for a given accumulated time moving in a certain direction.
+
+
  +
+      *  
+
  +      *  
+    ***  
+
  +    ***  
+  *****  
+
  +  *****  
+*********
+
  +*********
========== bearing
+
  ========== bearing
</p><p>
+
 
 
Note that you will have families of probability functions (defined by the variables used to classify the bearings) and many instances for each probability function. For example, one family might be defined by distance - accumulated time; the instance would be distance=500-accumulated time=20.
 
Note that you will have families of probability functions (defined by the variables used to classify the bearings) and many instances for each probability function. For example, one family might be defined by distance - accumulated time; the instance would be distance=500-accumulated time=20.
</p><p>
+
 
 
LauLectrik uses 20 of these families, and generates around 1300 instances (this means 1300 probability functions). The number of instances depends on the enemy. Some variables it uses are: distance, target direction, target velocity, target acceleration, accumulated time moving in the same direction, relative movement direction, etc.
 
LauLectrik uses 20 of these families, and generates around 1300 instances (this means 1300 probability functions). The number of instances depends on the enemy. Some variables it uses are: distance, target direction, target velocity, target acceleration, accumulated time moving in the same direction, relative movement direction, etc.
</p><p>
+
 
 
When you are going to fire, you select the instance for each family that best matches the current enemy state, and select the family with the highest probability (note that higher probability means that there is less variance in that space - the movement is more predictable).
 
When you are going to fire, you select the instance for each family that best matches the current enemy state, and select the family with the highest probability (note that higher probability means that there is less variance in that space - the movement is more predictable).
</p><p>
+
 
 
The advantage of this system is that you can try to create a movement that makes a probability function flat, but it will be very difficult to make ALL functions flat, so LauLectrik should always be able to find a good criterion to use for aiming.
 
The advantage of this system is that you can try to create a movement that makes a probability function flat, but it will be very difficult to make ALL functions flat, so LauLectrik should always be able to find a good criterion to use for aiming.
</p><p>
+
 
 
Sumarizing how it works:
 
Sumarizing how it works:
</p><p>
+
 
 
# Calculate the right gun bearing to hit (I use the algorithm described in the [[Wave]] page)
 
# Calculate the right gun bearing to hit (I use the algorithm described in the [[Wave]] page)
 
# Calculate the current bot state for each bot family, select the right instances, and update the probability functions with the right gun bearing.
 
# Calculate the current bot state for each bot family, select the right instances, and update the probability functions with the right gun bearing.
 
# When you aim, use the current bot state to select the right instance for each family, and select the instance that shows the highest probability.
 
# When you aim, use the current bot state to select the right instance for each family, and select the instance that shows the highest probability.
 
# Fire!!!
 
# Fire!!!
</p><p>
+
 
 
The gun has some problems that need additional work:
 
The gun has some problems that need additional work:
</p><p>
+
 
 
# It learns quite slowly, because of the large number of buckets.
 
# It learns quite slowly, because of the large number of buckets.
 
# The number of families must be limited. The higher the number of families, the higher the probability of chosing the worng function, just because of variance in the observations. A system to deal with applicability of the functions should be implemented.
 
# The number of families must be limited. The higher the number of families, the higher the probability of chosing the worng function, just because of variance in the observations. A system to deal with applicability of the functions should be implemented.
 
# It uses lots of data, so when you add persistence it consumes the 200K allocated VERY fast. This makes it important to limit the number of families, which reduces the gun performance.
 
# It uses lots of data, so when you add persistence it consumes the 200K allocated VERY fast. This makes it important to limit the number of families, which reduces the gun performance.
</p>
 
</blockquote>
 
  
 
== See also ==
 
== See also ==

Latest revision as of 04:28, 10 July 2020

This form of statistical targeting, which bears a strong resemblance to segmented visit count stats, was first described by Albert, who used it in his bot LauLectrik.

The idea is to track multiple sets of visit count stats as they relate to different targeting situations; when firing, use the data set with the best looking movement profile (among those sets that match the current firing situation) to generate a firing angle. With this method, a gun can exploit the weaknesses of different types of movement profiles without diluting its statistics by segmenting on all attributes against all bots, much like dynamic segmentation.

Creator's description

Albert described this targeting method on the RoboWiki in 2003:

BestPSpace is the method of Targeting used by LauLectrik 1.2. There may be other bots that use it under other names.

The system tries to overcome the problems PatternMatching, GuessFactorTargeting, and VirtualBullets have:

  • Pattern matchers have trouble predicting movement when the enemy behaviour has no clear pattern, or when future behaviour is not related to previous observations. It seems to happen with many top bots, and that's why the VB method seems to work better against them.
  • VB bots calculate the best relative bearing to fire at, based on previously collected data. For simple movements, this works fine. However, lately some top bots have appeared that create a movement that has a flat bearing probability function. The bearing probability function for these bots looks like:
 +probability for a given distance.
 +
 +
 +*********
 +*********
 +*********
 ========== bearing

BestPSpace tries to overcome it by mapping the right bearing to hit to multiple variables. It creates N probability spaces, each classified by a group of variables. For example:

 + SPACE 1: probability for a given distance.
 +
 +
 +*********
 +*********
 +*********
 ========== bearing
 + SPACE 2: probability for a given accumulated time moving in a certain direction.
 +
 +      * 
 +    *** 
 +   ***** 
 +*********
 ========== bearing

Note that you will have families of probability functions (defined by the variables used to classify the bearings) and many instances for each probability function. For example, one family might be defined by distance - accumulated time; the instance would be distance=500-accumulated time=20.

LauLectrik uses 20 of these families, and generates around 1300 instances (this means 1300 probability functions). The number of instances depends on the enemy. Some variables it uses are: distance, target direction, target velocity, target acceleration, accumulated time moving in the same direction, relative movement direction, etc.

When you are going to fire, you select the instance for each family that best matches the current enemy state, and select the family with the highest probability (note that higher probability means that there is less variance in that space - the movement is more predictable).

The advantage of this system is that you can try to create a movement that makes a probability function flat, but it will be very difficult to make ALL functions flat, so LauLectrik should always be able to find a good criterion to use for aiming.

Sumarizing how it works:

  1. Calculate the right gun bearing to hit (I use the algorithm described in the Wave page)
  2. Calculate the current bot state for each bot family, select the right instances, and update the probability functions with the right gun bearing.
  3. When you aim, use the current bot state to select the right instance for each family, and select the instance that shows the highest probability.
  4. Fire!!!

The gun has some problems that need additional work:

  1. It learns quite slowly, because of the large number of buckets.
  2. The number of families must be limited. The higher the number of families, the higher the probability of chosing the worng function, just because of variance in the observations. A system to deal with applicability of the functions should be implemented.
  3. It uses lots of data, so when you add persistence it consumes the 200K allocated VERY fast. This makes it important to limit the number of families, which reduces the gun performance.

See also