Code a la Mode - Feedback & Strategies

:pie: The topic where you can tell how you liked the challenge, & how you solved it. :strawberry:

=> Coding Games and Programming Challenges to Code Better

Thanks again to the creators csj and Matteh and to the testers eulerscheZahl, Illedan, Nanosplitter and SeebOmega

3 Likes

Nice contest overall.

Few if statements to make it to Bronze, few more to climb to Legend.

What I would like:

  • Different maps (maybe one with a wall to force coop after wood leagues)
  • A better handling of current orders (with an id) to make the match with the orders list easier
8 Likes

Lovely contest, and one of the best for me in terms of rank/code ratio - 45th legend before rerun, finalized at 64th.
I have promised a full article to Thibaud, but hereā€™s a quick boildown of my usual lazy approach, which did wonders this time.

I have a very straightforward core algorithm, selecting one order and working at it until itā€™s complete:

  1. if Iā€™m standing next to the oven and thereā€™s a croissant or tart ready inside, take it out
  2. if Iā€™m carrying a completed order, deliver it
  3. if the order Iā€™m targeting is not in the list anymore, pick a new one
  4. if all elements are ready for my current order, go collect them
  5. otherwise prepare the missing elements

Movement is very simple: with the single exception of the oven, for which Iā€™m keeping the location, I consider everything as a resource and locate it dynamically from the map, from appliances to semi-completed dishes and raw products. A simple function scans the entire map and picks the closest location to the target Iā€™m asking and goes to it with USE.

Elements pickup at step 4 is also rather simple: I go to the closest location that will provide the largest number of missing items.

ā€¦ and, well, thatā€™s most of it, really. No tricks, no cunning computations, no pathfinding, no accounting for the other playerā€™s actionsā€¦ More to come in the full PM :slight_smile:

9 Likes

BlitzProg - 306th (PHP)

This contest was harder than it looks, and even if you did things right, ranking through the leagues could very well not go as expected. Still, very interesting concept, the other players being partners rather than opponents is something Iā€™d like to see more in the future, perhaps with more defined roles at the beginning (so we actually have to co-operate rather than it being optional). Fairly happy with my rank for the time invested, even if not so good - my only goal was to get into the gold league so I stopped making progress when I finally got in.

Here are the strategies i used:

  • My AI consisted in preparing in advance most of the 3 required orders displayed, an internal value would be updated during the game, representing the current ā€œjobā€ of my bot. For example if there was no croissant anywhere and it was required by some customers (and the other player isnā€™t already doing that), then it will start making croissants until there is enough to satisfy all orders.

  • The same logic applies to strawberries and pies. It will only double on what the other player is doing if thatā€™s the only thing required before making dishes. A job only starts or ends when my playerā€™s hands are empty. When there is no job, it start filling dishes.

  • Dish logic is fairly simple too, every turn it looks at what it has on the dish, select the appropriate order with the most points, then find the closest ingredient needed to add to it.

I did not work on any form of path optimisation, The ā€œMOVEā€ command was only ever used for getting rid of items if every table around me was already full - and i relied on the built-in path finding to reach the points of interest.

My AI doesnā€™t deal with existing dishes nor look at what the other player is doing, maybe dealing with that could have improved it. If the dish is no longer usable, Itā€™ll just deposit it and forget about it.

This logic is what got me from silver to gold tho, this is an upgrade from locking itself to the index of the order (which could change and let it prepare an incorrect dish) and filling the dish in the exact order given, potentially losing time with terrible pathing and realizing at the end it canā€™t meet the requirement anymore.

Glad I made it into Gold! So far Iā€™ve finished every contest in that league :slight_smile: See you next time!

2 Likes

The most interesting contest since the beginning of Codingame.

I wrote a dirty code without reading the rules, in order to reach Bronze on the first Saturday. Then I realize that it was a coop game and it wasnā€™t necessary to steal croissants and tarts in order to be the first to deliver to customerā€¦

Reaching top 30 of the gold league was very easy, but the gold boss was pretty hard to pass.

In the legend league, I totally loose control. I tried many strategies but ranking was totally random.

Finished 93th with a pretty simple code :

  • Choose the most expensive command, but if turns remaining < 40, choose a customerā€™s command without croissant and tart if possible
  • Sort the to-do list looking what is already done, and what the other chief is doing right now
  • Prepare recipe using the built-in pathfinding. When waiting for oven, try to do something else
  • Deliver the command as soon as all the elements are available
