Fall Challenge 2020 - Feedbacks & Strategies

[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.

[Paikan2068]

Ok! Thanks a lot, that made that a lot clearer! And you’re definitely right about basic statistics being way better than no statistics at all in that case!

[ThomasNicoullaud]

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

In others words, “I will take myself”

[jft63]

Thanks for sharing! Do you have any idea if your implementation is faster than @eulerscheZahl’s one?

[BrainSolver]

Hi,

For the list of possible actions for Casts, I use 46-bit bitmaps (representing the 46 Cast cards) :

• one per player for the list of learned casts.
• one per player for the list of Casts not already played.

For each of the 1001 inventories I also store a 46-bit word containing the list of Casts that can be played with this inventory. (I store this in an unsigned long long)

This allows me to do functions like this one:

bool Game::isRestituable(int player)
{
    return learnedCasts[player] != notPlayedCast[player];
}

void Game::rest(int player)
{
    notPlayedCast[player] = learnedCasts[player];
}

unsigned long Game::castActionList(int inventory, int player)
{
    return notPlayedCast[player] & canBePlayed[inventory];
}

To count the number of possible cast actions, I do :

unsigned long long castActions = game.castActionList(inventory, 0);
int count = __builtin_popcountll(castActions);