gun tuning tangent
It's so strange, I found, once I add an attribute it doesn't really matter how much it is weighted (within an order of magnitude or so), I still get around the same results for gun accuracy. The biggest gains I had from genetic tuning was adjusting the speed that the 'time' attribute increased, and even then once it was in the right ballpark there was very little to choose between them. Still, it does help to squeeze that extra 0.1% out =)
Hmm, is it that strange though? You have enough good attributes already that the new attribute likely correlates to a significant degree (but not entirely) with one or more of them, which I'd expect to make it so it wouldn't change which points are closest when it's weighting is only changed a small amount.
True. I really need to PCA the data that gets generated by a typical battle. There must be an input transformation which can eliminate a bunch of the dimensions.
Attribute weighting is probably one of the things in Robocode that has received the most attention vs what it deserves. =) Sort of like dynamic segmentation, which used to get tons of focus, but is IMO much more elegantly implemented with KNN. I think it's worth having them tuned, but for example, Gilgalad is a super strong bot and recently got the exact same score when he removed his gun weights.
My thoughts with PCA would be that we could eliminate a large number of the dimensions stored in the tree by only taking the X main components, and make a transform which combines a large number of measurements from all sorts of things which aren't even very useful and turn them into a much more information-dense, lower dimension location. This would save on memory as well as search time while still keeping pretty much exactly the same results.
I agree that far too much effort has been put into refining weights, but it does have its place for ekking out that extra little bit of performance against a known population.
Obviously I agree it's worth some effort, if you check my recent version history. =) It's a very obvious and easy knob to fiddle with. And I can see pretty clearly with WaveSim that there are accuracy gains that can come out of it.
The PCA stuff sounds pretty interesting. I think it went a bit over my head in my Machine Learning class (though I understand the basic idea).
I think another big factor is that there's so much variance in hit rate, and so much score coming from movement and survival, that increasing accuracy beyond a certain point just doesn't translate into very many rumble points. The best of guns can miss 10 shots in a row and force you to rely on good movement and energy management. It's still fun though. =)
My current view is that movement and targeting inextricably linked with each other and it's impossible to say which part of points come from movement and gun. I think, that both statemets are correct:
- good gun gives less chances to enemy to hit you (so less score for enemy and more bullets for you, so more score to you), because steal his energy
- good movement gives less chances to enemy to hit you (so less score for enemy and more bullets for you, so more score to you), because steal his energy.
It's system of equal partners, imho for last few weeks:)
And a little offtop: also, imho for last few weeks, that statistical targeting is impasse (deadlock?) and next breakthrough may be in single tick playing forward. Especially in the light of the fact that totally annihilate of weak bots is more important, that destroy strong bots.
I disagree for a different reason... I think that's a bit of a false dichotomy, because I'd still classify the "single tick playing forward" methods as statistical targeting so long as the mechanism used each tick is still statistical. It adds another assumption to make each data point used more generally, but so do GuessFactors.
Really, what the technique provides, is denser data by making the assumption that on a given tick the opponant behaves in mostly-deterministic manner according to the attributes you're targeting based on. If your attributes are sufficiently complete, it should have a quicker effective learning rate.
I do think there is value in the "single tick playing forward" idea, but as-is it uses too much CPU, espescially if your targetting attributes are complex. I think one has to consider what it brings to the table and take advantage of it without making things so slow. My current view on the best approach, is that it would be doing larger number of ticks than one at a time (i.e. 10-tick-at-a-time iterative prediction).
I did not say, that behind ST-PIF must be kNN etc.:) Neural Networks may be used, for example. But actually yes - when i implement this, it was knn based. And you completly right: although this gun gets hit rate >95% against walls and >60% against crazy, it was unacceptable slow.
And I never said ST-PIF was always statistical, just that it doesn't have anything more to do with it being statistical or not than GuessFactors do (aka, nothing) :)
<random> Come to think of it, "Single-Tick" techniques and "GuessFactor" techniques have a lot in common... both "fold" data across lines of assumed symmetry. GuessFactors "fold" across the "front-versus-back" symmetry, whereas Single-Tick folds across a temporal symmetry of sorts.
GuessFactors have proven themselves highly beneficial, and Single-Tick techniques may also in the future, howver both techniques would perform sub-optimally when encountering something which violates the symmetry they assume. Unless the targeting attributes include something that differentiates front/back, GuessFactors will perform sub-optimally when faced with an opponent which treats them differently. Of course, it's difficult to take advantage of this in a major way I think.
Similarly the weakness of Single-Tick techniques is when an opponent treats different ticks differently due to something that cannot be detected in the targeting attributes. For most robots, even surfers, the assumption is probably good enough... but... in contrast to guessfactors... <evil>A cleverly designed semi-random multi-mode movement could be designed so that the movement path generated by a "single-tick" technique is never where it actually ends up ;) </evil></random>
Anti-Pattern matching comes to mind.
Have you tried using k=1? How does it compare then with something like regular kNN-PIF in terms of speed and hitrate?
Sorry, but i forgot details, everything that i remember i already wrote. Tomorrow i can publish that code, but i have no time in nearest future to liven up it
I guess K=1 would make ST-PIF have the same weaknesses as neural network based Pattern matching (non-statistical).
If a bot dodges 30% of the time going straight then turning to the right and 70% of the time going straight all the way, Neural Targeting averages both patterns and shoots slightly to the right, missing both patterns. In other words, it is awful against Walls.
Increasing K is what makes the gun choose the "straight all the way" pattern alone and achieve 70% hit rate.
Yeah, but you have other factors which would affect which scan is closest, like forward distance to wall, time since decel, distance last 10 etc. which all affect what the enemy motion will be. That is the advantage of this over plain single-tick pattern matching (which works better than regular pattern matching, but is slow/memory hungry). Even having k=3 would be quite fast for each kNN compared to what works well in guns now, where I can easily use k=150 and not skip any turns.
Also, once it gets onto one of the branches which suggest it will follow the '70%' you mention, the act of following that branch will make it more likely to further follow similar branches in the future, so it won't end up in between, but rather will end up at a different path completely.
Having a classifier which differentiates both patterns solves the problem (distance to corners against Walls).
If not, making many k-NN searches with k=1 gives you 30% of the ticks from one pattern and 70% of the ticks from the other pattern, and the resulting pattern is a 30%/70% mix of the two. It assumes a 3rd unseen pattern can be predicted from 2 previous patterns.
Should perform well against orbital movement, where turn rate changes gradually with distance and a 3rd unseen turn rate (or a zig-zag) can be predicted from 2 others. But perform bad against pattern movement, where patterns don't change gradually with classifiers.
I also thought on this problem and find out a possible solution: keep similar amount of data with different classes.
I tend to disagree - I think gaining rumble score via targeting has to come by improving against mid-range bots that are scoring significant amounts of bullet damage and survival against you. Whether or not I beat SpinBot 4000-0 or 5000-0 isn't going to make much difference. =) But going from 70% to 75% against a few dozen bots will make a difference.
Roughly, on eye, Diamond has >=90% APS against ~50% bots, so it's better to go from 90% to 95% against ~450 bots:) More accurate, Diamond has 5 bots with 70% APS and 28 bots with 90%, so, again, it's better to go from 90% to 95%:)
More accurate data: Diamond has 70-80 APS against 134 bots and 85-95 against 277 bots 90-95 APS against 168 bots
Sure, I'd love to go from 90% to 95% =), but that's incredibly difficult. It means cutting the enemy's score in half. And these are bots that you are already annihilating, and which are winning about zero rounds against you, so all the score increase has to come from relative bullet damage.
On the other hand, going from 70% to 75% means cutting the enemy's score by ~16%. And these bots are winning some rounds against you, which gives you more score to take from them as you improve.
I did not say that it's easy to more totally annihilate (completly totatlly annihilate:)) a weak bots. I say, that it's place where more points are hidden:)
Well, I weight the hidden points by how easy they are to obtain. =) For instance, you won't see me talking about the 55 points still "hidden" vs DrussGT...
But they are there!:) Ok, i offer stop this little offtop:)
