Winter Challenge 2024 - Feedback and Strategies

[Nipredil]

Hi all,

How did you make it through the 4th boss? I get the basics, I build a sporer, shoot at the A shaped thing. The A thing turns into a root and then I grow, but at the end I end up with the same amount of points like the boss and no resources left.

[yhuberla]

This question has already been raised (by @Dadacticiel) and resolved (by @Dadacticiel and @Rokerjea) in the thread. Here is a recap of the discussion:

@Dadacticiel

Hello !
I don’t get how we can pass Wood 1 division. We can’t beat the boss, only draw or am i missing something ?

@Dadacticiel

OK i got it, you can spawn a new root not only on protein (i thought so as the boss was always doing it)

@RoKerjea

you need to create a harvester next to the protein, not consume it like the boss. Then you just grow BASIC organs until you win

Cheers.

[azerty_04]

I ask again : what’s wrong with my code ?

import sys
import math
from random import randint
width, height = [int(i) for i in input().split()]
def next_to(pos1,pos2):
| |if (pos1[0]==pos2[0] and abs(pos1[1]-pos2[1])==1) or (pos1[1]==pos2[1] and abs(pos1[0]-pos2[0])==1):
| | |return True
| |else:
| | |return False
def diagonal(pos1,pos2):
| |if abs(pos1[0]-pos2[0]) * abs(pos1[1]-pos2[1])==1:
| | |return True
| |else:
| | |return False
def close_to(pos1,pos2):
| |if abs(pos1[0]-pos2[0]) * abs(pos1[1]-pos2[1])<4 and abs(pos1[0]-pos2[0])<3 and abs(pos1[1]-pos2[1])<3:
| | |return True
| |else:
| | |return False
dir=“N”
def analysis(_root,thing,organism):
| |if (organism==“HARVESTER” and my_c * my_d>0) or (organism==“TENTACLE” and my_b * my_c>0):
| | |enough=True
| |else:
| | |enough=False
| | |return “nothing”
| |for i in thing:
| | |for j in _root:
| | | |if close_to(j[1],i)==True and enough==True:
| | | | |typ=organism
| | | | |if diagonal[i,j]==True:
| | | | | |liste=[i[0],i[1],j[0]]
| | | | | |if i[1]>j[1][1]:
| | | | | | |dir=‘E’
| | | | | |elif i[1]<j[1][1]:
| | | | | | |dir=‘W’
| | | | | |if i[0]>j[1][0]:
| | | | | | |liste[0]-=1
| | | | | |elif i[0]<j[1][0]:
| | | | | | |liste[0]+=1
| | | | |elif i[0]-j[1][0]==0:
| | | | | |if i[1]-j[1]>0:
| | | | | | |liste[1]-=1
| | | | | |else:
| | | | | | |liste[1]+=1
| | | | |elif i[1]-j[1][1]==0:
| | | | | |if i[0]-j[0]>0:
| | | | | | |liste[0]-=1
| | | | | |else:
| | | | | | |liste[0]+=1

game loop

while True:
| |positions=[]
| |proteins=[]
| |enemy=[]
| |walls=[]
| |organs={}
| |my_roots=[]
| |entity_count = int(input())
| |for i in range(entity_count):
| | |inputs = input().split()
| | |x = int(inputs[0])
| | |y = int(inputs[1])
| | |_type = inputs[2]
| | |owner = int(inputs[3])
| | |organ_id = int(inputs[4])
| | |organ_dir = inputs[5]
| | |organ_parent_id = int(inputs[6])
| | |organ_root_id = int(inputs[7])
| | |if _type==‘A’ or _type==‘B’ or _type==‘C’ or _type==‘D’:
| | | | |proteins.append([x,y])
| | |elif _type==“WALL”:
| | | | |walls.append([x,y])
| | |elif owner==0:
| | | |enemy.append([x,y])
| | |elif owner==1:
| | | |positions.append([x,y])
| | | |if organ_root_id in organs:
| | | | |l=[]
| | | | |l.append(organs[organ_root_id])
| | | | |l.append(organ_id)
| | | | |l.append([x,y])
| | | | |organs[organ_root_id]=l
| | | |else:
| | | | |organs[organ_root_id]=organ_id
| | | | |my_roots.append([organ_id,[x,y]])
| |my_a, my_b, my_c, my_d = [int(i) for i in input().split()]
| |opp_a, opp_b, opp_c, opp_d = [int(i) for i in input().split()]
| |required_actions_count = int(input()) # your number of organisms, output an action for each one in any order
| |for i in range(required_actions_count):
| | |if len(positions)==1:
| | | |print(“GROW”,1,positions[0][0],positions[0][0]+2,“SPORER”,“E”)
| | |elif len(positions)==2:
| | | |print(“SPORE”,3,positions[1][0]+13,positions[1][1])
| | |else:
| | | |if my_a==0 and i+1<required_actions_count:
| | | | |print(“WAIT”)
| | | |else:
| | | | |liste=[randint(1,width-1),randint(1,height-1)]
| | | |print(organs,file=sys.stderr,flush=True)
| | | |while (liste in positions) or (liste in enemy) or (liste in walls):
| | | | |liste=[randint(1,width-1),randint(1,height-1)]
| | | |if my_a>0:
| | | | |typ=“BASIC”
| | | |elif my_b*my_c>0:
| | | | |typ=“TENTACLE”
| | | |else:
| | | | |typ=“HARVESTER”
| | | | |thing_that_dont_work_else=my_roots[i]
| | | | |organ_group=organs[thing_that_dont_work_else]
| | | | |analysis(organ_group,enemy,“TENTACLE”)
| | | | |analysis(organ_group,proteins,“HARVESTER”)
| | | | |print(“GROW”,my_roots[i],liste[0],liste[1],typ,dir,“slimy sounds”)

