Editing revision 45 of WaveSurfing/TrueSurf

Robo Home | Changes | Preferences | AllPages

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

"True surfing" is my name on what RaikoMX does. It picks the closest EnemyWave carrying a bullet and then in every tick checks if its visit count ahead of it is less then the current bin its visiting. If so it continues to move forward. If not it reverses. Thus truly surfing the wave. Pretty cool! And I think that correctly tuned it should be a very, very effective way of doing this surfing thingy. -- [[PEZ]]

can you define visit count and current bin please?--andrew

You'll have to read the VisitCountStats and EnemyWave page for that I guess. But a quick answer... EnemyWaves are just like normal [[Wave]] only fired from the enemy firing position. As the waves travels towards you you are always somewhere on the scale from -max_escape_angle to +max_escape_angle (or GF-1 to GF+1). With VisitCount stats this translates to bin 0 to bin max_bins in your stats array. Your current position can therefore be referred to as the "current bin." The "visit count" is  the number of visits added to the bin when the waves have hit the target. -- [[PEZ]]

thanks,i was just confused about which was which in the situation--andrew

I am curious how "True Surfing" ensures that you get to the edges of the graph. If all you are checking is the bin you are moving to as it compares to your current bin is it not possible that you could "get stuck" between a couple of exceptionaly high peaks and creat a "high valley"? -- [[jim]]

The distance looked ahead changes as the bullet closes - so it should find any green pastures far ahead, at least as far as a goto style bot would.  I think that this is a general problem with focusing on one bullet at a time, however the badness of my implementation introduces a small random factor which prevents it getting too locked in to one part of the graph. :-)  A good implementation could look at more than one bullet and make a more informed decision, something I will get around to implementing. -- [[Jamougha]]

[[Shadow]] looks at all the bullets in the air, wheights them acording to distance (currently 1/sqr(dist)), and sums the visit counts. <pre>if (gfDanger_invert < gfDanger_continue) moveDir *= -1</pre> There you have it [[PEZ]], I think it qualifies as TrueSurfing. ;) -- [[ABC]]

Oh! *slaps head* I knew you had to be reacting to more than one bullet to get such a superb movement, but it never occured to me to do it so simply.  I spent a lot of time trying to do a simulation of my movement with various patterns until the last bullet arrived, but it always needed Deep Blue to keep up. ;-)  Very interesting that we came up with such similar basic solutions though... but then I guess I'd tried everything else already, hehe.  -- [[Jamougha]]

Wow, thanks ABC! You actually cut the waves instead of surfing them. Hang ten! I'll definately try this. Makes a lot of sense. -- [[PEZ]]

I'm doing something like this now, prediction seems important, need more work in that area, especially when wall avoiding I think. I actualyl eventually gave up sort of and gave the FuturePosition class a try and it worked better at least. Many thanks for the inspiration! Question though, have I missed something or doesn't one need to compensate the visited guessfactors when adding them up? I mean the closer one gets to the ends (1 and -1) the fewer neighbours there are. Though this is quite a predictable amount. I doubt I'm the only one compensating for this though? Seemed to help some at least. Lots of things left to be tried with the wave surfing, but when I finally got it to work I was so relieved :) By the way general advice for people starting with wavesurfing: take it step by step and don't try and do it all at once, get the statistics collection to work first, 
don't surf waves that have went passed you (doh!), keep trying!, start with a large battlefield where you can predict you position easily (no walls), start with wall bouncing after that, test against a simple robot firing rarely and always head on, and then keep trying with more advanced robots, took me a couple of days to find that bug with trying to surf "old" waves. :-) -- [[Pulsar]]

Yes, there are lots and lots of traps to fall into when wave surfing. About that edge compensation. We don't actually know yet it's a problem or not. All my efforts with it has resulted in a lack of improvement at the best. And none of the top-3 dogs (all wave surfers) needs it to get their 2K+ scores so it might be a thing to try when all else is in place. And even then it might prove to   be not necessary... The SilverSurfer page is full of talk about this (should be moved to BinSmoothing/EdgeProtection if someone feels like doing that work).

When it comes to walls. The thing to do is to iterate the movements of the wave and your bot (with wall smoothing/avoidance) until the wave and your future position impacts. That avoids heading for edge guess factors that are outside the field. Exact future position prediction is not necessary. [[Pugilist]] only does the roughest estimation imaginable and it scores quite high even so.

-- [[PEZ]]

aaah thanks for the heads up regarding the SilverSurfer page, I'll check it out. Didn't realise that there could be such valuable discussions on the bot pages. What I do is quite simple and a very quick test showed that it didn't get much worse at least, actually a litle better, but could very well be random noise. At the beginning I populate one of my wave surfing guessfactor arrays with 1's and calculate the value for each index there (a compensation-array). Then I simply divide with the corresponding index value every time I calc the guessfactor value (visits) for a specific index. I'll investigate the iteration aproach further later on, thanks! Have a ton of fairly basic "todos" to do first though I guess.

-- [[Pulsar]]

By the way the reason it doesn't make that much of a difference could be that for around 30bins (I use 27 as that is about the number that covers one bot width at about 800distance) those factors are 0.9xxx for the edge factors to 1.3xx for the middle one (GF 0). Not huge, but I guess it could be noticable.

-- [[Pulsar]]

After finally coming to grips with this surfing method, I see that it would yield the same results as GoToSurfing due to the fact that it is recalculated every tick. However, if you wanted to speed your bot up, GoToSurfing that only calculates the best position once per wave would be a better option. Most of the current TopBots are SlowBots - and I'm guessing that this is the main culprit. -- [[Skilgannon]]

* Also, I disagree that most TopBots are SlowBots, but obviously it's all relative. Even the slower top bots ([[Dookious]] and [[Shadow]]) are about 5 times faster than what I would consider a SlowBot ([[X2]], [[Shaakious]], or [[Moojuk]]). -- [[Voidious]]

Well... [[Dookious]] calculates the danger of 9 positions each turn: the danger for forward, stop, and reverse, and the same again for each of those (lots of precise prediction). Hopefully this means I end up at the safest spot on the coming wave while also staying safe for the second one. This would be really tough to simulate with GoTo, and you'd end up doing a similar amount of calculations to get the same result - you'd just have to do it all in one tick, which probably means skipping turns on most clients. If you were just surfing one wave, though, I suppose there could be something to it. But who codes Robocode bots for speed over performance? ;)

Would be cool to see some order-of-magnitude faster surfers, of course, and maybe there's something I'm not seeing, but it'd definitely take some ingenuity if possible at all. [[Komarious]] is pretty fast. [[SilverSurfer]] is GoTo, and it's not particularly fast. ;) [[Ascendant]] I think has a TrueSurf and a GoTo style.

-- [[Voidious]]

I remember reading on the SilverFist page that it was quite fast, faster than either CC or SS. I think the gun is what is slowing down SS. --[[Skilgannon]]

Hmm, good eye there. =) Now you got me thinking. What I said before is true, but coding up a nice new WaveSurfing algorithm has been something I've wanted to do for a while. Maybe I'll actually try to do that sometime soon. -- [[Voidious]]

EDIT CONFLICT!!!
The goto bot would be fairly easy to implement, what I would do is limit the max speed so that we arrive at our position as the wave breaks. The negative segments, for me, would be the default because then you can get 100% against HOT, LT and CT, all for free. So here's the basic idea:

as a wave hits you, calculate: 
*what the max and min GFs you can get to as the next wave hits
*what the lowest GF between these is for all the waves' bins (weighted by distance)
*how far we have to move to to get to this bin
*what angle we have to move at to get to this bin
*how much time we have to get to this bin before the wave hits
*<pre>setBackAsFront(destDistance,angle);</pre>
*<pre>_robot.setMaxVelocity(dist/time + ACCEL_DECEL_FACTOR);</pre>

