ChaoticMovement

A movement system trying to take advantage of the fact that chaos is pretty unpredictable. I was a bit fed up with all talk about random and tried to figure out an unpredictable movement not involving random. To get chatotic movement into your bot you can:

• Use a model of a chaotic system simple enough so that it can be implemented in a robot.
• Set this system in motion and use it for fetching chaotic numbers.

Well known chaotic systems are:

• Wheather
• Double (triple, n-iple) pendulums
• Various driven pendulums
• Lorentz Equation
• ...

For obvious reasons you can hardly use a wheather system. It's too big and the CPU power used by wheather institutions are a bit far from what you can get from a JVM running on a PC. Also for obvious reasons a pendulum is a quite good choice. Firstly it's a small system. Secondly it's very similar to most movements seen in Robocode. For Mako 1.3 I used a double pendulum because those have been fascinating me since I was a kid. It also was pretty easy to ask the pendulum for it's current angular position and just steer my bot there. An interesting effect of using an "angle generator" like this is that you don't need to check if the bot has finished it's movement before giving it a new movement order. In Mako 1.3 I gave movement orders in every tick. This shows in a smooth movement in the bot quite different from all my other straigh-line movements.

Before you go ahead implement this movement remember that it's not very effective. Chaos might be unpredictable in the longer term but in the short run it can be very predictable. This made Mako 1.3 lose out big against good pattern matchers. When I realised this I immediately trashed this movement and replaced it with a boring RandomMovement.

-- PEZ

---

As you said pattern matchers are effective against this movement (and NN - at least the one featured by ScruchiPu also should be effective); just because pattern matching is a time-series prediction technique used to predict complex non-linear systems (which include chaotic systems). -- Albert

Yes, indeed. OrcaM, which doesn't perform all that well against most bots, totally trashed this movement. I actually knew all the time this short-term predictability of chaotic systems. Or had known or whatever, because I totally forgot when I got carried away in implementing it. Then it came back to me as a dissapointing reminder. =) Anyway, it was fun and interesting to explore the path. And, as I state above, the design pattern with an AngleGenerator, was also interesting and probably useful as well. -- PEZ

One thing that could be interesting is a bot that follows Mandelbrot set iterations or oscillates in brownian motion. (Just some random things I've thought of... the first would be better for melee, the second for one-on-one, seemingly). -- Kawigi

I experimented with Brownian and some others cupple of week a go, but it was not sucessul agaist guess/ targeting. The problem is the firing needs 3,4 turns which is enough to learn or guess. Those chaotic behaviors are quite predicable as PEZ said in the short run. -- SSO?

As Albert said, patterm maching is a time-series prediction technique, so it could be used against the chaotic system. Actually time-series prediction can be used against random movement too , because the random numbers generated by computer, you see, are not actually random and can be analysed. -- deadbeef?

I've seen this sort of statement many times in various robocode forums - however I believe the random number generation within java is effectivly random. For those that beleve there is a measurable predeictability to the random number generator they should provide a predicted pattern/distribution for sets of say 1 million random numbers sequentially extracted out of java which deviates from an theoretical true random number distribution. Once upon a time - in the days of hand calculations and tables of random numbers I believe an effort was made to have the random numbers evenly distributed over fairly short sequences - however, come the computer and the possiblility to perform many thousands of calculations an even distribution can be assured by making enough calculations. -- Paul

While I don't know how good Java's PRNG is, this paper makes me wonder about the strength of any given computer PRNG: [Strange Attractors and TCP/IP Sequence Number Analysis] -- Paul Ingemi

What's the relevance of that when it comes to Robocode. Even if the enemy bot woulde give away it's initial seed for free it would be very hard to do anything interesting with it. You'll have to know exactly how many calls to random() it has done at any given tick. Most of my bots are completely littered with calls to random(). I'd say that the standard Math.random() gives random enough numbers for the purpose of moving unpredictably. Anyone who has a different opinion will have to prove me wrong by making a bot that shows it. -- PEZ

I agree, and I disagree. It's not relevant to robocode because the attacks in that paper would give very little advantage to any robot, which is far outweighed by other factors in the robot's programming. Now I disagree that a robot would have to know how random is used or how often it's called. If your math and logic is working with a biased distribution, then your output will be biased and can be analyzed, perhaps with the techniques outlined in the above paper. -- Paul Ingemi

To get the seed value requires knowing to the millisecond when the other robot is initialized. Since your thread is asleep at that time you're kind of screwed from the get-go. Further, those attacks require knowing what the actual output set is, not merely some unknown function of it. Plus they're talking about railing dozens to thousands of trials in parallel, that doesn't translate to robocode terribly well no matter how you put it. -- Kuuran

I agree, Math.random() is good enough for anything we would want to do. Put simply: Java cannot predict Java's random numbers. It's people that try to actively get an even distribution that confuse me. If you do that, it stops being random, and becomes fairly easy to predict (not exact values, but the probability of it being in a certain range becomes higher than the rest). The whole point of random numbers is that anything could happen. You could get 0.452 a hundred times in a row. It's unlikely, but it could happen. With an actively evened algo it is impossible (or at least, much less likely, depending on how active you are, eg. weighting as opposed to selecting). -- Tango

We agree you and I? Wow! =) Math.random() gives a pretty even distribution. If you want a normal distribution you can use the nextGaussian() method of a Random instance. -- PEZ

Actually uniform distributions guarantee strong randomness and in a perfectly uniform distribution you can't know anything about the next number, so it hardly makes it predictably. The only thing you can predict is that it'll be one of the possible numbers with even probability of each, that's not really helpful in knowing what comes next. Java's PRNG actually goes to great lengths to assure it's distribution when a non-even distribution is specified as well.

Here are a few clickys: [Java PRNG As A Metric], [PRNG Tester With Explanation] and finally [Java API Description of the Random Class].

For those of you who don't feel like clicking here is the most important bit of the API Description:

 public double nextDouble() {
       return (((long)next(26) << 27) + next(27))
           / (double)(1L << 53);
 }

where next is :

 synchronized protected int next(int bits) {
       seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
       return (int)(seed >>> (48 - bits));
 }

and the seed defaults to the time in milliseconds at start of execution (creation of the Random class, which is done by the Math class at start of execution for Math.random()). -- Kuuran

If the distribution is being actively evened, it is predicatable. It's as simple as that. Let's give an example. I am picking numbers at random from 1 to 9, and get these:

1 6 3 5 6 7 3 2 6 3 6 3 7 4 7 1 3 7 3 5 6 2 3 6 2 3 6 3 4 6 3 6 4

Totals:

1s - 1 2s - 3 3s - 10 4s - 3 5s - 2 6s - 9 7s - 4 8s - 0 9s - 0

If this were intended to be an even distibution, it is not very good. There are more low numbers than high numbers. If the algorithm were to try to even that, it would have to weight high numbers more heavily than lower numbers. If i were trying to guess the next number, I would be more likely to be right if I chose 9 than if i chose 3. Therefore it is predicatable.

If the numbers were truely random, there would always be a 1/9 chance of each number coming up regardless of the previous numbers.

-- Tango

Yeah, but if there is an even chance of all the numbers coming up your distribution is uniform. Further, guessing based on past behaviour a targeter would guess 3 and 6 and be less likely to be correct, that's the point of flattening a profile. Ensuring distribution hardly makes things predictable, it simply ensures you aren't getting screwed. -- Kuuran

There is no point in questioning the java random numbers generator. We are robocoding, not enchrypting :-) The real problem is that even using random numbers for your movement you will never get it random, because the physics of Robocode (ie. walls and acceleration) will impose some restrictions to your movement. You can take a look into the NeuralTargeting page and you will see that even SandboxDT movement doesn't look random at all, and there are some patterns on it. Thats why pattern-matchers work against RandomMovement. -- Albert

I'm not going to disagree with you, first because I agree with you and second because you're completely right ;) There are confines within robocode which allow us to target at all, and minor discrepencies in randomness aren't really going to be exploitable since targeting and predicting random numbers are quite unrelated (I was getting at that in my response to Paul). I think the discussion has become academic since then, and is a point in itself ;) -- Kuuran

It's funny that this discussion takes place on a page for a movement i specifically designed to be NOT random. =) -- PEZ

If you flip a coin 99 times and it comes up 'heads' every time, what are the odds it will be 'heads' on the next flip? 1/2.
Making a number generator that forces an even distribution means that each successive number is less likely to be a previous one, and that's more predictible than not doing it, so what's the point? I can see if you were anticipating pattern matching against yourself and wanted to prevent a match, but that's got little to do with the distribution of your number pool.
By the way, I watched this for a while and it looks cool, but definitely target-able. -- Martin Alan Pedersen