Code4Life - Feedback & Strategy

12th
I implemented a random search (Monte Carlo).
When starting the turn at a machine, I might use it. Then I go to another machine to use it and to a third one to use that too.

Samples: give score for having samples. Choosing sample ranks is hardcoded. I randomize how many samples I take, as I might want to get samples from the cloud as well.

Diagnosis: first diagnose undiagnosed samples. Then randomize, how many samples to move to the cloud and how many to take. Returning a sample results in a negative score, as it costs time to do so and I prefer to have a sample that I might fill later when the opponent frees molecules.

Molecules: again: random. Take any amount and type of molecules. As it is hard to fill a sample having e.g. 5A (very unlikely that I choose 5A), the probability of taking molecules is not equally distributed, but depends on my own samples, samples in the cloud and carried by the opponent.
Score is awarded for taking a molecule, when only two are left and the enemy needs both.
The available molecules are time-dependent, so that I can simulate the opponent freeing them.

Laboratory: there are only up to 3! = 6 possible combinations to use the samples (assuming that you don’t go away with a sample although you could complete it).
For each of these orders I try to complete them, add expertise if possible and add the molecules back to the molecules. So I decide here, if my random move at molecules was a good idea.

I also check if I blocked the opponent with my chain of molecules:

foreach (Sample s in enemy.Samples) {
	if (s.Health == -1)
		continue;
	List<int> times = new List<int> ();
	for (int m = 0; m < MOLECULES_COUNT; m++) {
		int cost = s.Cost [m] - enemy.Expertise [m] - enemy.Storage [m];
		if (cost <= 0)
			continue;
		int startTime = -1;
		while (startTime + 1 < maxWaitTime && Machine.MOLECULES.Available [m, Math.Min (maxWaitTime - 1, startTime + cost)] >= cost)
			startTime++;
		for (int i = 0; i < cost; i++) {
			times.Add (startTime + i);
		}
	}
	times.Sort ();
	for (int i = 0; i < times.Count; i++) {
		if (times [i] < i + enemy.ETA && times[i] < 4) {
			score += weightBlockChain * (s.Health + weightGainExpertise);
			break;
		}
	}
}

some score is also given for having any molecules left (but not too many, I need free space to fill my own samples), preferably where the opponent has little expertise.

As I didn’t have time to fiddle with the parameters myself, I let the brutaltester try them out for me by randomizing my parameters and compare the results in matches against myself (fully automated).
Keeping all options open when randomizing my action and let the scoring function decide helped to make my bot do actions like collect molecules first and then go to diagnosis and get the sample for my storage or using newly gained expertise when pushing more than one sample without implementing it.

On the last day I added some basic waiting at the laboratory to block, but never found a replay where it happened before the end of the contest. But it worked, as I know now (frame 200).

I also have code to submit undiagnosed samples when I am about to lose anyway (hoping to be lucky), but didn’t get it working in time.

12 Likes

I’ll keep it short.

I had a fun approach. 5 days before the start, I started fresh to learn a programming language I knew nothing about: Ruby. I heard good things about it, I heard it was “Python”-like, which is a language I am more than familiar with. And I used Coding Game as a crash course.

I spend those five evenings reading the first chapter of the book “learn 7 programming languages in 7 weeks” and then just joined the competition.

This was truly a crash course, thanks to the competition I had to look up a lot of syntax, and would use and reuse the constructions I learned. This was such a good practice! Ended 10th in Silver, happy, given the constraints :smiley:

6 Likes

Simple and funny game! Overall great contest with change of rules for better gameplay.

