#121 (#4 in gold)
University of Wrocław #1 school
I will start with acknowledgments. Many thanks to @Zylo and other people from the polish slack CG community for many fruitful talks and sharing ideas. That was a nice experience, and I hope we will extend in time (reach @Zylo or me if you want an invite).
Thanks and congratulations to all our students and other members of UWr team. Great job, I hope you all enjoyed the game! That was definitely harder this time (previously we didn’t even need @DamianS help) and yeah - 7 out of top 10 unis are french, top 2 not :P…
Winners won, so they already know they did an amazing job, but that’s never enough - congratulations to everyone on top!
Last but not least, thanks to the entire CG team for making this contest!
The game and contest
I have mixed feelings regarding the game. At first I didn’t like it - I think it is overcomplicated. Yes, with time, I get used to it, and I think it is interesting, but still. Combining hidden information with controlling multiple entities and uncertainty plus so many instakill situations - that’s a little too much. The game is great but awfully complex as for the CG environment. Plus the visualization should contain debug mode with limited visibility… this was a pain to understand what is happening without this. (Also, the wood leagues were a joke :P.)
C# language issues - yep, thanks, that was not fun.
About the contest length - 10 days contests are awful. In a 1-2 days one, you just sit for a time and code what’s faster. In a month one, you can start in the middle and have nice results (see everyone from our uni during OOC), so it’s not that you have to sacrifice your life to CG. 10 days… if you’re gone for 2-3 days then things are getting messy, and if you’re not a fast-pacer but like to carefully think and write/debug every part - then either you’re a life-goner or out of the top.
My solution and history
So overly I’m a bit disappointed, given the time I put in. But the contest was hardcore, and not coding for a few days kicked hard. If I see descriptions of what seems a simpler bot in legend than ehhh… Sad cat :(.
My first approach was nearly no micro but a combination of pathfinding and opp/pellet tracking.
Pathfinding was based on BFS+Markov. For each pac separately, make BFS with counting my other pacs and opponent stronger positions(+this turn reachable) counted as walls. Then, from the most distant squares, I computed square value as a fraction of best + fraction of all neighbors from depth +1, and the base square score. This base score is a pellet value (if there is one) times discount on not seeing the square for long times the probability the pellet is still there (see later). Then greedy choose best actions for current turn and resolve conflicts by running the algorithm again with more walls to bfs if two pacs collide with each other.
As for an opponent prediction, we came out with @Zylo with a nice algo to track possible paths of the opponent when we see him again. We count upperbound on how many steps he may cover during this time, and for all squares assume that the ones with distance to old position + to the new position less equal than upperbound may bo on the path. Then we set the probability the pellet isn’t there for each square based on the length of the track going through that square and all squares that may belong to any such track. This very often detects just one track and give sure information about gone pellets.
This code was ~#70 on Tuesday, and still ~#230 on Sunday,
Then I wanted to improve pathfinding. And because I had some outside stuff, I kinda finished it on Sunday - not, as previously planned Thursday/Friday. This was the change I hated, rewrite the basics of the system, not incremental update. Probably still bugged, but works. Somehow.
What I did was entirely switch to frame-based architecture. Each pac took into account paths of other pacs, and the path computation went similarly as previously, but for 3 turns deep (I’ve tried with more but timeouts happened).
Each pac created his path on each turn deep computing new Markov with the pills and other bonuses/discounts properly updated. On the upper level I took all combinations of first/second/third computation order for three pacs or less. For a larger number, all pacs were computed as first, and then greedily, the best one was chosen the real one, then more complicated stuff for the second etc.
I added straightforward opponent prediction 3 turns ahead based on simple flow (no additional filtering on visibility etc) to discount in proper (I’m still certain there are bugs out there) turns squares that may be occupied by the stronger opponents.
I also added a few simple micro rules, and was in the middle of implementing tunnels but gave up on this as, without better opponent tracing, the discovery of such situations were very rare.
At this stage, my code became a mess, and I wasn’t sure of anything.
Last superfix, #230->#final @DamianS gave us ‘last advice’ on slack, to usually avoid dead-ends when taking the pills at the beginning. This was a default behavior of my bot, that a day or to ago I tried to force-change. This was actually easy to revert - one uncomment, and bam + 100 places.