Fall Challenge 2020 - Feedbacks & Strategies

[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);

[kovi]

12th

At the start I felt that the search space is too big and depth is neither possible nor feasible, as it seemed hard to predict opponent not to mention the later learns/brews ;). So I started MC with quick success (1st on saturday). Soon I realized that speed matte, so added state encoding/bitmagic to reach 1M+ checked states, and then with heuristics (eg. learn only 1) reached/explored depth 11 properly. Probably entered into parameter tuning too early, and even with that in gold the approach slowly lost momentum and I lost motivation.
Finally I decided to rewrite to beamsearch. But wanted safe legend first, so as a last resort I focused on reasonable opponent prediction. Running mc for a shorter time for the opponent earliest brews, then asses those separately as if were picked. Choose my best first action which has the best average score considering the various best first enemy picks.
This occasionally led back to top20, but with careless resubmit I missed to first legend migration waves.

I had no choice but finish beamsearch. After it started to work, I had to reevaluate everything and many of my earlier the heuristics didn’t work at all. Fortunately for beamsearch the speed/depth was not that important any more, enough depth (15+) can be reached easily. For the record my beamsearch had maxdepth 20, width 10k, learning only on first 3 steps, and eval is very similar to every else’s.
Last day I calculated the stats for learnable spells, and adjusted to prefer (pay for) the better ones.

It was definitely not my favourite contest. From the beginning I felt that interaction between players was too low, so it is too much a solo optimization game with relatively narrow possible approaches (more tc-ish than cg-ish). Nevertheless the strong competition made it challenging. Congratulations for the top3, they played a different league!

[reCurse]

I was concerned/curious about how the timeout issue would affect the rerun. So based on rerun data download by @eulerscheZahl (thanks!), here is the timeout leaderboard:

Name                 TO   G    %
[CG]SaiksyApo        45   791  5.69%
MichaelPu            21   784  2.68%
The_Duck             19   792  2.40%
omu                  19   809  2.35%
Gonny                16   816  1.96%
NinjaDoggy           15   765  1.96%
Rafbill              14   805  1.74%
Csipcsirip           13   828  1.57%
MSz                  13   790  1.65%
bourgeof             13   808  1.61%
aCat                 13   829  1.57%
sensaur              13   788  1.65%
Rounddice            12   857  1.40%
jolindien            12   886  1.35%
egaetan              11   764  1.44%
Shun_PI              10   790  1.27%
Zorg1                10   808  1.24%
zasmu                9    877  1.03%
KawattaTaido         9    822  1.09%
maras                9    790  1.14%
viewlagoon           9    807  1.12%
_Royale              9    796  1.13%
bowwowforeach        8    817  0.98%
ValGrowth            8    812  0.99%
dbdr                 8    778  1.03%
y_kawano             8    801  1.00%
reCurse              7    888  0.79%
Magus                7    798  0.88%
DomiKo               7    956  0.73%
wlesavo              7    801  0.87%
Bondo416             7    779  0.90%
aropan               6    967  0.62%
Nerchio              6    700  0.86%
tanzaku              6    810  0.74%
eulerscheZahl        5    782  0.64%
Neumann              5    767  0.65%
Vadasz               5    773  0.65%
RiSuS                5    839  0.60%
trictrac             5    791  0.63%
SlyB                 5    644  0.78%
iwashi31             5    734  0.68%
ichyo                4    860  0.47%
MichalOp             4    802  0.50%
takumi152            4    836  0.48%
Illedan              4    832  0.48%
VincentBab           4    795  0.50%
pb4                  3    838  0.36%
YurkovAS             3    838  0.36%
BrunoFelthes         3    761  0.39%
wala                 3    790  0.38%
NightLuna            3    767  0.39%
k4ng0u               3    809  0.37%
ucarts               3    815  0.37%
Fangel               3    785  0.38%
blasterpoard         2    825  0.24%
Redstrike            2    785  0.25%
Jirotech             2    809  0.25%
siman                2    815  0.25%
bin101               2    787  0.25%
Jeff06               2    509  0.39%
Agade                1    827  0.12%
Risen                1    788  0.13%
eki                  1    549  0.18%
scolen               1    756  0.13%
kovi                 1    839  0.12%
karliso              1    863  0.12%
betrue12             1    796  0.13%
delineate            0    954  0.00%
Valdemar             0    804  0.00%
Mazelcop             0    910  0.00%
sumoru               0    799  0.00%
AT274                0    769  0.00%
Skril                0    785  0.00%
Marrggta             0    802  0.00%
ClosetAI             0    781  0.00%
yukine3              0    595  0.00%
Samsonov             0    823  0.00%
Manwi23              0    835  0.00%
Saelyos              0    719  0.00%
SeJ                  0    611  0.00%

