I am not going to lie, between the random time outs and the natural speed disadvantage this language has, this contest was a bit frustrating for the Python users out there.
For me, it just meant I had to try and find different approaches to have a chance to compete. I spent a couple days doing just that, trying other things like turning the game into an optimization problem for example, but nothing worked. In the end I think this was just a game where the best approach was to try to model the game exactly in your bot, including not overfitting due to unknown future potions/spells, finding good heuristics to “guide it”, and then just let it do its thing.
I managed to get up to #3 gold on Sunday afternoon with a pruned BFS that got to me ~7-8 depth on average, and then converting this BFS to a beamsearch apparently (I wasn’t there to see it :/) made me stomp the boss and led to my final ranking. A few things I did slightly differently from others, which probably all helped a bit and a lot in aggregate came from being very constrained by the depth until I changed to beamsearch, forcing me to develop a solid heuristic. In more details:
I didn’t use 1 but 2 patience coefficients, 1 of 0.95 for your inventory value and one for potions that started at 0.99 but gradually got down to 0.95 as you brewed more potions and got closer to the end game. The idea behind that is that it matters more and more that you brew faster as the game progresses, but doesn’t really matter in the beginning
Similarly, my eval of inventory depended on how many potions p I had already brewed, taking only into account for each potion type max(6-p, actual potion number). This helped guide my AI towards not accumulating too much of soon-to-be-worthless inventory. Once I reached branches that led to the end of the game, I only kept those and of course used as the inventory eval what my actual bonus inventory score would be.
For learns, for the longest time I just forced my bot to learn a spell during the first 6 turns no matter what, otherwise they would often just start brewing. Ultimately, I added all the different learns you could do in 1 turn or in 2 turns (only allowing to learn on the 2nd turn if you also learnt on the first turn) and then not incorporating learns past that, and this approach when used with a beamsearch with a large depth actually made my bot a smart learner! I removed the 6 turns learn, and it seemed to be able to pick the right combos before starting to brew. Interestingly, @kovi mentioned among the top 30 I was the one that learned the less spells on average, and I noticed that sometimes I even only learned 4 spells and still somehow won.
Once I moved to beamsearch, I only used 150 nodes, the lowest I’ve seen in the comments. I think that was fine-ish thanks to a good pruning, and allowed me to reach a depth of 15-20, which was beyond my expectations in Python.
Thank you very much to CG, this contest was great as usual and I fully understand why contests see more and more participants! A few small points of feedback:
I know this was discussed before and I don’t want to open a can of worms, but for contests where it’s basically a simulation arms race, it would be great if languages could somehow be made a little more equal. I hear the old argument of “use the best tool at your disposal”, but being forced to always use the hammer isn’t that fun either. I’m sure there are ways to at least close part of the gap, such as for example a conservative benchmark to C++, compensating for GC time etc… Anyway, only 3/80 AIs in legends used python (but 2k / 7k users), that might be the lowest total yet (?) and either way extremely low when compared to 60/80 using C++ (but 1.5k / 7k overall).
That’s more CG being victim of their (again, well deserved!) success as @Razielwar said, but especially towards the end of the contest, commits literally took 2+ hours which made it really hard to roll out several incremental features
As others have mentioned, the random time out issues were also a little frustrating
More than usually, this felt like a single player game where taking what the opponent does did not matter much
But it’s not “the low-performance GC-managed language” to blame, it’s my lack of experience with game tree search. (And that Silver Boss was freaking tough!)
In fact modern .NET runtime and library allow you to write quite efficient code. Let me share some tricks.
To reach the bronze league I implemented a simple algorithm that chose the best potion possible to brew. If there was no potion possible to brew I casted a random possible spell. If there was no possible spells I rested.
To get to silver I did some basic DFS over game states. I also enforced a limit of learning at most 6 spells.
I was not a big fan of this game.
First of all was the experience with the game. The rules had some weird quirks that were tedious to implement (e.g. urgency bonus). Game mostly focused on speed and most solutions were very similar (DFS / Beam Search + heuristic).
Second of all, the idea of brewing potions is not very exciting. I really enjoyed contests when the game was fun and relatable (e.g. Hypersonic). It is much more pleasurable to write a bot for a game that you would be eager to play yourself.
By the way, I added a security to avoid counter of my opponent when I think I can win with the 6th potion brewed. And corrected two bugs: wrongly computed bonuses. Pages score completely false, I start to think that this part of my code is useless.
Ranking 1121 globally
Firstly the game was pretty hard to understand and complicated, what I really hated was changing the rules of game when your code goes up in leagues because every time I went up in leagues I needed to find every single place in my code that needed to be changed/upgraded. Second thing is that game wasn’t about thinking which ai algorithm to use and how to optimize it, the moment I realized that it is just write really fast BFS algorithm and collect every info you need as fast as you can or there is no way to climb the leaderboard it became more like Algorithms classes from university and less like AI for games. Third thing is that I prefer to write some simple simulator of game, write few files, which makes code organized and easy to optimize (running it few hundred of times to check how good parameters are etc) and in case of this game, after painful few minutes of understanding rules I gave up, almost instantly, on writing it on my computer, mainly because I didn’t know how potions recipes are randomized etc. and as everyone can see codingames ide to write code is bad, after getting into silver league I needed to scroll few hundred lines up and down to check code in different places.
So about my algorithm, I created a 13310 nodes in my graph (I encoded ingredients as follows ingr[0] + ingr[1] * 11 + ingr[2] * 121 + ingr[3] * 1331 ), ofcourse there wont be as much as 13310 nodes in this graph (there are a lot of not possible numbers to achieve using this encoding, because ingr[0] + ingr[1] + ingr[2] + ingr[3] <= 10 , but I didn’t have motivation to optimize this, game killed it). Then there is edge connecting nodes u and v if after casting spell a in shop state u I get to shop state v. So I run bfs from my actual state of the game and I’m finding path to each of potions (or every other state of shop that have enough ingredients to create this potion). There was some really frustrating piece of code to write so I could check if I need to rest before travelling with this edge. After that I have potion prices and number of turns to get this potion, so I divide price by number of turns and choose the best (there were probably a lot of much better heuristics but as I said game killed my motivation). I keep each path stored so after initial bfs I don’t need to rerun it if there was not any change in game state (enemy created potion or I created potion).
When game made it possible to learn spells I wrote additional bfs call, if I already founded some path then I have free time so I call bfs as much times as time limit makes it possible and for every spell which is possible to learn I find new paths in graph given that I learned this spell and if there is now better path than without learning this spell I learn it (if I have time to check few spells I choose the one making most improvement). I had hyper parameter to limit how much spell I will learn.
Can anybody share any bot which uses beam search technique and make it to Legend or Gold? I could not find any practical example online where beam search technique is used for writing good Bot. All references I see related to NLP!
And sharing my code for the beamsearch part will be useless. There is specific code for the current puzzle, I use 2 arrays instead of one to avoid sorting the Node directly (I sort an array of pointer instead) …
If you are looking for some pseudo code. Just look for a pseudo code of a simple BFS. A beamsearch is pretty much like a BFS, you just add a sort and you keep the N best nodes.
So I didn’t know of iterative deepening before you mentionned it, but from what I saw online it seems like you go through the whole tree from the start again at each new iteration. Is that actually what you are doing? Or are you keeping the last depth’s states you stopped at in memory, and keep going one depth further from that last stopping point until you run out of time?
Do you sort the whole fringe/frontier or just the children of the current node? Is it possible to use priority queue instead (basically the heap sort)? By which criterion do you sort — by the static evaluation of the node? Is it the same function as for scoring leaf nodes?
Ah got it, I just couldn’t understand the purpose if you really did that but it makes sense then, basically keep going until you run out of time. Thanks!
@Gronahak Congratulations on getting to gold with Python and such a low number of nodes visited.
Glad I’m not the only one who tried linear algebra ! Here was my approach :
Given the matrix of costs of all spells (each on a line), I estimate the cost of ingredients,that I just multiply with the potions’ costs. My formula formula for approximate ingredient cost was, using pseudo inverse:
time_cost = np.array([2 - castable]) # using castable property is optional : then it would be all 1
inv_c = np.matmul(np.linalg.inv(np.matmul(c.transpose(), c)), c.transpose())
approx_cost = np.matmul(inv_c, time_cost)
@Raf It works with any number of spells, and gives an approximate cost, which is somewhat the average exchange cost from all possible ressources, measured in rounds.
Also, one way to ensure invertibility is that all spells must satisfy the “increasing quality of gems” property, either purely producing spells, or producing ingredients all of higher tiers than the cost ingredients, so I used the following function to buy a new spell or not:
Anyway, in the end I also used tree search :/, and in this exploration rather than prediction mode, more different spells seemed to bring more diversity and gains, so I dropped the linalg strategy.
My final tree implementation covered only 200 nodes and I didn’t go far up the Silver League.
Me too, because I could learn much from it. However unfortunately the risk is just too high that if a full legend bot code is revealed, dozens of new clone bots will enter the legend arena from random Level 1 users. Some post mortems with pseudo code or limited code-excerpts are detailed, and of very high quality.
