Code a la Mode - Feedback & Strategies

[cegprakash]

My Strategy: Finished #107 in Legend

My core idea is behind an assumption that me and partner will always try to deliver dishes of different customers I predict the customer my partner is delivering dishes to and switch my customer accordingly. I keep track of my partner’s past customer just so if he drops an item on the table, I would still know his target.

Positives: First of it’s kind. I love playing team games. I always enjoy coding for grid games. (love to code anything without collision lolz)

Negatives: Last battles was always crashing. Heavy memory crashed chrome with error message “Aw snap” very frequently. We need fast servers at least during contest durations. I would like to see 100 games gets judged in the leaderboard in 5 minutes.

Suggestions :
Would like to see a 2v2 with Communications
We can even crowdsource the server cost for those 10 days for speed up.

Difficulty : All the bosses were set at the right difficulty keeping the contest duration in mind. I’d expect the bosses to be buffed in multiplayer (something that’s not just if else. Because legend should be given only to real legends - not me )

[DrBloodmoney]

I think the idea not too focus on orders but on the needed dishes is exactly the right approach in a co-op oriented contest. Great thinking!

[eulerscheZahl]

31st (about 15th before I broke my bot, being a tester)

I have a Monte Carlo search, which is quite similar to the one I wrote for Code4Life.
I generate 5 random actions. I hardcoded testing 500 plans (my sim is fast enough to get some more). An action is a USE here, so it can make me move accross the whole map. An action has to be valid, so the options to choose from depend on the item, that my chef currently has (if any).
My chef is not a teamplayer at all. I mostly ignore my partner,

After each of my 5 random actions I score 2 things:

• preparing the more complex foods (chopped strawberries, croissant, tart)

  double timeWeight = 1 / Math.Log (2 + TravelTime);
  double factor = Math.Sqrt (Math.Min (1, itemCount / itemNeeded)) - 
                  Math.Sqrt (Math.Min (1, previousItemCount / itemNeeded));
  Score += factor * itemCost * timeWeight;
  

• serving a dish to a customer

  Score += 3 * SearchDepth * customer.Award * timeWeight;
  

