Spring Challenge 2021 - Feedbacks & strategies

Contests
#75

You can take any binary data and transform it into a string using the base64 algorithm, which you paste in your source code. Then you decode that string into a binary array at the beginning of your program.

However, Codingame has the particularity of counting the number of characters instead of the number of bytes as the source code limitation. So you can do a lot better than the 6 bits per character base64 gives you by using the admissible extent of a UTF-8 character representation, which brings you up to easily 15 bits per character.

13 Likes
#76

Impressive :clap:

1 Like
#77

Not expecting you to share everything. I’ll accept all the details I can get though. Thanks. :slight_smile:

4 Likes
#78

It’s good to understand how NN (is it possible?) works, but also the training pipeline. My only known NN breakthrough bot was very leading until reCurse came and took over with 100% winrate against my bot. This motivated me to improve my training framework and given the same NN architecture it now wins against my old bot over 90% and is almost as good as reCurse’s one. And this training pipeline improved my other board games bots.

9 Likes
#79

Impressive and inspiring stuff! Thank you for linking all the external resources and explaining so much :slight_smile:

1 Like
#80

Hi, I finished around 1200th. Hardly a good or “achievement/T-Shirt” rank, but I want to tell yo a few words.

Personal record:
For first time I’ve reached the Gold League in a contest (I’ve participated in around 7 contests before that) and I’m proud of myself :slight_smile:

Lessons learned:
As always I’ve learned several things throughout the contest, which I’ll definitely try to follow the next time:

  1. Implementing a heuristic(simple if else logic) bot, based on the current game state, without looking in the future is very very important. Until now I wasn’t a big fan of heuristic evaluations, pruning moves and learning/analyzing the game myself, I just wanted to implement a general bot, given the state to output a move.
  2. But this time I’ve decided to start with a heuristic bot and it was worth it. It was fun, just chilling morning/afternoon programming, no fancy algorithms, no complex tree/graph data structures, no messing probabilities a dozen times, … only observing and trying new things. This really got me into the game and I was more and more eager to move forward.
  3. For first time I’ve watched a streamer and saw him analyzing a game of the top players very deeply (something which I don’t do), which helped me coming up with new ideas myself. Also chatting with outer players was nice.
  4. This helped me made a bot which SEEDs only when the seed cost is 0(on the best soil), COMPLETEs lately in the game and GROWs the trees on the best soil. And that’s it, this several lines of code moved me to SILVER league. In my opinion a heuristic bot could get you in GOLD, so dare to try :slight_smile:
  5. After that I was ready to make a simulation of the game with given commands sequence and look into future.
  6. The simulation part is very very important for any kind of AI approach, so implementing fast and correct simulation is a must.
  7. I was wondering how to test my simulation and came up with the idea to try classic Monte Carlo simulation approach, get the possible moves for the current turn, play as much random games from each one until the end as the time allows, choose the turn with most wins.
    After fixing simulation bugs for 2 days I saw that my MC couldn’t reach a lot of simulations, but after incorporating the ideas from my heuristic bot the simulations increased and I was able to reach GOOOLD :slight_smile:
  8. Then I wanted to implement MCTS and almost got it, but unfortunately couldn’t polish it for submit, which could got me in LEGEND, I’ll definitely try it in the classic game later.
  9. Time management is also very important, for first time I spent at least 3 hours per day for each day of the contest, which definitely paid off.

TODO:

  • I want to optimize my simulation and available commands gathering, maybe by using bitboards
  • Implement MCTS with random playouts
  • Implement MCTS with heuristic bot playouts
  • Implement MCTS with evaluation “playouts”
  • Implement MCTS with solver

The challenge was very fun :slight_smile:

12 Likes
#81

Javascript, finished 104th (legend) and the bot was a rule-based one.

First of all thanks for organizing the event, it was my first time and I loved the background of the game. The rules were pleasant and funny to read, it put me a good mood to learn the game.

To decide the action to play, it calculated a score for all possible actions and played the action with the highest score. When the highest score was negative the bot would just wait for the next turn.

Before detailling how scores are calculated I want to share the game state.

  • cells are stored in a hashmap indexed by cell index, and values were cell richness and cells neighbours - eg: it was easy to know what cell is 2 spots away on the bottom-right for a given cell: get(cellId)[1][1]
  • I had 3 trees hashmap indexed by cell index: 1/ all trees, 2/ my trees, 3/ opponent trees
    • the last 2 trees were used for performance
  • game state is stored in a hashmap, it contained:
    • nutrients, sun, sun direction
    • future sun direction: the sun direction after the turn - sun_direction+1%6 - to know what trees are blocked next turn
    • opposed future sun direction - future_sun_direction+3%6, - to know what trees are blocking next turn
    • my count of trees per size
    • opponent count of trees per size

The game state was re-calculated for each iteration.

Bot applies different weigh for scoring based on the following ranges:

  • early: days 0-5
  • early-mid: days 6-11
  • mid: days 12-18
  • late: 19-23

Bot analyses all actions and answers the following questions:
+: score increased
-: score decrased

Complete action

  • I am blocking my tree next turn: +
  • I am blocking an opponent tree next turn: -
  • I am blocked by any trees next turn: +
  • If scoring is the same for 2 trees, I will pick the one with higher richness
  • If richness is the same for 2 trees, I will pick the one who is blocked next turn

Grow action

  • I am blocking my tree next turn: -
    • when the blocked tree is already blocked by another tree: + (cancel the score)
  • I am blocking an opponent tree next turn: +
  • I am blocked next turn after growth: -
  • I am not blocked next turn after growth: +
  • Impact calculation: opponent_trees_on_all_direction - my_trees_on_all_direction (the more opponent trees are impacted the better)
  • If score is the same for 2 trees, I pick the one with higher richness

Seed action

  • I am next to one of my tree: -
  • I have a seed on the board: -
  • Impact calculation (see above)
  • If score is the same for 2 trees, I pick the one with higher richness

Thanks again for the contest ! See you next time.

11 Likes
#82

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
#83

If no one should share their codes publicly, how would the beginners learn to compete in such challenges?

#84

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
#85

For this challenge definitely not worth sharing heuristic bots (submit spam trained NN :joy:)

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. :stuck_out_tongue:

2 Likes
#86

~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 :slight_smile:
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 :roll_eyes:.
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
#87

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.

#88

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 :man_shrugging:

FYA I was around 50/50 against the boss, so depending on who is around the boss now it may be harder.

1 Like
#89

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
#90

Thank you for all those explanations. I feel really ignorant, but it opens new horizons :slight_smile:
Time, time… If only a had more of it :wink:

3 Likes
#91

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
#92

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. :wink:

1 Like
#93

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.

#94

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