Fall Challenge 2020 - Feedbacks & Strategies

I reached #43 legend using smitsimax; this algorithm was definitely not a good choice for this contest, and without any modifications, I think it would have trouble reaching even high gold because long, precise sequences of turns that maximize inventory value are extremely important in this game, and smitsimax just cannot find them (or might never revisit them because of random terrible rollouts in the same subtree and the need to expand nodes). My plan was to completely rewrite my bot during the week, but due to real life, I had time only during the weekends - so instead, knowing I couldn’t compete for the top ranks, I decided to try to somehow make smitsimax work.

I used smitsimax only to reach a fixed depth (anywhere between 10 and 25 depending on the version of my bot; the depth didn’t make any difference) and then evaluated the state: ([my score] + [my inventory]*0.5 - [opponent’s score] - [opponent’s inventory]*0.5 + [±25 points for winning/losing]). The results aren’t between 0 and 1, so I “fixed” that by using a higher exploration parameter. When the servers were working properly, I could reach ~100K nodes in each tree.

The most important thing that made me even reach #1 back in bronze league was that my rollouts weren’t random; for every possible inventory (there are only 1001 of them) I precalculated all the possible brews and casts and sorted them (brews first, then casts that add more value to my inventory), and when expanding a node, I tried the actions in this order.

That was good enough for high gold; for legend, I needed to somehow make smitsimax learn spells; at first, I tried adding actions “learn (1-6)”(only usable once per rollout) and “cast learned spell” to my smitsimax, but that didn’t work too well, so I switched to learning the first 8 0-cost spells instead. However, to reach mid-legend, I had to use another approach: statistics and if/else. I wrote a simple beam search (width ~3000; who knows, maybe it could do better on the leaderboard than what I submitted), I let it run overnight millions of times for random combinations of potions and spells, and I stored the result. I found average score per turn for every spell and every combination of two spells, copied these stats into my bot, I was willing to pay a tier0 ingredient for 0.08 score per turn, and I added some simple conditions for when to learn - depends on number of already known spells and the score of available spells.

On the final day, I noticed that my smitsimax used the order of spells that I precalculated for myself also when expanding opponent’s nodes; fixing this bug made me drop 15 ranks and for example my 80%+ winrate against wlesavo disappeared (expanding randomly was even worse than that), even if the evaluation of nodes in the endgame was much better. That made me realize that I had absolutely no idea why did my bot work. Back in bronze, I also noticed that at depth 15+, my bot played better if it could brew one potion multiple times, which is somewhat understandable unlike the bug with my opponent simulation. I couldn’t bring myself to reintroduce these bugs for the final submit.

13 Likes

I will share my inventory too.

constexpr uint64_t INGREDIENTS_CLEAR =        0xFF00FF00FF00FFUL;
constexpr uint64_t INGREDIENTS_ONE_NEGATIVE = 0x80008000800080UL;
union Ingredients {
    uint64_t value;
    char values[8];
    // use 0 2 4 6
};

so to add to invetories I can to this

Ingredients a, b;
a.value = (a.value + b.value) & INGREDIENTS_CLEAR;

to check if there is any negative i do:

(value & INGREDIENTS_ONE_NEGATIVE) > 0

what about repetable spells?
multiplying work’s too :star_struck:

(value + ((spell.value * repeats) & INGREDIENTS_CLEAR)) & INGREDIENTS_CLEAR;

Simply and fast!

15 Likes

Not much to add to what has already been said. This is my first CG contest in over 3 years, and it was fun for me.

Placed 450ish, near the bottom of gold, but for the amount of effort I put into it, I’m very happy with that. I took this on as an exercise to better learn PHP since I just started a job that uses PHP almost exclusively.

My strategy was simple: pure BFS. I didn’t get to implement pruning, so it’s not a beam strategy. I’m sure that would have helped me progress further. I did hash states and discard duplicates, though. Obviously it would be pretty easy to refine the code once it hits multiplayer.

