Talk:DrussGT

From Robowiki
Revision as of 03:35, 10 March 2009 by Zyx (talk | contribs) (safe spots)
Jump to navigation Jump to search

Just going through the algorithm, and I realised that there's a bug in my precise prediction: I'm using the bullet-hit-time of the 'target' point, not the point that I actually reach. This is left over from the days when the only thing my precise prediction checked was whether I could reach the target point. Now, for regular, constant distance surfing this is fine. But the moment I start changing distance my predictions can get a couple ticks off... Basically the less lateral velocity component I have, the more inaccurate my prediction gets. Which is bad against, say, RamBots, and in corner situations. I may have to rethink this algorithm... I've already tested doing an iterative search but it gets way too slow, way too quickly. --Skilgannon 10:47, 27 January 2009 (UTC)

Hi, I just want to know. You had once tell me that DrussGT doesn't call Math.random() in real battle, but it does in development process. Is the random call in development process use to generated all those 100 buffers' slices? Thanks » Nat | Talk » 06:02, 21 February 2009 (UTC)

Again, I'll rework DrussGT and see how it will act if it had 73,728 buffers. (The maximum buffer without duplicated buffer :)) » Nat | Talk » 06:05, 21 February 2009 (UTC)

  • My robocode crash after intialize that bot with 73728 buffers! I think it too much :) » Nat | Talk » 07:18, 21 February 2009 (UTC)

Yes, it uses random() to decide which buffers to use, and which slices for those buffers (ie fine, regular, coarse). Unfortunately I couldn't do every possible buffer, due to memory constraints. So I use random() and make a set of buffers that hopefully covers all the segments fairly evenly. Also, if I used every possible combination I would probably run into problems with execution time while extracting buffers to use and smoothing new hits into the buffers. --Skilgannon 22:45, 21 February 2009 (UTC)

One more question: Does it do hit surfing? I go trough your code to understand the flattener (it easier to understand than Dookious one because my robot base on basic surfer, too.) I've recognize that you only do logHit() on hit and do logFlattener on every waves. Does hit surfer competitive? Or I miss something in your code? Thanks. » Nat | Talk » 02:21, 22 February 2009 (UTC)

Yes, hit surfing is the primary way of surfing. The flattener is only enabled against top guns. The reason for this is that if we are flattening the whole time, we can never learn where they are shooting, and dodge those areas. For example, against linear targeting, hit surfing can learn to dodge it perfectly, whereas flattener-only will still get hit. The same is also true against GF bots because they will learn that you move in certain ways, but the moment you get hit by them, you know how they think you move, so you can move differently. By rolling your surfing stats quickly you can stay ahead of their stats and actually do better than just creating a flat profile. Only against fast adapting guns is it necessary to enable the flattener. --Skilgannon 19:49, 22 February 2009 (UTC)

Question: Why you always use Float in DrussGT? Is it faster than Double? » Nat | Talk » 13:51, 6 March 2009 (UTC)

Yes, a float is significantly faster than double for multiplication/addition, which is what I use the most. It is slower for trig due to having to caste into a double, but with the new FastTrig class I can change that. It also uses half the memory. If I tried using doubles DrussGT would skip quite a few turns, and might also skip turns on initialisation due to allocating twice the memory. --Skilgannon 22:14, 6 March 2009 (UTC)

Well, I just decided to add "float" functionality to my FastTrig class. Iterestingly, despite the bulk of the calculation involved being multiplication/addition to get the index it isn't actually significantly different than the plain double version of FastTrig:

FastTrig init time: 0.00703 seconds
Wrost error: 0.000436324725
FastTrig time: 0.520 seconds
Math time: 8.811 seconds
Wrost float error: 0.000465920262
FastTrig float time: 0.510 seconds

The difference is slim enough that I don't think it's worth keeping two different versions. I'm just not sure which version to keep. But indeed, floats are nice for speed/memory and I'm already using them in a componant of my upcoming bot other than the FastTrig --Rednaxela 23:03, 6 March 2009 (UTC)

I don't think floats are faster than doubles at operation time, if I remember correctly calculations are done in higher precision registers anyway. The main time difference comes from the memory bus, a float(32-bits) can be read and written on a single memory access, while doubles(64-bit) are not. Some 64-bit architectures can move the whole 64 bit at once and have no real performance hit, while some use only 48 bit transfers, in those cases there is still a small difference. It's been a long time since I have read any of this, but I think that is the reason. --zyx 06:07, 7 March 2009 (UTC)

I'd say it really depends. For some applications before I've noticed as much as a 10% to 20% difference using floats, even with not being on a 64-bit architecture at all. Though for FastTrig float doesn't give a significant performance benefit. The reduced memory usage though, is of course undenyable. --Rednaxela 06:20, 7 March 2009 (UTC)

