Difference between revisions of "Wave Surfing"

From Robowiki
Jump to navigation Jump to search
(Added a note on game theory)
Line 13: Line 13:
 
* Try to move to the safest reachable spot on each wave.
 
* Try to move to the safest reachable spot on each wave.
  
== Strategy ==
+
== Game Theory Perspective ==
  
 
[[Image:PayoffMatrix.jpg|right]]
 
[[Image:PayoffMatrix.jpg|right]]
  
Wave surfing employs ideas from game theory in order to dodge bullets most effective. Consider for example, that one could determine the number of bins that the opponent is using at the time of firing. Based on that knowledge one could construct a payoff matrix in order to evaluate the best plan of action and determine the best response.
+
Ideas from game theory have a clear niche when it comes to wave surfing. Consider for example, if one could determine the number of bins that the opponent is using at the time of firing. Based on that knowledge one could construct a payoff matrix in order to evaluate the best plan of action and consistently determine the best response.
  
For example, consider the payoff matrix at right. Assume that the target is at such a distance such that the shooter can fire in three unique locations that would hit all points that the target can move to. Then both players must choose from one of three strategies. The target can choose to move left, stay center, or move right. The shooter can choose to first in the left bin, the center bin, or the right bin. If both the shooter and the target choose the same strategy, the target is hit; else, the shooter misses and loses some energy.
+
For example, consider the payoff matrix at right. Assume that the target is at such a distance such that the shooter can fire in three unique locations that would hit the target regardless of where the target moves within the maximum escape angle. Then both players must choose from one of three strategies. The target can choose to move left, stay center, or move right. The shooter can choose to fire into the left bin, the center bin, or the right bin. If both the shooter and the target choose the same strategy, the target is hit; else, the shooter misses and loses some energy.
  
The question becomes, what is the optimal strategy? Clearly, if the target or shooter choose a pure strategy, that is, always playing the same strategy, then the best the opponent has two unique best responses that will eventually lead to a win. Therefore, the optimal strategy will be a mixed strategy, playing each a certain percentage of the time.
+
The question becomes, what is the optimal strategy? Clearly, if the target or shooter chooses a pure strategy, that is, always playing the same strategy, then the opponent has two unique best responses that will eventually lead to a win. Therefore, the optimal strategy is not to adopt a pure strategy, and instead opt for a mixed strategy- playing each of the strategies a certain percentage of the time.
  
In this case, since each strategy is effectively identical, it's clear that there exists only one Nash equilibrium at {(1/3, 1/3, 1/3), (1/3, 1/3, 1/3)}. (A Nash equilibrium is when both players choose a strategy such that neither would benefit by switching to a different strategy.)  
+
In this case, since each strategy is effectively identical, it's clear that there exists only one Nash equilibrium at {(1/3, 1/3, 1/3), (1/3, 1/3, 1/3)}. (A Nash equilibrium is when both players choose a strategy such that neither would benefit by switching to a different strategy.)
  
 
== Styles of surfing ==
 
== Styles of surfing ==

Revision as of 06:00, 25 March 2011

Youtube
Youtube has a video of Wave Surfing in action: click here to watch

A form of precise bullet dodging movement used primarily in 1v1. A Wave is a mechanic used to represent all possible locations of a bullet. Through observation of waves and bullets, one can try to project the relative dangers of each area of a wave in the air -- i.e., the likelihood that the enemy fired at various angles. (Note that Robocode bots cannot see bullets in the air.)

History

ABC was the first to implement true Wave Surfing in a Robocode bot when he added it to Shadow in mid-2004. As of April, 2010, the top 40 duelists in the RoboRumble use a form of Wave Surfing.

How it works

  • Detect an energy drop to know that a bullet was fired. Create a matching Wave.
  • Gather data from onHitByBullet or onBulletHitBullet, always matching to the correct Wave, to learn what firing angles the enemy gun uses in different situations.
  • For the nearest bullet(s) in the air, use precise prediction to deduce the areas of the wave(s) your bot could reach.
  • Try to move to the safest reachable spot on each wave.

Game Theory Perspective

PayoffMatrix.jpg

Ideas from game theory have a clear niche when it comes to wave surfing. Consider for example, if one could determine the number of bins that the opponent is using at the time of firing. Based on that knowledge one could construct a payoff matrix in order to evaluate the best plan of action and consistently determine the best response.

For example, consider the payoff matrix at right. Assume that the target is at such a distance such that the shooter can fire in three unique locations that would hit the target regardless of where the target moves within the maximum escape angle. Then both players must choose from one of three strategies. The target can choose to move left, stay center, or move right. The shooter can choose to fire into the left bin, the center bin, or the right bin. If both the shooter and the target choose the same strategy, the target is hit; else, the shooter misses and loses some energy.

The question becomes, what is the optimal strategy? Clearly, if the target or shooter chooses a pure strategy, that is, always playing the same strategy, then the opponent has two unique best responses that will eventually lead to a win. Therefore, the optimal strategy is not to adopt a pure strategy, and instead opt for a mixed strategy- playing each of the strategies a certain percentage of the time.

In this case, since each strategy is effectively identical, it's clear that there exists only one Nash equilibrium at {(1/3, 1/3, 1/3), (1/3, 1/3, 1/3)}. (A Nash equilibrium is when both players choose a strategy such that neither would benefit by switching to a different strategy.)

Styles of surfing

  • True Surfing - Decide each tick whether to move forward, backward, or stop. Used by the great majority of Wave Surfers and the Wave Surfing Tutorial.
  • GoTo Surfing - Calculate the safest spot on the nearest wave(s) and move there directly.
  • Melee Surfing - While many have tried their hands at Wave Surfing in Melee, there hasn't been huge success. For now, check out the talk page.

See also