Editing revision 154 of WaveSurfing

Robo Home | Changes | Preferences | AllPages

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

=== Variations and techniques ====
/TrueSurf - /GoToStyle - /ShrapnelSurf - /PrecisePrediction - /ReverseForwardSensors - [[/Experiments]] - [[/NanoSurfer]] - /PatternSurfing - /Archive20070511

=== Definition ===
A movement which focuses on the enemy waves, and not the enemy. The general idea consists in "surf" the enemy waves, and like human surfers, try not to be caught by the waves peaks "breaking" over you.

=== Useful links ===
* '''[[/Tutorial|WaveSurfing Tutorial]]''' - Walks you through creating a bot with a basic WaveSurfing movement with [[/PrecisePrediction|Precise Prediction]].
* '''EnergyDrop''' - A WaveSurfer must keep careful track of an opponent's energy level to detect when he fires a bullet.
* '''EnemyWaves''' - It's called WaveSuffering because of some of the most minute details of reconstructing the enemy's perspective before firing; some key details are discussed on this page.
* '''FuturePosition''' - [[Albert]]'s very, very helpful stand-alone class for simulating movement within the Robocode laws of physics. Along with the first two links to predict the enemy's segmentation data and wave positions, precisely predicting your tank's movement is crucial to figuring out the safest part of the wave you can get to before it hits.
* '''WallSmoothing''' - Not an explicit, or even necessary, part of WaveSurfing, but it is used by nearly all expert WaveSurfers.
* '''[[CassiusClay/Butterfly]]''' - A main stream way of implementing the central parts of a WaveSurfer. Code is open source and very neat.
* '''[[Dookious/DookiSailer]]''' - A very slight variation on CassiusClay's surfing algorithm. Code is open source, if a little messy.
**[[Slalom Surfing]] - An extension of Dookious' advanced surfing method.

=== Specific Challenges ===
* [[/BarracudaChallenge]]
* [[/DevilFISHChallenge]]
* [[WaveSurfingChallenge]]
* [[WaveSurfingChallenge2K6]]

=== Bots Using it ===
* [[Aleph]]
* [[Apollon]] (MiniBot)
* [[Artist]] (MicroBot)
* [[Ascendant]]
* [[CassiusClay]]
* [[Chomksy]] 1.5+
* [[Cyanide]]
* [[Crusader]]
* [[DarkHallow]]
* [[Dookious]]
* [[Immortal]]
* [[Komarious]] (MiniBot)
* [[Krabby2]]
* [[Lacrimas]]
* [[Okami]] 1.X or greater.
* [[Pear]]
* [[Phoenix]]
* [[PowerHouse]]
* [[Pugilist]] 1.0+ (MiniBot)
* [[PulsarMax]]
* [[R2D2]] (MiniBot)
* [[RaikoMX]] 0.2 or greater.
* [[SandboxDT]]
* [[Shadow]]
* [[Shiva]]
* [[SilverSurfer]]
* [[Stampede2]]
* [[Strength]]
* [[Toad]]
* [[Tron]]3
* [[WaveSerpent]]
* [[YALT]] - became [[Phoenix]]

(Well, I guess it can be simplified as the X top bots in the general RR@H class...) -- [[PEZ]]

----

Added six bots to the list of wave surfers, and I'm sure it's still missing quite a few: [[Chomksy]] 1.5+, [[Dookious]], [[Phoenix]], [[PowerHouse]], [[Stampede2]], and [[Toad]]. That list has come in handy for me in trying to learn new things about WaveSurfing, so I figured it would be good to get it up to date. -- [[Voidious]]

It seems like there is a significant lack of nicely outlined and detailed info about WaveSurfing on the wiki in comparison to how many masterful WaveSurfers there are in the rumble. (There is a good amount of info, it's just spread out and not always distilled to the precise facts.) Topics like GuessFactorTargeting are very clearly taught by pages like [[GuessFactorTargeting/Tutorial|Kawigi's tutorial]], and I may try and provide similar details for WaveSurfing in the near future. -- [[Voidious]]

