My path to be top #1 … In silver
So hello dear reader, Zakaoai here !
My final ranking are :
Introduction
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.
The challenge
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
Wood
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
Bronze
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.
Bronze to Silver
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.
Silver Before Gold
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.
An easy code rank #500 Global - Best Than Nothing
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.
Silver After Gold + Legend
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 
Begin Simulations, BFS For the win ?
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.
Upgrade Performance of the BFS
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.
Last Optimization get rid of duplicate array for spells and potions between state
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.
My Final BFS
Finally here it is. The final representation of my BFS
Node
State :
{
action,
myBinarySpells,
binaryPotion,
invHash,
score
}
Child Nodes
binaryPotion -> Brewable Potions
myBinarySpells -> Castable Spells
if myBinarySpells < pow(2,spell.length) -> Action Rest
Evaluation
Score only BrewablePotion :
Brewable Potion Price + Ratio * Price of the nearest Potion with the inventory after the brew.
Recommendation for future challenge
-
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 :
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
