|
#Stormrider |
|
I just tested Pytko, and it's pretty fast. So no need for it on the SlowBot list. Stormrider can get kind of slow (especially once the flattener enables), but it's nothing compared to X2 or Ala. I often use it for testing my gun instead of DrussGT because it uses a fraction of the memory. -- Skilgannon |
What's your definition of a slow bot - I don't think DT is very slow in 1v1 700fps against StatistRobot (not so good in melee) - it does do alot of math, doesn't use lots of memory (now) - perhaps there is a performance difference between platforms. (I'm a Intel_1.7GHz/Windows? NT4 man). Perhaps we can agree on a reasonable bot and normalise on that. -- Paul Evans
Possibly... I mean, DT is slower than FloodMini and Gouldingi and DT 1.61 in one-on-one, but what does that say? I don't think PEZ is testing them in melee, either. -- Kawigi
My definition is a bot that's painfully slow to test. Or a bot that's three-four times as slow as my own bots. DT belongs there on the platforms I am using (Linux and MacOSX, both on oldish hardware.) On my MacOSX laptop two Marshmallow's run at about 700 fps, Marshmallow vs DT runs at 120, Marshmallow vs Fhqwhgads 35 fps and Marshmallow vs Chameleon at 29 fps. With DT I'm pretty sure you really need most of those CPU-cycles you are using. The Fhq... bot doesn't. I bet Chameleon could be sped up consdierably as well, but I'm not as sure. -- PEZ
I submit Fhqwhgads to be taken off the slow list as of version 1.1. I just ran 1000 rounds with two F's, and they finished in 4 minutes, 8 seconds. By comparison, 1000 rounds with two M's took me 6 1/2 minutes, 2 Gouldingi's took me about 3 1/2 minutes. -- Kawigi
Thanks! I removed Chameleon as well since it's fully testable now. -- PEZ
Removed FloodMini, since version 1.4 runs as fast as any bot. Thanks Kawigi! -- PEZ
Added Teancum. Runs in only 100 fps here. -- PEZ
I think you'll find all the nano pattern matchers practically grind to a halt after 100 rounds or so. Particularly those based on Mike and Albert's gun. -- Kuuran
True: They are nanos, so there isn't a check on the history search lenght (no room). Thus, their performance degrades with the number of rounds. Anyway, I don't think running long matches with nanos is really necessary, so it shouldn't be a great problem. -- Albert
Oh, I can appreciate why, I'm not saying that makes the gun bad (it's an amazing piece of work!) I'm just saying after awhile they most definitely become SlowBots. -- Kuuran
Running FunkyChicken through the TargetingChallenge is a challenge in and of itself. I made some modifications to limit the length of the pattern buffer, but it still takes it as long to run 500 rounds against one challenger as it takes for my other bots to do the whole run (of course, my other bots use primarily faster algorithms altogether) -- Kawigi
Just discovered a new one. Immortal 0.88 is one of the slowest bots I've ever run. My AthlonXP? rig can't sustain 30 fps with it on the field against a Micro! Minimized it'll run 150-250 it seems. -- Kuuran
For comparison ScruchiPu vs TheBrainPi with a huge database runs about twice as fast. -- Kuuran
At least my Musashi bot is a top 20 here :-)!! Probably because of my pattern match gun - it makes a lot of calculus, i'll try to reduce it. Is there a more accurate method to measure how slow a bot is? -- Axe
More accurate than "runs slow on PEZ's machine?" =) Try with RoboLeague and make two divisions. You can choose your usual testbed (maybe it's the 10 bots above and below Musashi in the rankings). In one division you make Musashi the focused opponent and in the other you pick a bot you think is faster (as reported by Robocode when minimized). RoboLeague reports the average time it takes to run a round. This might be your more accurate measure. As for PatternMatching, are you using SymbolicPatternMatching? If not, you should consider that, it's easier and much faster. I think I have posted the source for LeachPMC here on the wiki, which shows one way to do symbolic pattern matching. -- PEZ
I took a quick look at Symbolic PM, and the idea is great, but my answer is no, I don't use any Symbolic approach in my PM. Thats how i do it: I save the history of target positions (3000 last positions). When aiming i use these points to generate vectors (that express velocity and heading of the movement by themselves) and search the vectors history in order to get the best fit. A little more than that, but basicly is this. I have intent to optimize this, but my problem by now is that i am completely rewriting Musashi, movement and guns, so i have a lot of cleaning code job ahead. -- Axe
When you say the "best fit" do you mean the "longest fit"? If so you could go symbolic easily. Otherwise... well, you might be able to go symbolic anyway. It will transform your bot to a TestBed while providing room for you to save a longer history if you would fancy. -- PEZ
When i say best fit: I'll take 6 reference vectors (let's call P(n) the Point representing the bot position at time n): P(n)-P(n-1)(witch is the vector going from the position that now stands the target, to the point on were he was); P(n)-P(n-2); P(n)-P(n-5); P(n)-P(n-10); P(n)-P(n-20); P(n)-P(n-40). First i calculate the 6 "reference vectors" (let's call them Vr[0]..Vr[5])for the actual position of the target (the signature of the move) and store the angle of the first ref. vector (P(n)-P(n-1)), witch represents the "reference heading", then i search the history using the following steps:
It works very, very fine. Obviusly i have a self-made AxeVector? class that do all the vec stuff. It's a first version of this cannon, i'm doing this all at the aiming time, witch proved to be expensible. My idea is to create a "PatternSample?" class representing the 6 vectors, this class implementing the Comparable interface will let me to feed them into a ArrayList and use the Collections.min(Collection coll) to get the best fit - and let those "rocket scientists" earn their money :-). By doing this i will spread the aim work doing a great part in the onScannedEvent?(). The rotation will be done also in the onScanned, because the class will normalize the first vectors to 0 degrees. Here is a prototipe:
![[Home]](/images/RoboWiki.png)
public class PatternSample implements Comparable {
// The static reference. Used by the instances to rate themselves in the compareTo()
private static PatternSample reference= new PatternSample();
// samples wideness
private int groups[]= { 1, 2, 5, 10, 20, 40 };
// the samples
private AxeVector samples[]= new AxeVector[groups.length];
public PatternSample() {
super();
for (int i= 0; i < samples.length; i++) {
samples[i]= new AxeVector();
}
}
public PatternSample(AxeVector samps[]) throws AxeException {
super();
if (samps.length == groups.length) {
samples= samps;
// ROTATE THE FIRST VECTOR TO NORTH (0 DEGREES)
// ROTATE THE REST BY THE AMOUNT ROTATED BY THE FIRST.
} else {
throw new AxeException(
"PatternSample: wrong samples array size:" + groups.length);
}
}
/** Sets the static reference vector. By being static all the instances will
* be able to use it to rate themselves.
* @param sample The 6 reference vectors
*/
public static void setReference(PatternSample sample) {
reference= sample;
// ROTATE THE FIRST VECTOR TO NORTH (0 DEGREES)
// ROTATE THE REST BY THE AMOUNT ROTATED BY THE FIRST.
}
public int compareTo(Object arg0) {
int ret= 0;
// DO THE 6 VECTORS COMPARISSON WITH THE
// 6 STATIC REFERENCE VECTORS.
// RETURN THE RATING (LOWER, BETTER!)
return ret;
}
}
I am very hopeness about this implementation, i'm a little concerned about the Collections-ArrayList performance, let's see if it works. I think that it is similar to some concepts in the Symbolic PM: pre-format the information, so the aiming need less processing; uses the java's classes ordering and searching algorithms. -- Axe
That should work I guess. I don't know how much it will speed things up for you, but it will certainly be a maintainable piece of the system. And I think that you from there (the PatternSample?) will find easier to make it a symbolic search. All you would really need for that is calculate a signature for the 6 vectors and convert to char. It's a bit like the Frame class of LeachPMC, even if LeachPMC stores much simpler patterns. -- PEZ
Wow. Looks very promising. However, if I were you, I'd get rid of all that Comparable and Collection stuff. If you're worried about size, it will probably cost you more bytes to edit the collection and compare it every time you want to shoot rather than just looping through and doing the vector comparison manually. If you're worried about speed, ArrayList is likely to be slow; just ask ABC. When you do create it, make sure you initialize it to the capacity of the amount of vectors you're putting in, and re-use it! Don't create a new ArrayList every time you want to compare; use the same one, swapping out old values with set(.). Anyway, other than that, I know diddly squat about pattern matching, so, good luck! : ) -- Vuen
It's quite green yet, i'll have a lot of testing job ahead. Somethings i have to discover:
Well, let's see... -- Axe
About saving a history of the enemies positions; Why not keep track of the two most recent positions & heading, calculate the needed vector from that data and just save a history of those vectors, instead of saving all positions and re-calculating those vectors everytime you need to aim? --Dummy
A positioned(a vector that doesn't start necessarily at 0,0) vector can be represented by cartesian coordinates (start_point and end_point: (x0,y0),(x1,y1)) or by Polar coordinates (angule and module and start_point). I do save the scanned positions, just because of the disk space (i use 2 shorts for each pos). But when i load the data, i use the n pos to create n-1 vectors with my AxeVector? class (fitten to manipulate vectors, adds, subtracts, rotates, translates, convert to polar...). The AxeVector? object can give me: the vector angle - the bot heading (aproximately..)); the vector module - the bot's velocity; the vector start point - bot's start position; the vector end point - bot's end pos. It is also simplier when playing the movie: each tick gives u the expected position of the target without having to calculate it based in the vel and head. -- Axe
When you say "when I load the data", do you mean loading data from disk at the start of the battle? Because from your explanation above, I was under the impression that you recreate your vectors from recorded absolute positions every time you need to aim, which sounds very time-consuming, as you will be generating 3000 vectors everytime. --Dummy
Which is why we have this discussion I think. =) About how to store those 6 vectors in one wide char. It depends on how wide each vector is. (I can't say I really follow the matrix math you talk about, I have quite a few white areas on my math map...) But if you look at the getKey() function of the LeachPMC/Code Frame class you see how I store three measures in one byte, so you might be able to store six measures in two bytes. But you can make it four bytes as well if you pad the highest order byte correctly so you avoid un-aligned matches. The LeachPMC code is a bit messy in the matching part, but it does a binary search in order to cut down on search time. It makes the search times increase linearly with the pattern buffer length I think. However, Dummy probably pokes on the real performance hog in your solution, which might make any speed increases in the search work only in the margin. One of the reasons you mention for keeping it like that doesn't hold I think. If you encapsulate the movie playback good it will be neat even if you'll have to calculate it using the velocity and heading measures. And it makes sense to only do this part when you have found a match, doesn't it? -- PEZ
Yes, forgot to answer... the symbolic matching as such doesn't close the door to fuzzy searches but most current implementations use indexOf() and that's an exact search method of course. You could use regular expressions I guess. But the "built in" regexp implementation will make your bot not run on pre 1.4 Java. Though I think the last 1.3 robocoder - me - has moved to 1.4 now anyway. =) -- PEZ
Yup. Don't worry about whether or not your bot works under 1.3; it's better to have a powerful gunning strategy that works under 1.4 than no gunning strategy at all. Besides, everyone has 1.4 anyway. -- Vuen
I think i did it. Take a look at the Musashi v 2.06. Did the above except for the part of sorting the ArrayList with Collections, more faster and malleable (thnx, Vuen). Also thnx PEZ and the rest for the ideas and sugestions, they help a lot. My computer is a Athlon 1600+, 512 Mb and win XP, the older PM aiming system was taking 60-120ms to perform a 3000 pos search.(I think that i have read somewhere that if you take > 30ms in a round you skip it - it means 2-4 rounds lost). Now it takes 0-10ms. to perform a 10000+ pos. search. In the process it have been improved in a lot of details. If u agree, i will ask to take Musashi from the list (and there goes the only time i was above DT...:-). -- Axe
Wow, looks like quite an improvement with the new Musashi; it has gone up quite a bit in ranking! Congrats : ). As I'm writing this, Fractal 0.32 hasn't yet played Mushashi 2.06 in the ranking table, but as Mushashi is a pattern matcher I predict heavy losses on Fractal's part... I think I might have a new problem bot ; ) If you feel that your bot isn't slow anymore, feel free to take it off the list. -- Vuen
Funny:
| axeBots.Musashi_2.06 | 35.3 | 1 | 13-11-2003:5:4 | 49.6 | -14.3 |
A 14.3% problem bot index for Fractal. Not too surprising :D; looks like my prediction was pretty accurate. Good job on the pattern matcher!
-- Vuen
Thanks, Musashi is rigth below Fractal. I think that now i've found the way to duels. I have some ideas to improve that cannon, and the movement needs work too (and a lot of code cleaning job to do, there is a lot of unused code to be removed - i hate this part). The result surprised me, i was working on the slowbot problem, but in the process the cannon was improved. So i was expecting a ranking improvement, but i've got a huge improvement (from 114 to 60 in the ranking). If you all agree, i am taking Musashi from the slowbot list... -- Axe
This wiki-page might be the best robocode page ever created. =) -- PEZ
You're just saying that because you made it when you were complaining about Fhqwhagds?. -- Kawigi
If i didn't saw my bot in the SlowBot list, we wouldn't had that PM discussion, nor i would improved my bot, and it probably stayed at 114. It was very profitable to me. -- Axe
Oh, it was me creating this page? =) And have you forgotten how to spell Fhqwhgads? =) -- PEZ
I'm wondering what you Robocoders feel is the maximum memory a Bot should reasoably be able to allocate - I have the seed of an idea which may work well in long battles, it won't use vast amounts of CPU cycles but it will hammer the memory - do any you have a view? -- Paul Evans
Well, as far as I know Robocode doesn't put a limit on the amount of memory a bot can use, so I don't feel there should really be a limit a bot can allocate, as long as the machine still runs. In Fractal's gun I opted for more memory as opposed to more CPU cycles. I don't think memory should be much of a problem for your idea, up until above a couple hundred megs or so, at which point the VM will crash on machines like mine. I must say though, hearing you speak of a new idea is scary to say the least... ; ) -- Vuen
Anything that works is ok, IMO. Once you get to too much memory the VM will just crash, so that is the obvious limit. New ideas from paul are a scary thought, i agree... -- Tango
Go on. We'll see how it works. I'm a bit curious about what it could be though. Something that will possibly kick in in long battles... Since it's not jogging the CPU it can't be a PM idea I guess... Can you give any more hints? -- PEZ
Nah - If you do your own guessing you'll have your own good ideas - I don't think I'll need more than a few Meg for plan A, I wonder if it will work, I've been thinking about it for a few months now but can't face all that coding and testing! (and there is no 1000 or 10000 round battle league). -- Paul Evans
Hrm Ive recently though of an idea that may well use lots more memory than CPU, and im in the middle of implementing it. It wont "kick in" in long battles, it will just be a lot more effective in long battles (I hope!). I havnt calculated how much memory it will use, I guess im going to just have to try it out and see what happens! I wonder if its the same or similar idea to Paul's???! --Wolfman
VIbora uses a HUGE ammount of memory (check its page for a description). I had no problem in my test (but they are never longer than 100 rounds). The real problem was to make all the updates to the information without skipping turns. If you are curious, just run Vibora for 1000 rounds and see what happens. -- Albert
Hmm... A few megs doesn't seem like all that much... I just calculated that the development version of Fractal should be using over 15 megs of ram; its GF gun builds an array of about 4 million ints. I didn't realize it was this big. Is this even possible? -- Vuen
It's a 4 megapixel graph then from the Fractal Grapher. Cool. I think I will import it to my digital camera. =) -- PEZ
According to http://www.internalmemos.com/memos/memodetails.php?memo_id=1321 'Hello World" Java2 app uses 9Mb on Sun Solaris :) -- Frakir
Has anyone tried Robocode on Solaris? It would be interesting I think. -- PEZ
Interestingly enough, most of the press regarding Java on Solaris is not all that favorable. I am not sure if this still holds true but I seem to recall something in the Java Developers Journal recently exposing some internal document where there were some squables between the Java development team and the Solaris development team over performance issues. I recall thinking that was very strange. -- jim
No, Fractal 0.32 only uses about 128k of memory for its 2 graphs (itself and the enemy); what it draws is only 101x80 doubles. Fractal 0.48 uses probably a bit less; it segments on more, but the data is much more coarse. The development version of Fractal has quite a few more segments, which is why it takes up much more memory. In any case, the grapher is unfortunately currently discontinued; I may rebuild it from scratch later on (once Fractal becomes competitive again). -- Vuen
Hrm, ok, my new thing uses LOADS of memory. Too much. I keep getting "OutOfMemoryExceptions?" !!!!!?!!!! Darn, looks like I might have to rethink it .... :(
--Wolfman
It might just have a bug. Check to see if you have an infinite loop somewhere in your code. What are you trying to do that could be using so much memory? -- Vuen
He's probably calculating PI to the 10^10 digit so that his victory dance can be as perfectly circular as possible. ;) -- Miked0801
BTW, I find Fermat to be a fairly slow bot when testing melee...
Fermat is a very slow bot in 1v1 as well. I never test against it because it's so beat your head against the wall slow. -- Vuen
Ahhhh, as I said, its not CPU that its taking up, its memory. Thus if I manage to cut it down to "fit" it runs pretty damn fast. Its just that cutting down the memory requirement also reduces the effectiveness. :-/
--Wolfman
Hmm. What kind of gun are you using? If it's something new and innovative, consider writing up a wiki page for it : ). Also, cutting down the memory requirement can't possibly make it less effective than throwing an OutOfMemoryException ; ) -- Vuen
Its a kinda combination of new and old. Im kinda being cagey about it because I need some kind of advantage over you guys otherwise I will never make it into the top 10. Not that its looking likely at the moment, im right on the limit currently of the memory - sometimes it says out of mem, sometimes not. And I want to add more! /me cries
--Wolfman
I own an unused copy of Solaris for i386, I could install it and try robocoding on it sometime if anyone's particularly curious. -- Kuuran
Curious how much pain you can endure, or curious just how much the different divisions of Sun couldn't get along? -- Kawigi
*laughs* I'm allowed to be curious about more than one thing ;) I mean, come on, you never licked a battery as a kid? -- Kuuran
Hey! Licking batteries is a tried and tested method of seeing how much power they have. Much easier than getting a voltage tester. (I can usually tell the power of a battery to the nearest volt just by touching it to my tongue for a second) -- Tango
Slightly surprised not to see Vapour mentioned here, based on the amount of calculations it does and the trouble I had getting it not to skip turns like crazy :) Is that just because nobody has noticed, or is it really not up there with the slowest? -- Shrubbery
Frankly I didn't notice it. I do now however that the bots of matt (UnderDark3 and Katana) are not quite fast. If you really have some spare time, try CombatTeam? against any other team. I don't get more than 20 fps minimized. My own bots are quite fast, but then again, they don't calculate anything worth to mention :-D -- GrubbmGait
Yes, my bots are slow: they calculate the folowing every turn:
CircularTargeting (Brute Forced)
AntiGravity (Brute Forced)
Highest LMMS value
Stats
--UnderDark
That's still probably not as much calculation as most of the bots mentioned up there. And teams tend to be pretty slow if they communicate, too (the communication mechanism is sort silly, in an artificially slow way). That's why a battle between ArmyOfShiz and HOFSwarm is faster than either one against TroodonPack - because TroodonPack sends a few messages around (of course, the bots are otherwise comparably fast). -- Kawigi
Added mn.Combat. This bot is seriously slow in melee and God help you if you are running a battle against the mn.Combat Team. This robot is the poster child for the milliseconds-per-bot limitation. -- Martin
Added Pugilist to kick myself in the butt so that maybe I can look into speeding it up some day. -- PEZ
Added Shaakious ... I gotta speed that thing up! At least it doesn't get updated too often. -- Voidious
Sorry about Gladiator, it's probably the PatternMatcher that makes it slow, I'll try to make it faster on the next release. I't tring to make it a FoldedPatternMatcher like in Che, but it might take some time. -- KID
Added X2, because you know something is wrong when you think Shadow is a fast bot. -- Florent
I've been avoiding this... but the truth is... Chalk's deserved it for months... not that I'm ever going to apologize... I'm proud of my little slow buddy... Cheers... --Corbos
A note, here isa site that can help you make smaller faster bots, this site is old, but still useful. http://www.cs.cmu.edu/~jch/java/optimization.html This one isn't java specific, but I think you can fish out the meanings. http://g.oswego.edu/dl/oosdw3/ch25.html And just for cause --Chase-san
I've been surprised when profiling a dev version of FloodHT that it spends about half of its time in Math.atan2. Actually, I still haven't figured out if I really call it that much, but I think calling trigonometric functions needlessly will result in a performance hit due to Java's "strictfp" requirements (which we probably don't really care about much in our bots, it's a shame we still basically have to use it). -- Kawigi
Added lechu.Ala, against SnippetBot it is slower than two X2 fighthing eachother. -- GrubbmGait
Ala 'is' slow, does it skip every round or something? Also if you find Pytko slow, you can add it here, I don't think its to slow. However Seraphim should definitely be on this list (so i'm adding it). --Chase-san
I just tested Pytko, and it's pretty fast. So no need for it on the SlowBot list. Stormrider can get kind of slow (especially once the flattener enables), but it's nothing compared to X2 or Ala. I often use it for testing my gun instead of DrussGT because it uses a fraction of the memory. -- Skilgannon