This gives less score for finishing a task later (in terms of the real game time, not search depth for my actions - so it’s fine to pick up a dish before a save the tart from burning.
I have a higher motivation to get my 1st croissant, than a 3rd tart.
Taking extra time gives a slightly smaller score.

When I found my best plan, I replace USE by MOVE, if I’m not next to my target already. That’s the only time, that I check the postion of my partner. I try to get close to the next cell in my list in this stage, so that I might save a turn later.

When I place an item on a table, I prefer central tables with many neighbors over corners. That makes it easier to pick up an item again, it’s easier to reach.

I ended up with a little less than 1000 lines of code. This is mostly the game logic itself, a little path finding. The actual bot is pretty simple.

[_CG_Maxime]

We need fast servers at least during contest durations. I would like to see 100 games gets judged in the leaderboard in 5 minutes.

We had a performance issue on the server that selects the participants of the battle and then updates the scores at the end. As a consequence, at several occasions, the “execution” servers were idle, waiting for tasks to process. We’re currently working on a technical task that aims at splitting services on dedicated servers, that should help.

However, seeing 100 games in 5 minutes might not be possible for a simple reason: except for the first 10 games, all the next games are computed sequentially because we need your current score to select your next opponents. If each game takes ~10s, you’ll need at least 15 minutes.

We’re of course open to suggestions to improve the computation of the ranking.

[TwoSteps]

I enjoyed the game a lot and wished I had more time to play. Finished 8th in Gold, tried the Legend until the end.

Like @teccles, I tried not to focus on one specific order but rather chose to prepare the closest needed available dessert and drop it on the right plate. My boss would never drop a finished dessert directly on a table (but to empty the oven). Unfortunately, quite a few bots in gold would not try to complete the unfinished orders on tables and instead would stubbornly try to finish one order on their own… leading to very poor performance. And my bot didn’t adapt well to these bots. This + a few bugs and unoptimized decision making regarding basic desserts vs advanced desserts explain why I didn’t get to Legend.

But I had fun! The semi cooperative thing was indeed very interesting despite the frustration of bad cooperation once in a while.

We dropped a lot of things during the creation (I think for the better):

• there was a bin to empty a plate
• there was BURNED_FOOD to be removed from the oven until it can be used again (if something burned in it)
• at some point, we could split a tart into 4 parts at the chopping board
• there were bananas and waffles
• you could move in diagonal for less steps than 1 horizontal move + 1 vertical move

Congrats again to the creators csj and Matteh, the graphic designer Bruno (part of the CG team), the testers, the streamers. I wish we didn’t have that annoying issue with last battles (I’ll push to fix this sdk memory issue before next contest). Apart from that, I think it was a really nice event.

See you on the 17th of May for A Code of Ice and Fire. I chose fire #TeamFire

Oh, I forgot, I tried to keep my code clean from the beginning because

[JoeSchmoe]

However, seeing 100 games in 5 minutes might not be possible for a simple reason: except for the first 10 games, all the next games are computed sequentially because we need your current score to select your next opponents. If each game takes ~10s, you’ll need at least 15 minutes.

First thanks for the game, loving learning how to code with a game.

Can you increase the batch size from one game at a time during the sequential scoring phase? I certainly agree with many others that it’s hard to test your bot if it takes a long time to find out how well it performs.
If the first 10 games take 10 seconds, then score and play 10 games against similar bots. That’s under 2 mins. Fine tune after that point if needed.

[Magus]

The first 10 games are used to estimate your initial position.

After that, the TrueSkill system require sequential games because each games need the result of the previous game. You can’t do any batch or parallel games.

[cegprakash]

except for the first 10 games, all the next games are computed sequentially because we need your current score to select your next opponents.

Can we reduce that dependency? For. eg. use the score of first 10 games to determine the next 10 games’ opponents. Then use the score at that time to determine the next 10 games’ opponents and so on… This way more parallelism can be achieved and we get a 10x faster leaderboard.

TrueSkill system require sequential games because each games need the result of the previous game. You can’t do any batch or parallel games.

For the final judging you can have the current judging mechanism. But during contest time I feel we have to reduce the dependency and increase parallelism. Instead of having less matches in a tight dependent ladder I would prefer a low dependency ladder with more matches

[darkhorse64]

I don’t know much about ranking but I guess batching games would increase unreliability of the result thus being an incentive to more “spam push”, no ?

[JoeSchmoe]

The first 10 games are used to estimate your initial position.

After that, the TrueSkill system require sequential games because each games need the result of the previous game. You can’t do any batch or parallel games.

I’d have to read up TrueSkill more, but an initial read does not seem to indicate a sequential games requirement. Maybe games should be scored sequentially, not even sure about that.

Seems to me that a tweak could be to have the matchmaker output a batch of “interesting” games, and then they could be played in parallel. Store the results to then be processed sequentially. Sure there is risk that a game that the matchmaker thought would be interested turns out to have been “uninteresting”, but the ranking system should still be able to update the rankings based on it’s result.

What I’m saying, and think I hear from many others is that it takes too long determine your bots results. Maybe the estimate of initial position could be improved?

Maybe we need a contest to see who can create the fastest ranking system that succeeds in ranking bots.

[Matteh]

Many thanks to Bruno for the awesome visuals!

[dolmen1234]

We could have more leagues, for example one new league every day
With fewer people in each league we may need fewer matches for one submission ?

[tutubalin]

tutubalin - 14th (Python3)

It’s weird how my opinion about contest changed over time.
When contest just had started I didn’t find it fun enough to even bother about. So first 2-3 days I only discussed ideas with fellows and didn’t even try to code anything. But when I started coding everything changed.
When contest was over I felt like something really important just have ended. During the contest I even saw it in a dream

As many other people already said, movement along the leaderboard was very surprising. Sometimes after implementing a major improvement my bot dropped 100 places down in a league. Then after changing 1 line it suddenly got promoted to the next league. But it was very emotional, especially when after frustration you get an unexpected success. I think it’s because of cooperative but still concurrent style of the game.

For example, I struggled several hours to get out of bronze. Then I tried to make chopping strawberry more important than baking stuff. BOOM! I am silver.

Getting out of silver was also surprisingly easy. I added just one condition: do not save bakery if chef is already has something in his hands. BOOM! I am in the gold instantly.

Another example: I decided that if both chefs are too into baking, they will block each other. So I decided to assemble orders while delegating baking to a partner. I created a super intelligent system that calculated which items in the kitchen are stackable, what orders can be partially satisfied and how. After submitting I dropped 100 places lower. So I just removed it and switched back to older version, made some minor changes. BOOM! I am legend.

So submitting new code was always a great rist. At some point I stopped coding in web editor and setup git environment - because I needed to track what exactly I change, and how every change affects the position of the bot. My effectiveness greatly increased after that.

Storming top20 was also surprising. In the morning of the last day I was somewhere in #30-40. I made an improvement: prefer more expensive orders. I submitted, and… I am #120…

Ok, that was because of bug. I fixed it while preserving improvement, and I am #50-55. Resubmit - still #50-55.
I tried old version - #35-45. Expensive orders are not so good!

So I had no choice other that revering this “improvement” and adding a different one. And suddenly - I am in top10. At this point I decided do not touch it.

A few words about my bot. It is built on “IFs”, or you can call it decision tree probably. The core of the bot contains only 18 ifs.
Most of conditions are simple and straightforward, for example: if bot holds strawberry, he wants to use chop board. If bot holds raw tart, he wants to use oven. Some conditions are more sophisticated. But in total bot code is pretty short and straightforward. I don’t even use MOVE command.

Some ideas that proved to be good:

1. If you hold ready order - serve it, don’t try to make it more expensive.
2. Save bakery unless it requires you to go too far.
3. Do something while baking is in process, do not just stand near oven.
4. Always go back for you own tart/croissant!!! Do not delegate saving to partner.
5. If you can make an order - make it!
6. Put stuff on the tables in the middle - they are easily accessible from both lanes.
7. Strawberry first. Bake later.
8. Bake! Bake! Bake! Oven is a bottleneck, it should be working 24/7.
9. Don’t know what to do - go grab dough.

That’s all guys.
Thanks for great contest! I am waiting for multi to continue my development.

[TwoSteps]

If you haven’t done it yet, please fill the survey: https://codingame.typeform.com/to/DriT4I

[dbdr]

First, sorry for the late PM, I stayed up coding and packing the whole last night of the contest, before flying to California the next day

The first night I wrote a simple heuristic in Java to get to Bronze. It actually got around #10 the first night, which felt nice. However I knew this was very preliminary and symbolic, and I was sure I would go for a search algorithm.

I went fist for a Monte Carlo simulation, for simplicity while implementing the engine, planning to switch to MCTS later. The alternative heuristics (“if forest”) approach was especially easy and strong in this contest, so it was not easy to get a strong search bot early on, as many people who tried know, needing in particular to spend time crafting a good eval function. But I had something decent after a few days, and I was relatively confident that in the end it would be easier to keep improving, while the if forests would become increasingly hard to maintain. There was still a doubt about which approach would be best though, and I think this is something great about this contest.

The next step was to switch to MCTS. I got something working, but it was not so clearly better, as in some cases it would make worse decisions. I realized that the strength of MCTS, going deeper in promising branches, made reasoning about it harder, because it would find a deep good solution (deliver a finished plate) and not find a shorter action plan (like making a very much needed croissant) that would be better in the long term. It might be possible to fix this by carefully tuning the exploration parameter and the evaluation function, but this seems just too complicated. So I decided to change the expansion criteria to simply the number of visits, to always explore in breadth instead of depth. Essentially this became a BFS search in the state space, implemented in a weird way :). This worked better, and importantly was easier to debug, because I knew all shorter solutions were considered before longer ones.

