MultipleChoice - Robo Wiki -= Collecting Robocode Knowledge =-

When your targeting algorithm finds more than one angle, point or in whatever shape it yields its results, you can use a MultipleChoice algorithm to calculate the one optimal firing angle that will hit the most of those options.

I believe Albert first used this term to discribe the system used in his Aspid gun.

Bots that use MultipleChoice:

(add more if you know more)

-- Vic

I'm curious. What algorithms are there for deciding this kind of thing? This topic hasn't been discussed much, and this is one area of Fractal's new gun that could be improved. Fractal's gun while learning can yield various simultaneous graphs of the enemy's movement profile (a 'graph' being a simple curve, what you would see in any graphing bot other than Fractal 0.32), and has to make a decision on which spike to use. Currently, to perform a MultipleChoice on multiple graphs, the development version of Fractal first casts out graphs that do not have enough data to be reliably used, then simply divides the values on each graph by the total amount of data in each graph and then sums them up; that way the value of the spikes is independant of the amount of samples acquired. Then the highest spike on the summed graph is used. I've been thinking for the past couple weeks on the best way to sum this data; I'm trying to figure out a way that a hardcoded 'usefulness' factor of each graph as well as a reliability factor based on the amount of data acquired in each graph could be used to perform a better MultipleChoice than the one Fractal currently uses. I've also been trying to devise a better way to improve the algorithm that casts out graphs; I'm trying to build an algorithm to find whether a graph as enough data as a function of the deviation of the highest spike. What are everyone else's thoughts? -- Vuen

LauLectrik also used a similar approach. It had several probability distributions (ie. graphs) and had to decide which one to use. I never found a good solution, because the more graphs you have, the more likely you are to choose a bad one with a big but irrelevant spike :-(

Usually MultipleChoice is easier, because you have only one probability distributuion (ie. graph) created from the different "observations". I'm using two different methods depending on the bot, but they all need to convert the points into bearings.

Just use a classical "data segmentation" approach, create buckets, classify your obsrvations, and pick the bucket with more observations.
Analyze each point, count the number of points that are at less than a given distance to this point, and select the point which has more neighbours. This one has the advantage that it will not sacrifice precission, and you can use it also to analyze multi-dimensional points. On the other hand, it is more intensive in calculus, and you will need to define a distance function and a max distance (and that can be tricky if you have multi-dimensional data).

-- Albert

Let me see if I understand what this is about. If I have a classic, segmented, GuessFactorTargeting gun and I permute the possible segment combinations for a given situation. Then I use some method to choose what combination to use for this shot. Would that be a kind of MultipleChoice? If so, we can put up Marshmallow in the list above, and also the next gen GloomyDark. -- PEZ

That might deserve it's own name, like "Desegmentation" or something. -- Kawigi

Ok, so if i have an array of positions that the enemy can be in, that i then convert to an array of bearing's, how do i choose which bearing i want to use. The most obvious way to me seems to be to round off the number to some precision, then create an associative array (probably from a hashtable) and increment according to the values in the array. Then pick the highest value. Is there an easier way?? --Brainfade

Probably it is (but I think there is no need to use the hash table). Aspid just uses an array with each position meaning a bearing range (ie. 0 from -0.9 to -0.8, 1 from -0.8 to -0.7, etc.) then it puts the bearings into the array using the classical bearingToIndex? function and then picks the index which has more bearings.

Another way (sued by Vibora) is to sort the bearings, then count, for each one, how many "close" bearings it has and choose the bearing with more "friends". The theorical advantage of this system is that it picks a real point, but I never found a real advantage using it.

 Example: if you have {0.19, 0.20, 0.21, 0.23, 0.25} and you consider "friends" any bearing close by 0.1 
          then you rate your  bearings like {1, 2, 1, 0, 0} so you will select 0.20 to fire at.

-- Albert

If you have an array of positions you can do it like I do in TronsGun: for each of those positions compute the angle tolerance for a bullet to hit in each case, and then count as "friends" the other angles that fall inside that interval. It's kind of a distance factored dynamic bin size. -- ABC

Adding RougeDC here, because it uses what I consider to be a form of this. In particular, it uses MultipleChoice on the many "guess factor ranges" returned by the DynamicClustering search (in my DynamicClustering, I record the full (and ultra-precise) range of GuessFactors that could have possibly hit), and after applying "weighting" to account for it's confidence in each little range, finds the best point to aim at according the the MultipleChoice. Also, since I'm big on the idea, I'm using a form of dynamically weighted MultipleChoice to implement CrowdTargeting to further improve my results. So far, I'm liking my dynamically weighted MultipleChoice/CrowdTargeting far better than any VirtualGuns setups that are typically used to combine multiple guns... :) -- Rednaxela

Hmmmm... was this the "secret sauce" that you said something about? =) -- Skilgannon

Well... the real "secret sauce" will be when I add a MultipleChoice SingleTick PatternMatcher to the CrowdTargeting, instead of just the CircularTargeting I'm using right now to tune the MultipleChoice/CrowdTargeting weighting scheme. I figure that if adding something as basic as a CircularTargeting to the crowd can improve my previously pure-DC gun, then surely I could do some neat stuff putting something stronger in my MultipleChoice/CrowdTargeting scheme. My preliminary tests so far, show that adding the CircularTargeting in my scheme, improves my results slightly both against surfers and random movers, and also makes my hitrate against sample.Spinbot far less embarrassing :) -- Rednaxela