Is there a bot that uses a godawlfully simple implimentation of Wavesurfing, asto explain the most basic way of creating a wave surfer, as thats the kind of bot I think would be best for a tutorial, not something with all the dodads that someone new would give up trying to understand and instead just copy and paste. Basically WaveSurfing reduced to something that might kinda surf, if it would stop hitting into walls =P. -- [[Chase-san]]

The bottom line is that there's a lot of nitty gritty details to get right in WaveSurfing, and it is quite worth it to get all of those details right. The BasicSurfer bot in the [[WaveSurfing/Tutorial|WaveSurfing tutorial]] is probably the simplest to understand, although it may still seem a bit complex at first. Have you looked at that one yet? I studied CassiusClay quite a bit while I was learning, but there is a lot more to that tank's movement code. -- [[Voidious]]

Yeah, the fact is that wavesurfing is pretty complicated even in its most basic form. The idea is simple enough, but in practice there are a lot of details that just have to be right or it won't work. Basically when you set out to make a wavesurfer, you just have to accept that it will involve a lot of [[WaveSuffering|time and effort]]. -[[wcsv]]

Yah, I know what you mena no, I have been putting alot into making this surfer work, it uses CustomEvents to wavesurf, but it seems to miss every other bullet when it is far away from the enemy. Any suggestions? (other then try it a different way please) -- [[Chase-san]]

Correct EnergyDrop detection is very important. Besides monitoring the enemy's energy, you have to account for 
*your bullets hitting the enemy
*the enemy's bullets hitting you
*the enemy banging into the wall
*collisions between you and the enemy (although this one is not so simple and you can forget it if you keep distance)
Use the <nowiki>onBulletHit and onHitByBullet</nowiki> to determine the real energydrop. Make a testbot that sits still but fires (random firepower) and does output to the debugwindow. Let your own bot fire small bullets (0.5 or so) and check if every bullet fired at you is detected ''with the right bulletpower''. Try to get the details right before tweaking against non-HOT targeters. -- [[GrubbmGait]]

Noo thats not what I meant, I already have that working just fine. Its the CustomEvents, I'll see what I can do to make it work right. -- [[Chase-san]]

As seen from Velsheas sour to spot 75, however I acquire as what is a good idea to Segment this movement by, everytime I think it should make it better, it makes it worse instead. Any suggestions (Wavesuffereing indeed)? -- [[Chase-san]]

Segment your surfing on acceleration, velocity, and distance. The rest is just details. =) --[[David Alves]]

Segment it on nothing until you get over 99% against WSC Bot A, then segment and get 98% against Bot B. BasicGFSurfer doesn't segment on anything and lacks lots of other important details, but it's in the top 50 just because it's bug free... -- [[Voidious]]

I would like to think mine are rather low in the bug area, but considering it gets about 40% vs B without segments (about 56 with), it still needs some work. -- [[Chase-san]]

* How's it do against Bot A? Sorry, I'm tired, you definitely need segmentation to get 98% against Bot B... But I wouldn't recommend doing that until you get 99% against Bot A. -- [[Voidious]]
* GresSuffurd surfs unsegmented and scores 99% against botA and around 60% against B and C. The first segmentation to use is 'current speed' (from 2 ticks ago ofcourse) to pump up the score against bot B and C. To get 99% against bot A you have to watch some battles, but the problem probably is that you get to close to it. Keeping distance and/or dive-in protection is the answer for that.  -- [[GrubbmGait]]
* Yah, I was attempting the whole, "from 2 rounds ago", but since from 1 tick ago is working better I guess I still have some bugs. I dreamed about 1 I might have, and thus I might need to fix that. -- [[Chase-san]]

I want some input on 'another' idea I have. Now I have many that are just plain FAIL, but this one might work. It has to do with a method such as WaveSerpents that just records the last n gf's it gets hit at and dodges them, thats about where simularities end, instead of just dodging all of those, which though while the internal surfing mechanism takes decent care of this. Do a core kernel calculation on all the GF's and pick the top n for dodging, which would probably be dynamic, based on how many different patterns present themselves. Basically all this does is reduce the static in the gf dodging to more well defined danger do not enter area's. --[[Chase-san]]

It's not clear to me what "core kernel calculation on all the GF's" means, precisely, but it reminds me of how [[Chalk]] and [[Lukious]] use DynamicClustering / KernelDensity on some ''n'' most similar scans to calculate the dangers for each wave. This isn't anything "pattern" based, but using a distance function on various attributes of the scans for those situations. You could surely use movement patterns as the distance function, though. -- [[Voidious]]

Kernel Density on a list of GF's to find the most densely populated ones, and then use those as the gf's to dodge then all the bunches of them. --[[Chase-san]]

Sounds very much like what [[Chalk]] or [[Lukious]] does, though I haven't read WaveSerpent's code as much. The key difference is you'd be using pattern based stats to determine the n most similar scans, instead of a distancing function on just the attributes from a scan? Sounds like an interesting idea and probably worth the experience of trying it, but based on experience with PatternMatching in targeting, I wouldn't have high hopes of it outperforming DynamicClustering or VisitCountStats based surfing. -- [[Voidious]]

It doesn't use PatternMatching, it uses the standard way of obtaining the GF, and just dumps the number into a buffer. It is exactly like how Chalk and Lukious does it, except it uses it for the surfing, instead of the gun (though thats certainly a possiblity aswell and could be interesting). --[[Chase-san]]

Actually, both [[Chalk]] and [[Lukious]] use that kind of stat system for gun and surfing. -- [[Voidious]]

My head hurts, so just to clairify and make sure we're on the same page, it uses the standard method to gain the gf, it also stores the gf in sliced bins, not a log as in DC or PM, it however keeps a list of the n latest GFs such as WaveSerpent does, my idea is to use Kernel Density to reduce the number of GF's to avoid. --[[Chase-san]]

Ok - I still don't completely understand how it'd all work, but that's ok. But also just to clarify, Chalk and Lukious definitely use the same methodologies for both their gun and surf stats systems (DynamicClustering). -- [[Voidious]]

I know all about dynamic clustering, made a few chalk like systems aswell. --[[Chase-san]]

Now that I think about it, its kinda like Dynamic Clsutering without the Clustering, so to speak. --[[Chase-san]]

----

''Rambling discussion snipped from [[Horizon/Questions]] on 7/20/2007''...

Here's a suggestion, you seem fairly active and have a working wavesurfing so I thought I would give the suggestion to you: How about keeping an extra 2 bins that save the amount of times you have been hit by linear or circular targeting? I suggest this because the GF you get hit on is not constant for these targeting methods, instead depending on things like speed, heading, etc. You could weight these bins on top of the normal ones when deciding the safest place to move to. -- [[Skilgannon]]

That's an interesting idea, and it really could give you a head start against those methods when writing a WaveSurfing movement. However, considering how well some WaveSurfers do against LinearTargeting and CircularTargeting already (check out [[MovementChallenge2K6/Results]] or the [[WaveSurfing/DevilFISHChallenge]]), I personally wouldn't want to muddy up my code with a special case for them. Also, consider that just because LT or CT would have hit you in that spot doesn't mean they're using it - if you start thinking you're facing LT and you're really facing GuessFactor / VisitCountStats or PatternMatching, you could really be corrupting your stats.-- [[Voidious]]

What I'm thinking is using these bins *on top of* the current bins. You still take into account your normal stats, but if you get hit on the factor that LT or CT gives then you *also* increment that bin. When you are deciding where to move, you could do one of several things: average the values of the LT/CT bins and the bins they 'line up with' for this wave, add the values of the two bins together, or even (temporarily) replace the value of that bin with the LT/CT bin.

I know that some bots are getting amazing results in the MC, but seeing the number of rounds run in RR@H is only 35 an extra 3 or 4 shots avoided while building segmentation data can give you an extra few percent against these bots, which translates into an increase overall. -- [[Skilgannon]]

Yeah, I see how it would work - it's definitely an interesting and perfectly valid idea. I hope I don't come off as too much of an [http://en.wikipedia.org/wiki/Eeyore Eeyore] when I say I don't think it's worth it. =)

Consider this, though: [[Dookious]] pre-loads one [[HeadOnTargeting]] hit into the surf stats before a match starts, so it actually is hard-coded to dodge <nowiki>HoT</nowiki> from the get go, yet it gets the same score (99.6%) in both the [[WaveSurfing/BarracudaChallenge]] and [[WaveSurfing/DevilFISHChallenge]]. Those are 35 round matches vs HeadOnTargeting and LinearTargeting, respectively. I kind of doubt any part of the statistics could improve those scores; it's more a matter of precise prediction, dive protection, distancing, and having zero bugs in your code.

Still, I say give it a go - you could well find it really is worth all the trouble, or it could lead you to some other great idea. I've tried countless ideas that didn't work out in the end, but I always learned something from them, and some of them are still kicking around my brain, waiting to be revisited and done correctly.

-- [[Voidious]]

Well for those of us who AREN'T able to get 100% bug free code ;-) Just kidding, though. I had one other idea, that was for an anti-ws gun. You use precise-prediction to figure out your enemies max escape angle, and then shoot at the lowest bin. What's your take on this? PS. Sorry about the page hijack, Aaron ;-)-- [[Skilgannon]]

It might work for few shots, but thats about it. As its not based on the enemies movements but instead on your robots own interal aiming device. If you really wanna make something like that, try only increasing the bins when one of your robots bullets actually hit and then interally having the enemy 'surf' the factor. But the differences in segmentation will quickly be made apparent, as I don't think this would work to well either. --[[Chase-san]]

My take on that is: it's a great idea, and one that I have explored myself quite a bit! =) Like Chase said, though, you need to record on real bullet hits, not normal wave hits. I have never had much too much success in making it into a killer AntiSurfer gun, though. Dookious actually does log "negative" hits for bullet hits into the stats of the AntiSurfer gun to try and simulate enemy surf stats a little, but it doesn't make a huge difference.

Using bullet hit stats to augment my AntiSurfer gun in an effective way is probably at the top of my list of good ideas that I want to revisit. The main problem with shooting at the "lowest" bin, in my mind, is that the enemy is going to dodge the other bullets in the air first, and then they will choose the lowest from the remaining bins, not the lowest overall, so I think you need to try and extrapolate their likely movement across all bullets in the air ''and'' the one you're about to fire. Also, of course, everyone segments on different attributes, so that's the other glaring issue. Lastly, precise prediction is super CPU intensive, so you will end up with a super SlowBot if you aren't efficient about what you need to calculate. (Sorry for hijacking, too, maybe we can move this discussion elsewhere...)

-- [[Voidious]]

I was thinking about trying something like that as a joke: making a gun that applies [[PrecisePrediction]] to the enemy, choosing which direction it is most likely to go and firing there. The joke would be that you could copy the segmentation and precise prediction from any surfer, be it [[BasicSurfer]] or [[Dookious]], and it would be able to get a perfect score against that bot and only that bot.

Getting back to where the conversation started, I have a few ideas that I think can increase my surfing ability against linear/circular targeting. For example, a circular gun takes two factors into account when it fires: your speed and your turning amount at the time of firing. Therefore, wouldn't it make sense to choose the segment or cluster not based on what your current velocity and rotation is but what it was when the wave you are surfing was fired?

-- [[AaronR]]

Aaron, that may just be why things are screwing up in your WS. You do need to choose the segments at time of the firing of the wave. The easiest way to do this is by giving each wave a 1D array at its time of creation, as done in the [[GFTargetingBot]].

About this anti-surfer gun, on second thoughts even if you segment it quite highly it will not update the stats as quickly as they are, so your stats would mis-align, and you would miss. So it's one and only use would be to knock down top bots' PL scores, I guess. <evil chuckle>

My last contribution for now (while I've got everybody's attention), and this one I'm fairly sure on. You guys are calculating the max escape angle using answer 1 on [[TrigChallenges]], when you should be using answer 2. It is shorter to move on the chord than along the arc, so the MEA is bigger for answer 2. IMHO, this is why you are sometimes recording GFs of more than +-1.

-- [[Skilgannon]]

It's been brought up now and again, but I'm pretty sure the max escape angle is found by going exactly perpendicular to the absolute bearing to the enemy at fire time. [[Kawigi]] (long ago) and [[Simonton]] (more recently) have both used their math chops to actually prove this, IIRC. The rought calculation is Math.asin(8/bullet velocity), viewable by imagining a right triangle with the proportions of max bot speed and the bullet's velocity. [[Dookious]] and [[Phoenix]] even use precise prediction to calculate the resulting escape angle exactly, also taking walls and WallSmoothing into account. -- [[Voidious]]

