Yes, it would be a good thing if CG completes the multi with every bots and new leagues, like other contests.
4 Likes
Took 7th place. Used very basic alphabeta with simple estimation function: (sum of squared roots of health of our units + sum of squared roots of health of neutrals if our leader is alive, divided by 2) * 100 - distance between our leader and closest neutral. If all turns in minimax search are equal then just send our leader to the closest neutral or our cultist with max health to the closest enemy.
8 Likes
Firstable: thank you very much CodinGame for this event, this is definitely the format I enjoyed the most to play. Playing multis alone with unlimited time to play does not motivate me the same, it feels nice to play to the same game with other competitors simultaneously, for the challenge, the help you can get/provide, boss openings⌠I even like the time constraint (that allows me to go back to real life once the challenge is done). I hope there will be more to come !!
Now for my humble post-mortem, which will feel a lot like the ones above:
Finished 13th global, 8th gold
It is a minimax implementation, with alpha beta pruning and iterative deepening. It was my first time minimax (and i had not played to this game before monday), so I did not have the time to study and implement all the various possible improvements (no move ordering, no transposition table⌠just alpha beta). For future me (or you): donât try to implement a minimax with a stack, I did it, it was hard and costed me some time, and perf was worse than a 40 lines recursive alpha betaâŚ
My node generation is very fast, so the bot managed to keep a depth of 6-7 in mid-game without all the possible minimax optims. I took the time straight from the beginning to ensure that state generation was strictly the same than what happened in the referee, time well spent IMO as I did not have to come back later to wrongly moved neutrals or stuff like that.
For my eval, nothing too fancy: big weight for living units on both sides, smaller weights for HP of the units, and some small tunings. Also: I precompute all the optimal distances from point A to point B during the first turn (with standard dijkstra), to allow a better hinting of moves for my cult leader.
Missing in my bot: indirect shots are not computed (I felt it once in goldâŚ), wait (not sure if it worth but still), better search,âŚ
7 Likes
Dumb heuristic
79th global, 65th silver.
Used a simple heuristic, seemed appropriate for the time I had to spare.
BFS to get distances across the board, scoring based on what I felt should be more important and worked from there:
- [Leader] Prioritize converting (small bonus if I can take enemy instead of neutral)
- [Leader] Am I in danger? Are there enemies which are too close? Prioritize running away, otherwise move towards the closest unit I can convert.
- [Cultists] Try to do as much damage as possible, with bonus points if itâs the enemy leader.
- Pick best rated move
Very simple, but was good enough to reach silver. Spent another hour or two fiddling with the parameters, basically âhow much should THIS move be worthâ, but ultimately didnât notice much gain compared to initial version.
I also tried considering âdangerousâ cells as obstacles in BFS (if cell X,Y would kill me in 2 turns, itâs an obstacle), but my bot was way too cautious (scared, actually), so it would mostly hide near the start and not convert many units.
All in all, fun quick contest, game was simple to understand and get started. I kind of regret not trying harder, since I gave up when bot reached top 40 and just left it there, ultimately losing another 40 positions 
6 Likes
3rd, used best-first minimax with uct (similar to mcts-ept) with NN eval
Given that the game was known a month before, I slowly wrote simulation part and was looking for appriopriate inputs for the NN. At first I wrote minimax considering neutral units didnât move. Didnât want to do expectimax etc., the randomness of the game seemed just a mere curiosity. Then I found out the units movements were deterministic and we know the seed. Of course I encountered some bugs trying to determine the seed, given that referee doesnât remove dead units and it still considers them in the random call. The classical eval for minimax was number of units, leaders, some hp. I also found that history values were important too, probably because it prioritized converting in the beginning.
Then I switched to NN and was searching for right inputs. I used td-learning (td-gammon style) for pretraining, it was fast and showed which archtectures were good. Then I settled on something like 729 inputs (8*91+rounds). My final net is 729x80 + 80x80 + 80x1. Then after td-learning training, I used 4-ply minimax positions for texel tuning-like training. Few iterations of such training and this is what I got so far. I wonder if the same net would be much better if I let it to train for much more time. Hopefully leagues will be moved to the multiplayer section.
I enjoyed this contest. Iâm glad there are more events like this on CG recently. Although this was the first one without the chat and the website seemed dead. None of the staff was talking on the discord, except when submits stuck there was quick reaction to fix it. While there were some discussions with other users on discord, they seemed less than if they were on the chat.
Props to @Nixerrr for making this multi.
12 Likes
Hello,
An event ended yesterday with this challenge. I participated in it without searching what community already shared about it.
I was unable to find a simple efficient algorithm approach in time.
I was hoping to make a brute force approach to best distance with obstacle calculation to work, and hit the timeout wall, had to kept a simplistic distance calculation to avoid timeout. 50 ms timeout seemed was short for my desired build fast code brute force at runtime approach.
Best regards.
5th, used an iterative alphabeta with transposition table and killer moves.
So nothing fancy here, in fact this was supposed to be the sparring partner of a Best First Minimax program using Descent Algorithm to learnâŚ
I chose not to use the whole board as input for NN but to use elements of the evaluation function I have for the alphabeta program⌠And even if I learns, I was more able to make the alphabeta program evolving far more.
How, using a Texel like tuning algorithm using 40000 self played games, in fact I was doing logistic regression to the result of the game and the evaluation was the part before the sigmoid function. So only a dot product of the features and some weights vector.
I also chose to split the evaluation in 3 categories learned separately
- There is no more neutrals => Leader are then fragile
- There is only one leader and still some neutrals
- There is neutrals and zero or two leaders
The last one where chosen to decide the weight factor so that a cultist with HP=14 was 1000 points.
3 domains of eval mean some blemish effect (for example the player keep a neutral till the end to not go from category 3 to category 1) but this was ok most of the time.
Elements of the evaluation:
- weigths for leaders health (so 22 , eleven for the player to move, eleven for the other player)
- weights for cultists health (so 20)
- weights for neutral health (so 10)
- 2 weights for the flood-distance for the nearest neutral to each leader
- 2 weights for the average flood-distance to the neutral for each leader
And that is all.
At the end for category 3 and 2, weigths 4) et 5) were optimized with a monte carlo search.
(was sufficient to go from Gold to Legend and even Sunday at 15:00 to be third before MsZ and Trictrac new versions)
I enjoyed this contest, the discussion we had with Jacek, the end with MSz new versions 
Thank you codingame, a regular chat was missing that is sure !
Congrats to MsZ, KawattaTaido, Jacek and Trictrac and also to all who entered this challenge!
Back to real life now !
11 Likes
Heuristic
57th, python
This was fun and hard to gain an intuition on. It completely matches my expectation that look ahead with ab-pruning was the superior approach. I would like to try my hand at implementing one.
Heuristic priority:
- convert adjacent
- shoot if possible
- move to convert closest by bfs
- push along shortest path to closest enemy where the exchange would be a win
Would love to see the bosses and leagues transitioned to the multiplayer version. Thanks for the contest, cheers all.
3 Likes
8th, like many others I used an alpha-beta search with iterative deepening and a transposition table.
Unlike most, I did not consider shooting neutral cultists in my search. Although I think this decision ultimately limited the ability of my bot, it seriously reduced the branching factor and therefore simplified a lot of things for me.
One of the things that helped me the most was setting up a sort of local arena, in which my bot could play games against the previous version of my bot. This was easy to multithread, so I could have self-play games running concurrently on the 12 threads of my CPU. With the winrate information, I was able to improve my evaluation function and increase my self-play winrate by about 20% (It seems health points are a lot more important than I initially assumed).
For the simulation, generating all possible âSHOOTâ moves was taking most of the time. I wanted to bitboard the game but wasnât sure how to do so, as the game has 91 squares in total, which is more than the 64 bits provided by a long long in C. This is where I learned about the so-called __uint128_t type which is provided by GCC, but is not part of the C standard. Luckily, CodinGame uses GCC to compile C code, so we can use it.
I added a __uint128_t occupied variable to my Board struct, where the nth bit is 1 if that square is occupied by an obstacle or a cultist, otherwise it is 0. Then I made a lookup table __uint128_t shotPath[91][91], which is first indexed by the square of the shooter and then by the square of the target. The result is another __uint128_t, where a bit is 1 if the corresponding square is on the bresenham line between the shooter and the target, and 0 otherwise. Using this lookup table, checking if a shot was blocked became as easy as taking the binary and of the occupied bitboard and the result from the lookup table. If the result is zero, the shot is possible, otherwise it is blocked!
As always, the most important thing that nobody ever mentions for some reason is to write a lot of unit tests (I had more lines of test code than âactualâ code!)
I enjoyed the contest a lot, and Iâm looking forward to the next one!
12 Likes
Would you mind elaborating on this detail? I donât immediately see why using a stack should be so punishing on performance. I want to go back and try a minimax approach. And consequently, I would like to avoid common pitfalls.
1st.
My bot uses iterative deepening alpha-beta with classic improvements from chess engines (hash move, quiescence, aspiration, futility, etc.).
The point was to make it very efficient. Even a small optimization was giving a noticeable improvement in the agentâs strength. Also, I prune many less relevant moves, depending on the position and the depth.
The evaluation was kept simple but fast; just material and distances between units, based only on precomputed BFS values. It was further simplified at the cost of quality to make the search even deeper.
Of course, exact simulation with neutral moves and indirect shoots was obligatory. With these, the rules of the game are only apparently simple, making the creation of an efficient simulation engine non-trivial and very interesting. For instance, it is possible to detect a potentially killable unit with one 128-bit mask operation.
These allowed computing about 120k states/turn in the middle of the game, which translates to an average depth of about 16 of the (pruned) search. With this, I think the benefits from neutral move prediction are much larger and local battles are better solved, as these are the things difficult for evaluation.
Thank @Nixerrr for the game and CG for organizing!
Certainly, it would not be possible to reach such a level of playing in a 10-days contest. Giving at least a month allows for doing some research around and learning new techniques, instead of just coding already known ones as fast as possible (and it is more compatible with normal life).
17 Likes
Dealing manually with stack instead of using recursion in minimax is bug-prone. While generally recursion calls are expensive, theyâre very negligible in comparison to entire minimax algorithm, even with very high depth. Not worth to deal yourself with them using the stack. Just call minimax recursively if needed.
3 Likes
I can see two main disadvantages (at least):
- first, even with a small state (mine was 78 bytes), you have to add metadata to your node (value, parent node,âŚ). And youâll have a lot of nodes generated, as this is a DFS algorithm. So in term of data locality, itâs worse
-second is really linked to my implementation: in minimax you have to loop over child states and you evaluate them one at a time recursively. But when you do it with a stack, itâs pretty hard to generate only one child state of the node and come back at your generation state later (or you have to store a lot more metadata to create a good iterator, and still it Iâll be expensive). So the trade-off I made is to stack all the child nodes systematically. Alpha beta pruning was done by skipping all the nodes between the one that triggered a branch cut and the parent node on the stack. But it was sub optimal, as it generated a lot of nodes just to drop them afterward.
So to conclude: it is doable, but you will face a lot of challenges that you wonât have while implementing a standard recursive alpha beta (which is very straightforward).
2 Likes
Extremely impressive!
I had some hard time finding good material for acquiring knowledge on minimax optimization techniques, would you mind sharing some of your sources ? (Papers ? Chess bot implementations ? Books?)
1 Like
A lot of up to date information here https://www.chessprogramming.org/
And there is a lot of chess program on github, including stockfish which implements a lot features.
OldJohn
4 Likes
28th in general, 2nd Python
Strategy: quick and dirty, maximum result with little work
Tools: IFâs, BFS for path finding, evaluation for [shoot, convert, move]
Specials: for leader move-convert path, all cells are rated +5 if neutral is neighboring and -max_shot_damage for that cell if that cell is in the range of an enemy.
No simulations
2 Likes
Very special case, i canât understand the calcul even by seeing the return difference between backward and forward.
turn 40 to 60 is very special to admit in this replayâŚ
in this case it seems to be the bresenhamBackward that is used.
I used the code but it return me the great 2 7 target when the id 2 is shooting⌠which we can also see in the replay.
Maybe it is normal but it is totally unfairâŚ
Yes that is normalâŚ
In fact Left shoot for cultist 8 and the cultists on the left are on the path so they are hit instead. This is one more example of indirect shooting
1 Like
why are they in the path they shoot the obstacle ? (for cultist 12 and 10 canât shoot and 2 can ? WTF ? seriously ?)