Difference between revisions of "User talk:Nat/SDSResearch"

From Robowiki
Jump to navigation Jump to search
(→‎Zoom Targeting: research reached the end, new research will lunch soon)
 
(6 intermediate revisions by 2 users not shown)
Line 73: Line 73:
 
   | +-All
 
   | +-All
 
   | +-A
 
   | +-A
   |   .
+
   | | .
   |   .
+
   | | .
   |   .
+
   | | .
 
   | +-B
 
   | +-B
   .   .
+
   . . .
   .   .
+
   . . .
   .   .
+
   . . .
 
</pre>
 
</pre>
 
When segmenting, check the children size will make it know how many data stored in each lower level. And this will make it faster since it doesn't need to perform String.equals() on every single items.  
 
When segmenting, check the children size will make it know how many data stored in each lower level. And this will make it faster since it doesn't need to perform String.equals() on every single items.  
  
 
I get above ideas when I'm taking a bath this evening. When I wrote this, I realize that this is nearly the same with [[Wiki Targeting/Dynamic Segmentation]]. Except that the this one can generate PM-like result. Comment? &raquo; <span style="font-size:0.9em;color:darkgreen;">[[User:Nat|Nat]] | [[User_talk:Nat|Talk]]</span> &raquo; 11:57, 23 May 2009 (UTC)
 
I get above ideas when I'm taking a bath this evening. When I wrote this, I realize that this is nearly the same with [[Wiki Targeting/Dynamic Segmentation]]. Except that the this one can generate PM-like result. Comment? &raquo; <span style="font-size:0.9em;color:darkgreen;">[[User:Nat|Nat]] | [[User_talk:Nat|Talk]]</span> &raquo; 11:57, 23 May 2009 (UTC)
 +
 +
Actually, some recent targeting I've been experimenting with is like [[Wiki Targeting/Dynamic Segmentation]], except instead of splitting across a single dimension at a branch, it splits across a hyperplane in the data. Actually, I suppose what I was doing was a form of "Irregular Tile Coding" with a dynamically grown tree-based implementation. My point though is, it's kind of interesting how you can discover algorithms that effectively do the same/similar thing, just in a different way. --[[User:Rednaxela|Rednaxela]] 14:06, 23 May 2009 (UTC)
 +
 +
: So you basically mean that thinking of the new way to do the same/similar thing is interesting, even the things you thought is supposed to be the combination or subset of invented algorithms?
 +
: I was thinking that if I finished the newer version of SDS using this method, this SDS gun may be like old Laser Targeting. [[User:PEZ|PEZ]] wrote in Laser Targeting page at the old wiki that if you fully understand GF gun, there is no need to create this gun since the GF is more effective version of Laser Targeting. This SDS gun will be in the same place as Laser Targeting that if you can create fully Dynamic Segmentation system, there is no need to create this type of gun (stats management?)
 +
: Anyway, I'll implement this. Expecting it in a week I think, but can't comfirmed. &raquo; <span style="font-size:0.9em;color:darkgreen;">[[User:Nat|Nat]] | [[User_talk:Nat|Talk]]</span> &raquo; 14:28, 23 May 2009 (UTC)
 +
 +
Challenge is running... Using the tree it didn't even skip a single turn! But it isn't really ''symbolic'' anymore, I use integer instead of characters now.
 +
 +
By the way, I completely rewrote my code for this new version with tree. I did copy some code from the older version though, but the main GF targeting system is all mine, except the precise intersection code which is Skilgannon's. The code is much more cleaner than before, and therefore the cleanest code I've ever written =)
 +
 +
From current result, it seems that this is the worst version of this research =) I hope it will went up when it finished all seasons. It is now 70% with 2.2 seasons. &raquo; <span style="font-size:0.9em;color:darkgreen;">[[User:Nat|Nat]] | [[User_talk:Nat|Talk]]</span> &raquo; 17:15, 31 August 2009 (UTC)
 +
 +
== When the earth becomes flat!?! ==
 +
 +
OK, upon close looking into the score for each version, I noticed a lot of 'weird' things:
 +
* Precise wave intersection make you lose your score
 +
* Use only firing wave is better against random mover, use tick-waves is better against surfer.
 +
* Having a weight on firing waves is worst against wave surfer.
 +
* Rolling average also do the different thing that it is supposed to do in other type of gun.
 +
OK, weird, no, ''very'' weird, agree? &raquo; <span style="font-size:0.9em;color:darkgreen;">[[User:Nat|Nat]] | [[User_talk:Nat|Talk]]</span> &raquo; 18:36, 31 August 2009 (UTC)
 +
 +
