aangairbender/cg-fall-challenge-2023-pm.md

## cg-fall-challenge-2023-pm.md

      
    Raw
  

              cg-fall-challenge-2023-pm.md
            
          
    aangairbender, Legend 11th!
Overview

Very important for me was having good toolkit for this contest:

code for state serialization (every turn I print base64 encoded state of the bot to stderr, so I can run my bot locally from any replay from any frame and debug the bot's behavior)
state visualizer (to debug fish tracking mostly)

Bot itself consists of 3 components:

fish tracking
planning
plan execution

Fish tracking

For each fish I maintain an axis aligned rectangle of possible positions.
For the first turn it would look something like this (for this match):

Each turn:

I enlarge each rectangle by 200 (to simulate fish movement), while limiting rectangle to the habitat area.
I cut rectangles based on the input radar blips
if fish appeared in scans of a drone, I intersect that fish's rect with AABB (axis-aligned bounding box) of that drone scan circle.
if fish did not appear in scans of a drone, I cut out rectangular intersection of that drone scan circle from fish's rect. E.g. here I would cut out green part:


If no drone has reached fish.y - 1400 coordinate, then I dont let fish's rect exceed middle of the map (because fish would collide with symmetrical fish and bounce back).

For example same match frame 14. My bot's predictions:


It's important to simulate fish movements after fish goes out of your vision range. On the screen above you can see all fish of type 0 are not visible, but are accurately tracked.
I assume fish position is center of the rectangle for undiscovered fishes.
Planning

There are 26 tasks:

12 scan fish tasks
12 scare away fish tasks (so that opponent cant scan that fish)
2 report tasks (1 per drone)

For each pair of drone and task I assign some value based on the current state and then I use assignment algorithm (munkres) to come up with the best assignments. Then I mark used tasks with some bad values and repeat assignment for 2 more times. This is needed for cases when drone can scare away a fish in 1 turn, but it should do it in a way to be closer to completing his next task.
Factors I include in the scan task value:

score I would get from target fish
how close opponent is to scaring that fish
whether the fish is on the same side of the map (left or right) as the drone

Factors I include in the scare task value:

fish type (higher = better)
how close I am to scaring that fish

Report tasks value is always zero.
As a result for each of my drones I have non empty list of tasks.
Important point is that for each drone I detect if that drone should report based on whether that drone scanned at least one type 2 fish or not.
If my drone should report, I check opponent same side drone position and decide max_y for that drone.
// d - my drone, w - opponent drone
int calc_max_y(const ISDrone& d, const ISDrone& w) {
	if (turns_to_report(d) < turns_to_report(w)) {
		return 500 + (turns_to_report(w) - 1) * 600;
	}
	else if (turns_to_report(d) == turns_to_report(w)) {
		return 500 + turns_to_report(w) * 600;
	}
	else {
		return 500 + (turns_to_report(d) - 1) * 600;
	}
}
I also check If my drone is below the opponent then I set max_y in a way, that I can scan/scare the fish below opponent while not letting opponent scan that fish. This usually means being around 1400 above the fish (if opponent is sticking to my drone). This gave me a huge score boost and pushed me from top10 to top3 at some point.
When I do simulation later, for each turn in the future I subtract 600 from the max_y (assuming opponent is going up).
For lights, I turn on light if my drone is in range of 2000 of any unscanned fish this turn or if it would be in range of 2000 of type 2 fish in the next turn.
Plan execution

I have simple HC (Hill Climbing). So basically I maintain 1 solution (solution being next 3 moves for each of my drone), try to mutate it, see if eval is better than the current. If it is then the new solution becomes the current one.
My mutations:

change the movement direction to one of the 16 predefined ones
change the movement direction to the hinted position (for each task I store hint where the target is, e.g. for the scan fish task the hint is that fish's position)
divide movement vector's length by 2
multiply movement vector's length by 2

For eval I just use eval function for each type of the task (all of them return value from 0 to 1):

eval_scan - just returns how close the drone is to the fish
eval_scare - based on how many turns it would be needed to scare away fish. This consists of turns to reach the fish side (f.x +- 800, f.y) and turns for fish to leave the map
eval_report - based on how many turns needed to report

If the drone exceeds max_y or is in emergency mode - there is a huge penalty.
For each drone I sum his tasks' eval results (with each consecutive task result multiplied by 0.1).
And the eval of the HC solution is sum of the drones' evals (I sum eval results for each depth with some factor).