Editing revision 75 of Simonton/PMResearch

Robo Home | Changes | Preferences | AllPages

Editing old revision 75. Saving this page will replace the latest revision with this text.

I have a goal to make pattern matching a viable alternative to the top GF guns.  Grab some base code from  [http://upload.frozenonline.com/view/simonton/MCPM.java here] and help me out!

My current test platform is the TargetingChallenge2K7.  I think it's going to make the most sense to tune one PM gun to hit adaptive movers, tune another to hit random movers / oscilators / etc., and put them into a VirtualGuns array.  Here's some scores as I make progress:

'''Surfers'''
| '''CC'''   | '''RMX'''   | '''SHA'''   | '''WS'''   | '''WOE'''   | '''Total''' | '''Gun''' 
|    73.85   |    83.56    |    67.76    |    86.03   |    83.73    | '''78.99''' | [[Dookious]] 1.543
|    71.74   |    74.21    |    68.75    |    75.07   |    79.47    | '''73.85''' | [[Shadow]] 3.66
|    68.95   |    78.28    |    69.85    |    76.19   |    75.60    | '''73.77''' | '''2 round history, 1 match tolerance''', PerformanceEnhancingBug
|    68.24   | '''79.80''' |    68.91    |    75.81   |    75.55    | '''73.66''' | 2 round history, 1 match tolerance, 1/2 bullet velocity past target, PerformanceEnhancingBug
|    70.11   |    75.21    |    67.97    | '''76.96'''|    74.23    | '''72.90''' | 2 round history, 1 match tolerance, 1/2 bullet velocity past target
|    66.82   |    77.63    |    68.66    |    74.87   | '''75.88''' | '''72.77''' | 2 round history, 1 match tolerance, 1/2 bullet velocity past target, 1 max match length
|    69.86   |    74.43    |    67.75    |    75.46   |    72.91    | '''72.08''' | 25 round history, 5 match distance, a second stab at wall-distance segmenting
|    69.16   |    73.83    |    70.62    |    73.65   |    72.71    | '''71.99''' | 35 round history, .5 match tolerance
|    69.67   |    75.92    |    67.94    |    76.15   |    70.29    | '''71.99''' | 35 round history, 5 match distance, a second stab at wall-distance segmenting
|    68.90   |    76.08    |    68.03    |    76.08   |    70.72    | '''71.96''' | 35 round history, a second stab at wall-distance segmenting
|    70.71   |    75.29    | '''72.40''' |    73.25   |    67.70    | '''71.87''' | 35 round history, 15 match distance
| '''72.05'''|    72.56    |    70.93    |    74.17   |    69.19    | '''71.78''' | 35 round history, 18 match distance
|    70.71   |    73.56    |    68.25    |    75.87   |    70.32    | '''71.74''' | 35 round history, 15 match distance, a second stab at wall-distance segmenting
|    68.97   |    73.59    |    70.60    |    72.38   |    71.28    | '''71.36''' | 35 round history, 1 match tolerance
|    69.29   |    74.62    |    69.07    |    72.80   |    70.87    | '''71.33''' | 35 round history, 100 distance tolerance
|    69.17   |    76.03    |    70.69    |    70.64   |    69.75    | '''71.26''' | 35 round history, 10 match distance
|    67.81   |    74.75    |    72.10    |    69.87   |    68.13    | '''70.53''' | 35 round history, 18 match distance, 1/2 retreating velocity for matching
|    68.11   |    73.16    |    68.43    |    73.59   |    68.78    | '''70.41''' | 35 round history, pickier matching, 18 match distance
|    67.53   |    69.68    |    70.59    |    71.55   |    68.85    | '''69.64''' | 35 round history
|    61.93   |    74.72    |    65.24    |    70.68   |    72.24    | '''68.96''' | 2 round history, 1 match tolerance, 1/2 bullet velocity past target, 2 max match length
|    67.98   |    70.19    |    68.86    |    69.35   |    67.75    | '''68.82''' | 35 round history, max 30 match length
|    68.73   |    70.59    |    69.51    |    65.92   |    66.35    | '''68.22''' | 35 round history, match only lateral velocity
|    65.81   |    68.38    |    71.24    |            |             |             | 35 round history, pickier matching
|    58.84   |    60.31    |    66.84    |    63.14   |    62.15    | '''62.26''' | 35 angle multiple choice, 35 round history
|    61.93   |             |             |            |             | '''     ''' | 2 round history, 1 match tolerance, 1/2 bullet velocity past target, 2 max match length
|            |             |             |            |             | '''     ''' |

'''Non-Surfers'''
| '''DM'''   | '''FT'''   | '''GG'''   | '''RMC'''   | '''WLO'''   | '''Total''' | '''BFly'''  | '''Cig'''   | '''DM'''    | '''FM'''    | '''Grb'''   | '''RMB'''   | '''Total''' | '''Grand Total''' | '''Comment''' 
|    91.13   |    83.03   |    90.56   |    83.86    |    89.17    | '''87.55''' |             |             |             |             |             |             |             |                   | [[Dookious]] 1.543
|            |            |            |             |             | '''     ''' |    99.89    |    90.10    |    96.58    |    93.42    |    93.93    |    94.73    | '''94.78''' |                   | [[Dookious]] 1.471
| '''89.01'''|    78.17   | '''88.34'''|    78.98    | '''82.75''' | '''83.45''' | '''99.54''' |    85.28    | '''96.73''' |    88.25    |    90.16    |    87.94    | '''91.32''' | '''87.75'''       | ''45 angle multiple choice, 35 round history, 1/2 retreating velocity for matching''
|    88.41   |    78.90   |    87.10   |    78.23    |    82.53    | '''83.03''' |             |             |             |             |             |             |             |                   | 45 angle multiple choice, 35 round history, 1/2 retreating velocity for matching, 100 distance tolerance
|    85.90   |    79.77   |    87.23   |    79.44    |    82.22    | '''82.91''' |             |             |             |             |             |             |             |                   | 45 angle multiple choice, 35 round history, 2 match distance, 1/2 retreating velocity for matching
|    87.87   |    79.69   |    85.22   | '''79.79''' |    81.69    | '''82.85''' |             |             |             |             |             |             |             |                   | 45 angle multiple choice, 35 round history, second stab at wall distance segmenting
|    87.64   | '''80.57'''|    85.78   |    78.24    |    81.36    | '''82.71''' |             |             |             |             |             |             |             |                   | 45 angle multiple choice, 35 round history
|    86.71   |    80.17   |    85.59   |    79.87    |    80.81    | '''82.63''' |             |             |             |             |             |             |             |                   | 35 angle multiple choice, 35 round history
|    87.86   |    78.45   |    86.22   |    77.92    |    82.39    | '''82.56''' |             |             |             |             |             |             |             |                   | 55 angle multiple choice, 35 round history
|    87.84   |    79.36   |    86.34   |    77.40    |    81.79    | '''82.54''' |             |             |             |             |             |             |             |                   | 35 angle multiple choice, 35 round history, match only lateral velocity
|    86.59   |    80.11   |    84.28   |    78.72    |    82.18    | '''82.38''' |    99.00    |    85.08    |    95.86    | '''90.66''' |    89.26    |    87.90    | '''91.29''' | '''87.24'''       | 45 angle multiple choice, 35 round history, 1/2 retreating velocity for matching, 200 distance tolerance
|    86.30   |    79.87   |    88.12   |    77.46    |    79.30    | '''82.21''' |             |             |             |             |             |             |             |                   | 45 angle multiple choice, 35 round history, 18 match distance
|    86.86   |    77.50   |    87.73   |    77.65    |    80.58    | '''82.06''' |    99.18    | '''87.43''' |    93.91    |    90.50    |    88.52    |    85.42    | '''90.83''' | '''86.84'''       | 45 angle multiple choice, 35 round history, 1/2 retreating velocity for matching, second stab at wall distance segmenting
|    88.22   |    77.64   |    86.22   |    76.94    |    80.80    | '''81.96''' |             |             |             |             |             |             |             |                   | 45 angle multiple choice, 35 round history, 10 match distance
|    88.31   |    77.67   |    86.54   |    76.39    |    80.24    | '''81.83''' |    98.93    |    82.69    |    94.29    |    90.08    | '''90.27''' | '''88.04''' | '''90.72''' | '''86.68'''       | 45 angle multiple choice, 35 round history, 1/3 retreating velocity for matching
|    86.18   |    78.47   |    85.54   |    78.44    |    79.89    | '''81.70''' |             |             |             |             |             |             |             |                   | 35 angle multiple choice, 35 round history, pickier matching
|    87.83   |    78.38   |    85.02   |    77.62    |    79.32    | '''81.63''' |             |             |             |             |             |             |             |                   | 25 angle multiple choice, 35 round history
|    86.43   |    78.07   |    84.56   |    79.15    |    70.17    | '''79.68''' |    99.85    |    85.04    |    95.50    |    90.77    |    90.56    |    89.67    | '''91.90''' | '''85.79'''       | [[Shadow]] 3.66
|    80.88   |    76.52   |    78.62   |    73.60    |    75.71    | '''76.47''' |             |             |             |             |             |             |             |                   | No multiple choice, 35 round history
|            |            |            |             |             | '''     ''' |             |             |             |             |             |             | '''     ''' | '''     '''       |

==== Comments, questions, feedback: ====

Might be useful to have [[Che]], [[PatternMatcherBot]] (if someone ran it...), and maybe a top-tier GF and top-tier DC gun listed here for comparison, too. -- [[Voidious]]

* Actually, I had an edit conflict because I was adding [[Dookious]] and [[Shadow]] as you made that comment!  :)  -- [[Simonton]]