Regarding the partner, for a long time I just ignored them (though by nature I would happily prepare ingredients that they could use, as I did not focus on a single customer). For a long time I even did not consider that they can block my path, being optimistic that they would just move away in time. That seemed to perform better initially, but eventually I switched to considering that they are static for a few turns, then disappear (since their position is too uncertain after some time). In the last week-end, I added a hard-coded behaviour that they take things out of the oven if they are next to it and they put the ingredient in, which gave a nice improvement.

One small feature I like was to give a small positive value to spreading dough and strawberries at useful locations. That meant for instance than while waiting for my tart to cook here, I picked this dough and place it where it can later be used in the oven or the chopping board:

All in all, I think that the search approach indeed allowed me to keep trying new ideas until the end with manageable complexity, and that it payed off, even though it was obviously harder in the beginning. My rank graph from @Adrien’s awesome tool illustrates that:

When legend opened, I was very close but did not make it, so I had to spend Friday evening making sure I promote, which corresponds to the zigzag on March 15th :D. My final rank was #5, which is my best result so far!

Thanks a lot to @csj and @Matteh for a fun and well designed coop game, to the testers, and to all the chat regulars for an awesome community during and between the contests!

[anon72424297]

A great thanks to @csj and @Matteh, the creators, and to all of the Codingame team !
What a contest guys ! First cooperative game of the platform, and not the last I hope. Excepted some balance problems in the ranking, I really enjoyed it.
But now it’s over, and I finished #106 in legend with C++.

