Archived talk:Pattern Matcher Challenge 20091015

From Robowiki
Revision as of 02:41, 16 October 2009 by Bnorm (talk | contribs) (Migrating)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Mmmm, it's getting lonely below the dotted line! Where do you guys find the time to improve your (patternmatching) robots???

  • Until recently i spent about 2 days a month on my robot. Right now i have more spare time and i have to make an effort NOT to spend too much of it Robocoding :-) -- Vic

Well, I had the luxery of a whole hour yesterday evening and was able to improve performance to a whopping 72.89% ;-) I still miss quite frequently, often just missing PatternBot by a fraction. I believe this is due to the setup of my bot (which was designed for melee): the calculation of the predicted bearing takes place in the Target-code, after which (mini)Fenrir requests this bearing, aims the gun and shoots. This can result in a delay, causing the gun to mis-allign. It's probably better to aim the gun in the same ScannedRobotEvent that updates the enemy info...
I will try this when i find the time again. --Loki

I found some time and added two minor changes: 1) now uses lateral velocity and acceleration for matching, 2) aim the gun in the ScannedRobotEvent. Result is only a slight improvement of approx. 2.5%. Probable causes:

  1. i use exact match instead of best match, resulting in lower match rates (the succesratio of matching is 99.32%, but this is mainly based on the contribution of small pattern lengths in the variable length matching)
  2. i don't take transversal movement into account in the prediction of the future position, resulting in a predicted angle that is to large. You can see this by the many 'near-misses'.

Maybe i have reached the limit of this type of pattern matching --Loki

update: I still have problems with the initial fase and too many near misses. --Loki

I disagree - your style of matching is similar to TeancumPMC, who uses lateral velocity and advancing velocity. The reason this is stronger against PatternBot is that this helps more accurately account for when PatternBot is moving toward or away from me (which might greatly reduce the near-misses). Now, if you can go beyond TeancumPMC with a relative sort of pattern-matcher, I want to know how :-) -- Kawigi


  • What do you use for projecting the new bearing then Vic? I use something like LateralVelocity. -- PEZ
    • I'm not sure what you mean by "projecting the new bearing"..could you explain? --Vic
      • The part when you figure out your new gun heading. This "prediction" I call "projection" in my codesome times.... -- PEZ
    • Ok. I guess i have a pretty standard delta velocity | delta heading SymbolicPatternMatcher inspired by Albert. It predicts the path of the enemy tick by tick until it finds a point where enemy_travel_time == bullet_time. Then i calculate the gunheading to that point. I have gone through a lot of trouble to make that point as accurate as possible. Ender's PM still has one known weakness. I am hoping that i can beat PatternBot when i remove that weakness. One particular strong point might be that Ender's PM can match against very large patterns (up to 200 ticks) without performance problems (read: skipped turns). Also i make sure that it records contiguous patterns and only matches and predicts using contiguous patterns. -- Vic
  • I have entered my results with a stationary version of mini.Fenrir but am not realy shure about the way the Index is calculated. I have presented the score of the bullet damage by mini.Fenrir. Is this correct? -- Loki
    • Correct :-) Vic
      • Not anymore, we have changed the index to the formula above. Could you fill in the new Index? --Vic

I'm struggling with finding the bug in my pattern matcher. It seems to do the matching quite well. But the projection fails obviously. A check question:

  • LeachPMC sometimes finds patterns of 600+ length against PatternBot. And it's often 200+ and 50+ on average. Does that seem within reason or should I hunt my matcher for errors instead of the projector? -- PEZ
    • Found the bug! It was inside the projector as I suspected. It seems PatternBot is truly predictable. LeachPMC actually finds patterns of 400+ in most rounds and I saw it match a pattern of whopping 1068 length also. Though it seems mathcing that large patterns makes me skip turns. Quite many. 797 in the last 100 round match. How does that compare to your robots? -- PEZ
    • I think the maximum pattern period should be exactly 600. But the pattern you match against is basically only limited by the duration of the round. So 1068 sounds totally within reason. The skipped turns are probably due to your large buffer size. I think 5000 should be big enough, since it only needs to contain one intact 600 tick pattern and a bit more for the future prediction. -- Vic
    • Thanks. I tried using 5k for the buffer, but it lowered my index with a few percent so I'm trying 15k now. -- PEZ

