The basic idea is to predict the enemy's movement one tick into the future at a time. Look at his last n ticks, find the next step he most frequently has taken after that sequence, and project his movement forward according to that step. Now from there do it again and again until your bullet intercepts him! That is the brief summary. Below is the write up I wrote back in the fall, moved from my page to here. Enjoy!
For a fully functional (if bare-bones), open source implementation using a HashMap?, check out SingleTick the robot.
The first step is to keep a list of the last n steps the enemy bot took. I use a circular buffer. By experimentation I've discovered that good values for n, if recording every step they take (as in a duel), are between 20-70, depending on the bot.
We are going to record the list in a pattern tree every time we add a step to it. We are going to keep track of as many of these lists as possible & use them to project probable future movement. The tree will allow us to find the most frequent step taken after any n-1 steps. To do the projection, we feed the tree the last n-1 steps, then project the bot according to the most frequent next step. Then we add that step to our history, feed it back into the pattern tree, and project the bot again according that most frequent next step. Lather, rinse and repeat until your bullet can reach the projected position! The tricky part is recording the information in the tree so that accessing it is fast enough. Here is some pseudo code:
![[Home]](/images/RoboWiki.png)
Step mostRecent = last step in the recent history
Node cur = the head of the tree
for (Step s : recent history, going backward) {
increment the number of times we've visited "s" in cur
cur = cur's child corresponding to "s"
(if it doesn't exist yet, create it)
}
Now to project the next most probable step:
Node cur = the head of the tree
for (Step s: projected history, going backward) {
cur = cur's child corresponding to "s"
if cur is null, break
}
return the step most visited in cur
Wow, that makes it look really simple! My implementation starts skipping a few times every round after I increase n past about 50. Note that if the given sequence of n-1 steps has never been recorded before, it will traverse down the tree as far at it ever *has* seen before & give you the most probable step at that point.
This technique can do some neat things. One of my favorites is predicting collisions. As you are projecting future steps, if it returns one that would crash the bot into a wall, replace it with a step like Robocode itself would generate. Then the pattern tree automatically starts giving you back the bot's most probable steps after hitting a wall! It was very rewarding watching this *perfectly* predict Walls' movement after watching him for 2-3 corners (and collisions with myself after seeing it once). It handles SpinBot when he hits the walls quite well, too. With a pattern depth of 68 or more, it predicts Crazy's movement with some pretty nice accuracy, too. For whatever predicting sample bots is worth :).
It is not, however, simple. One of the big problems is that, unchecked, this will consume all of your available memory in a matter of a few rounds. I overcome this obstacle by keeping a heap of all the nodes in the tree according to when they were last accessed, then booting out the LRU nodes of the tree once there are too many. I optimized my structure for memory usage & I can hold about 5,000 nodes per MB of memory I'm willing to consume. My poor laptop has been very abused.
So, there is a rough sketch of it all. This outperforms the other pattern matchers in the TargetingChallenge2K6, so maybe it's a nice idea! I'll keep checking this site for a while in case y'all have any questions.
Is there any bot on the repository using this type of PM yet? --Starrynte
@Starrynyte: Both WeeklongObsession and WeeksOnEnd use it, with repository links on their respective pages. @Simonton: This is a very interesting (and unique!) idea. I'd actually be skeptical it would work so well if you hadn't already proved it. =) Very neat, indeed. -- Voidious
Now that i get what you're trying to say, very interesting! It's like doing PM on PM...(which is better, now that you've showed it) --Starrynte
Could you perhaps make an commented example of this? String based or otherwise (which is easier to understand). I'm really interested in this, i'm just not sure of implimentation. --Chase-san
Sorry about that, Chase; you asked me to explain this a while ago, too, and I totally didn't live up to my promise. Well, here's SingleTick the open-source, commented bot. -- Simonton
Thanks, this should make the development of this more advanced pattern matching technique easier and bring it into broader use. --Chase-san
Wow, it'll take me a while, but I will definitely start looking in to this targeting method. I've been away for so long now. Maybe not in calendar time, but in terms of development. Entirely good job in dominating the minibot rankings like you do dude! -- PEZ
Why thank you. Good to see you again! -- Simonton
I love the concept behind this, but as I think on it I come to one problem: because you match on the most frequent next movement that you appended, you also 'reinforce' that pathway, making it highly probable that you chose from the same path on the tree the next time. This would essentially leave you with a stock standard pattern matcher. Of course you get other cool things like wall bouncing, but does that justify the extra complication? I'm sure it would be possible to add wall bounce prediction to a regular PM. -- Skilgannon