DeBroglie/Archived Talk 2010

Shooting where a surfer would go

This is not as simple as it first seems... Sure, you can keep track of surf stats from the enemy perspective, and when you fire, you can shoot at a less visited bin instead of a most visited one. But most of the time, there are already 1-3 bullets in the air. The enemy will first surf each of those before deciding how to surf the bullet you're firing, then he'll choose the safest from the bins that are still reachable, not from all of them. Add in the discrepancies in data analysis (what you segment on, how fast you roll your stats) and it's very hard. I don't think anyone's been able to find something that works. I've personally tried quite a few approaches with no success. Good luck though. =) It's actually something that I still think has potential. --Voidious 13:06, 27 October 2010 (UTC)

• That is something that occurred to me in the conceptual phase. My plan for movement was to recursively surf all waves in the air (or up to whatever depth I can handle, I have little experience with where Robocode shuts a bot off on data processing for a turn) meaning that by symmetry I could fire at an opponent surfing all of the waves I had in the air. In reality, this would work delightfully if I pitted two copied of deBroglie against each other, but the differences between my surfing algorithm and any other bot's would make the exercise fruitless in practice. -Tkiesel 17:49, 27 October 2010 (UTC)
• As a one-off, I wanted to try stepping the target through all the waves I have in the air assuming the target will pick the safest direction for each. I thought this may give a much more limited range of possible angles to fire at. These are all ideas that have been done to death by others, I'm sure, but I'm enjoying the process of trial, error and discovery. - Tkiesel 17:50, 27 October 2010 (UTC)
• Ah, I see. Well, if you could simulate enemy surfing, I personally think it could perform well, despite the differences in surfing styles and stats. The problem there is just CPU time. In normal "True Surfing", each tick you just make one decision (forward/backward/stop). But to aim, you'd have to simulate that decision over a lot of ticks, which is an order of magnitude more calculations.
  I like your idea about assuming the safest direction at each wave. I think you need something like that - simpler than full surfing simulation but taking stats into account - to make this work. My best idea in this department is near the top of Archived talk:Dookious 20071111 if you want to take a look. Hope you have more success than I did. Good luck. :-) --Voidious 18:08, 27 October 2010 (UTC)
  • I think I have an alright grasp of the most basic form of wave surfing. But in case I don't, I'll ask: I know a simple wave surfer will make the forward/backward/stop decision on every tick, but effectively, this means the surfer will either head to the far end of its possible bearing range, or stop/oscillate around a bearing on the wave that balances the forward/backward danger. If the surfer uses nothing for movement but the closest wave, then it should be trivial for that surfer to calculate this destination ahead of time in one tick (goTo style) and produce the same motion, yes?
    I like the masking concept you applied to this problem in the talk archive you linked! Once I have this bot halfway competitive, I'll have to look into exploring these ideas! For now, I really have to figure out what statistics are best to segment on, and get my bot wave surfing! I get hit wayyy too easily right now. -Tkiesel 21:05, 27 October 2010 (UTC)
  • Normally it should be in the same place. But in rare cases (especially if you are dodging enemy anti-surfer gun), the velocity may change the resulting position, see if the true surfer bot is moving in different direction than the optimal point decided by go-to algorithm, sometimes the true-surfer bot can't reach the same optimal position as a go-to surfing. And no, if both side of wave is balanced, the true surfer bots don't normally oscillate, since when the time passed, the reachable distance become closer, and dangers are evaluated from different points.
    Just a note, I have tried sometimes similar to you before (I can't remember where, but I have talked about this somewhere else); it consumes a lot of performance, and since the surfer is very adaptive, a little difference means a lot. And with huge processing power, I cannot add any fancy things to it. Just my experience, you may got it better. Good luck! --Nat Pavasant 13:15, 28 October 2010 (UTC)
  • Like Nat said, the furthest reachable points keep shrinking, so you end up considering all possible points, basically. In the simplest surfing system, sure, you could say you might as well just choose the safest bin and go there. One issue is that stopping right at the target point isn't necessarily trivial (calculating when to slow down, etc). True Surfing evaluates the exact points where you could be at wave intercept. In my (Diamond / Dookious) surfing, there are also some elements that change tick to tick, such as projected distance to enemy (don't want to get too close), and waves are weighted by time to impact. Obviously you can account for this stuff in other ways with GoTo (DrussGT does pretty well =)), but they are definitely very different approaches. --Voidious 13:58, 28 October 2010 (UTC)
  • Even in DrussGT's implementation of GoTo surfing I don't find the lowest bin and then go there. Instead I see where I would be when the wave hit if I tried to go to a whole bunch of different points. I guess it's actually a sort of hybrid between True Surfing and Goto surfing in their purest forms. Pure goto surfing would calculate the furthest point that can be reached in each direction, find the lowest bin in between, and then get to that spot. The trouble with this is that there is no way of accounting for where can be reached on the second wave, whereas my hybrid method *can*. --Skilgannon 06:44, 1 November 2010 (UTC)
    • This sounds vaguely similar to my plan for deBroglie. When I said "recursively surf all waves in the air" above, I'd planned a scaled down version of the following:
      1. determine rating of all bins reachable on this wave.
      2. for each bin, assume I am there when that wave breaks, now determine rating of all bins reachable from there on next wave.
      3. repeat #2 until there are no more waves in the air. For last wave, don't return a range of bins, but rather a composite "danger total" or somesuch.
      4. goTo bin on the closest wave that yielded the most desirable composite score.
    • Of course, this is on the order of total_bins^waves_in_air, or approx 20 million scores to compute with the number of bins I have now and the 4-5 waves I see in the air a lot, so my plan has been to trim it down a bit... look at the safest n bins on each wave and up to a maximum depth of waves, since it could get rather deep on a huge battlefield with combatants at the edge of their radar ranges. This will have the built-in effect of weighting closer waves as a higher priority, since the decision will consider the best places of each wave considered in isolation. The key before I attempt this is that I have to have my goTo movement down solid, otherwise my "assume I'm at the goal when the wave hits" assumption on step 2 breaks down really badly. So I've got a lot of ground-work to lay down first. ;) -Tkiesel 15:43, 1 November 2010 (UTC)
    • The important thing to remember is that for each point, you might still be moving when you reach it. You might also not be facing perfectly perpendicular to the enemy due to wallsmoothing etc. Which is why I start my prediction with a full assortment of points, and for each one see, if i go to that point, where I am and in what state (velocity, heading) i will be at the time that the wave hits. The importance of this is that it affects where on the next wave you can reach. If you are moving at a velocity of 8 you can reach a larger area on the one side and less on the other side than if you get to the goto point in time come to a complete stop. What I'm trying to get at is that you need some sort of way to initialize the predictions for the second wave (and 3rd and 4th if you can get your code to run fast enough) - a time of wave hit (easy), a position (easy - unless you want it uber-accurate) and a velocity and heading. You can make assumptions *fairly* accurately, but like position, getting the actual values requires a full iterative step-by-step prediction, which is slow =) I've probably spent more time getting DrussGT to run quickly than I have actually adding new features, and I still consider it to be a bit of a oldwiki:SlowBot --Skilgannon 19:51, 2 November 2010 (UTC)