Hi, thanks for your share! I have just a question about debugging of the solution: Which IDE or tool could help to debug a complex code as MCTS simulation? And how to import start data game?
Congrats.
2 Likes
If no one should share their codes publicly, how would the beginners learn to compete in such challenges?
Copy/pasting would harm severely this multi. There are a few multis where this happens and it does not make any good for the copy/pasters who do not learn anything and for the rest of the competitors who face a wall of clones. That said, how can you make progress ?
Here, at CG, code is private but knowledge is public.
For all past contests, there are dedicated forum pages where top players explain their strategies and the algorithms they used. Read them carefully and browse the Internet for ample ressources (sample code, explanation) on all the major algorithms.
Start simple: you are not expected to write a Legend bot on your first attempt. The Wood leagues are here for a head start.
Ask questions on the chat: there will always be someone who will point you into the right direction.
14 Likes
For this challenge definitely not worth sharing heuristic bots (submit spam trained NN 
)
Hey I don’t mind sharing the skeleton of my poorly optimized “beam search” as a starter bot. Something like that doesn’t break the ladder and it’s somewhat more helpful. 
2 Likes
~900th in Gold, nothing to be very proud of!
About my bot
I chose to use beam search, no opponent simulation. I spent the first weekend to implement the model and the generation of actions and turns, as well as writing a simple evaluation function. This got me easily from Bronze to Silver. I didn’t do much until Wednesday, just fixed some Timeouts & did some quick performances optimisations but this didn’t improve my rank.
The struggle for me was really in understanding the game as a human and be able to write a good evaluation, it looked very difficult to decode at times. Thursday I spent 1/2h looking at games in hope to understand better how to guide the search but I didn’t come up with anything. So I left the code there in silver until Sunday evening when I found motivation to at least go to gold.
I didn’t change my eval but fixed a couple of major bugs in the simulation and that was enough to reach Gold league. I’m sure there is more 
The evaluation I use is quite simple at the end, something like:
Big trees = good, trees in the center = good, trees too close to each other not good. This value decreases over time and the actual score value increases.
Conclusion
I enjoyed the contest as usual, I think I tend to prefer boardgame inspired contests like this one. It was difficult to find motivation this time though, not really sure why 
.
Can’t wait for the fall challenge, my goal is to switch from C++ to Rust and continue to learn how to design a good simulation.
5 Likes
Thanks for your post mortem. I did something quite similar, but could not reach Legend. I was stuck at #30 place in Gold.
Today, I tried your way, but it’s not really efficient. The Gold boss anticipated each of my grows, and make them useless. I tried 10 games, I never beat him.Something must be missing.
Furthermore, you said :
- seed on diagonals only, or distance 3 in a straight line. break ties by richness. nothing else for seeding
I watched you games, and I must add something. The seed may be at distance 3 in a straight line, but this cannot break the rule for the other trees. That means a seed must always be on diagonals, or distance 3 in a straight line of any tree.
My implementation does not follow this rule as it should. Maybe it’s this part that makes me lose all the games !? I’ll update, try again, and tell you how it changed the thing.
Good catch, that’s correct! There are some situations where it won’t seed for a while, which isn’t the best, so I’m sure you could improve it. I may have missed some other details or misremembered something 
FYA I was around 50/50 against the boss, so depending on who is around the boss now it may be harder.
1 Like
RESULTS
Thanks to a great community for this one. The chat was very energetic and had interesting discussions. At first I didn’t really work on my eval function, but went straight into a beam search that ended horribly, with numerous bugs. I then attempted to beam search again on final day but it struggled to get past 2 days and 1k nodes. If I was able to get a good number of nodes in my search I would have rewritten in C++ to improve the nodes. But I felt the python3 was so bad that a C++ wasn’t going to improve much.
The heuristics.py bot was able to achieve top 1k overall rank in the challenge running just a simple eval function with if-else statements. It divided the game up into stages, start, mid, end, and final day
The heuristics2.py bot was the last iteration on the heuristics bot, which achieved a ranking of 752 overall and around 500 in Gold league. It still involved eval function and only looking at next move, and it had separate priorities depending on the game day.
The general strategy was the following though for the final iteration.
SEEDING
The bot always seeds in knight move’s, which was an improvement I noticed earlier. The reason it works is it prevents self-shading. Early in the game, it prioritizes growing trees from size 1 to size 2 that have better soil quality in knight’s moves from it. This way I can seed higher quality soil sooner, prevents enemy from taking some good soil. Of course, I prioritize seeding in higher quality soil. Seeding is the highest priority action throughout the game until we get to the later stages after day 18. However, completing is given higher priority sometimes in mid-game under the consideration if I have allotted many sun points or I have 4 or more trees ready to be completed. Also I only seed one at a time, so that I never spend sun points on seeding.
GROWING
I prioritize growing trees that have better soil that are knight moves early in the game. In mid-game, I prioritize growing seeds over other trees, so that I can seed more. But growing to size 3 is preferred over growing to size 2. Also I prioritize growing in the better soil.
COMPLETING
I make completing the highest priority in mid-game when I have 4 or more trees or if I have over 20 sun points. I don’t think that happens often though, because my bot was using all the sun points. I also prioritize completing trees that are on better soil. But I prioritize the most to complete a tree that will be spooky next turn from an enemy (because I only use knight moves I never self-shade). I think this optimization made sense because if I complete a tree on better soil I may get 2,4 more points, but I’m losing more than 3 sun points next turn. I’d rather improve my sun points gained next turn.
NEXT
I want to learn how to use beam search, and DUCT MCTS to solve this problem as well. I am doing that post-contest. I also want to work on finding better eval function, something that maybe just looks at score and sun points potentially.
5 Likes
Thank you for all those explanations. I feel really ignorant, but it opens new horizons
Time, time… If only a had more of it 
3 Likes
hi @miklla I was also thinking about dynamic programming for this contest as I saw the graph is directed and acyclic in nature. Could you please shed some light on what is your DP state. I had a 13x7 board similar to this. But each of this cell has multiple properties making each state pretty huge. What exactly is ur DP state?
int boardIdx[BOARD_HEIGHT][BOARD_WIDTH] = {
{-1,-1,-1,25,-1,24,-1,23,-1,22,-1,-1,-1},
{-1,-1,26,-1,11,-1,10,-1, 9,-1,21,-1,-1},
{-1,27,-1,12,-1, 3,-1, 2,-1, 8,-1,20,-1},
{28,-1,13,-1, 4,-1, 0,-1, 1,-1, 7,-1,19},
{-1,29,-1,14,-1, 5,-1, 6,-1,18,-1,36,-1},
{-1,-1,30,-1,15,-1,16,-1,17,-1,35,-1,-1},
{-1,-1,-1,31,-1,32,-1,33,-1,34,-1,-1,-1}
};
1 Like
You’re a God for all of us. Prood to discover your ideas and performances with this challenge.
I will follow your works for the future.
Congratulation for you.
1 Like
I’m glad to hear of successfull MCTS implementations. I tried to do it, but miserably failed. It performed worse than my “let’s code some ifs to reach bronze”-Solution even with much more time per turn. So, with your descriptions I might be able to get it running for the puzzle, thanks.
Finish 522th / Gold 295
Really easy progression from wood to gold. But the challenge was really hard for the legend league. Maybe in the multi section.
Road from Wood to Silver
- Play possibleActions sort by action type alphabetical and by richness cell
That was too easy I suppose in comparison with fall challenge 2020.
From Silver to Gold
I only add a few thing to evaluate each actions.
Like a lot of people, I limit how many tree of each size I keep and dont cut tree until day 12-14.
But to reach Gold I simply add a “shadow score” to Seed actions. With this I prune a lot of seed action and teach my IA to reach only good spot.
Shadow Score is :
- (+ size) of opponent tree in the shadow of the 6 future day with the meaning that I grow the tree each day.
- (- size) of my Tree if it’s in the shadow.
With this my bot will less seed near my current tree but can do it if it shadow a lot more the opponent than my tree.
With this and some magic number I rapidly reach rank 182 at day 6 opening of gold league.
Well since the oppening of gold league, I tried a lot of magic number without success of reaching higher rank.
Conclusion
In comparison with the Fall Challenge 2020 I code less in this challenge but for the same rank.
I will read other PM to improve this later. But like the others challenges a wonderfull adventure with the all codingamers from the Fr tchat.
See you in the next challenge
3 Likes
Hi all. First of all - sorry for my stupid bot, it’s my first AI game and challenge ever, so i didn’t know which algo i need to use and also i didn’t know that i can ask for the help in chat
Result - bottom of the legend
The bot:
I separated it in 3 actions with some hardcoded rules (like number of possible 3 lvl trees at the end of the turn):
- Check the next tree to grow. I did it based on calculation of shadows for the next turn. Then calculate a score based on shadows for opponent’s trees and shadows for my trees, weight shadows based on tree height. Try to grow tallest trees first
- If number of 3lvl trees more than hardcoded value or number is the same and next tree to grow is lvl2 -> lvl3 - complete the tree. Calculate the score of the tree based on shadows for the next turn. Order by score and then by richness.
- If no complete action need to be done - grow the tree based calculated during step 1
- Seed logic - it’s possible to have only 1 seed. Find all possible cells to seed and calculate the score of each cell for next 6 days with assumption that each tree is grown every turn. Calculate shadows for my trees only. Try to seed with 2 cells interval from my other trees if possible.
P.S. thank you all for you PMs - now i see that i need to learn a lot Also thanks for that great challenge.
P.P.S Could anyone explain me how you was able to use NNs here? Is it possible to import a library like TF? I understand that @reCurse implemented his own NN and imported it here, but what about other developers?
2 Likes
You can view this thread: https://www.codingame.com/forum/t/neural-network-ressources/1667
You have to code it yourself, you can take a look at my slow C# NN for Onboarding:
2 Likes
This was my very first contest on here and I thoroughly enjoyed it. Thank you to all organizers, testers and participants for making it such an fun and educational experience.
I ended up finishing 9th, so I am only mildy disappointed
As my approach is quite similar to others already explained - in particular to that of Magus - I have unfortunately very little of value to add and shall keep this brief:
I used a somewhat optimized, heavily pruned sequential MCTS with “smart” rollouts. Like others, I tried to reuse the tree across turns whenever possible and fiddled with bits to get move generation and execution to be reasonably performant. The main differences, I believe, are in my reliance on the UCB1-tuned formula and slightly different rules deciding which actions to generate.
For node expansion, I came up with the following ruleset:
-
Do not complete any tree before day 13 and only complete on the final day or if the opponent has some size 3 trees, too(otherwise, barring some really rare cases, potentially collecting sun points for one more day should outweight the additoinal nutrients my opponent can gain)
-
Only seed in cells not covered by the seeding trees shadow
-
Never seed if you could grow instead
-
Never seed after move 20 (this might have been stupid for the tiebreaker but the reduced branching factor turned out to be more valuable)
-
Only allow a fixed number of not-fully-developed trees(6) and don’t seed if it would exceed that number
-
Never wait before turn 14, except if there was some action we would have liked to try but could not afford to
-
Only generate up to a fixed number of moves of each type(up to 4 complete, 4 grow and 5 seed actions). If more than this allowed number of moves are possible, I sort them and keep the “best” ones, according to simplistic heuristics:
- I precomuted a value for each cell, based on its richness, the richness of all cells that can be seeded from it and its proximity to the edge(as outer rings are better for sun collection)
- For complete: Higher richness is better. For same richness, prefer completing those with lower value.
- For grow: Higher is better. For same height, prefer those with higher value.
- For seeds: Less potential shadows by existing trees is better. Otherwise, chose the one with higher value.
For rollouts, I used almost the same rules, but simplified them a little further to save cycles and complete more of them:
- Whenever at least one complete action was possible, don’t even generate grow and seed ones.
- Don’t sort grow actions, just generate them ordered by height
- Ignore shadows for sorting seed actions
- Chose wait and seed moves with lower probability then grow and complete ones.
Thanks again for the great contest, I am eagerly looking forward to the next
13 Likes
In basic, my DP state is [day] x [nutrients] x [my_t[0]] x [my_t[1]] x [my_t[2]] x [my_t[3]] x [my_energy] -> my_score, where [day] - day, [nutrients] - number of nutrients on start of a day, [my_t[z]] - number of my trees of size z on start of a day, [my_energy] - my energy on start of a day, my_score - my score on start of a day. For example on first move the first state would be [0][20][0][2][0][0][2] -> 0 (But actually DP starts after depth 1 or 2 simulations, so in first move it starts from day 2). All coordinates are bounded to be bounded game, day <= 23, nutrients <= 20, my_t[0] <= const, …, my_t[3] <= const, my_energy <= const, all trees are assumed to dwell in medium reachness cells. I fill this multidimensional array from day to day, making all legal full day moves which lead to states with same bounds (if 2 moves from 2 states lead to exact same next day state, save only best score), opponent’s cut timings also affect nutrients, next energy computed as
next_energy = previous_energy - legal_move_energy_cost + e - e / C, where, e = next_t[1] + 2 * next_t[2] + 3 * next_t[3], C = const, next_t is my_t for result of the move, to approximate shadows mechanics,
until all day=23 elements are filled. For example there are 3 full day moves from day=0 position:
wait: [1][20][0][2][0][0][4 - 2/C] -> 0
seed: [1][20][1][2][0][0][4 - 2/C] -> 0
seed+seed (if my_t[0] bound >= 2): [1][20][2][2][0][0][3 - 2/C] -> 0.
My C > 2, so all 2/C are equal to 0.
Then I need to find best move. To do it I calculate final score of all day=23 positions (cut all your trees3 while your energy >= 4, then seed 1 or 2 times while energy/3 is not changing, add energy/3 to final score, add final number of trees to final score with small factor < 1). Pick day=23 position with the best final score and run backward to find optimal move sequence. It was basic DP, some enhancements can be found in my original post.
5 Likes
I wish once in a while, we would have an “open-source” challenge. I feel I could learn a lot by looking at code from the best players, as opposed to just a description of their methods.
I understand this kills multis, buy maybe not every challenge needs to become a multi?
2 Likes
@miklla: But how do u handle which tree is getting upgraded when u have multiple trees of same size? You need this for shadows right?
As I mentioned in original post, first I simulate all legal moves to depth 2 days with waiting opponent, then I use DP. For example on first move there are around 10 day=2 states with corresponding simulated real positions, 0 day=1 and 0 day=0 states. Hence precise shadows on next and after next days are considered. It’s true that I can’t foresee some shadows 3+ days ahead, but if you want, you can heuristically add their effect as modification of score in starting states of DP. I tried it and failed to improve my rating.