DrussGT/Understanding DrussGT

Understanding DrussGT (2.9.0)

This is an attempt to explain the internal mechanics of DrussGT. As far as possible, no references to actual code will be made. Instead, I will attempt to explain everything in terms of concepts and ideas, so that this turns into a learning exercise instead of one of copy-pasting code. The following expects some understanding of Visit Count Stats , KNN , Guess Factors, Wave Surfing and Robocode/Game Physics, so if you aren't up to scratch with those, this might be a bit confusing.

Movement

No-Wave fallback movement

The fallback movement system is what happens when there are no detected waves in the air. It is used primarily at the beginning of rounds before bullets have been fired, in close range combat when the bullet flight time is lower than the gun cooling time, and sometimes at the end of a battle when an enemy is low on energy and stops firing.

This movement is similar to classic Wall Smoothing Random Movement implementations such as Raiko, although without the decisions to reverse. Rather, both movement directions are tested, and the one which, when smoothed, takes DrussGT further from the enemy is chosen. The distancing angles are carefully tuned against GrubbmThree to make the best escape against RamBot-style aggressive movements.

Surfing

This is the main movement system, which is employed whenever a wave is available, which is most of the time against most bots.

Data Generation

Firstly, data about DrussGT's movements is stored into ArrayLists so that it will be available for future reference. This includes location, lateral velocity, heading, lateral direction, advancing velocity and angle from enemy. This data will be used later for determining attributes that the stats system will use to build a danger profile for fired waves.

Enemy Gunheat Tracking

When the enemy is detected as having fired, a variable which represents their gunheat is increased. The rest of the time, this variable is continually decreased by gun cooling rate. Only once this value is zero does the movement consider enemy energy drops as possible wave firing events. This helps prevent spurious waves from being fired due to wall hits which cause energy drops.

Gunheat Waves

Due to Robocode physics, all of the data which is used by the enemy to decide where to fire is available two ticks before it is possible to detect their energy drop from firing. As such, if you can predict what bullet power they fire at, it is possible to start surfing the wave before detecting it. This can help close-range fighting, because those extra two ticks can give crucial extra reaction time which can mean the difference between dodging a bullet and being hit.

Wave Tracking

Every tick, all active waves are inspected to see if they have passed the robot location. If there is no chance that the wave could still cause a bullet hit, it is removed.

Stats System

This is one of the very unique features of DrussGT. The stats system originated as a standard VCS system with a single buffer, similar to Komarious, and slowly evolved into the highly complex system it is today. Two desired characteristics were behind the development: adaptive yet accurate prediction of enemy targeting, and being able to do so quickly.

Accuracy

In order to achieve the accuracy required to unlock the potential of a high-end surfer, over 100 buffers were created in parallel, each of which has a randomly generated set of slices for its attributes. In addition, another 50 buffers are used for the regular flattener, and 20 for the tick-flattener. In order to ensure that as many possible situations are covered, each buffer is limited to only having 5 used attributes per buffer. In addition, several hand-tuned buffers with less attributes are added to ensure that some data will always be available. In order to get accurate Guess Factors, a high number of bins (171) are used. Low rolling averages are used (0.5 – 1.5) in order to keep the stats system highly adaptable to changes in the enemy targeting.

The following attributes are used for the random selection:

• Lateral Velocity
• Advancing Velocity
• Bullet Flight Time
• Time Since Direction Change
• Time Since Deceleration
• Acceleration
• Lateral Distance Last 10 Ticks, ie. abs(Sum of lateral velocity for last 10 ticks)
• Forward Wall Distance
• Reverse Wall Distance

Execution Speed

Obviously, to deal with so many buffers, each with its own set of attributes, and such a large number of bins, requires a great deal of running time. In fact, with a naive brute-force implementation, this system will be too slow and consume too much memory to run with the rest of the robot. Three main optimisations were implemented to overcome this problem:

1. Stats Retrieval Indexes: instead of keeping a set of slices for each buffer, which would then require a slice calculation for every single slice in every single buffer every time a new wave was created, an index of retrieval data was created. This entails keeping an index of which slices each buffer corresponds to. Then, when the wave needs to be created, every slice value for each attribute is calculated and placed into an array. From this, the results of each corresponding attribute can be simply looked up by each buffer, instead of having to be calculated by scratch.
2. Lazy Initialisation: Because there are many areas of the space which will never be accessed, it doesn't make sense to allocate memory for all of the possible areas that could ever be written. For instance, if DrussGT is decelerating, then immediately we know that the velocity is less than 8 and the time-since-decel is 0, so there is no point in initialising those areas. By only allocating buffers as they are accessed the amount of memory is cut drastically.
3. The final, and probably most important, optimisation was the move away from keeping a set of bins, where the hit was smoothed with a profile in the set, in every buffer for every situation. Clearly, with such a low rolling average, this is a highly inefficient way of storing where the last 2 – 3 hits were, as any hits before that are below the threshold of any influence. Instead, I now keep a circular buffer of the bin indexes of the last 2*rollingAverage + 1 hits which occurred in the buffer. At wave creation time I then take the bin indexes and increase the corresponding bin in my surfing buffer with decreasing weight the further back in the queue, folling the same decay rate as the rolling average would have given. Once this has run for all buffers I smooth all non-zero bins into a final buffer which is then surfed. This is substantially faster than simple bins because each buffer only needs a few writes to the main bins, and often multiple buffers will all increment the same pre-smoothed bin, reducing the number of bins which need to be smoothed.

