Hard-coded segmentation

Jump to navigation Jump to search
Revision as of 8 December 2013 at 19:01.
The highlighted comment was created in this revision.

Hard-coded segmentation

I know what you mean about those Hard-coded segmented bin-based statistical algorithms. I never liked those, I went to great lengths to try and make those easier to work with.

Now we just need to find a way to get rid of the hard coding in the kNN algorithms, that exist in the form of carefully tuned weights and states.

    Chase19:02, 6 December 2013

    I suspect we'd need much longer battles for dynamic weighting to ever out-perform hand-tuned weights. I'm not even sure enemy behavior has a non-negligible impact on the optimal weights, as we generally assume. Has anyone proven a certain set of weights to be optimal against one bot, and a different set optimal against another, beyond margin of error, in gun or movement?

      Voidious (talk)19:20, 6 December 2013

      I don't know if that's been proved either. However, just the way that stats are gathered combined with robocode physics are going to make some weights more relevant than others.

      Of course, I can choose two different bots that I know will be optimal with different kNN weights. Think a surfer vs a random-movement bot, and the weight of the rolling average between them. Or a bot that bounces off walls, and the effect of a wall-distance attribute vs a bot that smooths against walls.

      The best would probably be to have multiple weighting sets, and the gun chooses the one with the highest hitrate, or possibly with some classifier.

        Skilgannon (talk)19:33, 6 December 2013

        Hah, you just beat me to posting. I was about to say something similar, that due to the limited data within a single battle, it would probably be best to select the appropriate weighting via a heuristic rather than determining it "from scratch"

          Rednaxela (talk)19:38, 6 December 2013

          I don't know that a surfer vs random movement would have different optimal weights. :-) But yes, SpinBot and DrussGT have pretty different movement profiles. I don't doubt they have different optimal weights. But I still might be wrong, and that's why we have science. :-)

          Choosing among multiple weightings would mean a performance hit similar to adding Virtual Guns. So it's important to figure out how much of an impact sub-optimal weightings have in the first place. I've always thought we were fairly non-scientifically rigorous around here with some of this kind of stuff. It might be fun to try to do some rigorous testing. Actually that's one of the first ideas in a while that gets me excited about doing some more actual Robocoding.

            Voidious (talk)19:50, 6 December 2013

            Adding virtual guns is the easiest way I see to select between multiple weight sets in guns. Also the slowest.

            In movement, it is trickier. Maybe 2 weight sets, one for wave surfing and one for flattener.

            When tuning, use a different population for each set of weights.

              MN (talk)03:23, 7 December 2013

              I have actually been working for awhile to find a set of gun weights that is both highly efficient against both surfers and random movers, the same with a single set for movement to be good against both Statistical, kNN and Pattern Matching targeting. Since my most recent bots I eschew the use of Flatteners and Virtual Guns. Obviously I did okay coming in number 7 in the rumble, but I feel there is still room for improvement.

              Though I really do think there are different optimal weights for different enemies, but there might be a set that does well against all enemies (if not optimally).

                Chase07:56, 7 December 2013

                A single set that does ok against everyone is what is already calculated with genetic tuning against the whole population at once.

                  MN (talk)21:40, 7 December 2013

                  Well, that brings up the question of what one exactly means by "highly efficient against both", or to put it another way, how one scores the individuals in the genetic tuning.

                  The most common way to interpret it may be optimizing for APS, but that will tend to give very little weight being "highly efficient against surfers". Another way to interpret is optimizing the win percentage. In my mind the phrase "highly efficient against both" would imply optimizing with a scoring system that divides the population into "surfers" and "non-surfers" giving roughly equal weight to them, but the phrase is a bit vague.

                    Rednaxela (talk)22:00, 7 December 2013

                    Giving equal weight to surfers and non-surfers will hurt APS ranking. But may increase PL ranking.

                      MN (talk)20:57, 8 December 2013

                      If multi-objective optimization is being done, than surfers and non-surfers can be separated in distinct objectives. The output will be many different sets of weights, with different compromises between surfers and non-surfers, although all of them Pareto efficient.

                        MN (talk)21:01, 8 December 2013

                        I was referring to hard-coded bins, not hard-coded weights. Although Combat also uses runtime std. dev. based weights.

                        Tuning against a known population is clearly stronger than runtime estimation of std. dev. It would only be weaker if the population was constantly changing.

                        But having different sets of weights for different opponents seems to have potential. Forward speed is more important against rammers than wall distance. The opposite is true for non-rammers. But selecting which set is optimal against each opponent is tricky without hard-coding opponents names.

                          MN (talk)19:37, 6 December 2013

                          What type of distinction between bins and weights do you mean? They can have very similar effects, especially when using an interpolated VCS method. I tend to look at traditional VCS bins and kNN search w/ weightings as having a similar effect in the end, with the primary difference being that one has what is effectively a Math.Round() call in the transfer function of each dimension.

                            Rednaxela (talk)19:44, 6 December 2013

                            I posted that a long time ago. Only long after I learned the close relationship between bins, k-NN and kernel density.

                              MN (talk)19:49, 6 December 2013