It seems that the multiple choice does very poorly against AM, this makes sense because they constantly change their movement, and the older matches don't really have any bearing on what is happening now. If you take away the requirement for the angular velocity to also match, I wonder what kind of scores you will get. -- [[Skilgannon]]

* Ok, I'll give it a try next.  -- [[Simonton]]
* But the way a WaveSurfer adapts is so different from how a PatternMatcher aims that I don't think it's that simple. [[Shadow]] uses a form of multiple choice on its stats and it is one of the most potent surfer killers anywhere. I don't think he even has any VirtualGuns or an AntiSurfer gun. -- [[Voidious]]
*The multiple choice used here is not for different stats (like TronsGun, which uses different distances traveled in the last x ticks), but different matches at different places in the search history.
** No, [[Shadow]] definitely uses MultipleChoice in that it combines data from multiple parts in the history to try and decide on a resulting firing angle. As opposed to a VisitCountStats system where you just take the one most popular angle, or a PatternMatcher that finds one match and plays one movie forward. I just disagree MultipleChoice itself is bad against surfers - [[Shadow]], [[Locke]], and [[SilverSurfer]] all have guns that fare pretty well against surfers. Intuitively, MultipleChoice seems similar to PatternMatching in why it would do well against surfers: just because you're looking at the world in such a different way than a surfer, it can't predict your shots as well. (Similar way of viewing data is one big reason WaveSurfers can dodge GuessFactor guns so well.) -- [[Voidious]]
** The reason I don't think (intuitively) that multiple choice will work well against surfers is because surfers constantly change their movement, whereas multiple choice uses lots of data, possibly from a very long time ago. Multiple choice (as can be seen in the rankings above) is much stronger against non-adaptive movers than single choice pattern matchers, but the single-choice are stronger against surfers. -- [[Skilgannon]]
** Well, I think your intuition is good ;) - you need to discard or decay data against surfers to get best results. But there's no guarantee the "best match" in a single choice gun is any less old than the "best matches" in a MultipleChoice gun - in either methodology you could end up using old data. It's hard for me to comment on the above results without really knowing the code, too, as there are lots of ways to do MultipleChoice. -- [[Voidious]]
* Here's my reasoning why it will work better without matching on angular data: What I'm assuming is that the patterns a WaveSurfer generates when seeking the minimum danger will be patterns in velocity, and not angular velocity. The fact that my micro, symbolic, unfolded pattern matcher (in Decado) is able to enable the flattener in Dookious is testament to that. What I've done in Decado is actually removed the matching on angular velocity completely, instead assuming that the enemy will use whatever angular pattern they did last time their velocity matched this pattern. Why this works better (I think) is because potential matches don't get thrown out because the enemy happened to do a funny left/right angular jiggle, so we learn their pattern quicker. I plan to release a MiniBot soon which has Decado's gun, yet is folded. It may become a major ProblemBot for surfers (though not for my flattener idea in GoTo surfing). -- [[Skilgannon]]