Solution (C#)

Started of by trying simulation without any luck because I didn’t figure out how to model unknown samples. Changed to heuristics on this last sunday and had more luck, ending at 69th Legend. My solution is based on 2 important functions:

  • int[] FindBestCost(Robot r, int[] availiable)

    • Finds the cost of each Molecul for the best subsett(Most health) of samples held by this robot, given the availiable Moleculs. This returning null indicated no found solution.
  • List<Sample> FindBestSamples(Robot r, int maxRank)

    • Takes all the player’s samples, all cloud samples and 3 of each rank, but only 1 from rank 3 (from the samples module with health of each rank beeing: 0, 9, 29). Removes all above maxRank, orders descending by health and returns the first 3 which has any solution by using FindBestCost(..). This could result in just 1 possible Sample, but lack of time stopped me here.

Then I used these functions on the different modules.

Samples

Find the best samples where maxrank is given by Experience thresholds 0, 9, 15. Then, pick up samples from the best set which is not in the cloud.

Diagnosis

  • Diagnose everything.
  • Discard samples not in the best set.
  • Pick samples in the best set

Molecules

  • Pick items from the best cost prioritizing blocking the enemy’s best subset (didn’t block one sample in particular, but the best combination he had). Also blocked if enemy needed 2 or more picks to block me.
  • Never waited for the enemy to deliver needed moleculs.

Laboratory

  • Return everything, prioritizing the ones to give experience for others on hand.
  • Always finish all samples (if any was solvable at the time of finished returns)

Also with some optimalization about not going to Molecules if all samples could be finished or going straight to Samples if all samples in the best set were found in the cloud.

5 Likes

Oh wow, this is going to be fun to play with. Thanks for the tip!

What does ELO stand for?

I started off with a simple if-then-else bot that would follow a predetermined path with some heuristics and calculations to figure out what he could make and what molecules to choose. Mostly this was because I really had no idea what the evaluation function for a MiniMax ought to look like for this game. While I was doing this I also wrote the simulation code for when I went to my actual AI. That got me to Silver.

When Silver opened I took a day and a half messing around with a Minimax but never got it to produce useful behavior… moving from station to station was hard to generalize in an evaluation. So I went to plan B. This involved a mini-minimax for each station, plus some linking code (or maybe another minimax) for determining when and where to move when there was nothing to do at the station anymore. All I got done on it was the molecule selecting logic, but that was enough to get to Gold, even though I was still debugging it when I got promoted.

I submitted my dumb bot plus the fixed molecule picker and was 27th in Gold on Friday night. I figured that was a good place to start on my push to Legend when I woke up in the morning. Much to my surprise, I found myself in 2nd the next morning. Before lunchtime, I was in Legend. Everyone who was pushing their bots between those times, I thank you :slight_smile:

The rest of the weekend was frustration. I built my minibot for the diagnosis station but it wasn’t as good as what I had. I suspect that was because it needed to be more integrated with other minibots that I hadn’t written yet, but time was too limited to go all the way with it. I maintained a place between 30-55 all day Saturday and Sunday (leading to hopes of top-50 with some luck), but apparently everyone got better overnight. Finished at #87 in Legend.

Key points of the molecule picker:

  • Brute-force sample combinations to come up with the best samples I could make. This basically tried for double and triple turn-ins whenever possible, even if they might not score as many points. Expertise was the focus. It did not take into account future expertise from turning in the samples, though it should have (didn’t think of it until late).
  • The weighting of the samples differed between me being there alone and the opponent also being at the molecule station
  • Pick molecules for the best sample on my list in order, based on how much are available. More limited molecules are picked first.
  • If I can block the opponent by taking a single molecule, do that before picking for myself.
  • On a related note, if one molecule type only has 1 remaining in the stack, take it preemptively
  • After all that is done, if I still have 3 or more spots available for molecules, see if I can block the opponent with them.

Great contest… it was nothing like previous ones and it forced me to think in new directions.

6 Likes

26th Legend

First version

My first version was a mix between state-machine for the global AI, and a minimax for the molecules pick, I used this until Legend league. My minimax eval was pretty simple :

evaluate(robot) {
  score = 0;
  for (Sample sample : mySamples) {
    if (complete) {
      score += health * 1000;
    } else {
      if (enoughSpaceAndMoleculesOnBoard) {
        score += health * completion * 10;
      } else {
        score += health * completion * 1;
      }
    }
  }
  return score;
}

evaluate() {
  evaluate(me) - evaluate(him);
}

This worked pretty well in the first few days but my AI won’t quit the molecules stand unless it cannot pick any more molecules, so I added the “wait” move and a “trash molecules” component in the evaluation to counter that :

score -= 2 * trashMoleculeCount;

A trash molecule is a molecule that isn’t required by any of my samples. Then if my minimax finds that “wait” is the best move, I let my state-machine decide what to do (pay if something is to be paid, or go pick some samples). I also considered the enemy position with an ETA delay; if for exemple he’s at the DIAGNOSIS stand, I will consider only WAIT moves for his first 3 turns (most pessimistic case).

I wasn’t happy with the results of this version in the Legend league, and couldn’t figure if my evaluation sucked or if the rest of the state-machine AI sucked. Considering only molecules pick in the minimax has a few drawbacks :

  • I would often stay at the molecule stands to block an enemy sample even though it would be better to leave, pay, and keep farming.
  • If you’re at the MOLECULES stand and the enemy is on his way to diagnose some samples, it’s often profitable to wait a few turns for him to diagnose them, and then benefit from his ETA to try to block his samples before leaving.

I could/should have treated those cases in the rest of my AI, but it felt “hacky”. So I decided to rewrite the whole AI from scratch saturday, using only heuristics and a new state-machine :

Rewrite

I remembered Agade’s post-mortem on GITC and started with the most greedy/dumb stuff I could find, because apparently that’s what’s working. It’s basically a priority-based pile of behaviors (in this order) :

  • I’m at the SAMPLES stand ? GO pick some, or go to DIAGNOSIS if I’m full
  • I’m at DIAGNOSIS stand ? GO diagnose the stuff that isn’t already
  • I’m at LABORATORY stand ? GO pay stuff
  • List every possessed/cloud sample, filter those that can be completed in the current state of the game, sort them by (health/leftToPick/killCost) and look how much of them I’m currently carrying. If I carry less than X of them, then I go to DIAGNOSIS/SAMPLES to pick some new ones. X = 1 if I’m at LABORATORY or MOLECULES, 2 otherwise.
  • If everything else failed, I go pick molecules

The molecules pick behaves as follow :

For every enemy sample, I calculate its kill cost; i.e. for each type of molecules, I compute the amount of molecules that he needs to pick, and based on the amount of molecules available on the board I compute the number of molecules I would have to pick to kill it :

getMoleculeKillCost(sampleOwner, sample, molecule) {
    actualCost = sampleCost[molecule] - sampleOwnerExpertise[molecule];
    leftToPick = actualCost - sampleOwnerStorage[molecule];
    if (leftToPick == 0) return 99;
    return boardMolecules[molecule] - leftToPick + 1;
}

getSampleKillCost(sampleOwner, sample) {
  return MIN(getMoleculeKillCost(sampleOwner, sample, ...))
}

I filter the samples that I can kill for sure; i.e. the ones with a killScore lower than the number of molecules the enemy still needs to pick (I can kill it faster than he can complete it).

  • There is a sample that can be killed, regardless of it’s health or my score or anything else ? GO kill it
  • Else, try to complete some of my samples

I order my samples in order of completion : if sample1 needs more than 0 molecules of type A and sample2 gives expertise on A, then I chose to complete sample2 first. I completely ignore sample health in this sorting.

Once a sample is chosen, I pick the needed molecule with the lowest kill score, because it reduces the risk of it being killed by the enemy.

One of the latest addition was to first look for killable samples at the very beggining of my state-machine algorithm. If I can kill one enemy sample, I will go for it regardless of what I’m doing or where I am.

Issues

  • Because I always chose to kill an enemy sample before farming my own, I sometimes would kill an enemy sample and block myself without any possible completion of my own samples because of all the extra trash molecules I just picked… I Tried to add some conditions to discard some possible enemy kills but it failed.
  • Because I chose to attack whenever I can, I sometimes lose a lot of time travelling the map just for killing a rank 1 sample. Again, I tried to add some conditions to restrict this aggressive behavior but it would work poorly.
  • My AI lacks tons of features that I didn’t have enough time to implement correctly but where mandatory for the top players imo (see next part)

Things I wanted but failed to implement

  1. Don’t pay for samples that release molecules needed for the enemy
  2. Account for sample collision during sample choice to fasten the farm process and reduce movements between stands (don’t take samples that all requires the same type of molecules)
  3. Consider projects and try to finish some in late-game with rank 1 samples when you have the opportunity

Conclusion

Again, I lost tons of time on a solution that I couldn’t make work. The rewrite was good but too greedy/stupid. With more than 2 days on my second version, I would have been able to add the extra features it needed, but I poorly managed my time, even though I had lots of it for this contest (I spent several dozens of inefficient hours on this one …)

The game was fun, even though it a bit too RNG dependent. It was hard to have good feedbacks on its AI’s level. Sure you can see the results with a feature that drastically improve your AI, but the fine tuning part felt like blind tuning.

Thanks CG and see you at the next contest.

14 Likes

Guys, for those of you who enjoyed the game mechanics of this contest, you should checkout the tabletop game Splendor: https://boardgamegeek.com/boardgame/148228/splendor This is very similar to the contest: I suppose someone at Codingame know this game, given the numerous similarities. The game can be played with 4 players and has a less partial info: you see part of the samples at the beginning, no need to diagnose.

1 Like

Looks like you had a similar idea to mine with your alogorithm for finding a safe turn at molecules.

First I got the required molecules for a sample: required = cost - (storage + expertise). Expertise and storage adjusted for the optimal set of samples to turn in.
Then for each value > 0 I calculate the distance with distance = available - 2*required + 1

Next, distribute the number of moves the opponents is away amoungt the lowest elements.

If all distances are > 0 then you get resistence = min(difference)
Else you get resistence = sum(elements < 0) - count(elements <= 0) + 1

A positive resistence is the amount of “wrong” moves you can make before you can be blocked on a sample.
A negetive resistence is the amount of “wrong” moves the opponent must make so that you can guarantee to complete a sample.

So a resistence > 0 means that sample can’t be blocked (as long as you take the molecule with the lowest distance each round).

You can also check based on the molecule slots the opponent has left. For buffer = available - required the opponent needs more than min(buffer) to block the sample.

1 Like

#5th Legend / Java

I missed the first langage place winned by Egaetan, congratulation ! :wink: Follow and comment the final fights together on the chat window looking for who will reach the 3rd position was really fun.

It was very close and third place switched a lot (1st Agade and 2nd FredericBautista were unreachable, great job !). Finally, Egaetan came back to the 3rd position and Simon_v arised from the underworld so i ranked 5th :stuck_out_tongue_closed_eyes:.

Feelings

This contest was really fun, seemed very simple but was not ! I like the new contest duration that let us time to work on it even if we have a work and a family. It was also interesting as it doesn’t look like any other multiplayer game or contests i have ever done. No reuse of any old code for me.
Thanks also for the changes made in silver league that revive the interest of this contest according importance to science projects useless before.

Strategies

Wood to Bronze
Use a simple state machine with 4 operations associated to the modules. My first goal in each contest is to unlock quickly the rules and implement a good data model not wasting to much time on strategy as rules can really modify it.

  • SAMPLES : get as many samples as i can with rank determined by my current expertise and go to DIAGNOSIS
  • DIAGNOSIS : diagnosed those samples and go to the MOLECULES
  • MOLECULES : get 10 molecules trying to complete first the best sample determined by their health and not pay attention to sample i can’t complete
    Then go to LABORATORY
  • LABORATORY : produce all the sample i can trying to complete the best first, go to MOLECULES if samples i can complete remaining, otherwise go to SAMPLES

Really simple and quick to implement and did the job even if my bot seemed really silly always running in circle ^^.

Bronze to legend
I made only one change on my state machine to fix my first issue :

  • when i can’t complete any sample, my silly bot was turning around to infinity and beyond :smile:

push the worst samples to the cloud and go to SAMPLES to refill if no sample left

What was really fun on that contest was building step by step heuristics from watching my bot doing silly things and oponent doing well !

My priority here is not to improve my score but to find a way to lower my opponent score : attack !

I first tried to implement a minmax/alphabeta/killer on my molecule collection but without spending time optimizing my model it timeout at depth 4… My last failure with MonteCarlo algo in Ghost in the cell contest dissuaded me from following this way.

So i implemented an evaluation function to choose the best molecule to collect

  • For each molecule
    • Compute the worst available molecules considering my oponent will take the same molecule as me
    • Idem for the enemy
    • taking into account distance to go to MOLECULES if oponent is not here
    • for each sample i can’t produce yet
      • compute need using expertise, storage and available
      • assigns some points if need > 0 considering the risk i could be blocked by the enemy and applying a ratio depending on the earning to favour the best samples taking into account science project completion indeed !
        • URGENT do it now cause enemy can block
        • POSSIBLE enemy can not block for the moment
        • RISK you can try but in the worst case you will be blocked
        • NO COMPLETE few point if we need but we know the sample can not be completed as there is not enough molecules available or my storage will be full
  • For each enemy sample do the same
    • and apply a ratio < 1 to favour completing my sample before blocking oponent
  • Add to that my future score production – oponent future score production * K
  • Add malus if i lose sample completion possibilities and a bonus if it is the case for the oponent

My evaluation favours best sample completion, blocking, collecting molecule needed by a lot of samples.

Surprisingly and despite the fact i choosed my ratio and constants with just feeling, it works very well and bring me to legend without any difficulty and push me to the first place before Agade in silver using a rank 1 strategie for sample to favour science project when many player just take rank 2. I was so surprised i pushed on Wednesday a bad code to hide my strategy.

Legend
Before legend and after, i improved my heuristics with so many little things to improve my bot :
• Compute best production ordered using recursion
• Compute best sample to get from cloud ordering by points and cost
• Compute worst sample to push in cloud from number missing molecules
• Add transitions from LABO to DIAG and vice versa
• Add an ending strategy on each Module
• Wait strategy on DIAGNOSIS and MOLECULES if some molecules will be available soon (only if my future best score will be greater to the oponent to avoid him waiting for my defeat ^^)
• Detect oponent waiting and wait too if my future best score is higher or equal to the oponent score (lot’s of equality with Agade :stuck_out_tongue: )
• And many others…

My best improve was on my evaluation doing it another time considering i produce the current samples i can produce to optimise my molecule collection.

I hope untill the end i could earn the Robot as i was 2nd on Monday morning, but failed… I do not know if the first 50 will have some goodies or t-shirt. I really hope :smile:

7 Likes

15th Legend / Java

This is the first time I reach the Legend League in a multiplayer contest :stuck_out_tongue_closed_eyes:. What I like in this contest is that you can reach the top without rely on compute power which is disadvantage to languages other than C++, Java,…

At first, I aimed to implement Finite State Machine in Java then port it to Lua later for T-Shirt, but I realized no T-Shirt in this contest so I sticked to Java and improve my heuristic bot overtime by mixing top bots strategies.

Thanks CG and Roche for the exciting contest.

1 Like

17th, go
I did almost the same thing, as everyone else, who used state machine, except one thing:
At molecules, I didn’t focus on sample completion, but on molecules. I gave score to every pickable molecules based on following things:
-Least amount needed to block one of opponent’s completable samples.
-Amount needed by opponent to block one of my completable samples.
-Amount of samples blocked when picked the minumum amount.
And picked the one with most score.
I think that was the only smartish thing in my code, the rest was a whole bunch of if, else spaghetti. I tried to cover all the game situations with if elses.

2 Likes

Bowlful of Spaghetti ~#56

Interesting contest without obvious interactions with the other player (indirect blocking to slow them down). Really liked the balancing updates in the middle of the week. But overall I was struggling to add new ingredients into my already full bowl of spaghetti. After a while of ad hoc programming, my code got so messy I did a complete rewrite from java into python on Friday :dizzy_face:

Noodle:

  • Magic numbers: 12 18 base strategy (early snowball effect?)
  • Swap/Take/Discard samples at diagnosis
  • Take molecules based on rarest left
  • Permutate samples completed to find ordering that gives best health

Sauce:

  • ‘Responsive’ sampling (if enemy starts going above rank1 early, relax expertise constraint on taking higher ranked samples to keep up)
    • Not sure if this actually gave my bot an improved performance…
  • Construct virtual samples of required molecules in order to block enemy research
    • Thereafter my bot just treats blocking the enemy as ‘completing’ samples without considering expertise
    • Only valid if I can take the required molecules before the enemy can
  • Added bonus health to samples: +b/k^(expertiseLeft-1) if the gain contributes to a project
    • Used to sort samples to complete/pull from cloud

Final Thoughts

The scaling seemed to be better this time with more people getting promoted into Silver league (although not sure if this was due to allowing more people to play around with the rebalanced game).

Thumbs up to Marchete for his innovative strategy researching undiagnosed samples. Implemented it on the last day (increasing to rank2 if expertise high enough) but my bot performed worse (couldn’t get out of bottom 20 legend). Perhaps some additional constraints were necessary, e.g. Use this strategy if behind else continue blocking enemy and completing diagnosed samples || hoard molecules while using this strategy to slow enemy down.

Looking forward to this being released as multiplayer (as it’s quite different from the currently available multiplayer bot puzzles) :smiley:

8 Likes

Here is my postmortem.

Please point out any mistakes/unclear/unexplained things to me in the chat.

As a point of feedback, the game was interesting but it was unfortunate that there was such an amount of randomness to it. It made it hard for AIs to distinguish themselves on the leaderboard. You could always lose/win games by drawing terrible samples over and over or finishing projects by chance. Any kind of randomness pulls the win rate towards 50% and this game had maybe a bit too much of it.

28 Likes

Thx and congrat @Agade the pm is well written and I’m excited to learn things you mentioned in the post!

Great read on your PM Agade. :slight_smile:

I don’t see much point on documenting my disappointing result on this contest, however after some interest was shown in chat, I wrote an article about a fun side quest I did on the last day, which allowed games like this one to sometimes happen, albeit too rarely to help my rank. I hope you guys enjoy even if it’s technically not about the game itself.

26 Likes

Here is my postmortem .
Please send me comments when unclear/mistakes… on the chat
I don’t write often in english since my studies are over and now i have two kids…

7 Likes

That was my special feature too :slight_smile:
The idea was to be almost sure I won’t be blocked early and will be able to do both samples (since I arrive 2 turns before the opponent). This way, I could get a lead on expertise and potentially outrun my opponent. Unfortunately, the draw could be very bad.

I love Splendor game and I know the best thing to do in this kind of game is to gain expertise early and forget about points. That’s why I focused on rank 1 samples even before the balance update.

What I did early was to compute the best order of samples to do, to take into account virtual gained expertise. Maximum 3!=6 permutations. This took me to top 50 on Wednesday. Any small improvements I tried to add the next 2 days were bad.
Then I left for holidays. I finally finished after 400th rank. Quite frustrated since I thought I could get to top 100 if I could code during the weekend :slight_smile:

I have an issue when collecting molecules from the molecules module. It is my understanding that when you get a molecule using the print("CONNECT A") command the player’s storage_a variable is automatically updated. This does occur most of the time but occasionally the storage variable will stop being updated and will always be 0 despite the fact that I have taken many molecules. This causes my player to run out of room but when I print out all the storage variables they are all 0. I am not sure if this is a problem with the game or a problem with my code but I have no idea how to solve this.