1 Like

I find the ladder a bit too random. I was changing strategies each league to promote. Got legend but with 135 players in legend i donā€™t really care.

Also the randomness pretty much ruins testing. On top of that submits were extra slow this contest, takes far longer to test.

My last submit isnā€™t my best bot, itā€™s the one that randomly gets highest rank. Went for the dice roll with highest win chances and left it as it is, because in the previous contests i always screwed myself up on last minute submits.

Now about the game. I really liked the cooperative aspect of it. However a 2v2 would have been more fun.

Hope you allow communication at least in the multi to make it more interesting.

Issues about the contest and game:

  • first and foremost the leaderboard, again itā€™s horrible, please consider changing it. I was at #2 bronze for a while not being able to promote, then same code once promoted goes 200 / 320+, that just doesnā€™t make any sense.
    Same for when i was stuck at #2 gold, i ended up half way in legend once promoted (was at #25 to #40 for most part). I often reached the #2 spot in gold and kept being dropped randomly. This randomness is really annoying. Would rather have no random promotions at all.
  • if you play last and one of the others disconnect after accumulating score you get screwed over. So green is automatically at disadvantage when it comes to timeouts. Two bad bots are still better than one bad bot.
  • cooking is more about creativity, so this game reminded of the stressful busy hours rather than the fun aspects of it
  • dough should be called pastry and you could have shortened the tart recipe to pastry + blueberries + oven (blueberry croissant !! ). Donā€™t see the point in making it longer. Perhaps itā€™s because there were more fun recipes that were left out.
  • i would have preferred no auto pathfinding for this narrow game area (btw too small, too narrow) as it gives false comfort and would have rather spent some initial time to get it sorted early on.
  • the way the scoring works explodes the potential random outcome of the leaderboard. Basically if you get a bot that cooperates well with yours you have higher chances to win. For example 2 tart burners that always expect the ally to take out the tart would be fine as long as they get lucky with who they are matched up, it increases their win ratio for sure.

All in all i like the uniqueness and hope there will be more coop games in the future. Maybe different scoring system.

As for my bot, what i wanted the most is to simply improve my c++ knowledge and i think i spent most of the time fixing bugs. :smiley:

6 Likes

I finished somewhere around 10th (rerun pending) in legend. At the start of the week I wasnā€™t really a fan of the coop aspect so didnā€™t intend to spend a lot of time on it and started with a basic rule based bot, deciding what to do and then using the ā€˜USE X Yā€™ to move to that point.

I had 3 priorities: Complete Order, Manage Oven, Create Finished. My final bot still has these as 3 different things, but implemented with 3 searches instead of rules.

Complete Order does a breadth first search only allowing picking up items that could go into a finished order (with the exception of allowing the first item to be unchopped strawberries and the second action to be chopping). Nothing was allowed to be put down (originally I allowed dropping the item I was carrying at the start of the turn, but this didnā€™t work as well). Visited states were kept unique based on [location, inventory]. If I had a full order and was next to the customer window, Iā€™d keep the move that lead to the highest hand in score. If my partner had a dish with an item on it, the highest scoring order that could be filled with that dish was ignored.

If no orders could be completed from my current state then Manage Oven was called. If there was an item in the oven and my partner wasnā€™t next to the oven in a state to pick it up Iā€™d try to find a route that went to the oven. This was done with a breadth first search again, but this time I had to get to the oven before it burnt and was allowed to pickup a single item from the edge of the arena and drop it on tables towards the center (dough / strawberries could be chopped on the way and blueberries could be added to chopped dough) before heading to the oven. This was kept unique based on [location, inventory, dropscore] (dropscore was 1 for normal ingredients, 5 for chopped dough / strawberries and 10 for rawtart if the item had been dropped onto a middle table). Once Iā€™d dropped an item the search wasnā€™t allowed to pickup anything else, it just had to get to the oven. The idea was that items in the center were more easily accessible, but the priority was to not burn anything.

