Talk:Sequential Prediction

<math>Insert formula here</math>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)

I thought so at first, too (and almost changed it), but now I think it's fine like it is. This page is really describing an algorithm more than a specific gun's implementation of it, and others like Symbolic Pattern Matching are under targeting strategies, even though they're implementations of PM. --Voidious 16:53, 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(n²). 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 {
		double heading;
		PMEntry next, previous;
		String key;
		int matchSize = 0;
		int round;

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

	private class PMSequence {
		private HashMap<String, LinkedList<PMEntry>> dataMap;
		private PMEntry last = null;

		public PMSequence() {
			dataMap = new HashMap<String, LinkedList<PMEntry>>();
		}

		private LinkedList<PMEntry> getEntries(String key) {
			LinkedList<PMEntry> entry = dataMap.get(key);
			if (entry == null) {
				dataMap.put(key, entry = new LinkedList<PMEntry>());
			}
			return entry;
		}

		public void addNewEntry(PMEntry entry) {
			LinkedList<PMEntry> entries = getEntries(entry.key);
			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;
			entries.add(entry);
			last = entry;
		}

		public PMEntry[] getEntries(PMEntry entry) {
			LinkedList<PMEntry> entries = getEntries(entry.key);
			ResultHeap rh = new ResultHeap(entries.size());
			for (int i = entries.size() - 1; i >= 0; i--) {
				rh.addValue(entries.get(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;
			}

			public void addValue(PMEntry value) {
				// 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)

Thank you, it works fine now, except that it is awfully slow using HashMap and LinkedList =) Mine start skipping turns at round 20 and skipped turns like hell at round 28. But robot-generated PMC index (I make it collect data and print index every round) tell me that it work. One thing I don't understand, is why is it need to travel in reverse order? --Nat Pavasant 16:06, 3 October 2009 (UTC)

Very cool! Glad to see I'm not the only one in the Targeting Laboratory. =) I need to re-read this page a couple times before I fully grok the code, but I think I get the idea. I think Multiple Choice on the deepest matches is the kind of thing that could really put PM over the edge, and it's much more viable to do that with such a lightning fast PM algorithm. By the way, have you seen the Folded Pattern Matcher (old wiki link)? I believe it's different than what you have here, but it is another very fast PM, so I thought you might want to look for comparison / inspiration. Thanks for posting such an in-depth write-up - good luck with this. --Voidious 16:40, 3 October 2009 (UTC)