An optimization that I implemented that I haven’t seen mentioned yet (forgive me if someone else said this and I missed it) is that I gave a declining weight for LEARN. The action was weighted heavily at the beginning of a game, and got no extra weighting after about the 15th turn. This seemed to work well for me.

  • danBhentschel
5 Likes

Thanks for the contest, you got me hooked once more after that Spring Challenge.

I am glad that it’s over, I can finally sleep :slight_smile: My goal was Gold, yet I finished ~300 Silver. That silver boss was a tough nut.

My solution was in Java and used a BFS. As visited check for each turn the solution looks up if the generated ingredients were already generated; if so, only enter the next level if the way to get to this list is shorter. Total lookup limit was 6 spells (Adding REST is only done afterwards) … this way my BFS was hardly visiting more than 450 nodes (without learn) before having fully explored the full graph. Shockingly that still took around 15ms, I spent a lot of time reducing needs for object allocation.

Where I believe that my bot failed at:

  • What Spells to learn. I added some heuristics like if there’s a good antagonist in my spellbook, etc. (to optimize for repeat casts)
  • Use the 1s at the beginning to do anything useful
  • Evaluate and adapt to the opponent, this is only done at the last brew

With the 50ms timeout any runtime with a garbage collector seemed to be at a disadvantage.
I only realized halfway through that Coding Game is a hard real time problem!

So I guess I will pick Rust next time - I used C++ in spring and it was a nightmare.

Looking forward

2 Likes

5th Place

A fun challenge with great visuals. I really enjoyed it.

My entry uses 2 distinct strategies depending on the “phase” of the game we’re in.

Endgame (once we’ve brewed >= 3 cards)

Depth 13 search for both us and our opponent. Find the different turns that either of us could end the game along with the highest scores achievable at each turn (whether the game ends or not). Then we decide our optimal sequence (usually goes for the earliest turn we can finish, but sometimes we play “defense” if we see our opponent can end the game earlier). There are some interesting game-theory/mixed-strategy type endings that can come up but I didn’t get a chance to fully investigate this part.

Early-mid game

Depth-first search (depth 10-12 usually, but varies depending on how fast previous turns were completed). Uses early pruning after the first few levels if the “score” of the node we’re on is < best_score_seen_at_this_depth - threshold).

To value a node, my scoring heuristic uses:

  • inventory score (1/2/3/4 pts but with some adjustments penalizing “large” 3pt or 4pt holdings (“large” varies depending on the brew cards available)
  • our action cards (used only when we’ve brewed <= 1 card). We estimate how many points per turn our set of action cards can generate beyond our search horizon. To do this, we first get the net effect of all our cards if they were applied the maximum amount without input/inventory constraints. We then add a number of turns depending on our input “deficits”. For example, a deficit of -2 for the 4pt good would require 7 extra turns to fulfill using the base cards. (Thanks to csj for the idea of viewing action cards as “multiplications/transformations”)
  • brew cards already purchased so far (scores are “discounted” over time to encourage earlier brewing)

I also added artificial constraints to the game to greatly simplify the game tree. These avoid searching paths that were unlikely to produce good strategies, such as:

  • after we’ve brewed >= 2 cards, only search paths that learn <= 1 spell
  • we can only learn spells in “ascending” order
  • in the endgame, you can’t learn any new spells (this constraint could probably be relaxed a bit, but it simplified the tree a lot)
  • the tie breaker is “brews” first, then “learns”, then everything else. i.e. if we decide to “cast” a spell, then later in that path we don’t need to consider learning any spells that we could have learned earlier. We also only look for “learns” in the earlier levels while we’re searching.
14 Likes

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!

3 Likes

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!

6 Likes

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!

3 Likes

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.

14 Likes

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

4 Likes

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

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.

3 Likes

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!

7 Likes

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.

3 Likes

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)

5 Likes

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.

16 Likes

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

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

17 Likes

#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 :slight_smile:

5 Likes

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)

1 Like

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.

2 Likes