If neither of the above states were valid (no orders could be completed / oven was empty) my final search would try to find the best way to get a raw tart or dough next to the oven or chop strawberries and put them on a middle table. This was again done with a third breadth first search, only allowing picking up unchopped strawberries, dough, chopped dough and blueberries. The unique state for this search was [location, inventory, blueberry location]. If I was carrying anything other than blueberries at the start of the turn it was allowed to be put down on a middle table, but not included as part of the search. The blueberry location was set when I dropped blueberries (to allow moving them closer for preparing tarts). This search would terminate when it had found a route to do all 3 actions. Iā€™d then choose which of the 3 dishes to create based on number of turns, number of each item available and number of each item required for the current set of recipes. Cooking time wasnā€™t included in the time, and croissants had a penalty of 5 turns so Iā€™d prefer to prepare tarts as they were worth more. If the oven was empty and my partner didnā€™t appear to be trying to use it (carrying dough / chopped dough / rawtart) strawberries had a penalty of 5 turns added to prefer to get something in the oven.

For my partner I assumed they would stay still and do nothing at all times. If they were by the oven and could pickup the item in it then I would count the oven as empty. If they were in a corner and blocking an item Iā€™d move them one square away from me to allow the search to always find an item. If they had a dish with an item on it I would ignore the order with the highest score that they could complete.

I didnā€™t have any logic for allowing dishwashing (I tracked how many dishes were out and didnā€™t allow using it for a blank dish if 3 were out, but couldnā€™t clean a dish with items on it).

This was enough to be top of legend on Saturday, but other people improved a lot on Sunday. I think I end up struggling due to how Iā€™d separated tasks as I let things burn if an order could be completed and some maps I would do very inefficient routes as I wouldnā€™t start preparing a dish until all the components were available. Partners who didnā€™t stand next to the oven while cooking also caused me problems as Iā€™d try to save items that didnā€™t need saving, which I think was happening more and more towards the end of the contest.

7 Likes

What is your bot doing if the partner waits in the corner, next to the oven and blocks another item?

Fun ! I really liked this contest, sadly life got in the way after wednesday, so my final code is my wednesday code. Still I manage to reach legend with that code (itā€™s still stabilizing, but I would probably end up around 100-110).

Iā€™m starting to become a csj fanboy, I really liked Code Royal and really liked this one. Simple for heuristic and the co-op was a good idea (and funny since I was playing Overcooked these days with my gf hehe).

Iā€™d say most of my progress is du to a good organization of my data.

All the ingredients has some static data where I classed them like:

  1. Can they be in a dish
  2. Do they need transformation (ex: chopped strawberry)
    a. What ā€œstationā€ is needed to transform (ex: choppedboard)
    b. transforming what basic ingredient (ex: strawberry)

Then based on whats in my hands and the customers I would just sort missing customer ingredients by how long it takes to make them (tart, croissant, chopped strawberry, then the rest)

So letā€™s say I need a tart, I had a recursive function who would check:

  1. Do I have a tart ?
  2. No -> Does it need transformation ?
  3. Yes-> I need a raw tart
    Then recall my recursive function until I either find a wanted ingredient or start from the very bottom (ex: for a tart, go get a dough)

Once I had that it was pretty easy to separate the decision making from the ā€œdoing itā€.

The 2 other ā€œgood thingā€ my bot was positioning for next task and dropping stuff.

I made a small sim to predict depth 1, well not exacly depth 1, but where I would be once I reached the end of my current task (If Iā€™m trying to chop strawberry, that would be next to the choppingboard). Then I would simply rerun my AI on that new data, depending on the ā€œfutur actionā€ I would stand closer to this location since by default the ā€œUSEā€ command will stop at the closest location when going further could be better since you can move by 4.

The other thing was dropping, I would try to drop things either next to where im going (if im chopping stuff, Iā€™ll leave that useless icecream close to the chopping board) so I can potencially pick it back up once Iā€™m done. But later I added a check to drop stuff on a counter where someone standing next to the transformation station could reach it, so someone looking for strawberries to chop or dough to cook are more likely to have one standing right next to the station and combined with my better position because of my sim, it often meant going next to the oven pick that dough and put it in in 3 turns.

In the end I started to make enemy prediction, so I could stop going all the way around, it was working but didnt do anything with that info, if Iā€™m motivated for multiplayer, I would probably improve on that.

This was my first contest, did not know what to expect, but it was really fun. I guess my competitiveness took hold of me and I did not get enough sleep for a few nights.