Here’s a little overview of what I’ve done.

The data structure

After reading the statement and seen the amount of inputs, I started by coding the classes architecture destined to stock these ones. I wanted it clear, but also hyper simple to use, to be able to focus myself on the logic and the strategy of the game. Here’s the result :

• Coordinates : This class simply represent… coordinates. A x, an y and a simple (Manhattan) method of distance calculation.
• itemSet : A class destined to represent a set of items (dishes, ingredients and desserts).
• Order : A class inheriting of itemSet, adding the award to cooking it.
• Cell : A class representing a cell of the kitchen, walkable or not, and also inheriting of itemSet to represent the disponible elements on it. It also has a "type" attribute, to quickly identify it (I have simply keeped the ascii representation of the input).
• Kitchen : The representation of the map, containing, of course, an array of Cell.
• Player : Simply inheriting of Coordinates and itemSet.

The items sets representation

Since an Items set, i.e an Order, a Cell or a Player, can’t contain more than one element of each type, I decided to represent these items sets by bits fields, easier to use than strings. So I started by associate a power of two to each possible item via an enum :

From there, I modified my itemSet class to contain a bits field, and by adding to it a constructor taking a string and using it to fill this bits field.

The toolbox

After that, I employed myself to code all the possibly potentially useful tools which I could imagine :

• I added a series of methods to my itemSet class allowing to check if it contains an item, contains at least one item in a set, contains an entire set, and so on…
• I have improved my Kitchen class, notably by modifying the constructor to allow it creating as much data as possible from the input (kitchen in a form of Cell array, in a form of graph, Coordinates of equipment…).
• I have coded a BFS, and a series of functions based on it. First, several functions to find not walkable cells (closest item not in a dish, closest dish matching an order, closest "evacuation" i.e the dishwasher or the hatch,…), secondly a function to find the closest spot to access a not walkable cell. All of this taking the partner position in consideration.

About Remy

All of this done, it was time to code the decision function. Named Remy for the occasion, it has undergone a lot of modification through the leagues. But here’s in a nutshell the last version’s logic :

