Tournament Writeup 2023‐09‐11
Oort is a space fleet programming game where you write Rust code to control space fighters/cruisers/missiles/etc in combat with other players. This page contains deep dives into the AIs that competed in a tournament, by their creators.
Tournament results (note that the current simulation may be different than at the time of the tournament)
This time I used a 'unified' radar setup. The radar will always scan in an arc defined by a heading and max angle from that heading. If the max angle is greater than Pi, the scan is like a normal radar, scanning the whole circle. While doing this the radar will keep track of contacts for as long as their seen again within 0.5 seconds and assign them some id. Like in the previous tournament it tries to match radar contacts with the existing known contacts.
Unlike the last time, instead of switching to track mode, the radar has a list of tracked ids. Every tick the radar makes one step through this list and aims the radar beam at the contact with that id. When the iteration is done, one scan tick is performed before the iteration repeats. This way the radar can track many targets and scan for new ones simultaneously. I also experimented a bit more with track quality / confidence, and have since implemented kalman filtering for radar contacts. Kalman filtering is not used in the tournament AI.
Overall, this design worked very well under the right conditions, but there is still a lot of room for improvement with contact matching and using proper filtering to estimate contact position, velocity and acceleration. The missiles used this as well, but I think it would have been better if they used the old track mode instead.
A lot of work was done on missiles. The gist is that missile work with 3 Stages now: Boost, Cruise and Terminal, where the Terminal stage is most similar to the entire missile guidance setup from last time.
During Boost the missile will estimate time to impact (tti) based on closing speed and if tti is negative or larger than 5 seconds, use 5 seconds as tti instead. The it will accelerate towards the estimated position of the target in tti seconds until the boost fuel budget is exhausted or tti is smaller than 1 second.
In the Cruise stage, which is were the missile spends most of the time in long range engagements, the missile will lazily correct its trajectory until terminal phase is reached. It calculates tti and clamps it to a maximum of 5 seconds again to estimate the target position on impact. It also calculates terminal tti, where acceleration towards the target is taken into account. Then it estimates by how much it will miss the target, how much fuel a correction would cost, and how much acceleration would be necessary to correct for the miss within the terminal tti. Only when this acceleration exceeds our maximum acceleration or there isn't enough fuel, does the missile actually do the correction. This lazy mechanism worked quite well to conserve fuel when the target accelerates back and forth during cruise. Once the terminal tti is less than 5 seconds, or there is more fuel than it can use within the terminal tti, the missile enters the terminal phase.
During the terminal phase, tti is calculate with closing speed and available acceleration. An acceleration budget is estimated based on fuel and tti. Then the AI calculate how much sideways acceleration is needed to cancel out any perpendicular velocity within tti. Any 'leftover' acceleration is used to accelerate towards the target. If fuel reaches less than 10, the missile coasts. The missile explodes if it is damaged, the tti is less than TICK_LENGTH or the missile is within the explode distance. This distance varies, I believe 25 for missiles and 250 for fighters. Against fighters, ShapedCharge is always used, which sometimes caused a missile that should've hit to miss, because it wasn't pointed towards the target.
That was the main missile guidance, but there are some tricks. During all stage, except the terminal stage, the missiles send and receive radio messages. In order to avoid message collisions, most message are sent randomly with 10% or 2% probability each tick.
- MissileInit: Sent from the fighter when a missile is launched. Assigns the launched missile a target and an id.
- TargetUpdate: Sent from fighter and missiles. Gives the receiver an update on target location, velocity and class, in case they haven't seen the target on their radar.
- PotentialTarget: Sent from fighter. If any receiver happens to be on a good intercept path towards the potential target, they switch to that target. This is used to make missile intercept other missiles.
- Pair: Sent from Fighter. Contains two missile ids. Instructs the two missiles to pair up.
- PaitTTI: Sent from missile. Contains sender missile id and sender tti(unclamped).
The pairing is done to have to missile try to sync their time to impact in order to reach the target at the same time and only allow one missile to be shot down. During the cruise stage, a paired missile would slow down or speed up slightly depending on whether their own tti was smaller or larger than the received tti of their partner.
The target update and potential target message allow the ship to address specific missiles by id, but this isn't used in the tournament AI.
A lot of this is exposed in the debug text and shapes. Any time a ship sends a message is triangle is drawn around them.
Only missiles that are predicted to fly within 200 distance of the fighter are engaged. From those missile the one with the smallest intercept time is prioritised. The calculated lead angle is deflected clockwise or counterclockwise by very small amounts periodically to simulate some bullet spread and account for rotation lag and estimation inaccuracies. For rotation, a proportional and derivative controller is used with the torque api. Additionally all threatening missile are also engaged with missiles using the potential target message.
If there are no missiles to shoot, the AI shoots at the enemy fighter.
A closing speed of 100 is maintained towards the opponent fighter, while accelerating up and down. The idea was that constant acceleration would force enemy missiles to use more fuel. If the fighter got too close to the edge of the arena it accelerates towards the origin. Again, the edge avoidance seems subpar. I have also been thinking about using the boost ability to dodge missiles, but I don't see that being any more effective than just shooting the missile instead.
Changes from previous AI:
- Fixed orbit movement so the fighter doesn't fly off screen ever.
- Better aiming. (since this tournament I have improved this even further)
- Re-conceptualized radar. Before radar would track the active target. Now all known contacts are saved and radar is used to update, filter, etc... the known contacts. One obvious benefit of this is tracking multiple targets simultaneously. My next planned step here is to start utilizing snr and rssi to determine the accuracy of contacts.
- Updated radar transmissions to provide more information for missiles. Also encoded/encrypted messages such that they can be verified to prevent interpreting invalid messages from enemy team.
- Implemented primitive shooting down missiles. (This has been greatly fixed since the tournament.) My anti-missile defense still seem much weaker than the competition. I'm not sure what I'm missing. It seems like a combination of being too eager to shoot missiles, not detecting them quickly enough, and not being accurate enough.
My AI was largely the same as last time but had some bugs fixed:
- Turn towards the center of the map instead of to 0 degrees when we haven't found the enemy yet.
- Launch missiles from outside of guns range.
- Missiles only lock on to enemy fighters.
- Before radar contact, missiles fly toward target's predicted position assuming constant velocity.
Next time it will get a bigger update!
I had many ideas that I wanted to implement, but not that much time, which means that my code ended up being an unholy mess. I had my first AI capable of beating the default opponent for all 10 seeds just hours before the tournament deadline, so I'm happy to take co-last place 😅 I shall now give you my in-depth analysis of what went wrong, enhanced with data from my own local simulation of the tournament.
This was definitely my biggest weakness. Movement was a complete afterthought and basically the last thing I implemented. My thought process amounted to "I guess I should probably move", so I decided on a primitive strategy of flying towards the center for a bit and then settling into an orbit. I had seen that people struggled with hitting the arena border in the first tournament, so I definitely wanted to avoid that. If the predicted position after a few seconds was outside the arena, I would face inwards and activate the boost.
With that in mind, I give you the following diagram:
Oops... This unfortunately led to many avoidable losses. In particular, sought-ant was able to beat me by a large margin simply by waiting, not moving at all:
This was another weak point for me. While I was able to track targets with the radar quite well once identified, I chose my scanning distance way too small. This was another reason why waiting turned out to be such a good strategy against me. I had the most success against rlane, who was the only one who chose to attack head-on:
By getting close and into radar range, he allowed me to get quite a few missile hits before I had the chance to destroy myself by hitting the arena wall:
I wanted to implement sophisticated tracking of multiple targets, but ended up just tracking the enemy fighter and one missile, using predicted positions and radio transmissions to reacquire lost targets and to allow for some ECM and point defense scanning.
My big plan was to create bunches of three missiles each that lay dormant and all spring to life at the same time, to overwhelm the opponent's defenses. Unfortunately the radar weakness described above meant that missiles would often continue to idle after they were supposed to activate:
If the plan had worked better, you would be seeing three distinct acceleration phases 5, 10 and 15 seconds after launch as each bunch of 3 simultaneously accelerates, but instead it's very diffuse. The graph also shows the impact of my movement strategy: all of my missiles end with a similar maximum speed, whereas rlane's keep getting faster as his fighter gets faster later in the round.
The guidance algorithm is not sophisticated at all. I had read hopeful-quails description of accelerating to reduce the target's perpendicular velocity, so I implemented that very quickly and moved on. This can definitely be improved, but I think it worked well enough for now.
I spent a disproportionate amount of time building a sophisticated system for sharing targeting information via the radio. It's encrypted and basically uncrackable, but I dare you to try ;) This was the first thing I built because I happened to feel inspired and I ended up not using it for very much. I do think it helped missiles to stay on target while also using ECM.
Another thing that I spent too much time on is making my AI say a "cool" fighter-pilot-jock-line before every match. This might seem entirely useless, but it's actually vitally important and I plan to expand on it for the next iteration.
My AI ended up being around 850 LOC, and since coding in the browser and copy-pasting code between different scenarios is no fun, I needed a build system. Because I like suffering I chose GNU Make. This is my makefile:
codegen/%.rs: src/%.rs src/shiplib.rs
cargo test
cat $< >> $@
sed -i 's/crate:://g' $@
echo "mod shiplib {" >> $@
cat src/shiplib.rs >> $@
echo "}" >> $@
all: codegen/fighter_duel.rs tutorial
tutorial: codegen/tutorial/missiles.rs codegen/tutorial/radar.rs codegen/tutorial/deflection.rs
clean:
rm -f codegen/*.rs
rm -f codegen/tutorial/*.rsBeing able to code in the browser is nice to get people hooked, but a better mechanism for serious work would be really nice.
I definitely want to improve my AI and see if I can do better. It will be interesting to see how the recent buff to missiles plays out. Personally I think we haven't seen their full potential yet and looking at the stats for the matchup between the two top contenders stichinski and hopeful-quail, I'm not sure that they needed a buff:
It seems that what is needed instead is a nerf to the arena walls 😅 At least it's nice to see that even first place winner stichinski was struggling with it:
