Fall Challenge 2020 - Feedbacks & Strategies

Contests
#112

My path to be top #1 … In silver

So hello dear reader, Zakaoai here !

My final ranking are :

  • #544 / 7011 Global

  • #1 / 1913 Silver

  • #9 / 592 JavaScript

  • #191 / 2730 French Player

Introduction

For me, this challenge was the challenge of Performance against the choice of your programmation language.

I choosed JavaScript but was it a good choice ? Certainly not but I choosed it anyway.

The challenge

This challenge was really enjoyable. The rules and objectives are simple but there was a tons of combinations possible. Futhermore, the challenge theme was my favourite. I’m a huge fan of Zelda’s series

I will now explain how I reached my final Rank #1 Silver

Wood

Well for the Woods ranks, I need only some few functions. The goal was to brew only 1 and 3 potions.

I made function for :

  • Dealing with my current inventory

  • Filter castable spells if I have the ingredients

  • Brew only the best potions in the list

Bronze

For the bronze league, I do some overkill functions that I thought at the begining of the challenge can be a good BFS but it wasn’t.

The main idea was to precalculate with my inventory all the self sustainable of castable spells.

With this 1st idea, I reach fastly the limit of JS performance and that was at this moment of the challenge where I ask some questions to the Community.

Thanks a lot for all your advices Mazelcop.

Bronze to Silver

So after all, I rework my first Idea by starting with 5 states ( 1 by potion) and search the best spell’s chain that can help me to brew the potion.

My “fake” BFS make up to chain of 5 spell’s chain and I can repeat it 3 times their combinations. After I got the list of all actions, I store it in a List and play these actions without checking the game state.

NB : don’t do that :wink: The game state update every turn. That’s why it’s a “fake” BFS.

But with some luck, I was pushed in Silver.

Silver Before Gold

So here I am the final League but there was multiple “state” of silver league because before Gold we were a lot of player in it.

An easy code rank #500 Global - Best Than Nothing

So since I obtain my silver rank, I decide to erase all my code and write a simple function I called it “Best Than Nothing”.

The main idea was : If we dont know what to do, what can be a costless function to play other actions than ‘WAIT’

For this I used for the 1st time and until my last submit the famous META call Learn 8 Turns which mean to learn only at the beginning of the game.

So for the algo of Best Than Nothing


If a potion can be BREW with my current inventory

    I BREW the potion

Else

    I check all spell that I can CAST with my current inventory

    I sort the by the gain of the cast with the idea of price / ingredient [1,2,3,4]

    I cast the best one

If I can't cast a spell, I use REST

With this I was top 500 for at least 1 day. It was a funny joke for me to be this good with such a random function that only focus on production of ingredient.

Silver After Gold + Legend

Then, Gold and Legend League appears. The best player did beat the Bossdorf but I didnt reach my main goal of Gold. At least I’m Top #1 :smiley:

Begin Simulations, BFS For the win ?

So with the code I made, I decided with the recommandation of the community to do an evaluation function.

Not a BFS at first only evaluate one turn of play to do always the best action.

Then, I transformed it into a BFS.

The algo was :


Begin with the Initial State ( Castable Spells List, Inventory)

Add this state into a list