First stab at wallsegmentting gets an amazing 75.63% overall, above Ali and just below shadow! If this keeps going up, I might start poking more into PatternMatching. --[[Chase-san]]
* *has a sneaky feeling Simonton is doing this in an attempt to make a pattern matcher that can dethrone either [[Dookious]], [[Shadow]] or [[GlowBlowMelee]]* Hem, you have already taken all the other thrones by storm. --[[Chase-san]]
* Dookious may have the strongest gun in the rumble, but movement is really its leg up on [[Phoenix]] and [[Ascendant]]. The gun is even less important in melee. -- [[Voidious]]

Just wondering, how are you doing the wall segmentation? Do you check if the predicted position is near the wall, or do you just match on different patterns if the current position is projected to be outside the wall, or what? -- [[Skilgannon]]

* I've done it a couple ways.  The "first stab" above includes a "wall segment history", which is some function of the distance from the enemy straight ahead to the wall (the value most bots use for wall smoothing).  Then it just includes it as part of determining a match.  The 1 value you see for "200 wall distance segmenting" calls 200 or closer a different segment, then uses it only to match the very first symbol (like more traditional segmenting).  --[[Simonton]]

* (Edit Conflict) I don't know if this is what you meant anyway, but "distance straight ahead to the wall" isn't quite what most top guns use for wall distance. The common method I know of is you project the enemy continuing to move in an orbit and come away with the GuessFactor they will be at when they hit the wall. So a GF of 1 or higher means they could orbit normally and not hit the wall before your bullet gets there, while something like 0.25 means they will definitely have to take the wall into consideration (WallSmoothing or bounce the other way) for this shot. -- [[Voidious]]
* I'm dumb, you said "for wall smoothing" not "for wall distance". Anyway, I'll leave the comment in case it helps anyone. =) -- [[Voidious]]
* Have you attempted to do it like gf's, erm Slice style? Thought, not sure how you could have more then one buffer in such a setup (as how would you recombine it?). --[[Chase-san]]
* That is equivalent to the second style I mentioned above.  It just re-constructs the data for the slice based on which wall segment the enemy is currently in (more similar to a DC bot, I think). -- [[Simonton]]