Good tests are invaluable. I think this challenge has raised the quality of many pattern matchers. Most notably Leachs' of course, which started out being only half as good as a HeadOnTargeting gun. =) -- PEZ

How fast are peoples' hit-percentages growing in this? I suspect it takes Teancum's gun a little longer to learn than some others here, at least against PatternBot, but it takes it about 50 rounds or so before he gets his hit-rate over 90% and starts killing PatternBot. -- Kawigi


LeachPMC need one or two rounds before hit rates start being close to 100%. But since I don't like the first missed shots, I save the recording data between matches. =) -- PEZ

Also it takes MicroAspidPMC a couple of rounds to get a good percentage. Then it improves during 5-10 additional rounds, but not so much. -- Albert

Yeah, I think that TeancumPMC needs to see the movement at a few different angles before he really can predict fully accurately what's going to happen. -- Kawigi

EnderPMC needs one clean (no collisions) round (if it has no saved data) to get to about 98%. But strangely enough it seems to improve slightly in the next 10 or so matches (even with saved data!). This could be the matching probability of the very first shot in the true pattern movement phase. Just before that, PatternBot has turned a variable amount of degrees and before that, it has travelled linearly for a variable distance. The more data is stored, the higher the probability you can match the first shot correctly. Writing this down i realise that i should increase my amount of saved data. Currently i store only 5000 Ticks (inbetween rounds 15000) so it will take the first 10 or so rounds to fill back up to 15000. -- Vic

TeancumPMC is now submitted! -- Kawigi

There are 2 bots with an index over 100%, but below the dotted line. Is this a mistake, or am i misunderstanding something? -- Tango

The percentage is your bullet damage divided by PatternMatcherBot's - you complete the challenge when you beat it, those people still have a lower survival score than PatterMatcherBot. -- Kawigi

Yep, and in order to out-survive PatternMatcherBot you need to account for the beginning of rounds (ie before PatternMatcherBot get's into it's routine) and to be honest i couldn't be bothered so just settled for a 100%+ index -- Brainfade

I thought that might be it. Would that not cause a problem if someone beat PMB but got a lower index than someone who didn't? (i think it's possible...) -- Tango

What would be the problem exactly? =) -- PEZ

BotA would be below BotB because it had a lower index, but BotA would be meant to be above the line, and BotB below it. It's impossible to put them in an order that would suit both systems. -- Tango

I've been robocoding for a whole week now! I'm pretty chuffed with my 95.98% :-) ...no PMC optimizations though, for me thats like shrinking code is for PEZ -- Skilgannon

Very nice! -- Simonton

Not to bad for a first attempt I suppose, didn't even skip a turn either. --Chase-san

Hi All, I am just trying out pattern matching (switchover from familiar GFs...) . Is there anything else I can match other than velocity and Delta Heading To make it more effective? Also, other than PatternBot, I seem to have some skipped turns , stopping me for that round. Anyone has any idea? I may implement more in a Mini (Very Later...) and Maybe with wavesurfing in a mega (long way to go). Thanks. -- Aryary

Make the "keylength" that you are searching for search for several different sizes, and choose the biggest that gets a match. Other than that, delta-heading and velocity should be plenty. If you are getting stopped you probably have a runaway loop somewhere. -- Skilgannon

Hmm. Fixed Most skipped turns by editing some part within the searching, so now I only face problems when I meet a bot staying still and firing at me. The WaveSurfing Challenge Bots for exmaple. After about 3-4 rounds my bot gets jammed. Anyone knows why? Sorry I am just new to Pattern Matching. Thanks. Btw, the gun performance improved. -- Aryary