View source for Talk:Symbolic Pattern Matching

Credits - Implementation and advantages Old wiki page: SymbolicPatternMatching Original author(s): Albert, PEZ

From old wiki's Symbolic Pattern Matching page

Isn't a possible advantage also that this might lend itself to regular expression searches? -- PEZ

Probably you can, but first you should find a good reason to do it :-) -- Albert

Well, one reason to do it is to "blurify" your search. You could also use it to find the projection pattern if you were projecting future movement with it. I've thought about doing something like this (assume you are looking for a pattern of length 10 or something for a String called 'pattern'):

String toMatch = pattern.substring(pattern.length()-10);
String re = "";
for (int i=0; i<10; i++)
{
	re += "[";
	for (int j=toMatch.charAt(i)-1; j <= toMatch.charAt(i)+1; j++)
		//the \u is to match a unicode number by any 4 digit hex number
		re += "\\u" + padZeros(Integer.toHexString(j), 4);
	re += "]";
}
//don't even pretend to try this part in java 1.3...
Pattern p = Pattern.compile(re);
//don't find a match in the last 30 characters of the pattern
Matcher m = p.matcher(pattern.substring(0, pattern.length()-30));
//while matches are found:
while (m.find())
{
	int index = m.end();
	//An aspid-style pattern matcher would (if I understand correctly) figure out
	//the angle by projecting movement starting at index and store that somewhere.
	//This loop will iterate through all matches of the pattern in the pattern buffer.
}
//now you have all your data, figure out how to fire

.
.
.

//pads the front of the input string with zeros to be of length size
public String padZeros(String str, int size)
{
	while (str.length() < size)
		str = "0" + str;
	return str;
}

Is this a viable idea? -- Kawigi

That's great!!! I haven't understand anything of the code, but I understand the idea. One of the problems Aspid has is that there is a limit on the number of searches it can make. Probably it could increase them by using it. I'w try as soon as possible :-) -- Albert

The problem right now is that it doesn't easily let characters have more than one value hidden in them, of course I guess that can be done still, you just have to know every character that matches a certain number in the string, which if each character has two parts of data, there may be 9, or maybe you only alow deviation in one direction, so there would be 5.

If you've never thought about that much, the way you could store multiple variables in one character is by using a bitmask - I experimented with an angular symbolic pattern matcher (which may not be so bad, I may really get into that some time here...) which put lateral and advancing velocity into one character. Since I knew that these both would be between -8 and 8, I turned them into positive ints from 0 to 64 with something like (v*4+32). Then I designated the first half of the char to be advancing velocity and the second half to be lateral velocity:

char symbol = (latnum)|(advnum<<8);

To get them back later, I just said:

double latv = (symbol&255)/4.0-8;
double advv = (symbol>>8)/4.0-8;

To do fuzzy logic on that, I'd have to figure out each number I would want, if I want to allow a deviation of one in either direction, the construction of the regular expression would be like this:

for (int i=0; i<10; i++)
{
	re += "[";
	int num1 = (toMatch.charAt(i)&255);
	int num2 = (toMatch.charAt(i)>>8);
	for (int j=num1-1; j <= num1+1; j++)
		for (int k=num2-1; k <= num2+1; k++)
			//the \u is to match a unicode number by any 4 digit hex number
			re += "\\u" + padZeros(Integer.toHexString(j|(k<<8)), 4);
	re += "]"
}

Note that I forgot to add the end bracket originally. I fixed the code above, too. -- Kawigi

You don't need to encode two variables into a single character, just concatenate them into the string. Then, you do your search, and divide the index returned by 2 to get the real "instant". The same logic applies to 3 or more variables. -- Albert

That would work, too, I suppose. The chances of getting an actual match on an odd index would probably be small :-p -- Kawigi

Encoding variables into a single character would make the regex search faster though. -- nano

Well, except that it would triple the length of the regex (if done like above). The nice thing, though, is that it's not a looping-sort of regex, just more options for each character. And the regex wouldn't be quite as long if you chose to only allow deviation in one variable (i.e. - allow either variable 1 to be off by one, or variable 2, but not both). Then you have 5 possibilities for each character instead of 9 like I did in the example. I would also be wary that using two characters *and* using the regex search also makes you more likely to get an incorrect match (i.e.- an odd index). -- Kawigi

Just wondering, if you want to use two variables, can't you just load them up into a byte Array and turn that into a string? No point using a whole character variable if you are just going to use scan one at a time anyway. --DragonTamer

DragonTamer, yes, you can. In Java, a character variable is just two bytes. In the above code, Kawigi encodes two bytes into one character, and then concatenates it onto the end of a string. Instead of using the binary operators to encode the character, he could have made a byte array of length 2 and converted it into a String, however, that would be slower. -- nano

Just to share, what I did in my pattern matchers was to multiply the value by a fixed 'scale factor' when storing it, and divided by this when retrieving the value. This is a very lightweight method of achieving high accuracy, with a preset (and tunable) amount of 'distance' between the match and the record. --Skilgannon

Hi, what are some easy ways to improve the standard nano-sized pattern matcher? I've tried everything (that I can think of!) but each change just seems to make the gun worse. Thanks!

Think this way: if there are easy ways to improve, it should be already within every nano-sized pattern matcher.

And, most changes are making things worse simply means you may be already at some local minimum, which is discovered by the predecessors. The "improvements" you easily think of may be already tried by predecessors as well, and the ones that work are already applied.

So, to push the bar further, just go the "hard" way. Record some data of every opponent you need to face, encode some behavior of your gun into genes, and use genetic algorithms to find a way out!

Ah, I was hoping there were some simple ways that took a bit more codesize. Since the nano-sized pattern matcher I am using is not in a NanoBot, I can afford better performance for more code. I have quite a few bytes to spare in Basilite and I was hoping for changes that were easy to put in and gave small gains, like energy management for example.

Then don't look at pattern matchers in nanobots, look at those in microbots, minibots and even megabots. And energy management is mostly independent of gun type I think, as long as they are learning. So learn from gf targeting bots' energy management as well.

OK. I'll check it out ;)

Awesome! I'll try one of those later =)