[Manwi23]

46th Legend

Nice contest, nice game. This time it was more… well… mysterious - in both OoC and Spring Challenge the game was somehow more visual, “go there and collect that”, making it more interesting to watch or easier to spot bugs / unwanted bot behavior. At least for me. This game forced me to finally start using CG Benchmark and Brutaltester more rather than just watching a lot of games myself

Anyway, I guess what I did was not unique - I chose C++ and I started with DFS with iterative deepening (up to some fixed number of nodes seen) with simple heuristics - the score of the state was a sum of (discounted) potions’ value I made and inventory value (calculated as sum of i * tier_i). At first the discount was about subtracting 1 from the potion value every time I got deeper in the search, then tried with the usual gamma thing and realized it was noticeably worse than the first idea. Now as I read other postmortems I realize I probably should have tried more different gammas, but well. Oh, and for the sake of speed I was learning spells only at depth 1 (as the very first action).
When I finally debugged this it took me to low/mid gold.

To get to the legend league I did a bunch of upgrades.

1. I switched to actually measuring time rather than calculating the nodes and was ready to cut the search when there is no time left, but apparently the desired beam width and depth in beamsearch were enough to keep me away from timeouts.
2. Beamsearch - I went for width 2000, and with depth of 25 I’ve rarely seen a timeout / cut in depth. I changed the sorting heuristics to calculate inventory as (i + 0.5) * tier_i, it somehow helped a lot. I still was learning spells only at depth 1.
3. Forced learning spells as the first action - in the final version for 7 first rounds. It was a huuuge boost.
4. Taking opponent into account - if my opponent had 4 or more potions done, I calculated how many rounds are there still left in the ‘shortest time’ case - that they will do the rest of their potions as fast as they can. Then went just up to this depth in the search for my action and calculated the score there as in the endgame (below).
5. Endgame management - it wasn’t the most beautiful one, but well - I assumed the game to be close to ending if either me or my opponent had 4 potions done, and then 1. doubled beam width 2. switched to a different heuristic function for calculating state value - it was the old value for not-finished-yet game states, big number * (potions in the same manner as before + inventory value, this time tier_1 + tier_2 + tier_3) for ended games.

I stayed up to 4 a.m. yesterday (today?) to watch my bot beating gold boss. I wanted to be sure I’m in the legend league.

It was my first Legend, so overall - not that bad, I guess

[_CG_SaiksyApo]

I’m pretty sure all my timeouts are NPE that I wasn’t able to debug due to C# being compiled in Release in IDE But atleast I’m first

[phord]

I had a similar 32-bit integer of inventory and costs.

struct Pos {
    uint32_t p = 0;
    // Create a new pos from a sub-calculated 32-bit value
    explicit Pos(uint32_t x) : p((x + 0x40404040) & 0x3F3F3F3F) {}

    Pos(int a, int b, int c, int d) {
        p = (static_cast<unsigned>(0x100 + a) % 0x40)              +
            (static_cast<unsigned>(0x100 + b) % 0x40) * 0x00000100 +
            (static_cast<unsigned>(0x100 + c) % 0x40) * 0x00010000 +
            (static_cast<unsigned>(0x100 + d) % 0x40) * 0x01000000 ;
    }

    // I only used this for log output to display inventory counts
    int operator [](int i) const {
        int x = ((p >> (i*8)) % 0x40) ;
        return (x > 0x30) ? x - 0x40 : x;
    }

    // Test for valid positive numbers (inv counts)
    operator bool() const {
        if ((p & 0x30303030) ||                          // Negative is invalid
            (p + 0x05050505) & 0x10101010) return false; // Positive overflow (any item > 10)

        // Total must be < 11
        auto x = p + (p >> 16);
        x += (x >> 8);
        x &= 0xff;
        return x <= 10;
    }

    Pos operator+(Pos const & rhs)
    {
        return Pos{p + rhs.p};
    }

    Pos operator-(Pos const & rhs)
    {
        return Pos{p - rhs.p};
    }

    bool operator >=(Pos const & rhs) const {
        Pos x = Pos{p - rhs.p};
        return !(x.p & 0x30303030); // Negative is invalid
    }

    bool operator >(Pos const & rhs) const {
        return p != rhs.p && *this >= rhs;
    }
};

To determine if it was possible to take a move, I would add the cost to my inventory (pos for position). Then if the result had any negative numbers, it was invalid.

I stored my Brew costs as positive numbers so I could easily compare my current position to the cost of a brew. This was simpler as >= than simply >, so I used that.