• If Remy don’t have an order in progress, or if the order in progress has already been delivered, he chooses a new order.
• To choose the order to prepare, Remy consider two things : The award of the order, and if a pending dish somewhere in the kitchen is matching. If a dish match, Remy just add 1000 (Totally arbitrarily) to the award. At the end he chooses the order with the best reward.
• Then, Remy determine if some complex desserts (Croissant, tart, or chopped strawberries) must be prepared. If yes, he determine what to prepare first this way : If he’s closer to the closest strawberries than the closest dough, he start by the strawberries. If he’s closer to the dough, and the dough is closer to the oven than the chopping board, he starts by the croissant. Otherwise, he starts by the tart.
• Once a preparation started, Remy finish it step by step. For example, if the tart is the first element to prepare, Remy will pick the dough, then will chop it, then will garnish it, then will cook it, and only after that he will select the next element to prepare.
• If the oven is not empty, Remy will wait his turn, and eventually get out of the oven what is cooking, if the partner doesn’t (It’s the only case in what Remy take in consideration the partner baking.). During the cook, Remy just wait next to the oven.
• If Remy is preparing a complex dessert, and the partner put on a table one dessert of this type, he stops his preparation and consider this element ready, except if he’s monitoring a baking, in this case he goes to the end.
• At any step, excepted the baking, if the needed element has already been prepared and is available on a table, Remy will prefer picks it rather than prepare it.
• Once all the complex preparations done, Remy composes the dish. First, he takes the closest element of the recipe, dish included. If he has an element in the hands which is not a dish, he goes take a dish. Then he takes the other elements of the recipe, one by one, by order of proximity.
• When the order is ready, Remy deliver it. But if the partner delivers the same order before him, he put the dish on a table. Same thing during the preparation.
• If there’s no clean dish, and no in progress dish which match with his current order, Remy take the closest dirty dish and go put it in the dishwasher or in the hatch, according to what is closest.
• At any moment, if Remy is carrying something and needs his hands to do something, he’s able to put his load on a free table the time to perform this action.
  
  That’s all !

Dropped idea

I wasted a lot of time with an idea which seemed good to me, but the results did not agree…
The problem were since the BFS take the partner position in consideration, Remy has some time to do the entire turn of the kitchen to access to an element, whereas perhaps the partner would have moved, next turn.
So I tried this : If the shortest way to access the element is blocked by the partner, Remy move next to him and wait two turns (The best value I tested.), if after that the partner has not moved, Remy take the other path.
By testing this in the IDE, I seen a real improvement of the Remy’s movements. But in the arena, the global results were poor…
Not seeing any bug, I rapidly tested some improves, like reconsidering the path if the partner move during Remy’s kitchen turn. But with no results…
So, I finally dropped the idea…

Ideas of improvements

• I’m definitely convinced there’s a way to improve in the coordination of the Remy’s moves with the partner’s ones. Remains to find which…
• There’s clearly better to do with the preparations order. Like doing the closest task whatever what Remy is doing. For example : Put a raw tart on a table the time to chop strawberries, if they are on the way to the oven.
• Add a fix to avoid the infinite loops like : Remy is carrying chopped strawberries and puts them on a table to prepare another dessert. The partner is carrying a dish which is missing strawberries and see the Remy’s strawberries on the table. So he puts down his dish to come take these ones. But Remy see the partner’s dish and that it matches with his current order, without the strawberries. So, Remy take back the strawberries and go take the dish. But ! Not seeing the strawberries anymore, the partner takes back his dish. Not seeing the dish anymore, Remy puts down the strawberries, and so on…
• Consider all the orders at the same time, and not only one.
• Have a more collaborative comportment.
• …

Thanks again everyone !

BlaiseEbuth

[ValGrowth]

Legend 4th.

• Algorithm

I used simulation algrithm Chokudai Search.
It was invented by Chokudai and has similar features to beam search.
And it has an advantage that it is easier to manage time than Beam Search. Details are described here by Chokudai. (Japanese, but I think sample code is useful for everyone.)

In this contest, I set the search depth to 7 (Player1 → Player2 → Player1 → Player2 → Player1 → Player2 → Player1).
About 10,000 states could be evaluated in one turn.

• Evaluation Function

I set the weights of the two players equal. I paid attention not to give an evaluation value biased to either player.
I did following 3 steps in the evaluation function.

(1)sort customers

First, prioritize the three customers.
① Give priority to customers who have all the ordered foods on the tables or dishes or players hands.
② If ① is the same, give priority to high Award customers.
Considering serving foods in order of this priority.

(2)Assign players to customers

Checking the customers in the order they were sorted in (1).
If the customers who have all the ordered foods on the tables or dishes or players hands, it is evaluated which the player is likely to be able to complete the customer’s order first.
The player with higher evaluation is assign to the customer, and another player is sent to the next customer.

(3)Not assinged players will cook for not assinged customers

The player who is not assigned to any customers in (2) thinks to cook the foods of the remaining customers order.

After that, when comparing evaluations, it will compared in the following order

1. Higher game score is better
2. The more players are assigned to customers, and the dish is closer to the order, the better
3. Cooking processes have more progress, the better

