Amadeus challenge - Feedback & Strategies

Share your feedback & strategies here ! :airplane:
Final ranking here

Note: I’m part of Amadeus but not in the organization of this challenge in any way, just happy to read player PMs :slight_smile:



Sucker punch


Here’s my bot layout:

Fun game overall.

Finished 17th in Java

As many already know, at Amadeus we already had the exact same game during a private contest in 2017 (1.5 day duration).
So the 5 of us participating here had a nice bootstrap :slight_smile: (well done btw Adrien for the tool)

except that for me the code kept doing timeouts, and I was barely able to understand what we wrote not even a year ago (frightening ! :fearful:).

I was kind of motivated since it was my company’s challenge, so restarted from scratch, wrote the simu for the first time since MM (quite easy to implement even without a referee, for once), then implemented a minmax depth 1 (considering the opponent will always choose his best move against mine).
Since the search space was very large, for the action selection I only considered assigning all 5 units on the same planet, with or without spreading a “spreadable” planet. Later I added 3/2 type actions.

My engine / eval performance was below average I guess with maybe 7K simulations done per turn, so I had to implement some move ordering (ranking first the planet closest to some opponent units) and killer move to be able to do at least a depth 1 entirely (which was not always the case on large maps).
I’d be too easy to blame Java on this quite bad performance, and using JVisualVM I wasn’t able to find clear hotspots, so it’s definitely an area where I need improve for next times…

Finally regarding the eval, a mix of voronoi, total number of units, total number of controlled planets, all of this biased by distance to closest planet controlled by the ennemi. The coefs of the eval were dependant on the overall game progress (more weight on voronoi / units at the beginning, and only on controlled planets at the end).
I also implemented a detection of the articulation points in the last day, to treat them a bit specifically in the move ordering and evaluation, the detection was accurate but didn’t helped to improve the bot overall.

In summary fun contest which proves that simple rules can make an interesting game even for 14 days (one of the longest contest on CG along with TA and upcoming LOCM) !


I’m not that motivated at these private contests, so I only coded on the first weekend (and had a short look at the game before, changed a few parameters after).
I use a Monte Carlo search with depth 1 and don’t even have sacrifice actions apart from the rush to the articulation point.

As this game won’t become a multiplayer, I’ll just share my code (which I’m really not proud of): link.

1 Like

I also lost interest when i found out there’s no legend league. And i know it doesn’t matter much but on that same day i saw my bot briefly above all amadeus bots (at that point only darkloup was above me) so i thought, well the company bots are “defeated”, time to move on. The last bit of motivation had faded away …

I used an alpha-beta minimax. On the first turn I calculated distances / shortest routes between every planet, worked out if there was a good articulation point and calculated a value for each planet to be used in the scoring (I started with this as number of edges, but was changed to average distance to all other planets on the last weekend to prioritize the center). If there was an articulation point more than 2 distance away from my closest planet I had a hardcoded start to get there as fast as

I had 3 different scoring functions (articulation point uncaptured, standard and endgame)

  • EndGame was used on the last 3 turns, and was purely based on number of planets owned.
  • Standard had a voronoi component, and then each planet gave a score based on owner, number of units there, number of edges owned by me vs enemy all multiplied by the planets ‘value’ mentioned above.
  • Articulation point uncaptured took the standard value and added a lot of bonus score for number of units squared on a planet based on the distance to the Articulation point (number of units squared to encourage building up on one planet rather than splitting between planets of equal distance).

I had a complicated move generation system to allow the minimax to get to a decent depth

  • 5 / 5 + spread on a single planet
  • For the first enemy turn or my first/second turn allow 5 to a planet + spread on a different planet.
  • At depth 0 for me allow 4 to a planet with 1 to a different planet (I think this was a strong defensive move - eg if you owned the articulation point you could put 4 on it, 1 on the neutral on the other side and end up with more edges than the enemy so if they put five on it one would die and it would revert back to you). I didn’t allow spreads with this.

At depth 0 this generated a large amount of moves so I filtered it further by removing any planets as affect destinations if they were owned by that player and had no enemy owned neighbours unless they had 3 neutral neighbours (so a spread could save a lot of turns), were the closest playable distance to the articulation point or had any enemy units on them.

I didn’t allow spreading from the articulation point ever or spreading from its neighbours with only 5 units (as that planet would go neutral and the enemy would win on edges).

I did a lot of testing of allowing more moves, allowing the enemy to use my generation but found this gave the best results.