[berthy424]

I did it but I’m still stuck in wood 1 league. Every times I get a score of 12 (and 0 proteins) like the boss. I did create harvester too but I’m still in wood 1… . What do I miss?

[yhuberla]

Is your harvester harvesting the protein A, thus allowing you to create plenty of BASIC organs ?

[berthy424]

Thanks yhurbrla, but it’s impossible. In wood 1 league you start with only 6 A protein, and the A protein is 15 cells away. It’s impossible to reach it and harvest it in wood 1 league.

[azerty_04]

That’s why you must make a sporer, I guess

[yhuberla]

Here is the explicit solution to beat that one tricky puzzle in wood 1 league.

1. Build sporer next to root organ, aiming towards A protein.
2. Shoot sporer as to build new root close to A protein.
3. Build harvester next to A protein in order to harvest it.
4. Fill grid with BASIC organs.

Best of luck in the silver league.

[berthy424]

Oh thanks, I was misundertanding!! I thought it was necessary to shoot the protein to cerate a new organ! So what I missed is that it is possible to create a new organ with a spore at any place in the direction of the sporer.
Thanks @yhuberla

[MarkZ1]

When I try to grow a spore at the first turn, it fails with an error message: ((23,1)) is not to the E of ((0,1)). Is it a bug?

[_CG_KevinGuiraud]

Hello, this should now be fixed.

[_CG_KevinGuiraud]

Hello, you cannot spore there because a wall is in the way. The error message is wrong, this is now fixed:

[azerty_04]

So, do someone know how to fix my problem ?

[CoderSherlock]

The game input occurs such that initially ,the input specifies all initial placement of objects. And later input (after your output) describes changes in the environment (like a cell which was blank earlier has been converted to a organ) If you want to avoid conversion of walls you will have to declare the container( set /list or whatever you use) which stores the walls before the while True: loop of game , so that the data that you initially obtained about the walls doesn’t get lost.

[LoganWlv]

I really enjoyed this challenge—thank you to the CodinGame team for continuing to make it happen!
I finished 171st, but there’s nothing particularly interesting about my strategy.

My code consists of a mix of closest pathfinding functions combined with various heuristics. Each path has several characteristics that are used in the heuristics (e.g., eating a protein, being able to harvest a protein, posing a danger to the enemy, etc.).

The strategy is as follows: first, perform defensive moves; then, execute attack moves if there are “enough resources/income”; otherwise, focus on farming moves.

GG to @wala for the usual top 1 spot with Java (it was close, @Zylo)!

[yamo]

I finished 99th. Thanks a lot for letting me finish in the top 100

Here is my PM : My post mortem for the codingame Winter Challenge 2024 | Yann Moisan

[aropan]

I just leave this here.

[IloIlo]

Hi all,

I ended up Legend #32. Felt good to get to Legend after several contests being unable to do so.

I want to thank to Codingame for hosting another great AI programming contest. I’ve been playing them for lots of years now and still eagerly await for them and really enjoy playing them . This contest was particularly interesting and well crafted, with good possibilities to very different strategies, be it heuristics, simulations or NN. Congratulations to the creators and keep this contests coming !

Congratulations to reCurse for winning and MSz and aCat for completing the top 3. Your bots are amazing, I really enjoyed watching some games by them. I would have enjoyed it more if they would have been more time to watch them though . I still don’t quite understand the need to only join in the last hours of the contest, but still…

