# Talk:Sequential Prediction

(Difference between revisions)

$Insert formula here$Well this is the result of my quest for a good pattern matching algorithm, I hope you like it and please let me know if you have any doubts or comments.

Just for motivational purposes, I want you to know that my development version of this guns scores around 75 in average (with a maximum of 85 so far) against Shadow 3.66d in the TC challenges. I'm still under heavy development so I don't have definite results, but I think this will be a very powerful gun against surfers and it performs decently against random movers too (close to top GF guns but still doesnt outscores them). Hopefully in the next couple of weeks I will have some TC challenge results to post so I can encourage more people look into this. --zyx 07:44, 3 October 2009 (UTC)

While I'm not yet understand the algorithm, shouldn't this better be under Category:Targeting Implementations? Since it is still PM anyway. --Nat Pavasant 08:41, 3 October 2009 (UTC)

OK, I understand the algorithm now (how weird am I that I got confused by your explanation but understand with the pseudo-code?). I'm not sure about the category, it is the data management for sure, but not sure about the 'Targeting Strategy'

I think this algorithm can do Single-Tick, just that it will run in O(n2). We need to clone the entire log for this =) --Nat Pavasant 09:21, 3 October 2009 (UTC)

Have you try your gun in Pattern Matcher Challenge? (oldwiki:PatternMatcherChallenge)? When I plug this algorithm into my DC-PIF robot and make it choose only the best match, then entered it to the PMC, I got only ~70% or so. I'm not sure if it is a bug in my implementation or not... --Nat Pavasant 13:02, 3 October 2009 (UTC)

I ran two matches of the challenge to show you:

As you can see the index is over 100%, but this is without limitations, not on the size of the log and not on the number of matches to try. It start skipping turns after round 70.
My configuration is however more complex than the simple idea published. I have 3 different matchers in crowd form:
1. Lateral/Approach velocity, using 17 discrete values for each attribute.
2. Lateral/Approach velocity, using 34 discrete values for each attribute.
3. Velocity/Rotation velocity, using 9 discrete values for each attribute.
All matches are weighted as they are found by: match_size / DC_like_distance(last entry in pattern, current entry). Then I keep the best 100, play forward until I have the best 50 that stay inside the battle field. Then I run a kernel density function over those angles to find the best. In the DC like distancing I have many attributes, including distance of pattern to the log tail for fast adaptation. This configuration has been tweaked towards making a good AS gun, so I think I could get it to work even better for the PMC if I wanted to, but my goal is an alternative to current AS guns rather than killing simple pattern bots like this one.
What are you matching on? I found that matching on velocity/rotation gives the best results against PatternBot but is not optimal for top surfers, where Lateral/Approach velocity is much better. --zyx 14:46, 3 October 2009 (UTC)
I use velocity/deltaHeading (which I believe is as same as Rotation). 9 velocity discrete and 5 rotation discrete, yet it only find the pattern length <100 and it does match across round (I try adding ROUND_BREAK but fail) Perhaps there is bug in my matcher:
```	private class PMEntry extends Point2D.Double {
PMEntry next, previous;
String key;
int matchSize = 0;
int round;

public PMEntry(Point2D pt, double heading) {
super();
setLocation(pt);
}
}

private class PMSequence {
private PMEntry last = null;

public PMSequence() {
}

if (entry == null) {
}
return entry;
}

if (last != null) {
for (PMEntry e : entries) {
PMEntry previous = e.previous;
if (previous != null && previous.key.equals(last.key)) {
e.matchSize = previous.matchSize + 1;
} else {
e.matchSize = 1;
}
}
last.next = entry;
entry.previous = last;
}
entry.matchSize = 1;
last = entry;
}

public PMEntry[] getEntries(PMEntry entry) {
ResultHeap rh = new ResultHeap(entries.size());
for (int i = entries.size() - 1; i >= 0; i--) {
}
PMEntry[] result = new PMEntry[rh.size];
for (int i = 0; i < result.length; i++) {
rh.removeLargest();
result[i] = rh.removedData;
}
return result;
}
// Hijacked from Rednaxela's Tree
private class ResultHeap {
private final int size;
private int values;
public PMEntry removedData;
private PMEntry[] data;

public ResultHeap(int size) {
this.data = new PMEntry[size];
this.size = size;
this.values = 0;
}

// If there is still room in the heap
if (values < size) {
// Insert new value at the end
data[values] = value;
upHeapify(values);
values++;
}
}

public void removeLargest() {
removedData = data[0];
values--;
data[0] = data[values];
downHeapify(0);
}

private void upHeapify(int c) {
for (int p = (c - 1) / 2; c != 0
&& data[c].matchSize > data[p].matchSize; c = p, p = (c - 1) / 2) {
PMEntry pData = data[p];
data[p] = data[c];
data[c] = pData;
}
}

private void downHeapify(int p) {
for (int c = p * 2 + 1; c < values; p = c, c = p * 2 + 1) {
if (c + 1 < values
&& data[c].matchSize < data[c + 1].matchSize) {
c++;
}
if (data[p].matchSize < data[c].matchSize) {
// Swap the points
PMEntry pData = data[p];
data[p] = data[c];
data[c] = pData;
} else {
break;
}
}
}
}
```
I add ROUND_BREAK with blank key every round, but I still got `Time: 13; Match Length: 39` --Nat Pavasant 15:06, 3 October 2009 (UTC)

Oh wow! This is really neat! I wonder why it starts skipping turns after round 70 though... Even with three guns running at once, it seems to me it shouldn't start skipping turns that early, unless you're doing something like increasingly heavy multiple-choice throughout the match, without efficent PIF. --Rednaxela 15:02, 3 October 2009 (UTC)

It need to scroll through ~10,000 records each tick =) Even with ABC's PIF method, my (buggy) PM got skipping turn too. With normal PIF (sin & cos), it start at around round 24 or so. --Nat Pavasant 15:06, 3 October 2009 (UTC)
Against PatternBot rounds are about 1200 ticks, 70 rounds is a 84000 log size. I have ABC's fast play it forward but I do have heavy multiple choice and weighting. I think it can further optimized, but I actually only care about normal 35 round battles. So I won't tackle many optimizations yet. And is not like a skip forever, but some rounds it skips about 5 turns at the beginning, when PatternBot is positioning itself because that part is a really simplistic pattern so many many matches are found. Besides my clustering is based on Voidious' brute force method, I could try a heap like algorithm later, as Nat did. --zyx 15:31, 3 October 2009 (UTC)

Nat, remember you have to traverse the list in reverse order as they appear in the log. Try changing `entries.add(entry);` for `entries.add(0, entry);` in the `addNewEntry`. That should give better results, but not fix the across rounds matches. You have a static PMSequence? Then try reseting `last` to null at the beginning of each round. Although I haven't checked if mine matches across rounds, but I'm quite doubtful it does. --zyx 15:31, 3 October 2009 (UTC)