I really enjoyed this contest, even if the end results didn’t go my way. Congratulations to Daporan for clearly having the best bot. It would have been nice to have more games / rerun / best of 5 at the end as the rest of the top 5 was very close, but I think I probably would have ended up in the same place (with more games I feel recurse would have got second and me / y_kawano would be very close for third). I went very heavily onto winning articulation points which gave me a good lead throughout the first week and a half but they slowly turned into draws as others improved (after one submit at the end of the week I ended up with 14 drawn games out of 18 against y_kawano).


What depth would you reach on small/big maps ?

Thanks for the details !

This game was a good example of simple rules with good depth, it’s a real shame we won’t have it in multi. Could have used less maps with critical articulation points though. One interesting thing is this game shares a lot with CotC on the uncertainty aspect, as there are many situations where there is no best move, only a handful of them with rock-paper-scissors interaction. That’s another reason I would like to see this game again as there is no other quite accomplishing that so evidently.

I am starting to get quite annoyed with the format of no reruns and barely any games when submitting on top of a RNG-heavy map generation. With the costs incurred by the amount of players using the IDE, doing batches, etc., it is hard for me to understand why there is no budget left for adding a few hundred games at the very end for top players to make it more fair, which must be a ridiculously tiny fraction of all games played during the whole contest… Anyway, sorry for ranting, but I believe this is mostly why I finished third and not second place.

For better or worse I quickly discarded the idea of minimax because of the amount of combinations in planet heavy maps, as I did not think aggressively pruning the moves would work well enough. I also thought there would be a lot more subtlety on how to distribute the units (though tolerance ended up limiting quite a lot of that). But I was completely wrong as I may be the only one in the top not using minimax (except maybe for another one but since he never shares, who knows).

Instead I went for some sort of competitive evolutionary search where I maintain one pool of moves for each side, and I evaluate each move against some of the “best moves” of the opponent, using the worst case to determine scoring. I still believe sampling is necessary when the branching factor is too high, but my experimental approach raised more problems than I could cope with for the amount of time I had. I also hoped this sampling would allow me to reach depth 2, but had no such luck getting it to work well and quickly enough. Still a fun experiment overall though.

Scoring was nothing too special, mainly using the number of owned planets and shortest distance to neutral ones to determine which player “controls” which planets. The fancy part was in determining a front line (max distance of 2 for both players) and scoring those planets based on units+tolerance*5 to determine how “contestable” a planet is, along with its influence (number of controlled neighbors). I then heavily weighted towards distance <= 1. This allows to figure out which parts of the maps are stronger/weaker and focus on defending/conquering those. I had an end-game toggle (last 3 turns, coincidentally enough) to only focus on controlling planets.

For maps with a critical articulation point, I used distance*units and scaled to roughly powers of 7 so spreading would be seen as beneficial. I tried squaring units like Robo for favoring pooling units at the same place, but it was conflicting too much with other stuff, and no time left.

I also tried a lot of complex scoring that didn’t work out…

It was fun overall, I hope to see more “simple rules yet having a lot of depth” games like this in the future.


I ranked 13th :slight_smile: with a minmax.

First of all, due to the high branching factor, I chose to always spawn all the units on the same planet, and to spread only from the planet chosen for the spawn and its neighbours.
Then, planets that are far away from planets to capture are removed.

My scoring function gave a score for each planet: a bonus if the planet is owned by the player, the number of units on that planet and the number of units on its neighbours.
The planet’s score is then weighted by the “importance” of the planet, witch is computed at the beginning of the turn thanks to a Voronoi diagram (it’s the difference between the size of the Voronoi area with and without owning the planet + 1).

Since this contest probably won’t be available on multi, I think I can share my code (C++, but written in French):

I think this contest was a really good one, because the rules were simple and easy to understand, but many different strategies could be used.

I just didn’t like the fact that some people hid their AI, and only revealed it at the end of the contest :rage:

BTW, I used this contest to test a tool I made: CG-Ranking! :slight_smile:
It’s the one @Jahz used in his post (thanks!), and it will be available for the next contest (only the Marathon). It shows the evolution of a player’s ranking.


The problem is with the platform design that makes it the best way to be as competitive as possible, not the participants making the best out of the rules.


Nice tool! In the past I made screenshots to track my progress and find a good version of my bot again (or cried if I forgot it).
Feature request: save the agent ID too and show when a new version was submitted (at least if you show a single player, would probably get messy with more).

Example from the russian AI cup:


I finished #5 overall, here is a description of my AI :