Anyway, finished 70 Legend. As others, no problem until gold, then got stuck with the boss. What finally got me to legend was calculating distance to every needed ingredient and picking the closest.

My strategy was a simple one (if you can call 80 ifs simple):

  • Exclude order that partner has completed (or near completion)
  • Complete an order if I have one
  • Find order with least number of missing complex ingredients (strawberries, croissants, tarts)
  • Make complex ingredients:
    • Check oven
    • Make closest ingredient
  • When all complex ingredients are done gather and deliver order:
    • Check oven
    • Get a dish (also check dishes with ingredients on the table)
    • Take closest needed ingredient
1 Like

If I needed to be there Iā€™d just keep trying to walk into them. I never saw this happen more than once, but it was something I was concerned about and just didnā€™t have time to come up with a better solution (originally I moved them one square closer to me, but that performed worse). I think as it limited their options to only moving in the other direction most people would move away quickly.

1 Like

Looks like itā€™s going to be 116 for me, legend. But only because someone broke the gold boss last night and I passed.

It was certainly interesting to play coop, and like most people I didnā€™t realize right away. There was this one guy that kept throwing away my croissant to prevent me from fulfilling a recipe. Such fun!

It didnā€™t come naturally to me, so had to work hard to pass each league. In fact, Iā€™ve never put so much effort into a contest or multi so far and lucky me I didnā€™t have much work at work :slight_smile:

The core of my retarded bot was counting all the necessary items needed for the current orders and subtracting the relevant items that are ready laying around. Based on the count and the score of the order that an item is used in, I went for making the ā€œmost valuableā€ one. This worked far better for me than anything else, and, believe you me, I tried some stuff. I think this worked particularly well because this way more orders are ā€œcoveredā€ at the same time (e.g. 3 orders have a tart in them - go for tart). So the different sorting among other players problem was little bit eliminated.

Things that didnā€™t work for me (like in every contest/multi) was the predictions. For instance, I tried accounting the other chefā€™s items and subtract from the total count and so on. Result - abysmal. It was horrible. I think I passed bronze or silver (forgot) by just assuming the other cook is going to burn whatever itā€™s in the oven, so for a long time I glued myself to it, whenever there is something in it.

Some small things did help though: using BFS to measure distance instead of some approximation, leaving items on the S-ish shaped table in the center and ignoring the outer ring did open up a lot of options, leaving complete orders on said table for the other chef to deliver, and of course a little bit better oven handling with proper priority.

Iā€™m kind of surprised to reach legend, a bit of luck for me for a change :slight_smile:

1 Like

Finished pretty much at the bottom of Legend.

In all honesty, I wasnā€™t very inspired by this contest, probably due to a mix between the very slow pushes at times, the randomness of the ladder and the complexity of the engine if I was gonna write it combined to a bout of laziness. :wink:
In the end I think I must only have spent something like 12ish hours on this during the first half of the contest and left it at that.

If thereā€™s one thing to be proud of tho, itā€™s that my bot still made it to legend, with only some 260 lines of code, no simulation, and a minimal number of if statements.

I simply wrote the code for what happens when you ā€œUSEā€ any kitchen implement or item/dish sitting on a table according to whatever it is Iā€™m carrying.
So on any given turn, Iā€™ll simply try ā€œUSEingā€ every possible thing on the map (regardless of distance) and score whatever Iā€™m gonna be carrying as a result, compare it to my current score and then pick the best.

The eval is as follows:

  • Sum of points for the combination of items currently in hand that match any given active order (the actual number of points for a given item is the same as in the referee)
  • x10 on the score if currently carrying an item that leads to a finished dessert needed for an active order (this is to make the bot actually do croissants and tarts)
  • Bonus points if using something that is within 4 tiles (this is to make the bot prioritize using close things first)

If no ā€œUSEā€ action actually increases the score, drop whatever Iā€™m currently holding on the nearest empty table (because that means itā€™s useless).
And finally, if currently holding a dish that exactly matches an active order, go to the bell to deliver it.

And thatā€™s pretty much it. It actually performed admirably all things considered. :slight_smile:

7 Likes

Hi !
Iā€™m 6th Legend with deep search algorithm.
It was a funny and great contest, i loved it!