This would make you stop as you get there, which would make it easy to get to high negative GFs. Just a thought.
Maybe some kind soul will write a GoToSurfing Tutorial bot, I unfortunately write very buggy code, especially at larger scales.

--[[Skilgannon]]

With my 'gotostyle' rewrite of GresSuffurd, I calculate the best position to go to every tick. Then I set my velocity to get there on the right time. It will not be faster than the current GresSuffurd (but that one is quite fast for a surfer). Unfortunately I have some problems with WallSmoothing and reversing and with calculating the danger of the second wave, so it will not be ready for some time.  -- [[GrubbmGait]]

You could do that (Skilgannon); it would execute very fast. But imagine the following situation - wave 1 being closest:

* Wave 1's safest spot is GF=0.5. Wave 2's safest spot is 0.4 and its most dangerous spot is 0.5 (when translated to points on wave 1).
* You will probably avoid GF=0.5 because it's dangerous for wave 2 - but why? It's the safest spot for wave 1 and you will have ample time to get to GF=0.4 for the second wave. (Ok, depending on bullet speeds and which way you're moving, but assume you do.) It's clearly the best choice. You might end up choosing a much more dangerous spot for ''both'' waves!

The truth is that a lot of bots do factor in the second wave that way, including some top dogs like [[CassiusClay]]. But the way [[Dookious]] and [[Chalk]] factor in the second wave is much more sophisticated and you probably couldn't do it with GoTo-style.

I think I may try my hand at a new surfing algorithm or two, though, GoTo or not I'm not sure. (Thanks, by the way, this is my first Robocode motivation in a while. =) Would you believe I've had the same surfing algorithm, conceptually, since before [[Dookious]] was even at 1900 rating?)

-- [[Voidious]]

You would have to play with whether or not you want to stop, maybe by calculating whether a better place for the next wave is reachable by stopping or arriving at the speed(dist/time), and for the wave after, maybe recursively. Actually, that sounds much more promising, because it does not interfere with this wave's stats.

My actual motivation for making a (really) fast surfing method is to be able to run several pattern matchers and a GF gun or three in a virtual gun array without skipping turns. I recently read CC's page, and noticed that CrowdTargeting requires a large variation in crowd members. What I was thinking was weighting the different guns according to <pre>min(0,hitrate - averageGunHitrate)/noOfGuns</pre> and then averaging the angle offset according to the weight, and possibly segment the weighting as well.

-- [[Skilgannon]]

Well, I'd trade gun prowess for movement prowess any day of the week... =) -- [[Voidious]]

Hmm... well after getting tired out by some gun work, which I find worse than WaveSuffering, I think I'll get back to "Movement Labratory". In particular, I believe I have thought of a way to more accurately surf multiple waves. RougeDC already already surfs all waves, by giving an option to change direction for each wave, however this is far from optimal, because to best location to stop or reverse is often not only after the wave gets to me. Also it's certainly not the fastest surfer out there, because it gives the surfing an option to recursively "branch" the prediction after every single wave. I believe I've now come up with what I hope is a slightly new surfing algorithm that is in essence a form of [[WaveSurfing/TrueSurf|TrueSurfing]] but should be able to surf all waves, both faster and more accurately than RougeDC does currently, and at that it should only take 6 precise predictions at very most. In some ways, it's more closely related to a [[WaveSurfing/GoToStyle|GoToStyle]] surfing in the way that it searches for the lowest danger reachable locations, however it simplifies it to the case of only needing to decide a direction to go next and should use less time per-tick than a [[WaveSurfing/GoToStyle|GoToStyle]] surfer that tried to properly include all waves. Perhaps this idea isn't new, or perhaps it will flop, but either way this idea has inspired me to get back to working on movement. I'll post more details about my specific scheme after I get it implemented and run some preliminary tests, though based on what I said, people may already have some guesses at it... =) -- [[Rednaxela]]

Everything above 2050 ranking points in the rumble is suffering... it can even be depressing sometimes. By contrast, every single idea that works well is exilhirating. :) -- [[ABC]]

