Is my calculation of the line wrong? I’m shooting from (2, 4) to (4, 5). The obstacle is in (3, 4).
My calculation from lower Y to higher Y = (2, 4) (3,5) (4, 5).
Somehow it still hits the obstacle.
This seems to be happening more often. Looks like it starts one square to the right of the character? Same thing happens here starting from round 82.
Looks like your calculation is wrong then. You can find the referee implementation here
Specifically in your case the function “bresenhamForward” starting in line 285 computes the bullet path. There you will see that the path starts at (2,4) and the next tile is (3,4) thus hitting the obstacle and returning the tile (3,4). I hope that helps you and good luck! 
Ooh alright, thank you very much!
So I literally implemented the code above. But at move 76 it still calculates wrong. I don’t know how to fix this then…
I’m definitely enjoying the game so far - thank you to the team that developed it!
A quick question - I’m noticing the source code is starting to get more regularly published. For those not familiar with Java, is there a basic guide somewhere about how to use the source code to run simulations? I looked through the files and so far have only managed to use it to adapt the bresenham logic. Thanks!
Try cg brutaltester GitHub - dreignier/cg-brutaltester: A local arena for codingame multiplayer puzzles though i don’t see fork for cultist wars yet.
1 Like
I have the exact opposite example, as seen on turn 18 of this replay.
I calculate a collision, but the opponent’s 9 doesn’t care and hits my 3. Shouldn’t this behave the same way and hit the neutral unit instead, since paths are always drawn from lower y to higher y?
Both scenarios in a single match:
At turn 82 the silver boss hits me from (8,6) to (6.5) ignoring the (7,5) obstacle.
However, at turn 116 it can’t shoot from (6,6) to (4,5) because of a similar obstacle.
I ported the source code to C#, it’s all integers so there’s no rounding involved.
What gives?
It hits your leader, so the path is a little different and your unit is in the way, so it’s hit instead. I believe such case was overlooked when creating the game.
Oh I see what you mean, I didn’t think to check the output stream. 12 SHOOT 0.
Thanks!
Eehh, I don’t know how I feel about rewriting my entire approach for this.
Found by some folks on discord:
bresenhamForward Bitbucket
bresenhamBackward Bitbucket
One returns tile, the other one sets the targetTile. Dunno if there are cases in which it doesn’t work as intended, but one should be aware.
1 Like
Just a bit of strategy here…
If the opponent leader is chasing one of your cultist, it may be preferable to shoot it to death.
This means -1 unit for you instead of -2 units if it is converted !
BTW, I do not shoot on my cultists by principle !
2 Likes
Place 30 during event, so near top silver. Maybe some words for newbies
I’ve spent around 6 hours in total working on this event. Since I’ve had so little time I knew there would be no way to implement minimax or anything similar. So I went for simple 1-depth search
- compute all possible moves
- simulate game turn for each of available moves
- score result from simulation
- pick best move
Evaluation step 1 - Conversion
Make sure cultist leader is able to capture cultists even if trapped
#1 priority was to make sure I’ll convert some cultist. So flood fill to closest neutral cultist is just OK
#2 don’t get stuck. Higher score for cultist going closer to center than moving cultist leader
Evaluation step 2 - Shooting priority
Let’s deal some damage
#3 pick option that shoots opponent for as much hp as possible
#4 prefer killing enemy cultist before just shooting at somebody
#5 prefer killing enemy cultist leader before killing cultist
Evaluation step 3 - Survival
Fall Back!!!
#6 pull back if in danger (boolean)
This was most funny part. My cultists were able to run from dangerous situations (lets say 90% of time) based on following simple hardcoded part:
val cultistDeathThreat = when {
cultist.hp == 1 && dmg >= 1 -> true
cultist.hp == 2 && dmg >= 1 -> true
cultist.hp == 3 && dmg >= 2 -> true
cultist.hp == 4 && dmg >= 2 -> true
cultist.hp == 5 && dmg >= 2 -> true
cultist.hp == 6 && dmg >= 3 -> true
cultist.hp == 7 && dmg >= 3 -> true
cultist.hp == 8 && dmg >= 3 -> true
cultist.hp == 9 && dmg >= 3 -> true
cultist.hp == 10 && dmg >= 3 -> true
else -> false
}
There is lot of room for improvement, but this bot brought me satisfactory results for given timeframe.
So I was playing around with this scoring function →
score =
- ? * distanceToClosestNeutralCultist
- ? * sumOfDistancesFromMyCultistsToCenterOfBoard
+ ? * myCultistsHp
+ ? * (if (cultLeaderInDanger) -1 else 0)
+ ? * (if (cultistInDanger) -1 else 0)
+ ? * (myUnitCount - opponentUnitCount)
+ ? * (myLeadersCount - myOpponentLeaderCount)
8 Likes
Heurisic
92/544 global
78/98 silver
I used a simple heuristic working like this :
- 1/ Search for the neutral closest to my leader, not with manhattan distance but like in a maze, with a BFS. In the BFS, a cell where the opponent can shoot my leader was like occupied cell.
- 2/ Find if i can shoot someone, and retaining the shoot that makes the most damages
- 3/ Decision : should I convert or should I shoot ?
=> if i can make damages, i shoot
=> else, if i found a neutral to convert, move to him and convert
=> else, move the soldier that is closest to any opponent (with manhattan distance this time)
It was a simple heuristic but good enough to defeat the bronze boss.
I was close to the top 50 most part of the event, 65th the last morning, but a lot of people worked hard the last day when i wasn’t here, and i finished 92nd.
This event was really interesting, i missed the chat but i learnt a lot about minimax and i regret i didn’t have time to do it.
Look forward to the mext one
8 Likes
~top 20 silver.
Nothing much, I once again had little time and only two days, one of which I spend writing some strange fixed depth EPT MCTS, and another on debugging and trying to make it work with the help of visualizer. Quite a fun game, thx to Nixerrr for making it and to CG for pumping it up. This format of small contest looks nice and I hope this is not the last one.
8 Likes
Firstly, to CG: thank you! Awesome format and the leagues were such a good addition, also having difficult bosses was awesome too.
11/98 silver, 25/544 global, fairly shocking rank in my opinion 
Iteratively deepening alphabeta, some move ordering based on best move from previous depth and shallow search.
Had an existing bot but it had a few bugs here and there. Didn’t have to change much in the simulation, it was very fast, everything was bitwise-packed into integers so at least I didn’t have to spend time on making it faster.
The whole thing would have been a lot more effective had I not switched + for - in two places in my evaluation function.
Which I discovered 49 minutes after the contest ended
Anyway, had a lot of fun, was nice to see so many competing and it’s been great talking with everyone who’s been active in the discord. I hope to see more of this in the future!
6 Likes
Place: around top10
My search is alpha-beta with iterative deepening.
Evaluation function:
- hp of units
- big bonus for each alive unit
- when alive two leaders: small bonus for each nearest neutral unit (manhattan distance)
Ignored moves: wait, shoot to my units, shoot to my neutral units (for left player: x < 6)
Thanks to CG for the contest!
6 Likes
Place 2nd
Minimax with NN eval like stockfish in chess.
In the minimax part, I used negaalpha with move ordering and iterative deepening. Mean depth is 6~8 in the middle of the game, the simulation is ~30k per turn.
In the NN part, I used a simple fully-connected 364-32-32-32-1 model. As input variables, I used total health diff, unit number diff, distance to the nearest neutral from leader, the neutral units distance distribution from leader, the number of units in each row and column etc…
This is the list which made my score in the leaderboard better.
・Simulation of neutral moves. Thank you jacek for telling me how the LCG works in discord.
・Taking into account Indirect shoots. Since 50-70% of my execution time was used for NN calculation, checking all the combinations of shooter and target doesn’t slow down my simulation.
・Move ordering in minimax. This incredibly reduced the node to evaluate. In the final submission, I used some heuristics with a killer move.
・The distance distribution from the leaders in NN input. This prevents my leader from going to smaller groups.
・Optimization. I read “Optimized c++” this year, and it helped me a lot. Pre-calculation of bresenham’s line for all combinations of two positions in the first turn and caching the NN result in unordered_map<int,float> by using Zobrist hash may be noticeable.
This is the list which helped me a lot to improve my bots.
・Making a local arena to evaluate and self-play my bots. As many other legendary strong codingamer written in the past PMs, this helped to measure if my change is good or not. I compiled the judge’s java code by mvn assembly:assembly -DdescriptorId=jar-with-dependencies.
・Taking a profile of my code.
・Making a visualizer. I also plotted the evaluation score vs turn. I can find my evaluation function defect easily by showing the evaluation jumping.
Sorry for omitting the many terms’ explanations and the code details. I have no idea which parts I should describe in detail.
This contest was very educational for me to learn the details of stockfish-like minimax. (Actually, I read some articles for shogi and othello in Japanese.) And it was super fun to compete in the leaderboard and it motivated me so hard.
Finally, thank you CG for this contest and @Nixerrr for this great game!
18 Likes
We asked for more bot contests and CG delivered ! Kudos for all of you !
For a first, the event has been a great success regarding the number of participants (3 times more people compared to the multi leaderboard). Even if it was not an official contest, the level was quite high and the boss were insane.
I think the duration between leagues openings could be better balanced: there were 4 days for silver, 1.5 for gold, 1.5 for legend. I would prefer 3/2/2.
Finally, now that the contest is over, it would be nice to have those new leagues for the multi. We still have some pesky bosses to beat …
6 Likes