![[Home]](/images/RoboWiki.png)
WaveSurfing/TrueSurfcan 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.
if (gfDanger_invert < gfDanger_continue) moveDir *= -1There 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
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:
setBackAsFront(destDistance,angle);
_robot.setMaxVelocity(dist/time + ACCEL_DECEL_FACTOR);
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.
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:
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
min(0,hitrate - averageGunHitrate)/noOfGunsand 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 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 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 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 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
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 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
I don't have much to add to Rednaxela's and Skilgannon's suggestions, but I would strongly second the suggestion of not focusing on segmentation to start with. You can crack 99% in the WaveSurfingChallenge against Bot A (HeadOnTargeting) without any segmentation, and until you have done so (or at least gotten close), you still have significant bugs / issues to work out in your surfing. If you jump the gun and try to make progress via segmentation before you resolve those issues, I think you will just get frustrated. Also, have you checked out the WaveSurfing/Tutorial? That may be of some help to you (I hope =)). Best of luck! -- Voidious
I must agree with all three above. I started simple and got at 99% without any segmentation (see GresSuffurd/WeefSuffurd). I do believe however that that is only possible if you have any kind of DiveProtection and maybe Distancing. Also do not overestimate the influence of segmentation. I only surf on absolute velocity (3 segments) and it still got me in the top-30, as I do very well against the majority of simple aimers. Good luck on your quest. -- GrubbmGait