I find that the ways I make my points increase the most are when I listen to that small voice in the back of my head... And in DrussGT it's faster than the standard precise prediction because I break the problem down into a linear one, eliminating almost all the trig. Also, the moment I am facing directly towards my destination each tick is just a floating point subtraction, no trig, nothing. Another idea (of [[Krabb]]'s) that speeds things up a lot is not predicting any waves further if the sum of the danger's you've visited is already larger than the least dangerous complete branching. -- [[Skilgannon]]

Hm, I'm not sure I entirely understand that trig-less precise prediction yet, but in any case, branching is a bigger time increaser I think when considering multiple waves I think. RougeDC already does the optimization of not predicting any waves further when the danger gets too high, however, the new method I'm planning to use will allow [[WaveSurfing/TrueSurf|TrueSurfing]] of all waves in a fairly accurate way I think, while avoiding any recursive branching at all. =) -- [[Rednaxela]]

The linear precise prediction works as follows: take the start point and the end point, the current heading and velocity, and see how far you have to travel and how much heading offset from the required bearing. Make all the values relative, ie. make -PI/2 < offset < PI/2, then make offset an absolute value. Use the cos rule, with currentVelocity and distance as 2 sides of triangle, the offset as the angle between them, to figure out the next value for distance, which is the third side of the triangle (drawing this on paper really helps). Re-calculate offset as the exterior angle of the next-distance/velocity corner, then decrease it using the maxturn function. Of course as soon as the offset is zero you just subtract the distance linearly. You manage the velocity just like in regular precise prediction, but I added something to predict decelerating when I approach the destination point. By keeping track of the change in offset you can figure out it's bearing from the destination point, and you keep track of the distance anyways. This allows you to find the point you'll actually reach if you try to go this point, after x ticks. Unfortunately you can't really use this for True Surfing because you need a destination point. If you want to see a working implementation, the futureStatus(lots of parameters) method in DrussGT is there, and there is an early version of the code at [[Skilgannon/CodeSnippets]].

I'd be interested as to how you can get away with only 6 precise predictions!?!? Are they all at different speeds, so it's easy to predict the acceleration/deceleration without re-doing the trig each time? Though that would require 8.-- [[Skilgannon]]

Ahh, I see what you mean about that prediction. Well, how can I get away with only 6 precise predictions? Well, it involves for each of the 3 movement options (stopped, forward, reverse), doing 2 predictions in order to find how precise maximum escape angle for each wave is altered by a '''single''' tick of movement in a given direction. I then calculate the danger of each direction by summing the lowest reachable danger of each wave. It does lose some accuracy in aspects such as perfectly considering how moving to the lowest point on one wave will put the lowest point on other waves out of reach, however I think it will be worth it in terms of accuracy in other regards and could certainly run quite fast for it's accuracy level. -- [[Rednaxela]]

I'll probably soon be making a [[RougeDC/MovementLab]] page when I have tests more complete, however the preliminary results of testing my new method are interesting. I'm using exactly the same danger formula as before, and exactly the same method of predicting where the probable location of bullets are, however using my my new method that evaluates all waves with only 6 precise predictions. The preliminary testing is seeming to show that this might have the '''best''' perfection against HeadOnTargeting that I can ever recall seeing, however performs slightly worse than the old method when the bullet locations are not known as well (PM and GF guns for instance). In other words, I think this is certainly a stronger (and faster) way of evaluating dangers, however it's more predictable when the bullet locations are not known as accurately. I think this has some promise... -- [[Rednaxela]]