// Try to brew
if (inv >= brew.cost) {
    new_inv = inv - brew.cost;
    // ...

// Try to cast a spell
auto new_inv = inv + spell.cost;  // works for negative and positive numbers
if (!new_inv) continue;           // not valid.

[Razielwar]

93 th - 13th Gold

Thanks for this great contest really beautiful! It was a fun contest even if i was a little disappointed not reaching legend.
CodinGame you are victim of your sucess, more than 7000 players! But what a pain when we submit to wait for ranking… For the next contest i hope it will be faster

From Wood to Bronze

Java bot with a little heuristic

• if i can brew a potion brew it
• try to cast to build ingredient necessary for the best one

Bronze to Gold

I started developing a BFS and on monday i switched programming langage to give a try with C++ as i noticed it will be hard AI with search depth and i didn’t want to spend my time like in other contests fighting with Garbage Collector and timeouts.

On tuesday night my bfs was ready and doing well.

As explained by other players i used a BFS with pruning on inventory state as there are only 1001 inventories possible. For that i used a map and a hash computed like this :

hash = inv[0] | (inv[1] << 4) | (inv[2] << 8) | (inv[3] << 12);

Merge condition

• take the one with the best eval
• if equals take the one with the more spells castable (that not need to rest)

All my possible inventories are created statically and my states in my bfs only store the hash key. I use also bitsets to know which potions are brewed (10010), which spells need to rest (000100001110), which spells are learned and which learned spells need to rest. Thanks to Egaetan to share with me those tips!

For the evaluation, i used a decay with a Coefficient ^ depth * eval. Eval take into account score and inventory 0.05 * (a + 2 * b + 3 * c + 4 * d).

Note: as i have seen above perhaps i have not spent enough time in the evaluation function, i will try again in the game and hope to reach legend!

First turns LEARNING

I play my bfs but i force the first turn to be a learn and choose the best one for 7 turns
Why? because the boss was doing that

Middle game

I play my opponent during 15ms and reach above depth 12-16 playing 30-40k nodes. I would like to use that for defense not aiming potion i think my opponent will take before me or agressively to steal potion i can take before him but it didn’t work really well. Finally, i used it to build a best score array to know if i can make the last potion without risk. If i can i add extra points to the evaluation to force my AI to play this action.

The i play my witch during the remaining time reaching 16-20 depth playing 100-110K nodes.

End game

If i have brewed more than 4 potions and my score is better than the opponent + 5 i lesser the decay coefficient to force my bot to brew potions faster.

Conclusion

Really fun contest and time consuming
I have now some knowledges about c++ so that’s great and i think i will try other contests with this langage.

Thanks CodinGame of that great contest, i’m waiting for the next one

[aCat]

Individual ranking: #67
School ranking: #1 University of Wrocław
Language: C#

Thanks.
First is first - I need to thank quite a lot of people, for the contest itself, for valuable advice, and just a friendly talk and support. I am starting with huge thanks for the CG stuff for organizing the contest (@TwoSteps ). I would also like to thank the members of our Polish CG Community (including but not limited to @Zylo , @Nerchio , and @TheSkolar ) - if anyone wants to join, just let Zylo or me know.

Last but definitely not least, I would like to thank our students who participated in this contest. I hope it was fun for you (even if it was a mandatory AI4Games exercise list…). In particular, huge congratulations to the awesome coding team forming our university’s representation: @DomiKo, @MichalOp, @maras, @Manwi23, and my colleague @MSz . In my wildest dreams, I didn’t imagine having six people in legend. But I love you even when you don’t get such high scores, don’t worry.

My code.
I did (surprise) beamsearch. I started the contest with, of course, some fast-bronze short python code, then switch to C# and ‘wasted’ >two days encoding everything on bits. Inventory / each spell / tome /potion to fit in simple ints. With a little bit of overthinking, too early, and with multiple inefficiencies on the way, but I was really curious can I do this. I could, I did, and with small extensions I stuck with this representation till the end (with only minor copy-paste inconveniences along the way).

Simultaneously with representation, I was working on some basic BFS, gradually rewriting the engine and adding crucial parts. After finally encoding spells, I tried searching towards the endgame score, i.e., rupees + tier>0 resources. At that time, timeout issues kicked in, and I had to deal with the garbage collector and reusing memory (thanks to @Illedan for helping me). Then comes beamsearch, and some more or less viable approaches to make evaluation function dependent on the inventory related to potions. I had some days of no coding or just small bugfixing, and the gold league came out. I discover a stupid serious bug and, after a day or so, get gold finally. Ah, and of course, I always learn free spells for some constant number of first turns.

In gold, I finally implemented counting how many potions each player brew, and tried some pvp strategies. I got the following: when I discover the opponent has one potion to win, I make for him a BFS depth 5 ending with the first potion. This gives me a threshold, and I perform BFS for myself up to this depth, trying to maximize my score. I slightly extended this with search when the opponent has 2 potions to win and can make a potion in the current turn. I did the things ‘weird way’ because of my limited computational resources. That’s for the defense. For the offense, when my beamsearch discovered terminal state in the previous turn on depth <= 6, I performed BFS optimizing endgame score ending on the first score better than what the opponent can make in the current turn (1 depth search with pots/spells). At this point, I had about eight situation-tuned BFS variants copypasted in my code and reached the character limit, so I had to cut out the unused and commented ones :-).