Here is the pseudo algorithm of my solution.
(Please forgive my poor english grammar, i know my weakness :/).

Each Turn :

1- I remove the customer order more near from the other botā€™s dish (if have one with at least one item).
1b- If an order is removed, i add the next customer order from the full order list to the current list.

2- From the current order list, take the one (or more if theyā€™ve equals esimtations) wich have the next task more near to me (the most profitable).
(Next task can is : make an item, assemble the dish or deliver it).

Set the root node to the current kitchen state.

While have time (50ms) :
Build all actions from the current node state. Actions are, all moves 1-4 tiles from my position, all uses just next to me (3x3 tiles), one drop (the table beetween me and other bot), and wait.
There is 10-15 moves average in a game for a kitchen state.

For all actions :

  • Make the kitchen in the good state (play the action, or play all parents actions if deph is greater than one).
  • Evaluate action for each order in the current order list (see point 2) with an heuristic function. Itā€™s based on distance (real, not manhattan), checklist of recipe, items already crafted etc ā€¦
  • If Evaluation is more lower than others (lower because evaluation is mainly distances), keep it.
    The cooperation is practiced with the drop item action wich can produce good values corresponding to bots positions.
  • Reverse all actions on current node.

If iā€™ve evaluate all actions of the current depth, go to the next depth.
The next depth is a new action for me, not the other bot action. Itā€™s like i consider the other bot play only WAIT.

At the end of time, play the best move in depth 1.

My code be able to see depth 3-4, it depends on situations. So, my bot can takes shortcut for build the dish for exemple.
At the end of contest, i had a better oven management, plates counter, littles rectifications, etc ā€¦

Concerning codeā€™s architecture, i have an asbract Action with two mains methods [play(Chief, Kitchen) and inverse(Chief, Kithen)] for browse the game tree, and multiples extended actions likes MoveAction, OvenAction, DishWasherAction, DropAction, etc ā€¦

Itā€™s all :slight_smile:
Thanks to csj and Matteh for they job !

Thomas.

15 Likes

I coded only the first Friday to try the game and reach bronze, so my feedback is very limited, I just want to say that the ā€œcooperative but competitiveā€ genre of the game was fresh and cleverly implemented with the 2-player rotations !

4 Likes

That was a great game, I wished I had the time to really participate (my code is only a bunch of IFs conflicting with each other).

To the creators of the game: that would be awesome to have a SOLO version and an OPTIMIZATION version.
Here are some ideas:

SOLO: only one player, limited time to finish one or several orders (to be decided). 1 or more chefs (to be decided). Different maps or not. There could be several versions depending on the difficulty of the puzzle.
OPTIMIZATION: same as solo but you need to do the best score. Maybe only 1 test case ?

9 Likes

13th Legend. I went out of my way to do something complicated and sub-optimal this time, so the result is a nice surprise!
Regarding the contest, itā€™s really cool that it allows heuristics to be competitive, so kudos for that. On the other hand, scoring was ridiculously random, my bot could end anywhere between 10th and 40thā€¦ I wonder if there might be ways to improve this aspect.
For my solution:

  • First I try to figure out which order my opponent is working on. If I can, I ignore this order.
  • I didnā€™t want to write a score function, that seemed a bit hard to get rightā€¦ So I went for a depth-2 MCTS. For it to be able to converge, I had to be extremely severe in the choice of actions to consider, so I guess a big heuristic would have done just as wellā€¦ But whereā€™s the fun in that?
  • Each simulation would end either with a complete and delivered order, or when no more actions where possible. The score was simply the orderā€™s award.
  • To simulate the other chef, which made a big impact on my rank, I used very simple heuristics like ā€œIf heā€™s got a raw tart, heā€™s going for the oven!ā€
  • I would let my sim run on all remaining orders.

In retrospect I would probably have been better off taking the time to write a score function and limit the search to a few turns, but using more action possibilities, and simulating the other chef as well. But god do I hate to write score functions.

I have 179 ifs in my code. Could have been worse I guess.
Thanks again to csj and Matteh!

6 Likes

Great contest. Thanks a lot to the creators. I ended 8th and put my post mortem here:

Post Mortem

7 Likes

Many thanks to csj and Matteh for an excellent competition!

I ended up coming second. Many congratulations to morozec, a clear winner in a messy contest.