Thank you for the good contest, I really enjoyed it!

[Ethaniel]

I’m surprised to see that no one here mentioned the fact that this contest was the prisoner’s dilemma at its finest: If the 2 bots are cooperative (one staying near the oven and one near the bell for instance, and expecting the other to do its job in its half-kitchen) they will score very great, but if one of them tries to do everything alone without counting on its partner, then the cooperative one is strongly disadvantaged and the best solution is to work alone too.

[IloIlo_JRFerguson]

Thanks to the devs for another great contest. I really liked the coop aspect of it, it was a nice change.

This was my worst performance in a contest thoug, ended #186, I think mainly because of some bugs in my sim that i couldn’t fix in time. I’m waiting for the multi to test again !

I still wanted to share some aspects of my solution bc it differs from anything else I read so far.

From the beginning I knew I wanted to simulate the game and solve this by pretending the partner is controlled by me. I thought this would lead to the best coop behavior. I figured that trying to predict the opponent next move shouldn’t be so hard, and just assuming he would stay still is a prediction in itself that could lead to a very bad path decision. There are inbetween approaches (heuristic prediction), but I figured a combined evolution would lead to smarter prediction and coop. So I went for a GA with depth 14, where i play me in even turns, and my partner in odd turns.

For the data structures, I went for bit representations as others did, but to be able to count the ingredients easier I used different masks than MSmits or BlaiseEbuth. I used 3 bits for each ingredient to be able to count them. My masks were powers of 8, so i could count up to 7 ingredients. I have a mask to add and a mask and shift to count, so:

DISH = 0
BLUEBERRY = 1
ICECREAM = 2
…

MASK[[DISH] = 1
MASK[BLUEBERRY] = 8
MASK[ICECREAM] = 64
…

MASK_COUNT[DISH] = 7 // 1 * 7
MASK_COUNT[BLUEBERRY] = 56 // 8 * 7
MASK_COUNT[ICECREAM] = 448 // 64 * 7

SHIFT[DISH] = 0
SHIFT[BLUEBERRY] = 3
SHIFT[ICECREAM] = 6
…

Grab an icecream for me is:
player.item |= MASK[ICECREAM]

Pick an item from a table is:
player->item |= cell->item
cell->item = 0

Count all the Tarts in the field is:
int allItems = player->item + partner->item + (foreach table, table->item);
int tartsInField = (allItems & MASK_COUNT[TART]) >> SHIFT[TART]

I really struggled with the eval function. In the end it give scores based on game points and ingredients. Ingredients in finished dishes (ready to deliver) are worth the most, ingredients for dishes where all ingredients are ready to pick (tarts, croissants and chopped straws) are worth a little less, and ingredients for dishes in which at least one ingredient is missing are worth the less (but still important). Unfinished ingredients (dough, chopped dough, raw tart, straw) are only worth something if they are in the hands of any one of the chefs and if they can end up being used for a needed dessert (raw tart is worth 0 if i dont need tart, or if it’s in a table).

I know i’m late and that my ranking is not that high, but i wanted to share that with you guys.

See you on the next contest !

[Xa2017]

I have a different opinion about this game. Maybe because I didn’t perform well.

I started with heuristics which were working quite good since I was at the top of the silver league when it opened. However I wanted to write a new bot to simulate my partner and myself and to find the best combinations of actions. Unfortunately it didn’t work and I was stuck in silver league. After watching last battles I decided to disable the simulation of my partner and I accessed easily to the gold league. I was very disapointed because coop didn’t work at all.

Yes, we take into account the state of our partner but we don’t cooperate. My strategy was to put the plates on the tables and to fill them with desserts. But most of the time other players focused on their own order and didn’t try to fill the other plates. An obvious example is when the partner takes a dessert from the oven to avoid it burns and put it on the table next to the oven instead of putting it in a plate which needs this dessert.

With my simulation I came up with an example of what I would expect from a good coop: my partner put his croissant in a plate and I take this plate in the same turn to deliver it the next one. In reality, my partner put his croissant on an empty table next to the plate… To me actions of my partners were always unpredictable!