Flattener

DrussGT has a standard flattener, where as each wave passes over it logs into the stat buffers, regardless of whether or not there was an enemy hit. In addition, it has two other flatteners: the 'tick-flattener', so called because a wave for it is generated every single tick, regardless of if the enemy is even firing, and the anti-bullet-shadow flattener, which adds danger to any points on the wave which are more likely to contain a bullet based on the premise that the enemy is using bullet-shadows and made sure they were in a shadow as my wave passed over them. Because bullet shadows are an interaction of movement and targeting, this is an attempt to learn the enemy targeting better through analysis of any artifacts is displays in their movement.

The flattener buffers are entirely disabled (not even logging data) until the enemy hitrate passes a weighted threshold of 9%. At this point all of them are enabled, and weighted equally with the regular dodging buffer.

Bullet Shadows

DrussGT has a standard by-the-book Bullet Shadows implementation. The fact that it uses bins instead of a continuous danger profile probably makes this implementation easier than it would have been otherwise. When the gun fires a bullet, it passes a reference of the bullet object back to the movement. The movement then plays this bullet forward through all of the enemy waves and identifies which regions of which waves would hit the bullet. Similarly, every time a wave is added all bullets are played forward to see where they will create 'shadows' on the wave. It is then assumed that these 'shadow' regions are entirely safe, because if they contain a bullet it will be taken out by bullet intersection before the enemy bullet can hit me. It uses a tick-by-tick play-it-forward method to determine when and where the intersections occur.

Surfing Algorithm

DrussGT uses go-to surfing, which is very similar to Minimum Risk Movement. While minimum risk movement simply generates goto points and evaluates them, then goes to the one with the lowest danger, DrussGT adds an additional step: seeing how dangerous travelling to that point is, rather than simply the danger of the point itself. As such, there are three steps to the actual surfing algorithm:

1. Point generation – creating a bunch of points which are likely to be good places to evaluate
2. Calculating the wave-hit locations – figure out where the wave will cross me if I attempt to go to each point
3. Danger evaluation – given the wave hit locations, how dangerous does the stats system say this location is, plus some heuristics like distance-to-enemy and wave weighting.

Point Generation

Because the amount of time to run the surfing algorithm increases quadratically (for 2 wave surfing) as the number of points increase, it is important to reduce the number of points to the bare minimum. As such, the generated points must meet the following criteria:

• Be reachable from the current location
• Have correct distancing
• Cover a wide range of GF values
• Preferably be generated in an order so that all points closer than point K can be declared 'reachable' and don't need to have the wave hit location calculated (the slow part of the algorithm).

Because of these criteria, I decided to use a precise-prediction from my current location. Because it was already available, I used the precise prediction from Apollon. I then added a filter which removed points if another point closer than 7 pixels already existed. By controlling the precise prediction I can cover all reachable GF values, without attempting to generate points which were completely unreachable; it is also easy to control distancing, and the 'order' criteria above is also met.

Wave-hit Locations

This is the most critical part of the surfing mechanics, and the easiest to make mistakes in. Basically, given a starting {location,velocity,heading} and an end destination as well as a wave, calculate at what point along the robot's path the wave hits the robot, and, if they contained a bullet, what angles of the wave would hit the robot. I used to have a fancy linear predictor using the cos rule which ran blazingly fast, but eventually I broke down and went with a Cartesian implementation because I can integrate precise intersection this way. It just simulates a standard goto call being called every tick for the same end point, with the robot turning and moving and the wave steadily advancing until there is an intersection. I have two methods for this, one which implements the precise intersection math and is used for the first wave, and the second which just gives an intersection point, running much faster as a result, and is used for the second wave.

Danger Evaluation

Once I know which section of the wave will hit for each given movement option, I can evaluate how dangerous the option is. I sum the bins which correspond to the hit angles, then divide by number of bins and multiply by angle width to get rid of any aliasing effects. I also scale the danger based of the damage the wave would cause and the energy differential it would create, the amount of time the wave has to hit me, and how close the enemy is to the wave-hit location.

Second Wave Speed Optimisations

In order to speed up the second wave surfing, I devised an algorithm which would allow me to not calculate the second wave dangers in a large portion of the movement options, decreasing runtime significantly. This is done by first calculating all first wave dangers, then sorting them so that they would be processed from least dangerous to most. Then, a minimum total danger comprising sum of first and second wave danger can be kept and the moment the danger of the first wave in the list exceeds this minimum total danger, we can safely ignore the rest of the list because they also have a danger greater than the minimum.

Goto Function Behaviour Tweaks

Because I only need to get to the destination by a certain time, there are certain occasions where I might have extra time to get to the destination. In these cases I test whether accelerating or decelerating will prevent me from reaching the destination on time, and if it doesn't prevent me from reaching the destination I will do one of these options.

Also, with a go-to function, at very short distances the bearing-to-destination calculation becomes undefined. As such, if the destination is less than 1 pixel away I don't try to turn.