Finished #4
Many thanks to CodinGame and all the competitors for this very entertaining contest
For the first two thirds of the competition time-span, I tried to implement a full tracker of the opponents’ paths, similar to what I did for Ocean of Code.
I really enjoyed this aspect in UTG and OOC contests, trying to extract the maximum of hidden information from the few inputs we have.
It was very challenging due to the exponentially increasing number of states, and I was close to give up, facing all these timeouts . I’m glad I persevered, this tracker was certainly the only strength of my bot
It allowed me to remove a large amount of the pellets gathered by the opponent, and to avoid some (sadly not all ) of the bad encounters at the corners.
The rest of my bot is the selection of an action successively for each pac, only based on heuristics on the current state of the game. I did not take the time to implement a MCTS or other search algorithm, simulating next turns or trying to maximize farming.
Tracker
Each bot had a list of possible states (position, cooldowns, type, and visited cells).
The tracker maintained a list of possible valid combinations for those states.
Expected information :
- Sets of possible pacs positions, types and cooldowns,
- Removal of most of the pellets gathered by the opponent.
Information we had :
- Disappeared pellets in pacs’ visible area (+ big pellets),
- Increment of our and opponent scores,
- State of our pacs,
- State (or absence) of visible opponent’s pacs,
- Possible actions for a pac, based on its state, or based on combination of states (valid moves imply no collision).
How to use it :
- A disappeared big pellet means at least one pac was on this location last turn,
- A disappeared pellet means at least one pac visited the cell on one of the previous turns,
- A remaining pellet (or big pellet) means no pac ever visited the cell,
- An increment of X in opponent’s score means that each valid new combination of pacs’ states, expanding a previous valid combination, must have eaten the exact amount of pellets leading to that score,
- An unexpected loss of score means an opponent pac has taken the pellet or big pellet right under our nose,
- Spotted pacs (and starting positions) : self explanatory
- Non-spotted pacs in visible area means no pac is here now,
- Unexpected blocking (or death) of one of our pacs means an opponent pac is near us trying to move to the same cell,
- Absence of blocking or still alive pacs means the opposite.
Details (feel free to skip ) :
Pacs individual states :
Each pac state’s visited cells were reduced to their intersection with the possible remaining pellets at the beginning of the turn. The implied merging of states allowed to reduce now identical previously valid combinations of pacs formations.
Pacs were sorted by the amount of associated or expected states (dead first, then spotted, then pacs with the least previous states). Spreading of next evaluated pacs’ states could indeed benefit more pruning from the common properties of all new valid states for an already ‘expanded’ pac.
Taking into account the maximum and minimum amount of pellets gathered by other pacs and the score variation, we can deduce lower and upper bounds to the number of pellets gathered by the evaluated pac. In addition to gathered pellets count, verification also included (un)blocking, deaths (or absence of), invalid visited cells, etc.
The expansion of a state could identify previous states without children. Such an invalid state allowed the pruning of all previous combinations containing this state. Other pacs’ states referenced by invalidated combinations could themselves be invalidated if they did not appear in other valid combinations.
The intersection of visited cells for all remaining valid states associated with a pac allowed a first removal of remaining pellets.
Combinations :
After all these expansions of individual states, a set of new valid combinations was created from each previous valid combination, taking into account each new states expanded from those composing the combination. At each level of the cascaded loops, the evaluation of the new combinations was interrupted if requirements (gathering, killing, blocking, presence in one of the previous turn, etc.) could not be satisfied, whatever the state we chose for the next pacs (taking into account the common properties of the next pacs’ states).
Combinations leading to impossible combined moves due to collision between opponent pacs were filtered. When a seemingly valid combination was found, a last check involved merging of root combinations pacs’ visited cell and new pacs’ visited cells. If the variation of gathered cells between these 2 did not match the variation in opponent score, the new combination was discarded.
The intersection of visited cells for all valid combinations (union of visited cells for each pac) allowed a second removal of remaining pellets (and more merging/pruning of states and combinations next turn ).
All states belonging to none of the new combinations were then erased, and a new intersection pass lead to yet another removal of pellets…
Fallback :
It sometimes managed to track the opponent the whole game, but often the combinatorics was too high. In those cases, all combinations were cleared, but states expansion and pre-filters remained active. This resulted in a loss of performance, but was still usable. Most of the important pellet information was deduced before.
All in all, that was quite a complicated tracker, not sure it was worth it, but it was fun to implement (not so fun to debug ).
Game logic
The selection of each of our pac’s next move was done through the evaluation of the following steps, by order of importance (when an action was assigned to a pac, next step would not replace it) :
- Attack : try to trap and kill pacs in dead end (some ifs involving cooldowns, length of dead end, pacs types, …),
- Defense : flee, wait or switch to killer type if trapped in dead end (again, some ifs ),
- Enable speed : if cooldown ready, unless near big pellet or in danger (a known killer opponent is nearby, need to keep cooldown ready for switch or to flee),
- Gather big-pellet (some ifs, could have largely been improved…),
- Gather pellet (sort pellets by score for each pac ; select pac with the higher score then loop ; remove pellets on evaluated pac’s way for the evaluation of other pacs ; avoid dead-ends ; try to spread pacs),
- Flee or fight if needed, instead of standing still.
At each step, every pac was evaluated independently. But before the validation of an action, I checked that the pac would not collide with other already assigned pacs, and would not be exposed to a possible killer pac.
A set of possible opponent pacs’ states (up to 8 per pac, if more pac was ignored) was deduced from tracker, to help with the evaluation of those steps.
This game logic is relatively simple, with no deep search of the best possible moves. And I’d like to think that the efficiency of the bot was due the accurate enough information extracted from the tracker.
Thanks for reading
And again, many thanks for this very entertaining contest, and congratulations to the winners