While step below a defined depth (I can't go over 4 / 5 with Beam Search)

    For each states in the list search all child state ( using flatMap I can use only one list)

        Childs states :

            Each Castable spells with my inventory

            Each Brewable potion with my inventory

            Rest

    End For

End While

I try to do a Beam Search to upgrade the performance of my BFS but at the cost of lot of result. I can only achieve Depth 5 with Limitation of 50

Beam Search is a good solution when you know your evaluation of all nodes is good enougth to take only best nodes. And without good perfs Beam Search can’t achieve a good rank.

For this at the end of each For loop, I sort all node and take only the 50 best one. That also kill the perfs when you sort a lot of node. So don’t use sort to do that.

Upgrade Performance of the BFS

The next days after this 1st attempt of BFS was to do all I can for the performance of BFS in JavaScript.

Each day, I talked with community members and I read how many states others languages can check. Before my optimizations, I can only check 1000 states vs 20k after optimizations. Others players can go over 100k states, so it was really frustrating.

So here are all my tips to optimize your JS BFS by order of how I implemented them :

  • Pre Calculate all you can Turn 0 with all data you know ( even in the github project of the challenge)

    • Sum of all possible inventory (1001 possible states) with all known actions

    • Ratio of completion for all Potions with all inventory states

    • All maths function we use multiple times like Math.pow(0.9,n)

  • Create an hashtable of states to duplicate Node (hash based on inventory state and spell state) See binary representation bellow for a nice exemple

  • Use some tips to optimize BFS for the garbage collector and without queue Coding Game Optimizing BFS

  • Use standard function over JS function even if bench dont say so ( JS BENCH sites check only execution performance without thinking of Garbage Collector) so replace map and foreach with simple for

  • Optimize all objects instanciations to minimize impact of Garbage Collector. Use global constant for every string or generic object.

Last Optimization get rid of duplicate array for spells and potions between state

It was the first time I deal with binary operations since I was in school. So it was like I learn again how to use them.

So my objectives behind these binary operations was to never instanciate arrays for all my states and only store a binary representation of those arrays.

So I need to store a global array of arrays of all indexs combination for spells and potions list.

Exemple :

With Learn 8 strat we have 12 spells

So we can think of thoses spells with 1 bit for each spell (0 -> used spell, 1 -> castable spell)

So IIIIIIIIIIIII -> All spells are up. the number is 4095 (2^(12) - 1)

With this, I associate to this number a list of index of castable spell only

IIIIIIIIIIIII -> 4095 -> [0,1,2,3,4,5,6,7,8,9,10,11,12]

IIIIIIIIIIII0 -> 4094 -> [1,2,3,4,5,6,7,8,9,10,11,12]

With this list in global constant, I finally get rid of array instanciation between states of my BFS when I BREW a potion or CAST a spell I only store a binary number.

For the inventory it was an other method. I used 4 bit by type of ingredient. So the math function behind is :


function hashInv(i, j, k, l) {

    return i + 16 * j + 256 * k + 4096 * l;

}

With both of those binary numbers, you can achieve a good Hash of your state. So for combination I did a binary sum of these 2 numbers with a little trick :


(invBinary << mySpells.length) + spellsBinary

I shift the binaryNumber of my inventory with the length of my spells array. You’ll have finally a unique number for all your states.

My Final BFS

Finally here it is. The final representation of my BFS

Node


State :

{

    action,

    myBinarySpells,

    binaryPotion,

    invHash,

    score 

}

Child Nodes

binaryPotion -> Brewable Potions

myBinarySpells -> Castable Spells

if myBinarySpells < pow(2,spell.length) -> Action Rest

Evaluation

Score only BrewablePotion :

Brewable Potion Price + Ratio * Price of the nearest Potion with the inventory after the brew.

Recommendation for future challenge

  • Don’t miss steps. Write ideas but dont rush to code them without thinking if it worth the time

  • Try to translate all game datas to simples objects. A list of castable spells can be seen as a binary number with some imagination.

  • Prepare your generic functions to deal with timeout, logs, some math operations.

  • Split and comment your code as much as possible during the contest. When we need help it’s better if we can explain how we code our solution. Also, evolve a well splitted code is faster than a single function with hundreds lines of codes.

Special thanks to some French CG player who helped me even until the last minutes of the challenge :

  • Mazelcop

  • Fangel

  • Gh0stM4chine

  • All Fr community in CG chat

Finally, I made a YT video in French to talk about my code. How I upgrade all my function. It’s a long 4h30 talk where I interact with some CG player Debrief + Post Mortem

NB : Without new submit I achieve to be gold

#476 Global

#377 / 467 Gold

6 Likes
#113

Don’t you need two separate (independent?) bitsets for castable (not exhausted) spells and learned spells?

1 Like
#114

Hi everyone !
I finished Gold, 389 overall

There’s my postmortem:

I would be happy to have suggestions on it !
Thanks :slight_smile:

2 Likes
#115

How are you getting the path of actions of your AI ? I know how to get it with a MinMax but I have no idea with beam search …
Thks !

#117

Welcome back :slight_smile:

By the way, I finally got my revenge from Coders of The Carribean in 2017 ! :nerd_face:

Fall Challenge 2020

image
image863×302 47.3 KB

Coders of the Carribean 2017
image
image859×305 47.9 KB

10 Likes
#118

I just use a simple vector<Action>.

Pseudo code :

class Node {
    vector<Action> actions;
    Game game;
    double eval;
}

Node parent = nextNodeToExpand();
vector<Action> actions = computePossibleActions(parent);

for (Action action : actions) {
     Node child = new Node();

     child.actions = parent.actions();
     child.actions.push(action);
     child.game = parent.game;
     child.game.play(action);
     child.eval = parent.eval() + child.game.eval() * pow(COEF_PATIENCE, depth);

     addChildToTheListOfNode(child);
}
#119

On my side, I only have one action per Node but I keep a link to the parent.

class Node{
    	Action action;
    	Node father;
    	double score;
}

Thus to retrieve the list of actions, I will loop until the node without father:

public List<Node> getNodes() {
    		List<Node> nodes = new ArrayList<>();
    		Node rootToTop = this;
    		while (rootToTop.father!=null) {
    			nodes.add(0, rootToTop);
    			rootToTop = rootToTop.father;
    		}
    		nodes.add(0, rootToTop);
    		return nodes;
    	}
    }