Well, the memory is of course half of it when using floats :). That can also affect on performance from the cache fetching point of view, and honestly most people doesn't need the extra precision that comes from using doubles. What I mean is that there isn't any real time performance difference that should people use float over double, if it is memory you need to optimize, float is the way. Otherwise I think people should use which ever he/she feels comfortable with. I use double when is a fresh new application just because doubles can represent all 32-bit integers exactly. And when I'm working with an API(like Robocode) I use the same as the API, that ensures that I will consistently behave the same as the API. I wouldn't consider it PrecisePrediction if it uses floats, because there will be differences when Robocode handles the same situations with doubles, I'd think of it as an approximation to it. When working on something as non-deterministic as a Robocode, maybe it's not even good to have more bits, but I'm a precision freak :/, that's why currently I'm using 628318 divisions on FastTrig --zyx 19:04, 8 March 2009 (UTC)

  • Good point about the cache fetching. Also, as a precision freak, I take it you don't like VCS much ;P --Rednaxela 19:18, 8 March 2009 (UTC)
  • Hehehe yes, I had been looking forward to making a DC bot for a long time, but I admit that VCS is a very good technique and certainly was easier to learn the heavy stuff of GF and WS using simple VCS. -- zyx
    • Zyx, are you precision freak? I think not. I use 7,200,000 divisions on FastTrig in my Pallas! Take about 1 secs to load =) Also define this in it's FastMath class:
public static final double PI = public static final double PI = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986...D;
// actually it over 2,000 precision!
 :-D So who is real precision freak? I felt more comfortable with Digital (one mistake mean corrupted data), not analog (can have some disort). I always add the asin() to my nano linear targeting. If you are precision freak like me, you should use Anti-Alias VCS from Rednaxela. » Nat | Talk » 06:01, 9 March 2009 (UTC)
  • Sheesh, that would take 27.5MB of memory on FastTrig alone, that's outright wasteful. Actually, my anti-aliased VCS, while far lower data distortion than conventional VCS isn't as low-distortion as log-based techniques like DC are. If you made a spectrum where one side was fast/distorted and the other was slow/accurate, then Anti-aliased would fit somewhere in the middle, with DC towards slow/accurate, and Conventional VCS (single buffer) towards fast/distorted. So really, no, anti-aliased VCS isn't for a real precision freak even if it's more precise than other VCS. --Rednaxela 07:11, 9 March 2009 (UTC)
    • Then having 628,318 bins, plus 7,200,000 segments will give a DC-like result with anti-aliased VCS =D » Nat | Talk » 07:59, 9 March 2009 (UTC)
  • Well about the number of divisions, you are winning :p, I may push it higher but I haven't seen any real reason to do so yet. As for PI I use the Java Math.PI, but honestly I don't even know how precise it is (I don't really know Java), I just believe it is ok. But instead of your PI constant I would use:
public static final double PI = Math.acos(-1);
You can't get better than that, it will be as accurate as your compiler (or JVM in this case) can be :-). About the anti-aliased VCS maybe I will add it to Newton someday, but in the mean time my time will be spent on DC. -- zyx
  • Doesn't it Math.acos(0)*2? Anyway, Math.PI has 20 precision. Mine have 2,000 precision. 100 times! But java double can't handler it =). I think java trig function depend on OS, so predefine it is good ideas. I'm now planning to preloaded 720,000,000 divisions into FastTrig, then my robot jar will count as 300MB. Wait! just kidding! I am not that crazy... Note to your bot, don't stick with Newton and that DC (I can't remember it), create a new robot, base on old bot if necessary. » Nat | Talk » 13:54, 9 March 2009 (UTC)

I would like to point out that your surfing can only be as accurate as the enemy gun. Thus, if the enemy has a very low number of bins (for eg. I have seen 25), keeping PI to 2000 places will make very little difference. On the other hand, this gives me an idea: if you could figure out the granularity of the enemy's shots, and find that it is quite high, there could be 'safe spots' at long distances where the enemy doesn't fire, ie. between bins. In this situation having that precision may help.

To get back to the original point, the reason I switched DrussGT to floats (after going through my private release notes) is that, during testing, it would often crash due to an exception of some sort. Robocode doesn't (or didn't) release the memory from all those buffers when I restarted the match, so I would often have to restart Robocode every 30 minutes or so from running out of memory. By changing to floats it doubled the time between each restart of Robocode. Also, with the number of buffers I'm keeping, and thus the sheer number of floating point multiplication that gets done every tick, having floats instead of doubles means that much less memory is moved around, accessed or modified. For example, if, in the same tick I both get hit by a bullet and sense a bullet being fired, without flatter, just from the VCS I'm doing around 75000 float operations, over 14000 of which are writes to an array. Added to this I still have to do several hundred precise predictions, and it's easy to see how DrussGT could start skipping turns, even if everything just took a *little* bit longer. --Skilgannon 18:48, 9 March 2009 (UTC)

What you say about safe spots between bins sounds like a good exploit point for some guns, and seems doable without any rocket science theory. --zyx 02:35, 10 March 2009 (UTC)