Randomized surfing

Fragment of a discussion from Talk:Phantom
Jump to navigation Jump to search

Why would being one tick late stop you from perfectly predicting their movement?

Voidious (talk)18:09, 11 November 2013

Skipping a turn or being a tick late may make a difference, since an enemy can move up to 8 pixels in that missed tick. Now I'm not so sure of this, but missing that tick could make your bot's recorded(saved) stats off of the actual ones. But again, it's only 8 pixels so it won't be off that much. The stats would be near-perfect, but not absolutely. Again, I'm pretty new to robocode so I'm not so sure.

Also, I may never release Phantom. The movement sounds a lot more complex than I thought. I'm no expert at robocode(meaning I don't have bots like DrussGT, Diamond, Combat, Nene, RougeDC, etc.).

BeastBots101 (talk)23:02, 11 November 2013

If you make a specialist anti-surfer gun, you could PIT many ticks ahead and still hit with near 100% accuracy.

My theory about why random movements performs poorer than deterministic movements is because no one in the rumble is attempting to exploit the determinism.

Game theory model (already posted somewhere in the wiki):

Suppose there were only 3 GFs to shoot at, forward, center and backward. Suppose there were only 3 GFs to dodge to, forward, center and backward.

If both shooter and dodger choose the same GF, it is a hit and the shooter wins, otherwise it is a miss and the dodger wins. If you shoot at the GF with highest occurrences, which is what all statistical guns do, then the best response for the dodger is to move where there are the least occurrences, which is what all active flatteners do.

Suppose the flattener moves in a pattern like this: forward, backward, center, forward, backward, center... GF guns with data decay will shoot anywhere the 1st time, then forward the 2nd time, backward, center, forward, backward, center, and always miss.

If the flatteners instead used a random strategy and moved forward, backward and center each with 1/3 probability, then the shooter would have 33% hit rate, which is higher than always missing against deterministic movements. In this scenario random movement looks weaker than deterministic movement.

But, if, instead of using past data, the shooter hard-coded the pattern and shoot forward the 1st time, then backward the 2nd time, center, forward... it would always hit. Deterministic movements would give 100% hit rate while random movements would give 33% hit rate. In this more evolved scenario, random movement is stronger than deterministic movement.

The hard-coding counter strategy can also the used by the dodger, which hard-codes the shooter pattern and instead move backward 1st time, forward 2nd time, center 3rd time... and the hard-coded shooter will always miss, again.

This hard-coding of opponents patterns creates a cycle which is only broken if both shooter and dodger instead opt for random strategies. Random movement and random targeting. In this simple game it is 1/3 chance for shooting at each GF and 1/3 chance of dodging at each GF. This way, even if you reverse engineer the opponent, there is no room for improvement.

Rocobode is more complex than the 3 GFs shooter/dodger game, and I guess the most conservative (counter-proof) strategy would be a weighted random movement and weighted random targeting, which takes in account multiple waves and walls.

It is also interesting to note that if you shoot with 1/3 chance at each GF in the simple game, you would achieve only 33% hit rate against SittingDuck. Counter-proof strategies don't exploit opponents weaknesses. And strategies which exploit weaknesses also make themselves vulnerable to exploits.

MN (talk)01:42, 12 November 2013

There's a component you're missing, and that is the limited computational power available. By design, DrussGT doesn't know it's movements far enough beforehand to be able to predict what it will be doing as the currently fired wave hits. Not only that, but anybody attempting to predict DrussGT movements would have to predict many ticks of movements forward *every single tick*, and there isn't enough computational time to do that because just predicting DrussGT for a single tick already takes up a significant amount of the processing quota.

Perhaps for more light-weight bots I could understand how this could happen, but any multi-wave surfer can't be predicted like this because of processing time constraints.

Skilgannon (talk)08:32, 12 November 2013

You don't need to do this every single tick, only about every 15 ticks or so. And can spread the processing over many ticks. I didn't say it would be easy, but possible.

By the way, how does DrussGT calculate danger if it doesn't know where it will be when waves hit?

MN (talk)23:19, 12 November 2013

It knows where it will be, but it re-calculates dangers and precise-predictions every time the enemy moves >10% of enemyDistance. It also predicts enemy movements for use in the danger calculation, so the danger calculation changes based on the enemy movements. So you would have to re-calculate DrussGT's precise predictions in your simulations many times if you moved.

I'm thinking of incorporating a random gun and random movement just to future-proof DrussGT, although there are more fun things to do in the mean time =)

Skilgannon (talk)21:08, 14 November 2013
 
 

@ MN: You could potentially still win with 33%. That hit rate is fairly high against top bots such as DrussGT or Diamond(in my experience). You could still beat sitting duck, since you gain energy every time you hit. And sitting duck does not shoot, so you will still get 100%

BeastBots101 (talk)03:17, 13 November 2013

You will do well against top bots(assuming you have good movement) with a 33% hitrate. You will do well against sitting duck with 33%. But you may not get such a good score against average bots since 33% is okay, the enemy may have a higher hitrate.

BeastBots101 (talk)03:26, 15 November 2013