Well, Math.asin(8/bullet velocity) gives a smaller result than 2*Math.asin(8/(2*bullet velocity)), so I think that the perpendicular movement is slightly longer. Another way of looking at it, the average heading in the ChordMovement is perpendicular to the enemy, and it is perpendicular half-way to the destination - taking the shortest route to the point. I'm guessing that right now you get GFs greater than +-1 against bots that move in straight lines, Walls for example, because they take the ChordMovement instead of PerpendicularMovement -- [[Skilgannon]]

* Hmm, why would you ever use 2*Math.asin(8/(2*bullet velocity))? Anyway, the bottom of the GuessFactor page has some theory talk about the max escape angle. Based on my own calculations and my trust in [[Kawigi]] and [[Simonton]] as super smart dudes, I definitely think moving perpendicular to the bearing-to-enemy-at-fire-time is the way to maximize escape angle. -- [[Voidious]]
* It's true. Simple proof-to-yourself: moving in a straight line is obviously going to get you the greatest distance, the question is what DIRECTION do you travel. Try a few angles, you'll see that 90 degrees is optimal. So again, the answer is: exactly perpendicular movement from the line to the enemy AT THE TIME OF FIRE. Moving along a chord will actually be a lesser angle than 90 degrees, which will give you a smaller escape angle. Even smaller, as [[Skilgannon]] points out, would be moving in an orbit. Actual escape angles can be '''slightly''' greater than this based on the fact that we're working with a discrete system here, so the bot could move a maximum of 7.999999999 pixels further than you'd think on paper before the system detects the bullet hit. But then, the bullet will also hit one tick sooner than you'd think on paper given the width of the bot, so those pretty much cancel each other out. The only other option I can figure is off-by-one bugs in the caculation of fire time, etc. -- [[Simonton]]
**All calculations are for one tick, enemy distancer of 1000, and max velocity. Btw equal sign might also mean approximately equal to.
<pre>
***Perpendicular angle=tan(8/1000) =0.0080001706710 because 8 is the most the enemy can go in 1 tick and the enemy distance is 1000 (think about it as a triangle)
***Chord angle =2*asin(8/2000)=0.0080000213334 because the chord angle formula is 2*asin(chordlength/2(radius))); chordlength (most enemy can travel in 1 tick) is 8, and radius (distance) is 1000
***Arc (orbit angle) =8/1000 =0.0080000000000 because the arclength angle formula is angle=arclength/radius aka distance; arclength is 8 (most the enemy can travel in 1 tick), radius is enemy distance.
</pre>
Therefore moving perpendicular to the enemy gives you the maximum escape angle.
--[[Starrynte]]

I had at one time thought the same thing that if it was moving at a 45 degree towards the enemy at a certain speed it would end up outside the range by alot, but after some bits of math, I figure out that its all mathematical, and it takes all that into account. --[[Chase-san]]

Starrynte, you calculate MEA with bulletSpeed and enemyMaxVelocity, not distance. Thus:

For the 'arc movement': theta = 8/11 = 0.7272

For the 'chord movement': theta = 2*asin(8/(2*11)) = 0.7443

For 'perpendicular at time of fire': theta = asin(8/11) = 0.8143

Hmm, I see why the 'perp at fire' is actually the biggest now, I hope this explanation makes people understand and not just accept =). If you move perp. at fire, you end up moving away at a bigger and bigger angle. This makes the bullet take longer to reach the enemy, increasing the time allowed to increase the MEA. Thus, moving away slightly increases the MEA more than moving sideways as fast as possible, because there is more time before the bullet hits. -- [[Skilgannon]]
* I see your point. What i was trying to calculate was the MEA in one tick with a fixed distance, as you wouldn't use bullet speed if you're doing it that way. But it's true that if you are calculating the MEA for until the bullet intercepts the enemy, you would use bullet speed. --[[Starrynte]]