: Nah, not weird at all. The second and third points have been demonstrated in the past quite a number of times. What using tickwaves does against surfers, is it makes your gun more 'random' from their perspective. If the gun in question is sufficiently good at predicting surfers then tickwaves would become unhelpful, but since it's so hard to hit a surfer... :) --[[User:Rednaxela|Rednaxela]] 18:48, 31 August 2009 (UTC)
 +
 +
== Zoom Targeting ==
 +
 +
Anyone remember Zoom Targeting? It looks more and more like [[Zoom Targeting]] now =) &raquo; <span style="font-size:0.9em;color:darkgreen;">[[User:Nat|Nat]] | [[User_talk:Nat|Talk]]</span> &raquo; 11:39, 1 September 2009 (UTC)
 +
 +
OK, I realised that my gun is indeed a [[Zoom Targeting]] after I write new buffer (more detailed data). So now, this research is ended, and I'll lunch new research with Zoom Targeting shortly. Just please help me think of a cool name =) And, actually the real goals of this research (at first, look at the first revision of the research page) is to ''speed up the symbolic dynamic segmentation'', which is now success. &raquo; <span style="font-size:0.9em;color:darkgreen;">[[User:Nat|Nat]] | [[User_talk:Nat|Talk]]</span> &raquo; 14:35, 1 September 2009 (UTC)

Latest revision as of 15:35, 1 September 2009

Help, does anyone have a TC calculator? The score above is just a roughly averaged by eyes score. I think the actual is much lower except the Total score, that was calculated with ScoreAveragedAddOns / 350. I know that the surf score is invalid. » Nat | Talk » 14:37, 11 March 2009 (UTC)

Try RoboResearch - look on the old wiki for info. --Skilgannon 15:28, 11 March 2009 (UTC)

Actually, don't look on the old wiki for RoboResearch, the new wiki page is more recently updated I believe. But yes, RoboResearch is very nice, it automates running all the battles, calculating the scores, and even generating the table row in mediawiki syntax :D (actually, challenges pages really should state to use RoboResearch). With the GUI version you can queue up multiple versions to test one after the other as you sleep too. --Rednaxela 15:36, 11 March 2009 (UTC)

I usually don't download everything that I need to check out from SVN repository by my self :) I took an hour to find download link for RoboResearch and at last admit that I must checkout them from SVN. Question: Can I pause the challenge and resume it next time I turn on my computer? I am not allow to turn on computer while I'm sleeping. » Nat | Talk » 00:53, 12 March 2009 (UTC)

RoboResearch saves battle results in a database as it goes and doesn't re-run unnecessary battles. In fact, if two different challenges have an exactly overlapping pairing it won't repeat the battles unnecessarially. Also, the GUI version (which I highly recommend) stores currently running challenges in a config file so it's super-easy to close at any time and continue running later. In summary that answer to your question is: Yes :-) --Rednaxela 01:10, 12 March 2009 (UTC)


If I do bit shifting to fit the data into 8-bits link this:

0 0 0 0 0 0 0 0
  L     D   a W 
  e     i   c a
  t     s   c l
  e     t   l l
  r     a
  a     n
  l     c
        e

With this I can have up to 7 velocity segment, 7 distance segment, 2 acceleration segment and 2 wall segment. It can fit every segment into one character. Do anyone have idea how to cut the string as per SDS? Or just char & 0xFE or 0xE0? One more, what is faster, doing kernel density or log it to an array and find max? » Nat | Talk » 01:36, 12 March 2009 (UTC)

LinkedList is super slow. I change my code to use ArrayList(10100) and I can increase the segment and log size a LOT (see above). Let see 0002 with larger log size. And 0003 with non-firing waves with larger log size. Anyway 0003 is faster than 0001 » Nat | Talk » 14:41, 12 March 2009 (UTC)

