Simonton/PMResearch

I have a goal to make pattern matching a viable alternative to the top GF guns. Grab some base code from [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
73.47	79.86	72.30	79.61	74.15	75.89	SeaSerpent 0.2
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

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
86.74	76.94	82.65	78.50	79.54	80.87	99.93	85.05	92.94		88.08	82.96	89.79	85.33	SeaSerpent 0.2
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

• Yup. I even plan on it. Sometime ....... -- Simonton
• Hey, it actually turned out to give almost the exact same score. Which is nice, because it saves about 50 instructions (CodeSize). And actually, [version 1.8] will give a better comparison, because 1.6.3 matched on 11 angular velocity symbols. 1.7.x matched on 17 advancing velocity symbols, 1.8 matches on 9. -- Simonton