I started the contest one week after it started. At first glance I was scared that this will be a GITC bis, i.e. a contest in which a pure heuristic beats everything else. After a longer look at the top games, it appears that this wasn’t the case since unlike GITC, there is a quick and direct interaction between the two opponents. R4N4R4M4 proved that heuristics belong to the top too, but it seemed that the meta would revovlve around simulation-based solutions.

Almost every multiplayer game can fit in two main categories, PvE and PvP games.
PvP : TRON, CSB, WW, …
PvE : CR, STC, HS, …

For the first category, minmax seems to be the right choice of algorithm, whereas GA/MC/SA fits better the second one. There are exceptions but it’s often the best choice imho.

This game belongs in the PvP category because of the previously mentionned direct and close interaction between the two players; I then decided to use minmax.

#Move selection

The branching factor of the game is pretty huge and I spent a few days trying to figure out how to select the valid moves to simulate; you obviously can’t simulate every possible scenario, even at depth 1.

Looking at a few games in the leaderboard I noticed that Robostac was only playing 1/4 or 5/0 moves, and nothing else. This seemed to work well (he had first place at the time) so I did the same.

The first version of my minmax would select the N best planets based on a score computed with a heuristic, and simulates every possible 1/4 5/0 move on those planets, N being a constant. This kind of worked but the selection was still perfectible; N too small and I would miss some crucial moves, N too big and I would be stuck at depth 1.

I switched back and forth between 2 approaches :

Generate lots of moves and stay depth 1

Agade told me that he was using iterative widening; he keeps his minmax capped at depth 1, but iteratively widen the selected moves. I liked this idea and stole it (thanks). I would use the same principle as before, increasing the N value to take more and more planets into account each time, stopping when I run out of time, and keeping the last complete result.

Generate the fewer possible moves and reach depth 2 as many times as possible

I noticed that Petra was pruning even harder and only played 5/0 moves. I tried that too, and that would allow my AI to reach depth 2 or 3 quite often, even though in some scenarios it wouldn’t allow me to colonize the map as fast as the enemy.

Final move generation

Both approaches had pros and cons, but the move selection that worked better was :
Select all the planets that are worth simulating : every reachable neutral, every reachable enemy planet, every owned planet that is in direct contact with an enemy planet.
If more than 15 planets are selected, sort them by score (based on number of owned neigbors, and pathThrough ratio, which is explained in the next part) and keep the first 15 ones.

Generate all 1/4 4/1 2/3 3/2 5/0 moves on those.

That solution didn’t allowed me to reach depth 2 often but in the end it seems that reaching depth 2 wasn’t as important as simulating a bigger subset of moves.

I also used killer-move and (delta)hash-move to prune my alpha-beta in a more efficient way.


The map is a graph and not every planet is worth the same.

The metric I used for that was the pathThroughRatio.

For every planet, I first compute the pathThrough. It is the number of times a planet is on the shortest path between two other planets.
I then normalize this number; i.e. I compute a [0; 1] ratio for every planet such as :

planet.pathThroughRatio = planet.pathThrough / biggestPathThrough

I also used Voronoi to count how many neutrals were closer to me than to the enemy.