My strategy
In summary: a nest of ifs. Perhaps the core choice that I made is not to head for particular dishes. Instead, I make ingredients that are needed, and then assemble items that have all ingredients ready as they come up.

I have two main phases: target selection, which assumes my partner will stay still, and route planning, which thinks about partner movement.

Target selection

This returns our next usable destination and our probable destination after that, and is the meat of the algorithm.

We start by prioritising croissants, tarts and strawberries. We only care about items needed in the current three recipes that we donā€™t already have enough of. Within those, we prioritise those that donā€™t exist, and that our partner isnā€™t making. After that, we prioritise those we need the most of.

We then go down the following list, taking the first action that applies:

  • If we put things in the oven, or if our partner did and clearly isnā€™t going to make it, we stand next to the oven or remove things. During that, we can pop away for a turn or two to pick up a plate or other useful item, but always come back when the item is done.
  • If we are holding chopped dough/uncooked strawberries, make a tart/chopped strawberries.
  • If we are holding a raw tart, and the oven is nearly free, go there.
  • If we are holding dough, and the oven is nearly free, and croissants are higher priority than tarts, go there. Otherwise, chop it towards a tart.
  • If we are holding something on the way to a dish we can complete (that our partner isnā€™t clearly building), complete it and deliver.
  • If thereā€™s a raw tart or chopped dough on a table, and weā€™re closer to it than our partner, and the oven will be free in time, go pick it up.
  • Complete a dish and deliver it, if we are closer to the most important item than our partner.
  • Go down the priority list, making an item if we can. We only make an item if we are closer to the source (dough/strawberries) than our parther. For baking, we additionally have to expect the oven to be free when we need it.
  • Complete any dish and deliver it.
  • Partially assemble any dish.
  • Drop what we are holding.
  • Move directly away from our partner.

Route planning

This takes a destination and a next destination from the target selection

  • Run a simple algorithm to work out our partnerā€™s eventual destinations. This looks at what they are carrying, where they might want to take it, and their last move, to work out their plans as far as they can be predicted. So if they are holding dough, and their last move was away from the oven but towards the chopping board, they are going chopping->blueberries->oven.
  • Run a search, where our partner moves greedily towards their destination (as with a USE command), and we move as far as we can in one direction, next to our partner, next to our destination, or into the special passing places (IIRC, 4,4 and 6,2), without backtracking. When either bot gets to their final predicted destination, they stop moving.
  • Optimise that search for [our turns] + [partner turns] + c_1 * [our turns to next destination] + c_2 * [how many pieces of equipment we make it harder for our partner to access]

Other bits and bobs

  • If the game state (items, locs, and oven timer) is identical to two turns ago, we may have looped. We run away from our partner.
  • I got occasional timeouts in the search, so it breaks and just uses a MOVE command if time runs out.

Unimplemented ideas (mostly half-baked)

  • Incorporate planning and target selection. I sometimes selected targets that looked good, but turned out to be a massive pain for my partner.
  • More use of distance in target selection - my bot was fairly agnostic to how far away things were if it was closer than its partner.
  • Clever oven management - leaving things in longer, taking partner items, leaving items for partner.
  • Making any use at all of the value of dishes.
  • Changing my strategy as time runs out.

What I prioritised was definitely guided as much by what fitted into my (messy) code as what was important or right.

Thoughts on the game and my approach to it

  • It was super interesting - a cooperative game meant there was heavy emphasis on strategies that play nicely with different partner. It felt very different from any bot Iā€™ve programmed.
  • The cooperative nature also made it messy to evaluate ideas, and also to evaluate bots. I ended up watching a lot of replays, finding things I did wrong, and changing things until they were fixed and I did better with the same settings.
  • This was my first contest on CodinGame - I signed up to do it. This was also the first coding competition Iā€™ve entered that ran for less than around 3 months! Personally, Iā€™m slightly frustrated at the end point - I feel like I still had a few good ideas in me.
  • I coded messily in Python, which is the fastest way for me to write code up to a certain point. However, I got way past that point - Iā€™d have gone faster overall by keeping things clean and working in a strongly typed language - and also had some very mild timing issues near the end.
  • My final bot came in at 1192 lines, and 356 ifs. Thatā€™s 0.299 per line.

Thanks again to the creators for a fun contest!

20 Likes