* Keep in mind that your previous danger formula was tuned to the old algorithm - I have no doubt that there are a lot of hidden subtleties at play when tuning a danger formula. I bet if you switched the danger formulas between any two top-20 bots, they'd both lose rating points because their formulas are intrinsically tuned around all the other differences in their surfing algorithms. Glad to hear the idea is showing promise, as it sounds really interesting. Good luck! -- [[Voidious]]
* This is true, however so far no other tunings of the danger formula I've tried yet with the new algorithm beat it. Thanks. In any case, I've so far run 31 seasons of MC2K7, and I'm getting about 99.95% against [[HawkOnFire|HOF]], in the same league as Dookious and I haven't seen any other bot besides Dookious score that high, whereas my old surfing algorithm only scored about 99.70 to 99.80 against HOF (the numbers sound similar, but that means getting hit 4 to 6 times as much!), so it appears I now have top notch surfing against head-on I think, which shows the algorithm is good I think, so I just need to tune improve the bullet prediction and tune the danger formula. =D -- [[Rednaxela]]

Question: How do you come up with "danger" functions?  I've looked through a few of the better surfing Open Source bots, and tried to apply some of
the ideas to my own.  I finally had some success foiling an un-segmented GF gun, but "surffer" 20%+ hit rates when facing a basic segmented GF.  Part
of the annoying thing is on wall-approach, the bot winds up turning in towards the enemy and basically becomes a rammer (I'm using a stationary bot with
a GF gun as a testbed).  Any help/thoughts? -- djc

Well, the "danger" function is a measure of how likely you estimate them to fire in a location. If you're using VisitCountStats to store stats on their for instance, the danger could just be the number of visits in that GF bin. If you're trying to fool a a GF gun, you generally want to use stats of where you have moved before instead of where you've been hit, to create a [[CurveFlattening|flattener]], but even then most people have found it worthwhile to mix that with stats of where you were hit as well. Also, if you're doing well fooling an un-segmented GF gun but get fooled by basic segmentation, it likely means you need to add similar segmentation to your own stats of your movement, if you don't already have that. As far as that wall approach, DiveProtection page has some thoughts about this. Some bots simply add more danger for going near the opponent, some bots consider that moving closer increases the GF range they cover and calculate danger with accurate consideration of the size of that range, and there are a variety of other ways of dealing with it. Does that help? -- [[Rednaxela]]

Somewhat.  I'm keeping track of both VisitCounts and "GFHits" (like Raiko).  My first implementations I tried to move to the least visited VC, but that
really didn't seem to work so good.  I've also tried things like tallying counts for any GF that could hit the bot (also producing bad results).  Maybe my
segmentations are the problem (I'm doing 4 Velocity, 4 Lat Velocity, 3 Acceleration, 10 Time Since Stopped and 3 approaching wall/corner).  I'll try
segmenting exactly how my test-bot segments and see how well that goes.  - djc

Well, as far as deciding where to go, generally either [[WaveSurfing/ReverseForwardSensors]] or [[WaveSurfing/PrecisePrediction]] are used, but there is certainly room for imagination I think. The former being quicker/easier to implement and taking far less codesize, and the latter being considerably more powerful. The important thing when deciding to go to the "least visited" GF, is only considering GFs that you can actually get to. Also, I'd suggest you first work on perfecting your score against "Bot A" from [[WaveSurfingChallenge2K6]] (and later bots B and C), rather than worrying about scores against GF guns. A reasonably bug-free surfing movement should be able to get 99+ scores against "Bot A" regardless of the the stats/segmenting/etc are working, and is also a good test bed for getting rid of issues with diving too close like you were talking about. -- [[Rednaxela]]

I really suggest going light on the segmentation for your surfing buffers. The key element for surfing is fast learning, not perfect copying of their buffers, because you have so much less data to work with. I would suggest 3 or 4 lat velocity, 3 acceleration (make accelerating be an acceleration > 0.8, or < -0.8), and 3 approaching walls. No need to have a seperate velocity buffer, and you *certainly* don't need 10 time-since buffers. On the other hand, if you want to layer many buffers together (as do DrussGT, Dookious, Phoenix, and many others), you can have a finely sliced buffer and a coarsely sliced buffer working together, so you get the fast learning and the detailed learning all in one. I make the 'danger' be all the sum of the bins that the botwidth would cover, divided by that number of bins, times the botwidth 'angle', divided by the distance to the enemy, or something along those lines. -- [[Skilgannon]]

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

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