Wiki Targeting

From Robowiki
Revision as of 19:26, 1 May 2009 by Voidious (talk | contribs) (migrating from old wiki)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
Sub-pages:
Dynamic Segmentation - Code - Archived Talk 20090501

An idea for a targeting strategy by Vic Stewart. While there aren't many bots that would describe their targeting using this term, the ideas put forth by Vic and the resulting discussion and research revealed a lot of useful information about segmentation and Visit Count Stats.

Original post by Vic

Introduction

I've had an idea recently, and I thought I'd throw it into the community. I hope this will result in a lively discussion and hopefully I (or someone else) can implement it when the theory seems to check out. (Actually I'd like to get working on it right now, but I promised myself to first finish my SOOL targeting gun and my new movement)

Feel free to shoot at / correct any assumptions I'm making on this page. Also feel free to add or modify anything if you feel it improves the design or adds to the discussion. It would be cool if this would turn out a community design. (Hence the name WikiTargeting)

The theory

So here's the theory thusfar: (a summary is provided below)

GuessFactor guns have proven to be very successful over the years. In fact PEZ's CassiusClay gun holds the crown in the Targeting Challenge at the moment. So why do these guns perform so well?

These guns generally have a fixed number of segmentation nodes. Take for instance CC's gun: it has 6 segmentation dimensions, most of them with 5 divisions, except for WALL_INDICES which has 4. That means that it has a total of 5*5*5*5*5*4 = 12500 nodes.

In the RoboRumble CC will encounter most robots in only one 35 round match. Let's assume it gathers 1000 waves in that match. That results in a total of 35000 waves to be distributed over 12500 nodes. 35000/12500 nodes equals on average 2.8 waves per node.

I obviously don't think the strength of CC's gun lies in that number. The thing is that some nodes will be more populated than others. (It would be cool if someone has data on how the waves are distributed.) My guess is that a good GF gun like CC's gains most of its points using nodes that are much more frequently visited. The assumption for now would be that nodes with only 1 or two waves in it do not contribute to CC's success.

For now, I'm going to assume that a REALLY good node needs 100 waves collected or more. Probably this number could be much less but I think we can agree that such a population will give a pretty good estimate of the enemies futute position. Opinions?

Now I will make a bold assumption: I think on average 80% of CC's score can be contributed to 20% of its nodes. That means 2500 nodes do most of the work. If this WikiTargeting gun would use only 2500 nodes (dynamically segmented for each individual enemy) that would slightly decrease performance, but we can compensate for that. Let's suppose that CC would have 100 waves collected in each of those 2500 uber-nodes. Would that compensate the above loss? I'd say yes it does. This would mean that on total 2500 * 100 = 250,000 waves would have to be collected. Assuming 1000 waves per battle, that would mean 250 battles should be enough to gather the required amount of data. And the more battles, the better these nodes will predict the enemies future position. Off course all these assumptions need proof. Thoughts?

It is easy to conclude this would require prepopulating the gun with data. I will come back to that later.

Now we have a problem: some nodes will have hundreds or even over a thousand of waves collected, while other may only have 10! The distribution is not equal. This is caused by the fixed segmentation. Could we dynamically segment this data so we end up with exactly 2500 nodes each populated with 100 waves? I think this can be done by using a tree structure where we cut the population in half, using the most efficient dimension, as we climb up the tree. Probably there are other solutions. Suggestions?

Now suppose we have this stuff all working. Would one 35 round match have much effect on the data gathered in 250 matches? Not very much I think. That means the optimal GF found in each node should be enough data to store per node. No need to save all the other bins! This will reduce memory consumption. It also means that during matches no waves have to be fired and collected anymore. This will improve performance leaving more room for expensive movement algorithms. It will also decrease the data file sizes, leaving room for more prepopulated data files on individual enemies.

This creates a new problem: the gun will not be able to adapt to adversaries using adaptive movement. I think this problem can be discarded because there are only a few of those in the rumble. Opinions?

About prepopulating: now we have 2500 bins that need to be stored. We have reduced each node to one bin. So that requires at least one char to be saved. Because we will need dynamic segmentation, we will also need data on which segments this node has. Of course this depends greatly on the chosen algorithm but we will need at least one char to identify which segmentation parameter to use and a char for the division border. Probably we will need some more data if we were to use a tree structure, but for now let's assume we need 3 bytes (chars) per node. This means we will have to serialize 2500 * 3 = 7 kB. This obviously is way too much, because ideally we want to save data on all 286 RR participants.

  • We could decide to have a generic data file (generated from data collected from matches against multiple enemies) for the bulk of the enemy bots, and include seperate ones for the 26 most severe problem bots. (26*7 + 7 < 200kB) But this may blow away all advantages we have made so far compared to the good GF guns.
  • Or we could reduce the number of nodes even further.
  • Or we could define 25 movement categories, and add a file that maps enemies to catagories.

We need to solve another set of problems: How do we collect such huge amounts of wave data, when we can only store 200kB in our robot's data directory? And should our robot perform the dynamic segmentation itself? I have experimented with the latter a bit with Locke, and I must conclude that there is no way a robot can perform such heavy algorithms in-game. It will even time out in the post-match time. Therefore a separate application should gather the data out of the robot directory and process it. This application will generate the file(s) needed by the robot to populate its gun. We can solve the first problem by letting the application read and empty the robot's data directory every few seconds (asynchronously to the robot which at that moment is fighting its matches).

This will significantly reduce the amount of code required for the robot itself, meaning it will probably fit in a micro- or even nanobot.

Summary

  • create a helper robot that only fires and collects enemie waves and serialize those waves after every round.
  • have a seperate application collect all wave data and have it empty the robot's data folder
  • this application will analyse wave data collected from 250+ matches and construct a file which contains only dynamic segmentation data and optimal firing angles (GF format)
  • our real WikiTargeting robot will read those files and construct the appropriate graph in memory
  • the robot does not need to edit this already high quality graph. It does not fire waves or otherwise collect any enemy movement data.
  • the guns size can therefore be tiny, and may even fit in a nanobot.

Challenges to overcome:

  • solve the Lineair Distribution problem
  • fit as much data as possible in files as small as possible
  • determine how many nodes we will need to compete with or exceed GF gun performance

What do you all think of these ideas? Don't be shy now ;-)

Bots using Wiki Targeting

While no known bots would use the term to primarily describe their targeting system, several bots have used it to augment their existing systems.

See also

Retrieved from "http://robowiki.net/w/index.php?title=Wiki_Targeting&oldid=5942"