Do I need to publish code for each research bot? I can have them on my page in a minute, but not sure if I need, or anyone want. Note that this research have codename Astraea. All the bot is Astraea with SDSxxxx version number. (OK, at first it is a competition robot, but I can't find better, but not the best, wave surfing to plug in + it really slow so it is now a research. In fact, a entry Astraea DEV in TC2K7 fastlearning result is really a SDS0001) » Nat | Talk » 14:41, 12 March 2009 (UTC)

Non-firing wave

I'm wonder, with these incomplete result show that non-firing is better against surfer but worse against RM? But let see a complete score before. » Nat | Talk » 14:41, 12 March 2009 (UTC)

Complete score out, but still I got more from surfer but less for random. It seem that SDS0001 (or 0.1TC) is best against random anyway. Very Mysterious. » Nat | Talk » 11:25, 13 March 2009 (UTC)

Yep, that makes sense, not really mysterious. Random movers don't react to firing, thus not caring about whether the waveis a firing one or not leads to faster learning of them. Surfers on the other hand react to bullet fire thus putting more weight in firing waves makes it more accurate against them. --Rednaxela 14:01, 13 March 2009 (UTC)

Ah.. Rednaxela, SDS0003, which have highest score against surfer, use non-firing waves and weight them equally. No special case for firing waves. I say it is mysterious because a surfer, that react bullet fire, is better with firing wave. But the random mover, which doesn't react bullett fire, is better with non-firing wave. If you watch score closely with the version history, you'll see that by using only recent data (0.1TC, SDS0001) is better against random mover and worse against surfer, but for SDS0002, which take all the data, better against surfer but worse against random mover. I'll published my source code to let anybody to see is there any bug in my gun? Everything seem to be inverse from ordinary stats gun. » Nat | Talk » 15:30, 13 March 2009 (UTC)

List speed

By the way, keep in mind that LinkedList is VERY slow if you use list.get(number), but if avoid accessing by index it's fast. Just the general rule, if it was very slow you were probably accessing with .get(number) --Rednaxela 14:59, 12 March 2009 (UTC)

Yes, I use .get(). Just foroget it was LinkedList! Now, I use ArrayList with initial capacity over than maximum element. (say, 0002 max is 10000, initial ArrayList to 11000) But, as of ABCLinkedList challenge, someone test that ArrayList is faster than a custom linkedlist anyway, and custom linkedlist is faster by 10x to java linkedlist. » Nat | Talk » 00:32, 13 March 2009 (UTC)

  • Well, ArrayList would be faster if what you look at is average speed of insertion/read, but ArrayList would have FAR higher PEAK time for a single .add() due to on ocassion having to totally re-copy the array. I consider peak time per operation more important than average when in the context of robocode because spikes can lead to skipped turns. Personally I plan to some time make a custom list class that's somewhat of a hybrid. It will store in a list of arrays, it first has one array and when that fills it adds a second array, etc, which will give average performance similar to ArrayList with far smaller spikes in insertion time. --Rednaxela 03:01, 13 March 2009 (UTC)
  • Do it need to copy with stats = new ArrayList(23000); ? I think I have set initial capacity to over than the data I'll store, but soon it will grow there :-) (with 35 rounds, I've collect about 25000 non-firing waves) » Nat | Talk » 11:25, 13 March 2009 (UTC)
  • Well, with 23000, it would still copy if you collect 25000 waves of course, only once but possibly enough to skip a turn. Really though, if you want to set the initial capacity to something that's surely enough, I'd say you might as well just use a plain old array, which would actually be slightly faster to access than an ArrayList I believe. --Rednaxela 14:01, 13 March 2009 (UTC)
  • OK, my gun clear keep the log size to maximum of 22000 waves. If exceed, a first stats is being removed until it reach 20000 waves. It'll never exceed of course, but I still use ArrayList for .remove(index) functionality. Anyway, only ~15000 waves is being collected in actual match :) » Nat | Talk » 15:34, 13 March 2009 (UTC)
  • Just a suggestion, be cautious of .remove(index), because doing that requires the ArrayList to re-copy the whole array that's after the index point. If you do that with a near-0 index, it will slow things down tremendously. Removing the first element of a large list is one thing that LinkedList does many orders of magnitude faster than ArrayList (For removing from the middle of a list, either could be faster, depends on exactly where in the middle and the size of the list). --Rednaxela 17:23, 13 March 2009 (UTC)

Let see if I use circular-array will faster? Use the same implementation as circluar-queue :) » Nat | Talk » 01:19, 13 March 2009 (UTC)

KMP vs Java Built-in

About String.equals being faster than KMP, well it really depends on many things. But overall I think I misread how Symbolic Dynamic Segmentation was supposed to work. KMP may outperform the Java built-in functions by far, depending on the characteristics of the text and the pattern. Such things as text/pattern size and how long partial matches may be have a real difference on how they perform. But it can also be much slower if not properly optimized. What I think that could make KMP faster is that it is able to tell you where all the matches are, and if it doesn't find an exact match it can tell you all the places where the biggest partial matches were found. But I don't recommend implementing KMP until there no more optimizations and you are in real need of some ticks. Except of course if you want to expand your algorithms trick bag ;-). --zyx 03:07, 13 March 2009 (UTC)

Robo Research