#120

Wow! I independently invented totally the same approach.

#121

I tried something similar, but not with more success ^^. In order to find better moves, I run 2 BFS for me and the opponent to prune automatically some moves which take more times, and to have another pruning by evaluating the final nodes to eliminate the bad ones. My idea was then to explore those trees with a smistsimax (which performed really badly) or a DUCT (it was better, but still bad).

I still don’t completely understand why it didn’t work, but anyways it was not the good approach and I didn’t have the time / motivation to write something different.

#122

Final rating: 621st place in Silver league, 1177th place in global leaderboard

The algorithm I’ve decided to use was simple BFS. Using this approach, I was looking for the potion I could brew in the least amount of turns. After that I would execute the first action on the path from the current state to the state returned by the BFS. Besides that, during the first 10 turns I would learn a free spell with probability 9/10 (with probability 1/10 I would run BFS). The differences between my algorithm in wood, bronze and silver division were simply some bug fixes and taking into account new rules.
I didn’t like this challlenge, after implementing BFS I wasn’t really interested in trying to improve my algorithm.

1 Like
#123

I don’t entirely understand why did my rollouts work so well either; I also tried sorting the possible moves not by how much they increase the value of my inventory, but by distance from the closest gamestate where I’ve brewed all the potions (either 5, or how many I need to win) while ignoring that I need to rest, which reduced the size of graph to only 32032 nodes. Moves minimizing this distance should be relatively good (I later used this distance to prune the beamsearch when calculating statistics I mentioned in my PM), but it still performed much, much worse (only 30% winrate vs my bot) for some reason I fail to see.

#124

How do you implement vanilla beam search and beam stack-search? Could you please share a link to pseudocode of both? I failed to find good descriptions, free of confusing context like neural networks.

Do you need to use some priority queue (n-ary heap) for the frontier? Then you need to evaluate all intermediate nodes, not only leaves? Is evaluation function the same for leaves and inner nodes?

1 Like
#125

