Talk:Pallas

I use Simonton's KDTree for Dynamic Clustering. I modified it to accept 'dynamic' weighting. If I have add a 'hit' dimension to my movement and weight it 100 when in normal situation and weight it 0 (not take into account) when go for flattener, will it work? » Nat | Talk » 11:32, 28 February 2009 (UTC)

It would work, except keep the following in mind: When 'hit surfing' you always want to record the exact direction the bullet was aimed in, whereas with 'flattener surfing' you should only record the center of where your bot was, so you probably should store two seperate values in entries where you get hit: one for the enemy's bullet aim and one for the center of where your bot is.

I also have one other note: You say on the page "3 KDTrees", actually you could probably just do with 1 tree, which would save you CPU and memory: For the first two guns there you only need to do one kd-tree lookup, and just make your data contain information in both GF and 'play-it-forward' mode. For the third mode, you could just do a second kd-tree lookup with different weightings fed in. --Rednaxela 18:02, 28 February 2009 (UTC)

Note that my 3 KDTrees: 2 are used for gun and one for Wave Surfing. I'll make it with 2 trees, as I can't make the surfing and targeting use the same tree (or anyone can?) » Nat | Talk » 01:53, 1 March 2009 (UTC)

Oh wait, I did misread (didn't read the whole sentance) and thought the 3 meant one for each gun. But anyways yep, my main point was that the same kd-tree can run the tronsgun and the wave guns :) --Rednaxela 04:42, 1 March 2009 (UTC)

Just want to know, what is the TronsGun actually call. ABC call it Forward Pattern Matcher, Florent call it Pattern Recognition. In the TC board, it call Dynamic Clustering, where dynamic clustering is only technique to manage data. I think Rednaxela call it Play It Forward (from comment on this page). I'm currently call it DC-FPM gun. In outer world (the old wiki), some one say that he use Play It Forward gun. IMO, Play It Forward is a technique for find enemy location from current scan. So, what it actually call? » Nat | Talk » 12:59, 3 March 2009 (UTC)\

I would call it Dynamic Clustering using Play-It-Forward. DC-PIF. DrussGT uses DC-GF. --Skilgannon 15:10, 3 March 2009 (UTC)

And, if it is DC-PIF, what it is if it has only PIF? » Nat | Talk » 07:24, 5 March 2009 (UTC)

I'd say "Pattern Matcher" would be misleading because "Pattern Matching" means the proess of finding matches. "DC-PIF" or "TronsGun-style" are what I'd call it. Also note, 'traditional' pattern matchers could actually be called PM-PIF in truth. This is because theoretically you could have a PM-GF gun, that finds matches via PatternMatching and projects future position with a stored GF. Actually PM-GF is not just theoretical, it was used heavily by Iiley as I understand! As far as "just PIF"? I don't think that has any meaning, you need some way to decide WHAT to be playing forward. I should make a table of these various interesting configurations some time on the wiki... :D --Rednaxela 07:49, 5 March 2009 (UTC)

Simonton's KDTree

Hey, anyone use Simonton's tree? I'd want to know what the maxDensity mean. Is it mean the child of each node like: (set maxDensity to 8)

                           ROOT
                            |
     +------+-------+-------+------+------+------+-----+
    1st    2nd     3rd     4th    5th    6th    7th   8th
     .      .       .       .      .      .      .     .
     .      .       .       .      .      .      .     .
     .      .       .       .      .      .      .     .

or mean the item to keep in one node like:

                ROOT (1st,2nd,3rd,4th,5th,6th,7th,8th)
                                |
      +-------------------------+--------------------------+
 NODE (1st,2nd,3rd,4th,5th,6th,7th,8th)      NODE (1st,2nd,3rd,4th,5th,6th,7th,8th)

? I'm getting confused with this tree. » Nat | Talk » 08:13, 3 March 2009 (UTC)

I don't use Simonton's one (I wrote my own from scratch because I decided I decided it was good to learn to), however looking at the code, maxDensity refers to how many data points can be inserted into a node before that node will split into *two* children. I believe this is like what you have in your second diagram, except it should be noted that in a kd-tree, only the leaf nodes actually contain data points. Stem nodes like "ROOT" in that diagram only contains a "boundry" value and two child nodes. I hope I'm clear enough --Rednaxela 09:26, 3 March 2009 (UTC)

OK, correct me if I'm wrong, when the data points in node exceed the maxDensity, the node split into 2 nodes. The parent node contains the links to its children, only the lowest level node contain data, right? One more question: how many point the data can store? Is it 2^floor(depth/dimension) * maxDensity? » Nat | Talk » 10:39, 3 March 2009 (UTC)

That all seems fine to me. As to your formula, I'm too tired right now to really analyse it, but I would say it is depth, not depth/dimension. Each time you split it doesn't matter which dimension you split on, you still double the number of data point available. However, unless you get a *perfect* spread of data, some places will reach max depth before others, so you will never really 'fill' your tree. --Skilgannon 15:10, 3 March 2009 (UTC)

I don't even think that it will have a really edit conflict on the new wiki. Rednaxela, I want to know that which editor do you use? I think the wiki editor warn you if there is edit conflict.

Am I misunderstanding about KdTree? I think it a binary tree (of course). The 1th level is 1st dimension, 2nd is 2nd dimension and so. Is it mean that the actually depth of the tree is depth*dimension? I don't understand tree in anyway. » Nat | Talk » 07:28, 5 March 2009 (UTC)

Er, whoops, that was editing an old revision, not an edit conflict, thus I didn't get a warning (I clicked edit when looking at a diff). As as far as a KdTree, well, the 1st level could be the 1st dimension, the 2nd the 2nd and so on, BUT actually it's very often not done this way. The definition of a KdTree doesn't define which nodes split across which dimensions. In my impmentation I make nodes split at the dimension with the widest spread data, but there are plenty of other ways. And really, you split across dimensions more than once, there isn't really an actual limit on depth to a KdTree in theory. I suggest you look at some online resources on KdTrees, such as here. The "nearest neighbor search" is for example is what a DC-gun does with a KdTree, and the "the levels of a kdtree" kind of shows the structure of the KdTree --Rednaxela 08:04, 5 March 2009 (UTC)

ArrayList usage

I'm wondering about highly used ArrayList. If I add one element to the array list each turn. will this faster?

ArrayList list = new ArrayList(1000);

do {
    // ....
    if ((list.size() - 200) < getTime())
        list.ensureCapacity(list.size() + 1000);
    execute();
} while(true);

» Nat | Talk » 09:43, 5 March 2009 (UTC)

I doubt it would matter that much. ArrayList already allocates in chunks at at time as need arises and should be pretty optimized in terms of how much it does it by. --Rednaxela 06:33, 7 March 2009 (UTC)

Performance issue

I know that ABC use his own LinkedList for the performance. I'd want to know what is faster, ArrayList or Vactor. » Nat | Talk » 06:17, 7 March 2009 (UTC)

Java's "Vector" is functionally like ArrayList except that it's "synchronized" which means it's safe for multi-threading, but at the cost of performance overhead. In other words.... don't use Vector. Also, if this is for storing a log like it's sounding like, I strongly suggest you avoid ArrayList, and use some kind of LinkedList (either a custom one or Java's one works). This is because for ArrayList to increase in size it must allocate new memory and copy the old contents over every so often, but a LinkedList has no such need. Therefore even though ArrayList tends to be faster on average usually, slowness spikes periodically are more likely to cause skipped turns. --Rednaxela 06:33, 7 March 2009 (UTC)

I'm using custom LinkedList for almost all stats and highly use lists, but I just ask for some debugging graphics (DrawingBot), active waves and some not-so-large lists. One more, do generic-type list and raw-type list effect performance? I think not, but not sure. More, for active waves (including non-firing waves), which is better, ArrayList (as in BasicSurfer), LinkedList (as in Komarious) or PriorityQueue (sort by travalled distance)? I'm wonder about this bot speed because I requested many clusters to be created every tick =) » Nat | Talk » 08:32, 7 March 2009 (UTC)