Using both those metrics, the evaluation function is quite simple :
for (Planet planet : planets) {
  score += (1 + 2 * planet.passThroughRatio) * ((planet.tolerance[me] - planet.tolerance[him]) + (planet.units[me] - planet.units[him]));
  if (!neutral) {
    score += (1 + 2 * planet.passThroughRatio) * ownBonus * (mine ? 1 : -1);
score += 10 * (voronoi[me] - voronoi[him]);

ownBonus is the weight I give on owning a planet. Its value is 10 the whole game, and is progressively raised to a max of 1000 during the last 10 turns.
…, 10, 10, 100, 200, 300, …, 1000

#Choke contest

A large portion of the maps (I’d say half of them, but I haven’t measured) are based on a choke contest. On these maps, each player starts in the corner of a semi-symetrical map, and a large part of the map is only accessible through a single planet :

In this exemple, 14 is the choke, and the first player to own that planet will most likely win the game, since it will allow him to colonize the top part of the map.

The first played moves on this kind of map are crucial; a suboptimal move can lead to a 1 tolerance difference or a 1-turn delayed spread and the loss of this planet.

My initial evaluation function cannot detect those optimal moves so I added a small part dedicated to these special cases :

First, detect these choke planets at the first turn; it’s the articulation point (i.e. remove the planet and the graph is no longer connected) that is equidistant to both player starting positions. If multiple planets are eligible, take the one that is closer to the start positions.

In the evaluation, I added :

if (planet.isArticulation && neutral) { // choke contest
  int chokeDiff = 0;

  for (Planet otherPlanet : planet.neigbhorsOrderedByDistance) {
    int distance = distance(planet, otherPlanet);
    if (distance > 3) break; // only considers the planets in a radius of 3

    if (otherPlanet.owner == me) {
      chokeDiff += (otherPlanet.units[me] + 6 * otherPlanet.tolerance[me]) * reinforcementBonusPerD[distance];
    } else if (otherPlanet.owner == him) {
      chokeDiff -= (otherPlanet.units[him] + 6 * otherPlanet.tolerance[him]) * reinforcementBonusPerD[distance];

  score += chokeDiff;


const array<int, 4> reinforcementBonusPerD = {0, 100, 10, 1};

The reinforcementBonusPerD is meant to give more value to 1 unit at distance 1 than 5 at distance 2. That way, my AI gathers units close to the choke by spreading neighbors, allowing a future spread towards the choke, etc.

This tiny piece of evaluation is worth a lot of ELO (the map pool was unbalanced imo).


Very interesting game that shows that deep games do not need thousands of mechanics and a 10 pages statement (yeah, I’m talking about the past 3 CC, even though I know that designing a game is really hard). Congrats on the design CG-team !

Two bad points though :

The lack of rerun. Two weeks of work ranked on such a small number of games is painful, and demotivating. There’s a big chance that this will always be that way for semi-private contests, but still, it hurts.

AI hiding. Please fix this, this is getting ridiculous. Every IDE game replay is already saved, just make them public, I’m sure the community will be ready to develop his own tools to explore/filter these if that costs too much on your side.

Thanks !


Why not? There weren’t that many moves / turn.

Let’s say that you can put units on 10 planets, which is quite low on this game :

With 5 units, you have :
(5+10-1)!/5!(10-1)! = 87178291200/(120*362880) = 87178291200/43545600
= 2002 combinations not counting the spreads

Assuming both players have 10 reachables planets, that gives : 2002*2002 = 4008004 move combinations for depth 1.

My engine is not that fast :slight_smile:

I did ignore owned planets surrounded by other planets that i own and that don’t have any enemies on them or around them.

Generated all possible unit placements for each node individually. Evaluate.

Then i tried combining the more promising moves. Evaluate again.

I think this checks all moves that matter.

1 Like

That sounds like a reasonable/cheap approach on its own, but that’s not “every possible scenario”.

1 Like

Interesting, I didn’t knew the term but also ended-up doing the same, since very often I was wasting more than half of a round duration. I was widening only my moves however, not the opponent ones who stayed on his initial move list.
Very interesting read overall, thanks for all the details and the clever pathThroughRatio which I realize was so much missing in my AI.

FYI the official term for it in graph theory is the betweenness centrality. Good to know it worked out for someone, as it did not help my scoring function at all despite a lot of attempts with it…

1 Like

I also used a minimax but capped at depth 1.
I was generating 2/3, 4/1, 5 moves and sorting them by distance to border. I also used alpha-beta with killer move to increase performances.

For the evaluation the 2 main parts are:

  • the number of planets controlled
  • a voronoi. One thing which lead to a big improvement was to break the tie when a neutral planet is at equal distance from the 2 players by checking the number of units and the tolerance on the nearest planet for each player. The neutral planet is given to the player that maximizes the formula 9 * tolerance + 2 * nbUnits.
    This formula is made to know which player will be able to win the maps with articulation point: for the planets which are adjacent to the articulation point, it is better to have 4 tolerance and 6 units than 5 tolerance and 1 units because with 6 units you can affect 5 units on the articulation point and spread from the adjacent planet and immediately get control of the articulation. It is also better to have 5 tolerance and 1 unit than 4 tolerance and 5 units as you will end up getting the articulation when the opponent have 0 tolerance.

I also consider the number of units with regards to their distance to the border in my fitness function.

I’m sure I missed something to know which planet are important to fight for, because my AI was clearly bad on “open” maps. But I was on holidays for most of the time and I had basically only the last week end to make my AI (after having code the simulation / minimax during the first week) so I couldn’t find anything to improve that.

Some game feedback:

  • It was for me one of the most interesting games we had on CG, simple rules and a lot of depth :slight_smile: It’s quite a shame that it was only a semi-private contest with a low number of participants and no multi coming after.
  • As others said, it is unfortunate that we didn’t benefit from what other contests have: not even a small rerun, no referee (even if it was not really needed this time with the simplicity of the rules), league promotions every hour (like old contests ?)
    And yeah, I hope that something can be done for AI hiding, it is slowly killing the competitive aspect of CG.