First CG challenge for me. Ended gold 1 hour before the end of the challenge (400th of gold).
I’ve take part in the challenge to learn Rust and i aim for Gold so i’m happy since both of my goals are completed.
I’ve learn in bonus a lot in graph search and real time (So many TOs).
My strategy for the challenge :
2 days before the challenge : made an account CG, did some puzzles in Rust and setup my dev env.
Wood : I was checking all possible actions for the turn, sort them by price and take the first one.
I’ve set security stock of 2 meaning that i dont cast spells if it lower my ingredients below my security stock so my bot had some of each tiers to brew.
I’ve manage to get bronze without a search, i was looking only for the current turn.
Bronze & Silver : First i just add a basic learn that took the production spells. (not repeatable ones). Then i needed a search.
I’ve quickly got a BFS but it was very slow because i each node was big (700 octets) and the copy was taking a lot of time (using smaller type was a big optimisation).
My search had the learns, rest, casts, and was stoping at brews. But it was the first time i had to program a graph search and my code was not optimise at all.
But since i’ve implemented the learn and the repeatable my bot was well place and i’ve got silver when the league opened.
My search was very slow and i knew i had to optimise to even consider sorting between solutions or getting path with multiple brews.
I’ve refactor during 5 days, using bitwise to store the states, heterogenous collections for the spells and brew and a unique spellbook for all the nodes (yes i had a copy of the book at every node before). But it was a pain to add the repeatable casts so i had to roll-back at a version from 5 days ago. (That was a tough call).
Silver to Gold : After the rollback i’ve add some of the optimisations i’ve come up in the 5 days.
Bitwise state, smaller nodes, one spell book.
and i was happy with the performance (Depth of 9, 30 to 50k nodes, 8k solutions found).
I start to add other features like looking what my enemy was doing etc.
But gold was hard to reach…
Then i’ve come up with a rough formula to sort my solutions and i quickly got to the top of silver.
I was about to go sleep (it was the last day at 8 in the morning) but my bot climbed out of silver and i got hype and stay awake to see him reach gold.

What help me:

  • I could run test offline and that was waaaaay faster that submit on CG.
  • Smaller type
  • tests

Where i’ve failed:

  • My node could be smaller (I’ve learn about unions after the challenge)
  • I didn’t use the 1s of the first turn
  • I didn’t profile my code (I wanted to but didn’t had the time to make it work)
  • i didn’t know Rust enough to see the costly operations (mallocs for example).

What i’ve like:

  • Love Rust, the challenge, and the tough competition.

What i didn’t like:

  • All into one file, ive hated this so bad, at the end i was just searching for everything. (My file was 1k lines)
  • The search make your bot harder to understand. (Sometime i look replays and don’t get what my bot is doing and why)
  • Maybe the leagues were too big.

What i’ve wish for:

  • An arena to make bots versus player
  • More chatty bots, plz put your stats into the log ><

Here is one of my matchs : (One that ive won :wink: )


Thanks to CG, and to all the competitors.
#126

~1200 place overall

My simple approach was as follows:

  • at first learn some spells
    • no heuristic to determine the best one
    • learn the first one, not to spend money on that
    • goal: learn 7 new spells
  • then for each move run a BFS
    • no special logic here
    • expand the action tree only if I can cast the spell (also check if spell is repeatable)
    • goal: run till I don’t find a first potion I can brew
  • if I didn’t find a potion to brew in given time - cast a random spell

I tried also running the BFS until the most valuable potion was brewable, but usually I wasn’t able to do so, ending up
doing a random move.

1 Like
#127

I finished #27 overall, and #1 in Python.

I am not going to lie, between the random time outs and the natural speed disadvantage this language has, this contest was a bit frustrating for the Python users out there.

For me, it just meant I had to try and find different approaches to have a chance to compete. I spent a couple days doing just that, trying other things like turning the game into an optimization problem for example, but nothing worked. In the end I think this was just a game where the best approach was to try to model the game exactly in your bot, including not overfitting due to unknown future potions/spells, finding good heuristics to “guide it”, and then just let it do its thing.

I managed to get up to #3 gold on Sunday afternoon with a pruned BFS that got to me ~7-8 depth on average, and then converting this BFS to a beamsearch apparently (I wasn’t there to see it :/) made me stomp the boss and led to my final ranking. A few things I did slightly differently from others, which probably all helped a bit and a lot in aggregate came from being very constrained by the depth until I changed to beamsearch, forcing me to develop a solid heuristic. In more details:

  • I didn’t use 1 but 2 patience coefficients, 1 of 0.95 for your inventory value and one for potions that started at 0.99 but gradually got down to 0.95 as you brewed more potions and got closer to the end game. The idea behind that is that it matters more and more that you brew faster as the game progresses, but doesn’t really matter in the beginning
  • Similarly, my eval of inventory depended on how many potions p I had already brewed, taking only into account for each potion type max(6-p, actual potion number). This helped guide my AI towards not accumulating too much of soon-to-be-worthless inventory. Once I reached branches that led to the end of the game, I only kept those and of course used as the inventory eval what my actual bonus inventory score would be.
  • For learns, for the longest time I just forced my bot to learn a spell during the first 6 turns no matter what, otherwise they would often just start brewing. Ultimately, I added all the different learns you could do in 1 turn or in 2 turns (only allowing to learn on the 2nd turn if you also learnt on the first turn) and then not incorporating learns past that, and this approach when used with a beamsearch with a large depth actually made my bot a smart learner! I removed the 6 turns learn, and it seemed to be able to pick the right combos before starting to brew. Interestingly, @kovi mentioned among the top 30 I was the one that learned the less spells on average, and I noticed that sometimes I even only learned 4 spells and still somehow won.

