[Home]Marshmallow/PatternMatcher

Robo Home | Marshmallow | Changes | Preferences | AllPages

This is the heart of Marhsmallows MogBot style PatternMatching. It's not a very effective pattern matcher but can be used instead of LinearTargeting and CircularTargeting and also hits Calliope style Oscillators pretty well. Use it like so:

For historic (and stupid, Java newbie, etcetera) reasons the Tracker class is an inner class of Marshmallow's Enemy class. I think it's fairly simple to use it as a stand-alone class. It should only be to make record() accept the arguments that it should pass on in it's call to movie.add(). Also you'll need to replace the "MC_..." constants with constants of your own. Current values are:

        static final int MC_RECORDING_SIZE = 400;
        static final int MC_MATCH_PERIOD_LENGTH = 7;
        static final double MC_MATCH_DIFFERENCE_THRESHOLD = 0.01;

I think you might consider using a SymbolicPatternMatcher (NanoLauLectrik style) instead of this one since those matchers can handle much larger "recordings" and "period lengths". Just promise to make your SymbolicPatternMatcher compatible with JDK 1.3.1, I'm so fed up with all these bots I can't run on my machine. =)

The code (I really don't recommend using it for anything else than get a general idea about pattern matching MogBot style).:
    class Tracker {
        private ArrayList movie = new ArrayList();
        private boolean movieIsFull = false;
        private int movieSize = 0;
        private double lowestDifference = 99999.0;
        private int recordingSize = MC_RECORDING_SIZE;
        private double differenceThreshold = MC_MATCH_DIFFERENCE_THRESHOLD;
        private Point2D newLocation = new Point2D.Double();
        private Point2D deltaLocation = new Point2D.Double();
        private int uses;
        private long totalIndex;
        private double totalLowestDifference;
        private int periodLenght = MC_MATCH_PERIOD_LENGTH;

        void record() {
            movie.add(new Frame(headingDelta, velocity, time, bearingDeltaAverage, velocityDeltaAverage, timeDelta));
            if (movieIsFull) {
                movie.remove(0);
            }
            else {
                movieSize++;
                movieIsFull = movieSize > recordingSize;
            }
        }

        Point2D guessedLocation() {
            return nextLocation(similarPeriodEndIndex());
        }

        Point2D nextLocation(int start) {
            newLocation.setLocation(location);
            if (movieSize > recordingSize - periodLenght - 90) {
                double momentHeading = heading;
                Frame first = (Frame)movie.get(start);
                for (int i = start; i < movieSize; i++) {
                    Frame frame = (Frame)movie.get(i);
                    momentHeading += frame.headingDelta;
                    deltaLocation.setLocation(Rutils.sin(momentHeading) * frame.velocity * frame.timeDelta,
                        Rutils.cos(momentHeading) * frame.velocity * frame.timeDelta);
                    Rutils.pointTranslate(newLocation, deltaLocation);

                    rBulletTravelTime = Rutils.travelTime(robotLocation.distance(newLocation), rBulletVelocity);
                    if (frame.time - first.time >= rBulletTravelTime) {
                        break;
                    }
                }
            }
            return newLocation;
        }

        private int similarPeriodEndIndex() {
            lowestDifference = 99999.0;
            int index = 0;
            if (movieSize > recordingSize / 3) {
                int i, j;
                Frame recent = null;
                Frame old = null;
                for (i = 0; i < movieSize - 1 - periodLenght - 90; i++) {
                    double difference = 0.0;
                    for (j = 0; j < periodLenght; j++) {
                        recent = (Frame)movie.get(movieSize - 1 - periodLenght + j);
                        old = (Frame)movie.get(i + j);
                        difference += recent.differenceVH(old);
                    }
                    if (difference < lowestDifference) {
                        lowestDifference = difference;
                        index = i + j;
                    }
                    if (lowestDifference < differenceThreshold) {
                        break;
                    }
                }
                uses++;
                totalLowestDifference += lowestDifference;
                totalIndex += index;
            }
            return index + 1;
        }

        void printStats() {
            if (uses > 0) {
                System.out.println("  PM mean difference: " + totalLowestDifference / uses);
                System.out.println("  PM mean index: " + totalIndex / uses);
            }
        }

        class Frame {
            private double headingDelta;
            private double velocity;
            private long time;
            private long timeDelta;
            private double bearingDelta;
            private double velocityDelta;

            public Frame(double headingDelta, double velocity, long time,
                         double bearingDelta, double velocityDelta, long timeDelta) {
                this.headingDelta = headingDelta;
                this.velocity = velocity;
                this.time = time;
                this.bearingDelta = bearingDelta;
                this.velocityDelta = velocityDelta;
                this.timeDelta = timeDelta;
            }

            double differenceVH(Frame frame) {
                return Math.abs(this.headingDelta / this.timeDelta - frame.headingDelta / frame.timeDelta) +
                    Math.abs(this.velocity - frame.velocity);
            }

            double differenceBDVD(Frame frame) {
                double diff = Math.abs((this.bearingDelta * this.velocityDelta / this.timeDelta) -
                    (frame.bearingDelta * frame.velocityDelta / frame.timeDelta));
                return diff;
            }

            double differenceBD(Frame frame) {
                double diff = Math.abs(this.bearingDelta / this.timeDelta - frame.bearingDelta / frame.timeDelta );
                return diff;
            }
        }
    }

What's going on? You wonder. Well, it's MogBot style, remember? Recall that Dave Mold, author of MogBot, says this:

  1. Churn through the list of data, and find a stretch of 7 game turns that most closely resemble the opponent's behaviour in the last 7 turns.
  2. Iteratively predict the position of the bot by adding the heading change vectors and the velocities for the length of time the bullet will take to reach the bot to the bot's current position.

For this the Tracker uses a "movie" (an ArrayList of Frame objects) which it can play forwards to do the first step (similarPeriodEndIndex()) and then play forwards again to do the second step (nextLocation()) The Frame class is responsible for calculating the actual difference between two adjacent frames. It has three difference functions just because I have been experimenting with different input for the actual matching. I have concluded that it doesn't matter much and am currently back at matching on velocity and heading change. These two imformations are also what's used for iterating the enemy bots position forward from the matching point in the movie.

Again you need to implement some /RobotUtilsCode functions to use the above code. Sorry if it's a bit strange and ugly, it is about the first Java code I wrote in my life... Use the code as you like, just to get the idea about how MogBot style PatternMatching can be implemented or grab the code as is and tweak it from there. If you do the latter I again ask you to give me credit since this took me a while to get working. -- PEZ


Questions? Comments?

Robo Home | Marshmallow | Changes | Preferences | AllPages
Edit text of this page | View other revisions
Last edited June 20, 2003 9:19 EST by PEZ (diff)
Search: