Fall Challenge 2020 - Feedbacks & Strategies

[JohnCM]

Hi, this is John. I managed to get 281st overall with a push into Gold 4 hours before end of competition! Hurray!

Here’s what I did.
DFS with depth limit 6 (that was as far as it would go before timeout).
Language: C++. Python timed-out at depth 3.

Key idea: Balance between efficient conversion by spells vs Producing the Spells (10 pts for converting efficiently, 5 pts for each depth earlier of brewing potions)

My eval function was to prioritize efficiency in conversion. I wanted my AI to convert the whole board like the gold boss as far as possible. This was done by giving an efficiency bonus of 10 points to the eval function when efficient conversion (gain of 5 points and above) is done before turn 30.

After a successful brew, I would terminate my simulation straightaway for that branch. The score would be (depth remaining)*5 + potion brew value + efficiency bonus + inventory score.

Inventory score is similar to the algos above: 1 for tier-0, 2 for tier-1, 3 for tier-2, 4 for tier-3.

If no potions are brewed at the end of the depth, then the score will simply be the efficiency bonus plus the inventory score.

I learn the first 6 spells for certain, and after that, I do a DFS of not learning any spell vs learning spell 1, 2, 3, 4, 5 and 6. I pick the action which gives me highest returns. After I brew potion 5, I do not learn any spell as the focus is to complete any potion asap.

In order to reduce excessive branches, I have a heuristic to determine whether a branch has been done before, and if so, the search terminates for future branches. This heuristic is based on number of rests since start of search, number of tier-0 to 3 ingredients, and search depth.

1. Additional pointer: In order to “force” my AI not to use the lousy beginner spells of converting only 1 ingredient to the next tier, I had an inefficiency restriction. Basically, only after every brew or rest I reset this inefficiency restriction. Basically, my AI is only allowed to do 1 inefficient conversion after every brew or rest. This greatly helped the AI to pick the better paths and also serves to restrict the number of possible game branches as well.

Was an overall tough challenge. Easy to code the AI, but the optimization and heuristic evaluation required was intense. Great competition!

[valcodi]

Hi, it was a great contest, thanks a lot!
Ranked #98, using a DFS approach with iterative deepening (so no beam search :D)

Usually I reached a depth of 6-7, two optimizations improved it significantly from 4-5:
- After REST, in the next turn only the ‘unlocked’ spells are available
- Eliminating duplicate game states with a hash set
I also implemented the algorithm in an iterative manner with an array as the stack, was not sure if the compiler would do it.

Tried a lot of things, like tweaking the evaluation, predicting the endgame or the enemy, but nothing really improved the bot. Guess you can go only so far with a suboptimal approach, sadly I haven’t heard of beam search until yesterday or so, but then it was too late.

But after all, thanks again for a great experience!

[alchemsti]

Thanks CG team!

11th in Silver in a last minute push.

I only noticed the contest once it was about half over. Oops. Still I decided semi-spontaneously to participate.

I liked that it was very simple to get started, and the first two wood leagues were easy to get out of.

I didn’t really search – I went with trying to pick the best move with a complex eval function. This was apparently a mistake, as search with a simple eval function seems to have performed very well.

In the early leagues, I just worked out how ‘far’ I was from a potion, with the base spells, and moved towards the best “DPS” (gold / turn). Improving that by factoring in needing to rest and tracking back got me into low silver, I think.

I think added buying spells. I judged them by counting the ‘value’ of ingredients they produced versus used, bumping them further if they were repeatable, and if they didn’t need any ingredients to be cast (as those are always applicable, and presumably valuable). I wanted to factor in a penalty if they required too many items.

I also added the tax and bonus afterwards. I think this worked fairly well. I later put a time factor in (which seems a really important thing in multiple places in the game). This got me to middle of silver, I think.

The biggest problem was that I didn’t take into account the new spells, except if one was immediately applicable.

So, I did a fairly big transform of doing a search (sort of guided, but not really) to find how far away potions really were. This got me to about 500, I think. It had some bugs, and I think was not very efficient.

I then changed things in kind of a big way again, unifying my eval to evaluate the world, and just trying all moves. This was quite last minute. In it I use my exact potion distance, and just combine the money I have with a mix of distances to the nearest (by tweaked DPS) of all potions. I like this because it unifies resting, casting, and buying potions. I put in some special cases, like checking if I would win (6th potion and more gold) and boosting that.

Here tweaking made a big difference, but I hadn’t set up local testing, and submission was so slow, I just kind of winged it, but got a pretty good improvement.

I didn’t consider the opponent at all.

I liked that the contest was different; I didn’t like that debugging / tweaking was so hard – in other games I’ve been able to often see where my program did something clearly wrong – this one seemed much more slightly different balances that might have gone differently in different cases. It also just didn’t feel very creative overall – but that may have been because my basis wasn’t solid enough.

In any case thanks to CG, the participants, and all the people posting here, as it’s great reading!

[anon72424297]

Rank : Somewhere over the rainbow league…

First of all Thanks for the contest, it seems to was really fun.

Here’s my PM:

• 10 days before the contest on the Fr chan:
  dwarfie dare me to do the contest in clojure. That sounds great.
• The week before the contest:
  I read clojure courses, clojure’s documentation, write some clojure code, do CG puzzles in clojure, start a CG multiplayer game in clojure, sleep in clojure, eat in clojure, see parentheses everywhere…
• Day 1:
  I discover the rules, seems cool.
• Day 2:
  I code my first bot. It seems ok, so I submit it… Bad ! Bad, bad, bad, bad ! What a shame to have such a bad score in wood league ! So I look a bunch of replays, and my code seems to timeout at the first turn about 50% of time ! And of course, impossible to reproduce in the IDE… But reading the discord, I saw that another player encountered the same issue, and had pushed a simple “BREW 0” in clojure in the arena with the same result. The staff is on it, I just have to wait…
• Day 3:
  No clojure yet in arena. So I transpose my clojure code in c++ to reach bronze league and see the full rules.
• Day 4:
  Not yet.
• Day 5:
  The silver league is open, but I’ll be patient.
• Day 6:
  Clojure ! Where are you ?!
• Day 7:
  The gold league is now open, and the doubt assail my mind.
• Day 8:
  Should I stay or should I go (in c++) ?
• Day 9:
  The legend league is open, and I see my motivation take its flight to better places…
• Day 10:
  I start to code a little something in c++, but I don’t have faith.
• Day 11:
  I lose myself in my code, and see I will not have the time to finish. So I go to bed.
• Day 12:
  I sleep.

Conclusion: Meh.

Anyway. See ya on chat/forum/discord or at the next contest.

[Smekarn]

Mid gold (#204), Python.

Thanks CG for a fun and addictive contest!

Silver -> Gold

Changed from DFS to BFS was only able to visit ~1500-2000 nodes so max depth was about 5-7.

Since many bots seem to take the shortest path to brew (leaving them with empty inventory after a brew) my strategy was to learn the “only + spells” before my opponent. Resulting in opponent needing more turns after a brew.

Realizing this shortcoming in my own bot, I required some ingredients left after a brew (except the 6’th brew).

Gold low -> mid

The starvation strategy I used in silver league didn’t work at all in gold. I hard-coded a few spells that fit together well with other spells and could pay a little to get those. Otherwise just learn the first 7 turns.

After a hint from @Qoo I implemented a bunch of lookup tables where inventory was represented as an int (instead of a tuple as I had before). This gave me only ~x2 the performance (I expected much more).

I also predicted the opponent’s next move in order to reduce my search tree.

Had issues with timeouts in the arena so I ended up breaking after 40ms (it didn’t solve it all, but it got better). Normally there’s a few turns where I don’t find any path, in those cases I cast the spell that increase my inventory score the most or rest if I have 3 or more exhausted spells.

I did try to use a priority queue but didn’t find a good way to score my nodes. I’ll have to investigate beam search! Overall, I’ve learned a lot, thanks CG and those of you that streamed on Twitch!

/Smekarn

[JBM]

I got dragged in a contest. That hadn’t happened in a long time

I ended #138 #136 (so upper Gold), quite better than I expected considering the experience lag I’m starting to accumulate in multis.

As for strategy, I’ve got the same run-of-the-mill BFS that I streamed get me out of Wood-1, just faster, deeper, and with an actually reasonable heuristic. I simulated a single opponent step maximizing finisher moves.

I’ll write a more in-depth postmortem in the week.

[Raf]

I also tried linear algebra! I was so hyped when I found it!
I tried to go further than that. The thing about changing from one base (ressources) to another (spells), is that you need the same dimensionality (4). That means you can only translate to a base of 4 spells. (Squared transition matrix)

If k is the number of spells you learnt, that’s ((4 + k) choose 4) sets of 4 spells.
Second condition is that all vectors must be L.I (linearly independant). You can filter those sets to keep only the one that have 4 L.I. vectors.

Once you have that you can compute the inverse matrix for each set, which allows you to translate one combinations of ressources to a combination of spells (new base).

I then converted the potion (difference with my inventory) to every single base that I generated before. As you said, when translating one vector of ressources to a vector of spells, sometimes you end up with negative values (which mean negative spells), which is wrong. I filtered those.
Once that I sorted them by two things, sum(spells) + max(spells). total number of spells and number of times you need to rest.

Starting from the base with the lower score and until i found a path I did:
A* from [0, 0, 0, 0] to [#S1, #S2, #S3, #S4], #S1 #S2 #S3 #S4. being the number of times i had to do the spells S1, S2, S3, S4 respectively.

• neigbhors are simple to generate, just +1 to one coordinate. In order to check if a neigbhor is valid you have to translate it back to ressources base and check along the inventory properties.
• L2 as heuristic, so the algorithm tends to do one spell at a time, S1 S2 S3 S1 S2 S3 rather than S1 S1 S1 S2 S2 …

Great thing is here that A* is fast, compared to BFS, and the heuristic fits the new bases really well.

It managed to work. Unfortunately some paths were unfeasible and I sometimes had to go through 30 bases (30 A*) to find a suitable path.
The second wrong thing about it is that as i mentionned, you are limited to 4 spells for this technique. Sometimes best solution uses more than 4 spells.

And at the end it was taking longer than my BFS. But god it was such a blast to apply linear algebra!!

Python3, around 2k ranking. I spent way too long trying to speed up my code for BFS, caching as much as I could, heuristics, distances, neigbhors. It was still not enough to go deep enough. #PythonLetsBreakUp.
That’s why I went for that linera-algebra-exotic approach on the last days even tho I didn’t have much hope as the limits were pretty clear from the start.

Always a blast to participate CG contests. Can’t wait for next one! GG to everyone, love reading the post contest feedbacks!

[NitMpez]

228th overall - 148th in gold

I normally just throw something together quickly in java, but wanted to try C++ this time, so I gave that a go. My program was pretty basic, just did a BFS (wanted to do a beam search, but ended up worse, cause I’m horrible scoring stuff). This got me to silver fairly easy.

Crappy scoring:

#define get_score(price, depth, invTot) (price*10-(depth*9)+invTot*2)

From there, I made some optimization improvements because I heard @eulerscheZahl talking about doing a single add for inventory. Thanks @Counterbalance for showing me unions, cause this helped make this happen. I ended up with the following struct/union which handled my inventory, total inventory, tier1+ inventory, score and the learned at the end just kept track of the last spell I learned since I only expanded learning spells on my first depth 0. I did this because I was only reaching around depth 6 to start.

struct Tiers{
    char val0 : 6;
    char val0_o : 2;
    char val1 : 6;
    char val1_o : 2;
    char val2 : 6;
    char val2_o : 2;
    char val3 : 6;
    char val3_o : 2;   
    char tot : 6;  //total
    char toto : 2;
    char t1plus : 6;  //total tier1+
    char t1pluso : 2;
    char pscore : 8;  //price or score
    char learned : 8;  //spell i learned
};

union Delta { uint_fast64_t value; Tiers tiers;};

constexpr uint_fast64_t neg_check{0x0000202020202020}; 
constexpr uint_fast64_t overflow_mask{0xffff3f3f3f3f3f3f};

So with the above masks, I was able to do a single add to update everything and use my mask to clear out my overflow bits. I was also able to do a single check to see if any inventory values were negative as well.

node->inv.value = (node->inv.value + entities[node->mv.id].tier.value) & overflow_mask;
if(!(node->inv.value & neg_check)){}

This helped performance quite a bit. To reach depth 8, I ended up using another 32 bit integer to store what spells I’ve used, and basically, if I rested, only cast the spells I’ve used. Line of thinking here, is if I’m resting, I want to use a spell I’ve already used. I shouldn’t rest and cast something I already have available.

My learning was awful, I always learned 8 spells at the start, as this gave me the best results, and I picked spell by running my same code and storing my 20 best results. I then tracked what learned spells I used the most and would grab a rank 1 spell 2 ahead, and rank 2/3 1 ahead. Really the only other things I added, was doing basic enemy prediction in my first 10ms to depth 5. I would store the min depth they could reach any brew, and would reduce my score based on how much quicker they could reach a brew before me.

That is pretty much it for my first crummy C++ contest submission. Was fun, I normally just throw something together and that is it, but I really enjoyed brainstorming some ideas with other coders this time. Thanks for taking time to chat with me.

[Gronahak]

I actually transposed my matrix of spells to be able to use more than 4:

initial inventory :  [3 0 0 0]
wanna prepare potion [1 3 1 1]
available spells:
[[ 2 -1  0  0  4]
 [ 0  1 -1  0  1]
 [ 0  0  1 -1 -1]
 [ 0  0  0  1  0]]
path : [0, 5, 3, 1, 1]
5 x [-1  1  0  0] partial inventory : [-2  5  0  0]
3 x [ 0 -1  1  0] partial inventory : [-2  2  3  0]
1 x [ 0  0 -1  1] partial inventory : [-2  2  2  1]
1 x [ 4  1 -1  0] partial inventory : [2 3 1 1]

The variable ‘path’ is what I compute and it tells me how many times each spell should be cast.
3 problems arose :

• some partial inventory contain negative numbers
• this tries to compute the exact inventory for the given potion i.e. it tries to get rid of excess ingredients to hit exactly the required number for each ingredient
• some coeff were negative

I managed to find a workaround for the 3rd point by using the fnnls module (Fast Non Negative Least Square).
Problem is that I wasn’t allowed to use this module in the contest so I switched to BFS when I saw that x)

[wala]

It was a really fun a contest (the graphics were impressive). Thanks to CG as always. I ended 19th and java 1st.
It was my first beam search and my first efficient use of timeout during a contest (i set the limit to 45ms and had almost no timeouts).
One thing that always puzzled me, in the beam search algorithm, was the sorting at the end of each turn (sorting possibly thousands of elements to only keep the 200 firsts appears to me like a possible loss of performance).
So to avoid sorting i had 3 arrays :

• one for the 200 ways i’d keep.
• one for the corresponding scores (sorted).
• one for the corresponding hashes.

For each new calculated way:

1. if its score was greater than scores[0] (the lowest score) => i did a binary search in the score array.
2. if it was found => i look for hashes with the same score (to prune duplicates).
3. then eventually i add the way, score and hashcode in the arrays and shift down the lesser elements.

My ways were byte arrays :
[price sum, brew nb, round nb (repeat count as 1), ing0, ing1, ing2, ing3, action nb, idAction1, idAction2,…]

For the java users :

• I almost don’t use anymore List, Set, Map… I have small utilities to use array instead of collection (basically the first element of the array is the number of elements in the “list”). It avoids boxing/unboxing, the creation of “useless” objects (Integer, Byte…), to clear a “list” you only set the first element to 0…
• I always implement the @Neumann trick [JAVA] JVM memory issues in the first round : create a lot of objects then call the garbage collector. Otherwise even if i avoid object creation i always have GC timeouts.

PS: One small criticism, it was hard to make more than 2 complete submits the last sunday.

[Raf]

Haha damn that’s nice!
Cool to hear someone else had similar ideas !

[NinjaDoggy]

NinjaDoggy - 68 legend

Thanks for the contest. It was a lot of fun!

Overall I wasn’t too happy with my bot this contest, so I’ll share only the parts I was proud of:

Search:
I used BFS as opposed to Beam Search and still managed to search incredibly deep with the “secret sauce perfect pruning” I kept hinting at in chat:

If the game consisted of only casts/brews/rest(and a predetermined set of tomes)

I think I’ve basically solved the problem of getting to a specific inventory, set of potions brewed, and resulting tomeCastableBitmask in the shortest number of moves.

The problem can be thought of as a shortest path problem in an unweighted graph(each edge has length 1)

The BFS state consists of 3 things:
-the Inventory(10 bits,0 - 1000 because there are only 1001 distinct inventories possible)
-a bitmask of potions that have been brewed(5 bits, 0-31)
-a bitmask of tomes that need to be refreshed(technically up to 46 bits if you learned every single tome)

So there are up to 2^51 * 1001 nodes in the graph

and each node’s edges are simply all the possible actions(rest,cast,brew)

Start with the initial state and BFS out
3 ways to prune a node from being added into BFS:(All 3 pruning techniques are “perfect” in the sense that they won’t remove any potentially optimal paths)

Pruning Technique 1:
Hashset to check for duplicated state(this is the most obvious one)
The key insight to pruning methods 2 and 3, comes from the fact that we don’t really care too much about the tomeCastableBitmask. Specifically, we know that one state is 100% superior to another state if the inventories and potionBrewedBitmask are the same, and the tomeCastableBitmask completely covers the other:

Example:
State with:
inventory = 5
potionBrewedBitmask = 10010
tomeCastableBitmask = 11111111

is strictly better than a state with:
inventory = 5
potionBrewedBitmask = 10010
tomeCastableBitmask = 10110111

2.So as a result once we’ve reached a node with a all tomes off cooldown, we can prune all nodes after it that have the same inventory and potions brewed

3.If we reach node A without all tomes off cooldown, we can still prune all nodes B after node A
as long as they have the same inventory and potions brewed
and distance to B > distance to A
(more details below)

Pruning Technique 2:
For each combination of inventory and potionBrewedBitmask
store if there has been a state reached with a perfect tomeCastableBitmask(right after a rest)

States that have inventory,potionBrewedBitmask that has been reached previously with a perfect tomeCastableBitmask can be pruned!(because there is a node we’ve visited that’s strictly better than this one, and it had the same or shorter distance)

Pruning Technique 3:
For each combination of inventory and potionBrewedBitmask
store the minimum distance we’ve obtained so far

States that have the same inventory, potionBrewedBitmask with a longer distance can be pruned!

example:

let’s say we’ve previously reached state A:
inventory = 2
potionBrewedBitmask = 00010
tomeCastableBitmask = 0000100100
with a distance of 2

and now we reach state B:
inventory = 2
potionBrewedBitmask = 00010
tomeCastableBitmask = 0010101100
with a distance of 3 or more
this node can be safely pruned because we know we can reach a strictly better state with the same/shorter distance can be reached simply by resting from state A

With these 3 pruning techniques I was able to get my bot to search a much greater depth

While I was trying to find a tierlist for the tomes I ran some offline evaluations that put this to great use:

I fixed the starting inventory to be 3 blues, 0 greens, 0 orange, 0 yellow
and had 11 potions(but restricted it to only brew from the first 5 available ones each time)
so the state became:

-the Inventory(10 bits,0 - 1000 because there are only 1001 distinct inventories possible)
-a bitmask of potions that have been brewed(11 bits, 0-2047)
-a bitmask of tomes that need to be refreshed(technically up to 46 bits if you learned every single tome)

I ran the bfs up to depth 100(to simulate a full game)

and on average it finished in < 500 milliseconds
and rarely did it take more than 1 whole second to compute the shortest distance to all possible combinations of 6 potions brewed out of the 11 with all possible ending inventories

[Sakisan]

#425 global / gold league

DFS

Since I don’t have much knowledge of graph theory and I was using a pure functional language (Haskell) my simulations were just a straight recursive function. Pretty sure that’s DFS, and I assume it wasn’t the best choice but I spent all my energy to get it to gold league. And boy the silver boss was quite the challenge.

At first my simulations were iterating only spells, so no REST/BREW/LEARN actions at all.
The REST action was only factored in by making uncastable spells count for 2 turns (and resetting the other spells in the process).
A branch ends as soon as the first BREW is found. I expanded this later to find a 2nd BREW and to include LEARNs too, but in my final version I excluded the LEARNs again.

I used a few different ways to cap the depth of the DFS: number of nodes, numbers of combinations, turns needed to perform the sequence.
These had to be finetuned precisely otherwise some low hanging fruit could have been missed.

When a node has the same spells but in a different order, I skip it. Other than that I haven’t done any tricks to increase performance.

Only sequences leading to a BREW are kept and compared using a turns/points/inventory ratio.
I had a couple different formula depending on how far the end of the game was.
This required quite some experimenting to get the coefficients right because it’s often not clear what’s better, and the slow submits were stressing me out too because of that.

LEARN

As I said LEARNs were included in the simulation. I allowed one LEARN per path and I would LEARN it right away. This way I would always choose relevant tomes to the current state and I didn’t worry about doing any static evaluation of the tomes.

However some experimenting revealed that learning some random spells up front was beneficial too. And going full on pre-learning allowed me to go deeper in the simulation.

The last bits of developments that pushed me over the silver boss was to pick spells in a smarter way. Either based on what I needed, or counter picking spells that my opponent needed.
If you have spell that produces lots of t1’s but no spells that consumes lots of t1’s then you’re not going to perform well. This doesn’t always work, but it proved effective nonetheless.

BASE SPELLS

Before completely excluding LEARNS, I excluded the 4 base spells from my simulation and worked entirely with learned spells. This worked surprisingly well.It was a big performance boost, since base spells can be used much more often they take the biggest amount of nodes. And base spells aren’t exactly the most productive in terms of inventory value anyway.
After this simulation I did a second shallower simulation with the base spell included, just in case there would be a short path to a brew that would otherwise be missed.
However after excluding the LEARNs I could permit the base spells to be in the main simulation again.

This was my first CG contest and I had a blast! I’m already looking forward to the next one

[NinjaDoggy]

I think one way to deal with sorting is to make each layer a priority queue(or implement a heap for even more efficiency),
and have it poll() the worst node each time you add one over your limit(200)

[murrayr]

242, mid+ gold

Crude PvP search. Instead I used a lot of dynamic programming to calculate (near) optimal spell sequences to brew potions.
For the learn phase, 8 spells, DP to evaluate minimum time to brew every potion starting from zero resources given a spell set. Try to minimise the sum for all potions, with a 3 deep search to get the best future spell set.
For the brew phase, use DP to get (near) optimal spell sequence to complete every pair of potions from current resources, favouring early completion of the first. Do that for both players, then iteratively evaluate the spell sequences against each other to select the best vs the opponents last best choice.
The DP was near optimal because it didn’t try at all combinations of spells used at any given resource set + distance from start.That only seemed to matter very occasionally.

[MichaelPu]

Finished bottom legend, 3rd python.

Thanks for the event, it was fun!

Wood 1: Just tried to buy the most expensive, without even checking if it’s possible.
Wood 2: Read something in the chat about stopping casts at random. Worked perfectly

Bronze:
Python is slow, so I had to come up with great heuristics to compete with the C++ bots.
How slow? BFS reached only depth 2-4.

My logic was to completely ignore the endgame, and focus on overall efficiency.
The key was to realize that you don’t just get score when you brew. Just like in life itself, you are usually born with a lot of resource that’s called “time” and a little bit of other resources.
every turn, the bot converts that time resource to other resources:

• LEARN - converts time value to learned spell value, because it allows you to cast more efficient spells.
• REST - converts time value to active spell value, because it allows you to use efficient spells again.
• CAST - converts time, active spell and ingredient values to other ingredient values.
• BREW - converts time and ingredient values to other score values.

Now all that’s left is to give values to each:
score: well, that’s obvious.
time: just usual total score gained during the game / total # of turns. turned out to be around 3 - 3.3 per turn (=TURN COST).
ingredients: (1,2,3,4) * PERCENTAGE * number_of_duplicates^CONST1
percentage was about 0.85 (to implement that you gain additional value by brewing) and CONST1 around 0.95 (to avoid getting stuck with inventory of oranges or yellows that you can’t get rid of)
active spell: TURN_COST / num_of_spells (by using spells you gain “debt” that you have to repay when you rest)
learned spell: That’s the most important one. Because if you’re stuck with bad spells, no matter how much lookahead you do, you’re stuck with a bad hand.

So learned spell = total gain in ingredients by using spell * estimated_turns_left * REPEATABILITY / (#_of_known_spells + 1)
REPEATABILITY represents how many times it can be used on average in one cast, based on the space requirement in the inventory:

REPEATABLE_SPACE_REQ_2_MULTIPLIER = 30 / 11 # (0 * 2 + 1 * 2 + 2 * 2 + 3 * 2 + 4 * 2 + 5 * 1)/11
REPEATABLE_SPACE_REQ_3_MULTIPLIER = 15 / 11 # (0 * 3 + 1 * 3 + 2 * 3 + 3 * 2)/11
REPEATABLE_SPACE_REQ_4_MULTIPLIER = 10 / 11 # (0 * 4 + 1 * 4 + 2 * 3)/11
REPEATABLE_SPACE_REQ_5_MULTIPLIER = 7 / 11 # (0 * 5 + 1 * 5 + 2 * 1)/11

SINGLE_SPACE_REQ_1_MULTIPLIER = 10 / 11 # (0 * 1 + 1 * 10)/11
SINGLE_SPACE_REQ_2_MULTIPLIER = 9 / 11 # (0 * 2 + 1 * 9)/11
SINGLE_SPACE_REQ_3_MULTIPLIER = 8 / 11 # (0 * 3 + 1 * 8)/11
SINGLE_SPACE_REQ_4_MULTIPLIER = 7 / 11 # (0 * 4 + 1 * 7)/11

(Obviously the statistics are way too simplistic, but it was enough…)

This scoring system, in spite of the extremely small lookahead, brought me to be absolute 15th (during day 3), and kept me in the top 80 until legend league opened, so I only had to fight the gold boss.

GOLD:

• Implemented beam search with a buffer of up to 700.
• Used numpy to represent the potential future states as vectors.
• Encoded inventory and actions as integers (blues1 + greens21 + orange21^2 + yellow21^3), this way actions were a simple addition that’s natively supported by numpy.
  when trimming, didn’t sort the arrays (complexity of O(n*log(n))), but just deleted anything lower than average score until it was shorter than the allowed buffer (complexity of O(n))
• Cleaned duplicates after that.
• Dropped the active spell heuristic to not overcomplicate the already complex coding with vectors.

It resulted in lookahead of 10-15 steps which were more than enough.

• Added simple checking of when the opponent can brew every potion, and added penalty for brewing after that
• Added checking if opponent can brew 6th potion and max score at that turn
• Added additional scoring for learned spells that checks which ingredients are already produced and used
• Some more small tweaks etc.

All this effort to get up ~ 40 places and beat the gold boss.

LEGEND:
Everything seemed random. Except the top ~20 bots who always won, I seemed to win about half of the battles. All the bots surpass human ability, doing very logical and super-efficient moves. Even more strangely, my bot was relatively good against people in mid-legend, but pretty bad against people on the bottom. It caused a weird phenomenon that my bot had 2 relatively stable ranks - one at the very bottom, and one at about 35-40th. Seems like the fluctuations at the last 10 minutes of the contest dropped it from 40th place to 50th, from which it was doomed to dive to the bottom.

Learned a lot during this contest, and had a lot of fun!
May you all use your turns wisely, not just in the contests, but also in life

[Paikan2068]

Congratulations, and thanks for the explanation about spells and such! Definitely gives ideas to try, and to eventually think in other ways next time! I’m not sure to understand the way you calculated repeatability of spells. Especially how do you calculate the multipliers? My understanding for space_req_3, is that you could use it with 3 elements, 6 elements, and 9 elements, to create respectively 1, 2, or 3 elements, but I don’t understand how to get 15 / 11. Did I miss something?

[PonyPonyCodeCode]

99th overall (~32th now by tweaking some magic numbers)

I started the contest with a decoupled MCTS as described by jolindien in the Xmash Rush PM (XMash Rush (CC07) - Feedback & Strategies). I had a small eval at depth 10 and the result was not very good (around mid gold). Thinking about it now, I had some serious bugs in my engine and my MCTS could have gone higher.

Anyway, I threw it all away 2 days before the end and I did a beam search as everyone. I was 2nd gold 2 hours before the end so I submitted again and lost 15 places. ;-(

Once the multiplayer game was opened I changed a few magic numbers and was just below the gold boss. After that, I was pushed into legend and finished 29th. I guess the number of games for a submit is too short in gold. I struggled to reach the boss before the end of the submit and now I’m 50 places above!

I reach legend with a classic beam search and completly ignoring the opponent. The beam width is 1000 at depth 1 with a decay of 80 by depth and a minimum at 400. I have around 30 000/40 000 nodes with a depth between 10 and 15. My eval is also quite simple:

• 1 to 4 points for each ingredient in my inventory
• 2 * price * 0.99^depth for each order
• 10 000 if the 6 potions are completed

I just have 2 special cases:

• I learn 5 spells 0 at the start of the game
• If I have a learn in my path without brew before, I did first. I read this suggestion in the chat but I don’t think this helps much.

Thanks to CG for this great contest!

[BlitzProg]

I meant to pay for a specific spell in the spellbook. Doing it consumes a turn, but my beam search processes the exploration as if it already had it unlocked, so I had to compensate by making the exploration from these nodes worth less.

[MichaelPu]

Thanks!
Let’s take a spell that takes the spell with 3 spaces. It can be cast:
0 times with three options (0,1,2) of the spots that are according to the requirements,
1 time with 3,4,5
2 times with 6,7,8,
3 times with 9 or 10
There are a total of 11 options in total.

Again, the statistics are not correct, but it’s better than not differentiating between them at all.