Wow it is very interesting to see how much the “basic score” diverges from the actual spell value you were able to compute.
What was your method for determining the #3 point - “this spell contributed to X points”? Do you average the points gained over a sequence of spells for each potion brewed? I was curious on your approach for calculating the value of the pair-wise combos of spells too.
I’ll call the list of spells that have been learned a “deck”.
K represents the number of spells in a deck
N is the total number of spells (46 in this case)
Let us assume that a deck’s value can be calculated as the sum of the intrinsic value of the spells it is composed of.
deck_value = sum_i(s_i)
with s_i a spell’s intrinsic value.
Let us calculate the average value of all decks containing a given spell i :
A_i = s_i + (K-1) * (sum_j!=i ( s_j )) / (N-1)
The values of A_i can be observed, this is what I store in steps 3 to 5.
Knowing the values of all A_i and with a little bit of rearranging all the equations, it is possible to calculate the intrinsic s_i values. It is those s_i values that I have given in the first table.
Writing this, I notice that I didn’t account for the fact that spells 0-3 are always learnt, and should be treated differently in the equations. This is a mistake, but I don’t think it would change things too much.
===============
Now for the combos…
Under the first assumption where spells have an intrinsic value and no mutual dependency, it is possible to calculate the expected average value of all decks containing both spells i and j.
It is also possible to observe this average value. The combo value in my second table is just the difference between this expected and this observed value.
The combo value is significantly larger than the intrinsic values because I took the table from the full calculation which takes into account the marginal decrease of spell efficiency. (ie: learning a 21st spell when you already have 20 spells is useless. Learning a 5th spell when you only know 4 is very useful)
For the sake of completeness, here is my full formula, which works pretty well within a range of 4 to 20 spells learned :
deck_value = sum_i(s_i) #intrinsic values
+ sum_ij(combo_value_ij) / (deck_size - 5) #combo
- 0.15 * (deck_size - 4) * (deck_size) #marginal decrease of spell efficiencyHi everybody,
This contest was very fun, thanks to CG, to the game creators, and to all participants. I finished #460 on global (with C), glad to not be completely stucked on far bottom Gold as I was nearly all the time in this league.
On first day, my mother asked me how was this challenge, so I decided to share my screen on private Facebook. On the last day, I got 32 hours of videos that you can see now on Youtube searching “CG FALL Challenge 2020”, speaking french sorry, and it’s not very fun to seek my bugs with me 
.
I think my great error on this challenge was to use BFS only for grabbing informations (distance to potions) from a single state, so I could use heuristic evaluation to decide what was the best move.
So my BFS runs into a 4D map where all inventories are represented by a point (a, b, c, d). Too late, I realized that this model didn’t permit to explore further than the next potion, and I had to managed with heuristics to make a lot of decisions.
My last code worked with :
On my last push, I deactivated the MCTS on the 8 first turns (I think the MCTS was not ideal with my learn values), and go back to manual criterias to chose Learns (free spells, color weight, number of ingredients won)
Thanks again for this great challenge
I answer to a question here.
I received a PM from @semera
I respond here because the answer can be interesting for other people.
“Patience coefficient” is probably not the “school” term. I suppose it is a “custom codingame term” like many others. So sorry, I don’t know what you should write into google But I can explain what is it:
Let’s say you want to evaluate a path of your simulation. Take this 2 paths for example:
CAST 1 1 BREW 2 REST CAST 4 1
BREW 2 CAST 1 1 REST CAST 4 1
If you just evalute the game state at the end of the 4 turns, the score will be the same. But this is not what you want. You want your AI to take the second path, because a brew now is better than a brew later.
This is why we use a “patience coefficient”. If the brew reward 5 points (for example), the brew at depth 0 will reward 5 * PATIENCE_COEF^0 and the brew at depth 1 will reward 5 * PATIENCE_COEF^1.
You can use whatever patience coefficient between 0 and 1. A “common” patience coefficient I saw in many contests on codingame before is 0.7. For the Fall Challenge 2020, according to the differents PM, a good value seems to be between 0.95 and 0.99.
Yes Magus, but if you see the opponent will brew the second potion (with +1 bonus) and you will brew the first (with +3 bonus), you would want to let him take this potion with +1 bonus and take yours the turn after, or at the same time, to not let him grab the +3 bonus… I agree, in this case, your eval would say it
It’s a discounted reward.
I finished 240 using Java with a depth 4 simple MC with ~30K average unitary simulations done per turn.
Nothing fancy in there, but at least this time I managed to avoid objet allocations in the loops and escaped the GC’s timeout nightmare.
I precomputed during turn 1 the use of all spells (with all their repetitions) on any of the 1001 inventories, but this was probably not a good investment of my time since it didn’t led to any major performance gain.
I’m still amazed that for the “learn phase” I wasn’t able to find anything better than “learn first spell for first 8 turns”, especially when it’s really not the case in the boardgame version according to this, but that’s how it was.
Thanks to CG once again for a great challenge ! 
Congrats to my Amadeus teammates for reaching #1 in the company leader-board ! 
Congrats to the top 3 pb4 / Agade / reCurse (and thanks for sharing your PMs as always), it was fun to see you battling each other a bit like Tennis’ big 3 Federer/Nadal/Djokovic 
Wish my bro Saelyos (the “nextgen” ?) could have competed with you, but it wasn’t to be the case this time !
Hi all !
First of all thanks to CG and all participants. I think this challenge is one of my favorites, as it was quite original, with nice graphics. I finished #53 in legend. I learnt a lot on this challenge and on the other hand, I really failed some parts of my AI and still wonder what to do. I have some regrets on the global efficiency of the matching… I suppose it is due to the great number of participants. But well, I had to wait more than 2 hours to finish my matches. In comparison to previous challenge, I felt to have done 5 times less matches. The backfeed on modifications was thus very slow… 
My strategy was a beam search depth 15 width 200 evaluating on the score… Yes on the score because I did not manage to find better eval… Even spending hours trying ! I considered opponent only to predict a coming end (with depth 5). My learn was first basic (7 cheapest ones), but I tried to give values on different spells to see if buying a better one was efficient… Not sure I succeeded. So I won’t talk anymore of the heuristic as I really feel to have failed it.
So on what my AI was good ? clearly on data structure IMHO. For me, a node of the beam search contained 3 things:
So the nice trick was to check if a state or better was already visited. I used BFS, so I solved depth after depth. A state is clearly better than another if it has the same inventory state and a better achievement/readiness state, that is to say at least the same bits at 1 (and possibly more). One can check it simply on A and B, bitarrays, if A&B==A, B is a better (or equal) state.
So I built a list of 1001 lists of the encountered achievement/readiness states. When I find a new element A, I go to the list of the inventory index and compare it to every element B in the list.
If I find B better than A, then I already crossed a better state, I break and trash A.
If I find A better than B, then I can break because B already passed the check before (so A would do it easily) and I replace B by A.
If I reach the end, I append A.
I first thought this check would kill my perfs. But finally it revealed to be very efficient, as A tends to improve with depth, the number of comparisons does not grow that much and the pruning is really worth. Well to be honest I found the final form of this algorithm on last sunday at 2.00 am and was not confident enough to submit it
Note on the root move that I always solved in order for a depth, all REST, then CAST, then LEARN, then BREW. So by construction, BREW > a > b > c always come before in the check than a > b > c > BREW, which prevents doing a uselessly risked REST > BREW.
Now some additional thoughts, this game was nearly solo-player. The main interaction in my opinion is on the 5 first turns when both players are buying learns at the time and at the end when one stops the game. Even the concurrence on the brews is really small. Most of the games in top legend last between 32 and 40 turns. And the one who ends generally wins. Even if he took smaller potions, it has the decision to end the game in his hands and the last move is necessarily a score step for him with the last potion.
When I did matches vs top 5, I generally lost with only 3-4 potions, and I really believe that they win because they are faster. I even won some matches vs them, when my AI was luckily fast and brewed the 6th before them. I tried some match vs the dummy AI (wood boss isn’t it ?). And yes don’t worry I won all of it, but I realized that the matches last between 38-48 turns. So yeah, there is only one ressource in this game (like many other), it’s time and winners just used it better, congratulations to them !
So hello dear reader, Zakaoai here !
My final ranking are :
#544 / 7011 Global
#1 / 1913 Silver
#9 / 592 JavaScript
#191 / 2730 French Player
For me, this challenge was the challenge of Performance against the choice of your programmation language.
I choosed JavaScript but was it a good choice ? Certainly not but I choosed it anyway.
This challenge was really enjoyable. The rules and objectives are simple but there was a tons of combinations possible. Futhermore, the challenge theme was my favourite. I’m a huge fan of Zelda’s series
I will now explain how I reached my final Rank #1 Silver
Well for the Woods ranks, I need only some few functions. The goal was to brew only 1 and 3 potions.
I made function for :
Dealing with my current inventory
Filter castable spells if I have the ingredients
Brew only the best potions in the list
For the bronze league, I do some overkill functions that I thought at the begining of the challenge can be a good BFS but it wasn’t.
The main idea was to precalculate with my inventory all the self sustainable of castable spells.
With this 1st idea, I reach fastly the limit of JS performance and that was at this moment of the challenge where I ask some questions to the Community.
Thanks a lot for all your advices Mazelcop.
So after all, I rework my first Idea by starting with 5 states ( 1 by potion) and search the best spell’s chain that can help me to brew the potion.
My “fake” BFS make up to chain of 5 spell’s chain and I can repeat it 3 times their combinations. After I got the list of all actions, I store it in a List and play these actions without checking the game state.
NB : don’t do that 
The game state update every turn. That’s why it’s a “fake” BFS.
But with some luck, I was pushed in Silver.
So here I am the final League but there was multiple “state” of silver league because before Gold we were a lot of player in it.
So since I obtain my silver rank, I decide to erase all my code and write a simple function I called it “Best Than Nothing”.
The main idea was : If we dont know what to do, what can be a costless function to play other actions than ‘WAIT’
For this I used for the 1st time and until my last submit the famous META call Learn 8 Turns which mean to learn only at the beginning of the game.
So for the algo of Best Than Nothing
If a potion can be BREW with my current inventory
I BREW the potion
Else
I check all spell that I can CAST with my current inventory
I sort the by the gain of the cast with the idea of price / ingredient [1,2,3,4]
I cast the best one
If I can't cast a spell, I use REST
With this I was top 500 for at least 1 day. It was a funny joke for me to be this good with such a random function that only focus on production of ingredient.
Then, Gold and Legend League appears. The best player did beat the Bossdorf but I didnt reach my main goal of Gold. At least I’m Top #1
So with the code I made, I decided with the recommandation of the community to do an evaluation function.
Not a BFS at first only evaluate one turn of play to do always the best action.
Then, I transformed it into a BFS.
The algo was :
Begin with the Initial State ( Castable Spells List, Inventory)
Add this state into a list
While step below a defined depth (I can't go over 4 / 5 with Beam Search)
For each states in the list search all child state ( using flatMap I can use only one list)
Childs states :
Each Castable spells with my inventory
Each Brewable potion with my inventory
Rest
End For
End While
I try to do a Beam Search to upgrade the performance of my BFS but at the cost of lot of result. I can only achieve Depth 5 with Limitation of 50
Beam Search is a good solution when you know your evaluation of all nodes is good enougth to take only best nodes. And without good perfs Beam Search can’t achieve a good rank.
For this at the end of each For loop, I sort all node and take only the 50 best one. That also kill the perfs when you sort a lot of node. So don’t use sort to do that.
The next days after this 1st attempt of BFS was to do all I can for the performance of BFS in JavaScript.
Each day, I talked with community members and I read how many states others languages can check. Before my optimizations, I can only check 1000 states vs 20k after optimizations. Others players can go over 100k states, so it was really frustrating.
So here are all my tips to optimize your JS BFS by order of how I implemented them :
Pre Calculate all you can Turn 0 with all data you know ( even in the github project of the challenge)
Sum of all possible inventory (1001 possible states) with all known actions
Ratio of completion for all Potions with all inventory states
All maths function we use multiple times like Math.pow(0.9,n)
Create an hashtable of states to duplicate Node (hash based on inventory state and spell state) See binary representation bellow for a nice exemple
Use some tips to optimize BFS for the garbage collector and without queue Coding Game Optimizing BFS
Use standard function over JS function even if bench dont say so ( JS BENCH sites check only execution performance without thinking of Garbage Collector) so replace map and foreach with simple for
Optimize all objects instanciations to minimize impact of Garbage Collector. Use global constant for every string or generic object.
It was the first time I deal with binary operations since I was in school. So it was like I learn again how to use them.
So my objectives behind these binary operations was to never instanciate arrays for all my states and only store a binary representation of those arrays.
So I need to store a global array of arrays of all indexs combination for spells and potions list.
Exemple :
With Learn 8 strat we have 12 spells
So we can think of thoses spells with 1 bit for each spell (0 -> used spell, 1 -> castable spell)
So IIIIIIIIIIIII -> All spells are up. the number is 4095 (2^(12) - 1)
With this, I associate to this number a list of index of castable spell only
IIIIIIIIIIIII -> 4095 -> [0,1,2,3,4,5,6,7,8,9,10,11,12]
IIIIIIIIIIII0 -> 4094 -> [1,2,3,4,5,6,7,8,9,10,11,12]
With this list in global constant, I finally get rid of array instanciation between states of my BFS when I BREW a potion or CAST a spell I only store a binary number.
For the inventory it was an other method. I used 4 bit by type of ingredient. So the math function behind is :
function hashInv(i, j, k, l) {
return i + 16 * j + 256 * k + 4096 * l;
}
With both of those binary numbers, you can achieve a good Hash of your state. So for combination I did a binary sum of these 2 numbers with a little trick :
(invBinary << mySpells.length) + spellsBinary
I shift the binaryNumber of my inventory with the length of my spells array. You’ll have finally a unique number for all your states.
Finally here it is. The final representation of my BFS
State :
{
action,
myBinarySpells,
binaryPotion,
invHash,
score
}
binaryPotion -> Brewable Potions
myBinarySpells -> Castable Spells
if myBinarySpells < pow(2,spell.length) -> Action Rest
Score only BrewablePotion :
Brewable Potion Price + Ratio * Price of the nearest Potion with the inventory after the brew.
Don’t miss steps. Write ideas but dont rush to code them without thinking if it worth the time
Try to translate all game datas to simples objects. A list of castable spells can be seen as a binary number with some imagination.
Prepare your generic functions to deal with timeout, logs, some math operations.
Split and comment your code as much as possible during the contest. When we need help it’s better if we can explain how we code our solution. Also, evolve a well splitted code is faster than a single function with hundreds lines of codes.
Special thanks to some French CG player who helped me even until the last minutes of the challenge :
Mazelcop
Fangel
Gh0stM4chine
All Fr community in CG chat
Finally, I made a YT video in French to talk about my code. How I upgrade all my function. It’s a long 4h30 talk where I interact with some CG player Debrief + Post Mortem
NB : Without new submit I achieve to be gold
#476 Global
#377 / 467 Gold
Don’t you need two separate (independent?) bitsets for castable (not exhausted) spells and learned spells?
Hi everyone !
I finished Gold, 389 overall
There’s my postmortem:
I would be happy to have suggestions on it !
Thanks
How are you getting the path of actions of your AI ? I know how to get it with a MinMax but I have no idea with beam search …
Thks !
Welcome back
By the way, I finally got my revenge from Coders of The Carribean in 2017 ! 
Fall Challenge 2020
I just use a simple vector<Action>.
Pseudo code :
class Node {
vector<Action> actions;
Game game;
double eval;
}
Node parent = nextNodeToExpand();
vector<Action> actions = computePossibleActions(parent);
for (Action action : actions) {
Node child = new Node();
child.actions = parent.actions();
child.actions.push(action);
child.game = parent.game;
child.game.play(action);
child.eval = parent.eval() + child.game.eval() * pow(COEF_PATIENCE, depth);
addChildToTheListOfNode(child);
}
On my side, I only have one action per Node but I keep a link to the parent.
class Node{ Action action; Node father; double score; }
Thus to retrieve the list of actions, I will loop until the node without father:
public List<Node> getNodes() { List<Node> nodes = new ArrayList<>(); Node rootToTop = this; while (rootToTop.father!=null) { nodes.add(0, rootToTop); rootToTop = rootToTop.father; } nodes.add(0, rootToTop); return nodes; } }
Wow! I independently invented totally the same approach.
I tried something similar, but not with more success ^^. In order to find better moves, I run 2 BFS for me and the opponent to prune automatically some moves which take more times, and to have another pruning by evaluating the final nodes to eliminate the bad ones. My idea was then to explore those trees with a smistsimax (which performed really badly) or a DUCT (it was better, but still bad).
I still don’t completely understand why it didn’t work, but anyways it was not the good approach and I didn’t have the time / motivation to write something different.
The algorithm I’ve decided to use was simple BFS. Using this approach, I was looking for the potion I could brew in the least amount of turns. After that I would execute the first action on the path from the current state to the state returned by the BFS. Besides that, during the first 10 turns I would learn a free spell with probability 9/10 (with probability 1/10 I would run BFS). The differences between my algorithm in wood, bronze and silver division were simply some bug fixes and taking into account new rules.
I didn’t like this challlenge, after implementing BFS I wasn’t really interested in trying to improve my algorithm.
I don’t entirely understand why did my rollouts work so well either; I also tried sorting the possible moves not by how much they increase the value of my inventory, but by distance from the closest gamestate where I’ve brewed all the potions (either 5, or how many I need to win) while ignoring that I need to rest, which reduced the size of graph to only 32032 nodes. Moves minimizing this distance should be relatively good (I later used this distance to prune the beamsearch when calculating statistics I mentioned in my PM), but it still performed much, much worse (only 30% winrate vs my bot) for some reason I fail to see.