Once I moved to beamsearch, I only used 150 nodes, the lowest I’ve seen in the comments. I think that was fine-ish thanks to a good pruning, and allowed me to reach a depth of 15-20, which was beyond my expectations in Python.

Thank you very much to CG, this contest was great as usual and I fully understand why contests see more and more participants! A few small points of feedback:

  • I know this was discussed before and I don’t want to open a can of worms, but for contests where it’s basically a simulation arms race, it would be great if languages could somehow be made a little more equal. I hear the old argument of “use the best tool at your disposal”, but being forced to always use the hammer isn’t that fun either. I’m sure there are ways to at least close part of the gap, such as for example a conservative benchmark to C++, compensating for GC time etc… Anyway, only 3/80 AIs in legends used python (but 2k / 7k users), that might be the lowest total yet (?) and either way extremely low when compared to 60/80 using C++ (but 1.5k / 7k overall).
  • That’s more CG being victim of their (again, well deserved!) success as @Razielwar said, but especially towards the end of the contest, commits literally took 2+ hours which made it really hard to roll out several incremental features
  • As others have mentioned, the random time out issues were also a little frustrating
  • More than usually, this felt like a single player game where taking what the opponent does did not matter much
17 Likes
#128

@Magus, why did you decide to add iterative deepening to your beamsearch?

#129

~Top-20 Silver, 560 overall, C#

But it’s not “the low-performance GC-managed language” to blame, it’s my lack of experience with game tree search. (And that Silver Boss was freaking tough!)

In fact modern .NET runtime and library allow you to write quite efficient code. Let me share some tricks.

Action[] actionsFromPool = ArrayPool<Action>.Shared.Rent(actionCount);

Span<byte> bytes = stackalloc byte[sizeof(ulong)];
BinaryPrimitives.WriteUInt64BigEndian(bytes, _data);

bytes[4] = unchecked((byte)score);
return BinaryPrimitives.ReadUInt64BigEndian(bytes);

int castableCount = BitOperations.PopCount(leaf.CastableBitset);

public override int GetHashCode() => HashCode.Combine(_data, CastableBitset, LearnedBitset);
3 Likes
#130
  • Overall: 2355
  • Silver: 1812

To reach the bronze league I implemented a simple algorithm that chose the best potion possible to brew. If there was no potion possible to brew I casted a random possible spell. If there was no possible spells I rested.

To get to silver I did some basic DFS over game states. I also enforced a limit of learning at most 6 spells.

I was not a big fan of this game.

  • First of all was the experience with the game. The rules had some weird quirks that were tedious to implement (e.g. urgency bonus). Game mostly focused on speed and most solutions were very similar (DFS / Beam Search + heuristic).
  • Second of all, the idea of brewing potions is not very exciting. I really enjoyed contests when the game was fun and relatable (e.g. Hypersonic). It is much more pleasurable to write a bot for a game that you would be eager to play yourself.
5 Likes
#131

Because there is little differences between a beamsearch at fixed depth and a beamsearch with iterative deepening (in the code).

And fixed depth is dangereous. Is you fix the depth at 10 for example, you can timeout because you’ll maybe never reach this depth in 50ms.

1 Like
#132

When you are surrounded by c++ but you keep trying to fight ^^

image
image679×684 34.3 KB

By the way, I added a security to avoid counter of my opponent when I think I can win with the 6th potion brewed. And corrected two bugs: wrongly computed bonuses. Pages score completely false, I start to think that this part of my code is useless.

6 Likes