This match tolerance looks promising. I'm guessing it is similar to what is posted on the DynamicClustering page? Sort of a combination of everything? If so, the weightings can probably still be tuned. 2.5% below Shadow's gun, not bad, not bad. ;-)-- [[Skilgannon]]
* The match tolerance just keeps a sum of the differences between your recent history and the history you're matching against (the sum of: difference in lateral velocity + difference in retreating velocity). --[[Simonton]]

Huh - combining match tolerance and wall segmentation seemed to give the worst of both worlds, instead of the best. -- [[Simonton]]

Oh, I get it now. I suppose the only real way to get a PM as good as a GF is to definitely have a multiple chioce PM.. or rather a Virtual gun for one good vs normal bots, and one good vs surfers. --[[Chase-san]]

You are running loads of tests here - if it were me, I'd just ignore the surfers and move onto them later. They are much slower and also less important in developing a good gun, IMO. You could probably benchmark against 10 more non-surfers in the same time it's taking you to do those 5 surfers and it might really help give you a better picture of your stats. Just a thought though, keep up the good work. -- [[Voidious]]
* Good thought, and I certainly respect your input.  Noone can claim a better understanding of what it takes to get a good score than you!  Perhaps I'll add the TC2K6 non-surfurs to the benchmark (and perhaps surfers, too).  But thanks to the distributed-computing feature of RoboResearch, I'm not worrying about computation time.  I've been running 5-20 at a time when I'm tinkering, and I could expand if I wanted.  Computer labs are a wonderful thing.  -- [[Simonton]]
** That is so totally awesome, using your lab like a miniture super-computer. We just can't compete with that, hah. --[[Chase-san]]
** Speak for yourself! *Voidious orders dual CPU / quad core Mac Pro.* Just kidding, that is pretty sweet man. =) -- [[Voidious]]
** There's nothing miniature about running 22 battles at once!  (That's ... like ... 60 GHz.)  I used the same technique for a research project & was once using over 100 machines in parallel.  And I was sitting across the country on Christmas break!  It was pretty sweet. -- [[Simonton]]
*** 100!!?!11?one!! O.o... I am.. very impressed... 22 battles at once, your really putting those machines to work. Remind me to buy up alot of surplus computers and cluster them. --[[Chase-san]]

Oh, I forgot to say, thanks for running those battles against [[Shadow]], [[Chase]].  I wish the results were a little different! -- [[Simonton]]
*I just copied it from the TC2k6 pages, aren't you using 500 rounds? --[[Chase-san]]
*Oh, look at that!  I thought I checked before to see if the scores were from the same version of Shadow ... apparently I didn't check very well!  Thanks just the same, though.  -- [[Simonton]]

Impressive scores so far, put the top guns togeather and might have a top 10 bot, atleast if the movement is as good. --[[Chase-san]]

Now I just have to figure out exactly what that PerformanceEnhancingBug did .... -- [[Simonton]]

Look at the huge difference between 2 rounds with max match length of 1 and 2.  Why would max match length of 1 do so well?  And given that it does, why wouldn't 2 work better?  At least then it would know if the enemy was accelerating/decelerating. --[[Simonton]]

Note sure, this has happened to me before when making one of my first DC guns. Also, why not put some of that processing power to work on the rumble. :P --[[Chase-san]]
* All the parallel machines run off the same directory (NSF mount), so any bots that use data saving would get messed up if they ran more than one at the same time. That, and I (or someone ... I haven't hear back from sourceforge about hosting RoboResearch) would have to write some code to submit RoboResearch-style results to the rumble.  -- [[Simonton]]

I noticed that WeeklongObsession dropped a bit when you switched to matching on lateralVelocity/advancingVelocity, have you considered changing your bots here to using acceleration/angularVelocity? -- [[Skilgannon]]

Summary:
Consciousness check: 4 + 4 =
This change is a minor edit. Send email notification that Simonton/PMResearch has been changed.
(Visit Preferences to set your user name.)

View other revisions
Robo Home | Simonton | Changes | Preferences | AllPages