Then comes a long, last day of using CGBenchmark and optimizing parameters. (And constantly being in nearly-top gold.) Finally, the function turned out to be pretty simple:
PotionValue * 10 * 0.97^depth + Tier0 * 4 + Tier1 * 7 + Tier2 * 8 + Tier3 * 15
I also added some small fix to check my one-turn win, and increase initial learning turns to 10. I tried using hashtables, but they didn’t improve.

I don’t know when (I was finally sleeping, @Manwi23 kept watch) the code was promoted to legend. In legend, I just discovered that as I aready removed one of my expensive heuristics out of evaluation, I can increase search depth limit. Now (using beam size 1000) I usually reach depths 9-11 with ~80-100k nodes per turn.

The game.
I didn’t like it. At all. It was a really awful game showing out what is worst at CodinGame.

The game required really fast performance, cutting out most of the slower languages users except some expert wizards. It had again (remember the post mortems from the Spring!) very low interaction between the players. Not fun. I still feel somehow bad that I made it an exercise list on my AI course. If not for the contest, and knowing it in advance, I wouldn’t use it in my classes.

And the visualization, although graphically nice, was terrible to analyze. It really should have some debug mode with even plain circles and arrows. Pausing each frame to understand which jumping potion comes from which cauldron to which order was a pain. Really.

On top of that comes server issues, extremely lengthy submissions, dead chat problems, etc.

Summary.
The contest was really awesome, and I will always remember it, but sadly not because of the quality of the game - the reason will be people and interactions, making it a great community/social experience. This cat thanks you all.

[Anatoli]

Hi there,

interesting game. Timeout spend the most time how by most players.

Ended somewhere in the middle of silver.

Way to bronze:

needs just running code with 2-3 lines for some decition and brewing.

Way to silver:

Here was needed simulation. I used BFS.

• Have started with saving all data for each SimulationStep, and also REST as own Step. At some point i have seen, that REST could be handled with one property for next Step instead of making a new REST Step for simulation
• Timeout was the biggest problem. Possible ways to solve
  • Time for Simulation. Have maked it to 40 seconds, and if the round taked 45 seconds, the next round – timeout 35 seconds.
  • Count of simulations. During the content one of the Steps could take up to 30 seconds.
    • Why? – the memory. Special – garbage collector has starts on one Step to work, what has occured, that one Step was so long.
    • What have i maked? – 1. Each 1.000 Simulations execute garbage collector by self. Was a part of solution, but it have spend a lot of time, why i could only execute 16.000 simulations per round.
    • Later – i have executed it only once per round, but still maximal 16.000 Steps per round.

That was not enought to come in silver. I was around top-100. Then i have maked a learning. Always first 5 rounds – learn. And i was in top 10.

Because of other players, who was better than a boss, i could‘n come in silver, but have reached it, as i executed the code on next day, where no many players was on.

Silver:

Here was no changes in game rules. So it comes to performance of code and tactic.

What i have maked:

• Previously i changed castable state of spells and saved it for each step. I don’t need it, while i always have access to current state of my spells and can extract thhe id of spell from action. If it is castable - do it, else – REST,
• At the end by each Step i was going throught all spells, checked, if by this executing my inventory had valid state (all over -1 and sum of items smaller as 11) and added it as new Step. I have added it only if it not increase my maximal size of steps of 16.000, because i would never come there.
• Also by each step i checked, if i can make some order with current inventory, and have removed the order from list, because the quickest way is found. All orders found – no need to go over all 16.000 simulations.

At this point i have reached 18.000 simulations without timeouts. After the event end i could make 60.000 without some Timeout problems. Don´t know why, 50 ms should be always 50 ms.

Order decition: here was the question, what to do – become most rupee or close it as fast as possible. I ended with getting most rupees while i or other witch have not maked 3 orders, then switch to make quick orders in hope to have more rupees. Here could be played a long with decition to win by most players.