Pyramid Bins

From Robowiki
Jump to navigation Jump to search
Youtube
Youtube has a video of Pyramid Bins in action: click here to watch

A form of statistical targeting that combines guess factors, segmentation, and visit count stats.

PyramidSegmentation.jpg

Idea

Segmentation typically involves segmenting into a significant number of buckets- it's not uncommon to see 30 buckets or more. However, by scanning the distance to our target, we can actually reduce the number of buckets to only a fraction of what's typically used, based on the maximum escape angle and chord lengths. The result is greatly improved learning speeds and improved accuracy, particularly against wave surfers.

Implementation

In order to implement pyramid segmentation, we simply need to make a few calculations to determine how many buckets we'll need at any particular range. -First, calculate the Maximum Escape Angle. -Then using the triangle used to calculate the MEA, calculate the length of the side opposite the MEA. Since the triangle is Right, this comes out to be 'distance to target' * tan(MEA). Call this length 'C'. -Divide 'C' by twice the width of a bot minus one, 36 * 2 - 1 = 71, and take the ceiling of the result. This gives the minimum number of buckets needed to hit the target at that distance.

By pre-calculating which distances lead to a change in the number of buckets, we can very easily implement this into our code. For simple purposes, the breaks are at d=79n/tan(MEA) for all integer n (but this only needs to be calculated up to the size of the battlefield). For Firepower=3, this comes out to a break at every 75 units, which isn't bad given that the size of a typical battlefield is 800 (that is, 11 buckets at most).

Notice that we used buckets of width 79- This means that in order to to work properly our gun must fire directly into the center of each bucket.

Advanced Refinements

-Since only at breakpoints are each of the buckets an even 79, it's clear that inbetween these breaks, all the buckets are of a width smaller than 79. This means that by firing directly into the edge buckets (0 and n-1 of our array) we actually are losing some accuracy. More advanced implementations could have the turret fire as close to the center as possible while still covering every point inside the bucket.

-The gun could also just the MEA by adjusting firepower. Since against a good wave surfer, the gun's accuracy will be at worst 1/n where n is the number of buckets, it could very well be worth it to slightly decrease firepower in order to constrict the MEA and stabilize the number of buckets.

-Furthermore, the bot could attempt to position itself at certain ranges that are better defined, rather than fight at ranges where information is sparse.

Weaknesses

When the target is near walls, the shot often goes into the wall unless the Precise MEA is calculated.