How can I set the default author/gun for RoboResearch GUI? » Nat | Talk » 11:52, 13 March 2009 (UTC)

About the name of gun

Hey, what name should I call this gun? It once call Symbolic Dynamic Segmentation, but I think it a kind of data collecting/stats manager. I now call it GF/SDS. But, about the multiple choice system, what is better between using Kernel Density and log the hit to array? KernalDensity is more precision, but with array, I can do custom bin smoothing and rolling the stats. Every version here is using array, so I call them GF/SDS/Arr. Is it good name for gun? I may have some GF/SDS/KD (for Kernel Density) soon. » Nat | Talk » 09:49, 14 March 2009 (UTC)

  • Sorry, id should be SDS/GF all over there. » Nat | Talk » 09:50, 14 March 2009 (UTC)

Using tree instead of a list of String/GF pairs

If I use the tree to store each character in each level, may be it will be faster?

ROOT
  +-All
  +-A
  | +-All
  | +-A
  | | .
  | | .
  | | .
  | +-B
  . . .
  . . .
  . . .

When segmenting, check the children size will make it know how many data stored in each lower level. And this will make it faster since it doesn't need to perform String.equals() on every single items.

I get above ideas when I'm taking a bath this evening. When I wrote this, I realize that this is nearly the same with Wiki Targeting/Dynamic Segmentation. Except that the this one can generate PM-like result. Comment? » Nat | Talk » 11:57, 23 May 2009 (UTC)

Actually, some recent targeting I've been experimenting with is like Wiki Targeting/Dynamic Segmentation, except instead of splitting across a single dimension at a branch, it splits across a hyperplane in the data. Actually, I suppose what I was doing was a form of "Irregular Tile Coding" with a dynamically grown tree-based implementation. My point though is, it's kind of interesting how you can discover algorithms that effectively do the same/similar thing, just in a different way. --Rednaxela 14:06, 23 May 2009 (UTC)

So you basically mean that thinking of the new way to do the same/similar thing is interesting, even the things you thought is supposed to be the combination or subset of invented algorithms?
I was thinking that if I finished the newer version of SDS using this method, this SDS gun may be like old Laser Targeting. PEZ wrote in Laser Targeting page at the old wiki that if you fully understand GF gun, there is no need to create this gun since the GF is more effective version of Laser Targeting. This SDS gun will be in the same place as Laser Targeting that if you can create fully Dynamic Segmentation system, there is no need to create this type of gun (stats management?)
Anyway, I'll implement this. Expecting it in a week I think, but can't comfirmed. » Nat | Talk » 14:28, 23 May 2009 (UTC)

Challenge is running... Using the tree it didn't even skip a single turn! But it isn't really symbolic anymore, I use integer instead of characters now.

By the way, I completely rewrote my code for this new version with tree. I did copy some code from the older version though, but the main GF targeting system is all mine, except the precise intersection code which is Skilgannon's. The code is much more cleaner than before, and therefore the cleanest code I've ever written =)

From current result, it seems that this is the worst version of this research =) I hope it will went up when it finished all seasons. It is now 70% with 2.2 seasons. » Nat | Talk » 17:15, 31 August 2009 (UTC)

When the earth becomes flat!?!

OK, upon close looking into the score for each version, I noticed a lot of 'weird' things:

  • Precise wave intersection make you lose your score
  • Use only firing wave is better against random mover, use tick-waves is better against surfer.
  • Having a weight on firing waves is worst against wave surfer.
  • Rolling average also do the different thing that it is supposed to do in other type of gun.

OK, weird, no, very weird, agree? » Nat | Talk » 18:36, 31 August 2009 (UTC)

Nah, not weird at all. The second and third points have been demonstrated in the past quite a number of times. What using tickwaves does against surfers, is it makes your gun more 'random' from their perspective. If the gun in question is sufficiently good at predicting surfers then tickwaves would become unhelpful, but since it's so hard to hit a surfer... :) --Rednaxela 18:48, 31 August 2009 (UTC)

Zoom Targeting

Anyone remember Zoom Targeting? It looks more and more like Zoom Targeting now =) » Nat | Talk » 11:39, 1 September 2009 (UTC)

OK, I realised that my gun is indeed a Zoom Targeting after I write new buffer (more detailed data). So now, this research is ended, and I'll lunch new research with Zoom Targeting shortly. Just please help me think of a cool name =) And, actually the real goals of this research (at first, look at the first revision of the research page) is to speed up the symbolic dynamic segmentation, which is now success. » Nat | Talk » 14:35, 1 September 2009 (UTC)