I originally tried using Smitsimaxi (Decoupled UCT) but couldn’t make it work since the branching factor is so high and the potential actions depend on the state of the game. I ended up implementing a beam search of width 5 and depth 3 for each organism. I don’t simulate the opponent.

Here are some details of my implementation:

Actions

• I divide the actions into “walk”, “spore” and “non-walk”.
• Walk actions are non-spore actions to get closer to some protein or to the rival. They usually would be basic, but could be tentacles, harvesters or sporers depending on available proteins.
• Spore actions could be either just spore from an existing sporer, or a grow_sporer + spore combo which uses 2 turns. Non-walk actions are either harvesters that harvest some protein or tentacles that attack a cell with dist to rival <= 2.

Pruning

• I simulate every available non-walk action, but only simulate the most promising 2 “walk-towards-protein” actions, 2 “walk-towards-rival” actions, 2 “spore-towards-protein” actions
  and 2 “spore-towards-rival” actions. So at each node expansion of the beam search I simulate 8 + N actions.
• The heuristics for determining the most promising nodes is based on distance to rival and distance to most needed protein sources.

Eval

• 1 point per organ
• 0.5 points per unoccupied cell closer to player (voronoi style Voronoi Diagram - GeeksforGeeks)
• 0.35 points per protein
• Points per harvester. They decrease incrementally as the number of harvesters of the same type increases, following a logarithmic decay function.
• Points for being close to protein sources.
• Points for attacking cells close to the opponent.
• Big penalty for not having enough harvesters to allow me to grow any kind of organ (no A and no any pair of B/C/D).
• Penalty for distance to closest protein sources that I have no harvesters of.

Note: Points for harvesters and being close to resources decay over time and are lower the more proteins of that type I have.

Data structures and algorithms for efficiency

• Every cell knows if it’s being harvested by any player, attacked by a tentacle of any player, the distance to the closest cell from both players, the neighbors in every direction.
• At the beginning of each turn I run an initial bfs from every cell to calculate distances between any two cells, the predecessors in the paths of any 2 cells and the heuristics
  score for closeness of proteins and opponent organs used in the action pruning.
• For each organism I keep track of the frontier (the unclaimed cells dist 1 from any organ of the organism).
• I create every object I will need in the first turn. I have an action pool and a beam node pool.
• I use only 1 game state instance to run simulations.
• I keep track of the modified cells in each simulation to rollback more efficiently.

Thanks again and see you all on the next one !

[0x6E0FF]

thanks for the detailed PM, can you indicate roughly how many turns you managed simulate in the 50ms time limit?

[blasterpoard]

#7 Legend
I started by messing around with deep searches, trying to figure out how deep could I go if I got creative with pruning. The result of that was a beam search that could on the first turn easily get to depth 20 with width ~3000 on maps with a lot of walls (often under 200ms), and at least figured out where I should start putting my roots on the more open maps (~depth 8). The heuristics I used to prune were:

• limit to 4 organisms; after growing the 4th one, the bot stops following the beam
• every sporer has to make a root immediately
• limit sporer and root options to 2-3 most promising ones per organism
• after growing a basic organ, the organism has to build something on the newly-neighbouring squares next turn
• use only basic organs to move, and retroactivaly change them to other organs if I run out of A
• prune non-optimal sequences with harvesters (that lose resources compared to options that build harvesters sooner)

The nodes were evaluated based on the resources, the distances between the roots, and their position relative to the opponent’s first root.

The bot follows the results of the beam search until it meets with the opponent, possibly inserting other moves found by my other algorithm if they don’t interfere with the beam.

I wanted to keep looking at deep searches for 2 players with similar (or even more aggressive) pruning, but unfortunately I got sick a couple of days into the contest, so I gave up on time-consuming apporaches and switched to a “simple” depth 1 bot. I chose to use genetic algorithm with 2 populations - 1 population per player, 1 gene per organism, evaluation by simulating them against each other and rewarding destroying/threatening organs and quantity of resources (and distance to the ones not being harvested). I thought this algorithm was just a meme (I saw it in another postmortem), but surprisingly it could have worked somewhat well. Its biggest problem was that in rock-paper-scissors situations, which were rather common, it kept switching between the options every couple of generations and often chose some of the weirder ones - which I fixed by having one last “generation” of all the unique winners of the previous previous generations.

The vast majority of my bot’s losses were due to the beam search coming up with a specific solution, which the genetic algorithm forgot as soon as it took over, not grabbing space early on (because I would need to tune my beam search’s eval based on the characteristics of the map), and my genetic search’s eval being quite bad at evaluating fights taking more than 1 turn.