Question for all those wavesurfers out there, if you could perfectly predicted what gf the enemy fired at could you dodge every shot ? if so what movement strategies would you use -- [[Gorded]]

* Well, the scores against HeadOnTargeting (Bot A) in the [[WaveSurfingChallenge2K6]] are the best answer to that. We pretty much know exactly where every one of those bullets is heading. You could dodge very close to every shot, unless the enemy moved very very close to you (like a RamBot). I'm not sure what you mean by "what movement strategies", though - you'd just use your normal WaveSurfing algorithm with the highest danger at the GuessFactor where the bullet was on the wave. -- [[Voidious]]

Well it seems that even the best of bots cant dodge every bullet from Bot A even though we know where the bullets is  . What i was getting at when i say what movement strategies was would A Shrapnel surfer or True Surfer fair better than the other ? -- [[Gorded]]

* I honestly don't think either would do better than the other. The style of algorithm is far less important than a clean, precise, well-tuned implementation, especially against HeadOnTargeting. In fact, against a gun that fires at a single GuessFactor, TrueSurfing and Shrapnel Surfing would give the same relative dangers for every GuessFactor, I think? And I bet GoTo would have you moving to the same spot, too. That said, I say dive in and give it a try. =) -- [[Voidious]]

If you know _exactly_ what angle the enemy fires, maybe a normal surfer is not ideal. Normally a surfer will try to get the furthest possible from the predicted gf, making it easier to get trapped in extreme conditions. Maybe a goto surfer without a lot of smoothing would be the best? -- [[ABC]]

I would say that those rare cases that Bot A hits is when the surfer starts cornered, and takes a hit when trying to maneuver out. If your bot is at a reasonable distance and takes into account all the surfable waves, I don't think it is really possible to be hit by power 3 (and thus slow) GF 0 bullets unless there are bugs in your algorithm. Which I have learned is always possible, even at 2100+ scores =) -- [[Skilgannon]]

Depends on what you call a bug :). If you wallSmooth a lot and have a permissive "angle to enemy" threshold you can get into very tight spots. And then there are those small decisions like if the enemy's GF 0 calculation exactly in the same tick as yours... -- [[ABC]]

Well, I know DrussGT and Dookious have unlimited WallSmoothing and don't have an "angle to enemy" threshold. My WSC tests with DrussGT 1.0.5 he got 0 damage, 4 damage, 0 damage against Bot A over 500 rounds. IMO your danger calculation should be able to say whether a spot is a bad position or not, without having to add things like "angle to enemy" thresholds, but I guess that's just personal preference. And I'm not sure I understand your final remark...I thought the definition of GF 0 is where a HOT would shoot? So surely there is only 1 possible tick to base the data off of? -- [[Skilgannon]]

* I don't see why you couldn't use "angle to enemy" as a factor in your danger calculations, just like we use distance. But you're right that I don't think a strict threshold is the best way to go. Then again, [[Phoenix]] uses something more like that (and less like what we do) and he does pretty well. -- [[Voidious]]

Against Bot A yes, but against other (moving) HOT bots there are some differences because some will not take the tick needed for gun turn into account. You're right that a perfect movement should predict bad positions, I know Shadow's movement is far from perfect, but everytime I try to make it "perfect" it ends up (very slightly) better against Bot A and worse against real opponents... ;) -- [[ABC]]

* Right - in my gun, I project each bot's movement one tick (theirs is estimated, mine isn't) to use as the basis for GF=0. In my movement, I actually assume the enemy ''doesn't'' do this, for two reasons: most bots don't do that in their guns; the ones that don't are the ones that I dodge the best, so a little imprecision would hurt more against them than against a better gun. -- [[Voidious]]

So you assume they fired at your position 2 ticks before you detected the energy drop? I don't remeber now what I decided to do in my movement, but I remember testing different tweaks, and noticing different HOT bots acting slightly different. And I usually keep the one that dodges the top guns best. ;) -- [[ABC]]

* Yeah... Actually, they aren't really firing at that position, but at that absolute bearing, since they actually end up firing from their position 1 tick ago. At least I'm 99% sure that's what I do. I haven't dug deep into that stuff for a while now ;) -- [[Voidious]]

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

View other revisions
Robo Home | Changes | Preferences | AllPages