Fall Challenge 2022 - Feedbacks & Strategies

Contests
#27

Thanks @IloIlo_JRFerguson. Yes, that’s right. The twelve lines correspond to widths ranging from 1 to 12. More specifically, I had maps where one player started in the top row and the other in the bottom row and I had the AIs try to maximize their score regardless of winning or losing the game. The starting money was 10 vs 10, 10 vs 20, 10 vs 30, up to 10 vs 200 (so the AI would build the extra robots on the following turn). I updated the write up and graphs to make it more clear (and fixed the x-axis).

I would guess only the difference in robots matter since robots cancel each other out 1:1. This was all to get an approximate relationship between army_strength_difference, boundary_size, and extra squares.

It was later fine-tuned using arena testing using more realistic maps/conditions. It confirms the idea that if you have a big army advantage or disadvantage, building extra income recyclers isn’t very helpful (they have diminishing returns).

9 Likes
#28

Hello @Lysk,

Thanks for the question, I agree it seems that the threshold comes from nowhere and it is a bit the case.

I explain myself:

I have in my IA many experimental hardcoded threshold to solve issues with my heuristic. It seems globaly a bad idea but I didn’t manage to do better.

The exact condition to build a recycler is the following AND condition:

  • turn > 2 => to avoid blocking my robots in the first turns
  • !hasBuildLastRound => to avoid to build too many recyclers
  • (notGrassBlocks.length >= 130 || opponentRecyclers.length > myRecyclers.length) => to avoid killing myself on small maps. The 130 threshold was originaly 80 but it seems that 130 was giving better results. Therefore on small maps I only build if the opponent has more recyclers than me. I count every blocks on the map but blocks with 0 scraps.
  • (myRobots.length < 10 || myRobots.length <= opponentRobots.length + 5) => to build robots but not too many
  • myMatter < 40 => if I have 40 matter in one turn, I have already too many recyclers.

If all this conditions are true, I build the best recycler on a case which will bring me more than 20 scraps and sorted by scraps/grassCreated.

I hope the 130 treshold become clearer.

Cheers

2 Likes
#29

My first attempt was smitsi, but i never tried depth 1, and rejected the idea quite early. The biggest problem for me was spawning many units in a single turn.

1 Like
#30

I used Smitsimax with depth 1. It’s viable I think (if you get the little details and other heuristics right, which I didn’t yet).

1 Like
#31

k4ng0u - 69th (11th gold)

Since the contest was during end year celebrations, I didn’t know how much time I could spend on the game and I started with a simple heuristic bot that would do the following:
_defense
_build recyclers
_expansion
_free moves

I didn’t use any search algorithm and based my whole bot on prioritizing tasks.

For defense, I would list all the threatened cells (owned cells with more than 1 opponent unit as neighbour) I would give defense priority depdending on the number of opponents threatening it, number of neighbour neutral cells that are closest to me and some other micro heuristic. Then I will loop on the sorted cells to defend, and try to first assign lazy robots (that don’t need to defend anything) to move there, then put robots in hold or spawn robots/build recyclers depending on conditions.

For recyclers, I would only build one if I have enough matter, I have no cell to defend, and the nbCellsLost <= 2, expectedGain/nbCellLost >= 15 and expectedGain >= 20 (one recycler should at least give me a new unit advantage)

The expansion phase was my weak point. In my early experiments I decided to list the 12 cells closest to each frontline, sort them, then sort the frontline depdening on my closest owned cell (either dist to unit or dist to owned cell without unit + 1) to them. Then I loop on the frontline and assign the best remaining unit/spawn to them. Retrospectively this approach was quite flawed as my robots were often changing targets doing back and forth and losing turns.

Then free moves were totally handled by heuristic prioritizing neutral cells and cells that are closest to the border.

When legend opened, I was around 20th gold. For a few all nighters, I tried to tweak the sorting/heuristic coefficients to enhance my bot but it was not enough. I probably should have rethought the expansion algorithm and actually insert a notion of attack instead of relying on expansion and free moves.

Overall the challenge was quite nice and the various strategies from PMs are quite refreshing. But for the future, I wouldn’t recommend contests during end year celebrations and I really didn’t like the fact that legend league opened on a week day and ended before a week end.

Thanks CG for the contest and congrats to delineate for winning and leading the contest for quite a while!

5 Likes
#32

Seems we have a very close Heuristic Bot based :slight_smile:
I have exactly the same issue with my expansion phase where my bot frequently changed targets and going back on their path.
GG for your 11th place !

#33

56th in Legend.

I tried my hand at beam search for the first few days/one week, but got overwhelmed by the sheer amount of possible moves.
Reluctantly, I switched to a heuristics bot.
Every turn, I calculate all the distances from each tile to another (using Floyd Warshall), I re-use this information to check how far each tile is away from any of my units or enemy units which I can use later.
I also divide the board into islands.

On the first turn I calculate all of the midline/frontline tiles (my_dist - opp_dist + 1 < 2) (I try to weed out ‘fake’ midline tiles) and each turn after that I update it if I haven’t already grabbed it.

Before calculating all my moves, I generate all combinations (within the time limit) of my BUILD/SPAWN actions, calculate the heuristic of those with an evaluation function for a build action, and one for a spawn action, and grab the best combination of actions and perform those.

Then for each island, I grab my units, and send them to midline tiles if they still exist (they can swap targets if it makes the total distance shorter, I saw people talking about the Hungarian Method on the last few days but it was too late for me to implement it), otherwise I just send them towards the nearest enemy. This last part could have used some work, but I was too exhausted the last 2 days to put actual effort into it.

Thanks for the contest, it was a lot of fun, happy to have helped my Uni to take pole position and my first ever top 100 finish!!!
I’m kind of on the fence about the duration of it, but it was at least fun for a change.

See you all next time.

5 Likes
#34

Hi @delineate, congratulations for your contest.
Can you detail this: "add random noise for each cell’s cost in the movement BFS searches, and then repeat (20-30 times) to find the best set of paths ".
Why add noise ?
Thanks for your post mortem.

#35

Thanks @Hexabine

So the BFS search might pick a suboptimal path, especially when a lot of paths are close (or tied) in cost.

For example:
image

Imagine there are 2 possible boundary targets (A and B). And we want to find paths from X and Y.
The lowest cost path might be X → B going through R. But the best global set of paths might be X->A and Y->B.

If we just reran the same search without any noise, it would just give the same set of paths every time. Adding some random noise helps generate different results each time.

The noise was just used for sorting which square was next in the priority_queue and the actual “true” cost (without noise) is also stored since that is needed too.

I experimented with different things (varying amounts of noise, different magnitudes, etc.), but a random uniform amount between 0 and 1 was just as good as anything else so I kept that. Noise was added for both starting squares, target squares, and intermediate squares. Basically whenever anything is pushed onto the priority queue: sort_value = value + noise

I’m sure there are more clever and efficient approaches, but this was easier and faster to implement.

7 Likes
#36

Me too one month is so cool for improve our bot ! It was an excellent idea with an excellent contest ! Thx for the staff !

2 Likes
#37

Nothing specific to add (finished bottom gold) other than really interesting game, and thank you to CG for doing it. Also thanks for having a specific name for the contest too! Month-long format was cool for a game like this but I’m not sure christmas/new year period was the best idea; though I appreciate that CG had a fairly hectic year in terms of change and whatnot.
Still, it was fun. And congrats to @delineate for the clear win. Some very interesting approaches in this thread, much respect to all players :slight_smile:

3 Likes
#38

Hello !

Thanks for your PM et gg for your rank !

I’m trying to improve my expansion with Munkres algorithm but I didn’t manage to include the spawn.
You’re talking about variable location but I don’t understand how you manage to put that into the Munkres algo.

Could you help me to understand :slight_smile: ?

Cheers

#39

Sure.

For munkres you need a combination of an objective, a worker and a cost.

-The objective is just any objective you want to assign the spawn to. It makes sense to use the spawn as defense, but if you use them for the early expansion, that works too.

-The worker is the same as a robot would be, except the robot is tied to 1 specific place and the spawn is not. It’s just wherever you want it to spawn. This is no problem, because munkres does not require a position as input.

-The cost is where the difference between a spawn and a robot matters. You will probably figure in distance for some objectives. Robot distance is calculated with BFS. Spawn distance also, but instead of using the distance from a specific origin to a specific destination, you use the distance from the closest owned tile(that has no recycler) to a destination. And you add 1 because of spawn delay. You don’t even have to know exactly from where you are spawning it, to use the munkres algo, just as long as any distance calculations are correct. After munkres is done, you can choose from several owned tiles that are equidistant. Perhaps some make more sense than others.

3 Likes
#40

Thanks !
It s much clearer for me now !
My issue was with the distance but I understand now that you can just the closest one and decide the exact location afterwards.
Last question: if you can spawn n robots, do you put n more workers in the Munster matrix?

#41

10th

My bot uses a mix of Hill Climbing and Hungarian algorithms.
It tries several different options for action selection and chooses the best through evaluation of the resulting game state.
For instance, recyclers are added greedily one by one, after which moves and spawns are added by the Hungarian, which are then completed again in a Hill Climbing manner.
Of course, I also compute the opponent’s actions and mix evaluation of different possibly resulting game states.

The evaluation uses a lot of ingredients and as it is quite costly, I had to optimize it a little to be able to evaluate more action sets.
The exact computation of regions (islands that will not be recycled) and distances to the borders (inverse Voronoi) are computed with an adaptation of Dial’s algorithm, which works here in almost linear time.

The issue that appeared crucial to me is the units–terrain trade-off, determining how many recyclers to build. I tried to optimize this parameter through extensive experiments for each map size and the boundary size, which gave moderate success. Now I know it is not enough and I am impressed by the better solution of @delineate.

The problematic part of the rules was pathfinding, important for backup moves. I did not have enough time to rewrite the engine to calculate them exactly so I stayed with an easy heuristic here.

Thanks for the challenge!

5 Likes
#42

Yes, for each spawn you can do (matter / 10) you make a new worker.

#43

#57 Legend in python

Comments

Thanks CG for the contest, I liked the format and the when it happened, I believe that being a holiday season allowed many players to find time to play. One thing: can we get a fix for move cancellation when a recycler is placed on a neighbor cell please? I want to spend some more time on the multiplayer but I find tedious to work around whatever java queue is doing.

I was impressed by the level, on the last Friday I managed to reach 19th but went down to 40th by Saturday end-of-day. Had to ship multiple improvements to get back up.

Thanks also @bourgeof for pushing me into Legend, I was <0.3 below the boss and you pushed it down just enough :slight_smile: I had the pleasure to exchange with @slamo, @DumbassDan , @davidshhh and @VisualDev-FR , discussing replays and ideas.

Bot

Not much to add to other PMs, so I will focus on the steps I took. I hope it will help folks making incremental improvements.

Starting simple

I tend to start with really simple bots. Getting out of wood and messing around in Bronze:

  • Assign units to their nearest opponent or neutral cell, don’t send another unit to that cell, no ordering of units. As dumb as it sounds it was enough to compete and start building some intuition about the game.
  • Build one recycler in the first cell on the first turn. That worked for a while.
  • Simple “battle” code: spawn to protect or build recycler. Nothing fancy initially, just enough to get a sense of what data was needed (# opponents, count units coming to the cell from neighboring cells, etc.)
  • Use Manhattan distance, I used it until the last weekend, t’was enough. Sometimes units get stuck.

Iterating

From that bot I decided to focus on:

  • From the above simple bot: sort units by distance to the nearest opponent.
  • Spawn not 1 but 2 recyclers! My final version was doing that: up to 2 recyclers before meeting the opponent.
  • Better combat code: block if I cannot spawn enough units otherwise spawn, then bring neighbor units not facing an opponent to that cell. Attack when possible.
    This helped but not that much since I was meeting the opponent on my side of the board.
  • Improve spreading units to meet the opponent at the center of the map: this was a constant source of improvement until the last Friday where I refactor the code. Save where the initial frontier is, then combine spawn/move to have units reach it as fast as possible.
    One thing that helped most of the contest (it’s now holding me back), if a stack of units is moving to the same cell and there are neutral cells around then split the stack (unless the neutral cell is behind). Until I assigned units to the initial frontier that encouraged spreading without much complexity (no BFS, just checking neighboring cells).
  • Units that are not taken for attack/defense would go to the nearest neutral cell if any.

All of the changes where tested locally, I was looking for a winrate of +5% to test in the arena.

Final thoughts

Given the different game mechanics (see how everyone is splitting their logic) I’m glad we had more time than usual for the contest. It feels like this could be a great beginner friendly multiplayer: smart ordering of orders works (I mean if-else spaghetti), scoring cells works, some search can help (like identifying a frontier or a player’s influence), etc.

Until next time :slight_smile:

9 Likes
#44

Hi, Thanks to CG for this great challenge !
#27 Gold (#85 global)

Divide the map in several areas, and each area is treated as an independent game, except for the winning evaluation, where the global score is the sum from each area.
Pathfinding is done with 2 BFS. First BFS to select the best target, and second BFS to select the best path without falling in cells which will desapear. The second BFS uses the first BFS distance needed to calculate those cells.

  • Inaccessible area :
    When no player can access to this : Do nothing

  • Area won :
    When all squares of an area are mine : Do nothing

  • Area to explore:
    When an area has only neutral cells and at least one friend cell

  1. If none of other areas are fighting, spawn one robot if no robot is present in this area
  2. With all robots on this area, capture neutral cells
  • Area to capture :
    When an area has at least one opponent cell and at least one friend cell but no robot at all
  1. spawn one robot if I have none on this area
  2. This area becomes a fighting area
  • Fighting area :
    When there are at least one opponent cell and at least one friend cell and at least one robot
  1. Simulate one Build and evaluate if I can win the game
  2. If there is only one opponent robot on an area, all my robots on this area move to it
  3. 1 robot by 1 robot, simulate the best neutral cell capture, evaluating the voronoï control of my position
  4. 1 robot by 1 robot, capture the most possible neutral cells next to mine, except those isolated from opponent by my own cells. Prefer neutral cells on the border.
  5. All other robots move to the nearest opponent position
  6. Spawn 1 robot while it increases the voronoï control of my position
  7. Some direct attack if in superior number, to a neutral or opponent cell
  8. Defend my attacked cells by requiring some help from neighbour robots it they are not attacked
  9. Defend my cells with Build or Spawn. Try to not build on a cell with neighbour neutral cells. If there is no more resource to defend a cell, and some robots on this cell had planned to move, cancel this move.
  10. Spawn all resource left at the smallest distance from opponent
  11. Build 1 recycler (until 2 are built) on the best cell without create inaccessible area. This build sometimes interrupts some spawn (from points 6, 8 and 9). Best cell to build is evaluated with the total scrap and some future dead cell malus
    My logic suffered a lot from the build priority, because I was unable to manage properly resources between spawn and build. Sometimes, building a new recycler to collect more resource blocked defensive spawns. After reading other PMs, surely I didn’t spend enough time on this resource issue.
    This challenge was very interesting, thanks again to CG !
3 Likes
#45

Legend 4th.

I used hill climbing. Two players alternatively improve their moves.
I refered this reCurse’s post. It seems that in A Code of Ice and Fire, it was better to take the minimum for all opponent actions, but in this game it was better to take average. I assume this is because this game is simultaneous.

[Possible Actions]

Move: Move to 4 directions or stop for all robots.
Spawn: Only at the edge of my area.
Build: All buildable cells.

[Neighborhood]

・Change direction of movement of one robot
・Add, delete, or change the location of a spawn
・Add, delete, or change the location of a build

Spawn and Build are more likely to be chosen near the opponent’s area.

[Evaluation Function]
First, let me explain what I call the middle cells, which is an important concept. This is the cells where I just collide when my conduct a BFS from my own area and the opponent’s area at the same time. If these are cells, the middle points are that cells; if these are edges, the middle points are the neighboring opponent’s cell.

My evaluation value is a linear combination of four values. In the following, written as “symmetrical” is calculated as the player’s evaluation value minus opponent’s evaluation value.

  1. Area size I can reach before the opponent (maximized, symmetrical)

This is calculated by BFS as described in the middle points section.
This value determines the movement of my front line units and how to set up recyclers for defense.

  1. The amount of matter after N turns (maximized, symmetrical)

This determines how the recyclers are placed to earn matters.
At the beginning of the game, N=7 and gradually reduced to N=5 as the game progresses. N=10 was not so good because it destroyed too much of my own cells.

There is a trade-off between the evaluation values 1 and 2. Placing a recycler in my own area decreases the evaluation value 1, but increases the evaluation value 2. This relationship is roughly between 1 cell = 6 matter ~ 16 matter. The larger the map, the higher the evaluation value of matter, and the further the battle progresses, the lower the value of matter.

  1. The number of cells I lost this turn + the number of opponent cells (minimized)

This is not symmetrical. The reason is that if I simply try to increase the number of my cells, my robots will spread out to neutral cells. This evaluation value affect on the attack and defense of the front line.

  1. Distance to the middle points of each of my unit (minimized, symmetrical)

Rear units are not yet evaluated in the evaluation values of 1, 2 and 3.
(The evaluation value 1 only affects units in the front line)

Since I want the rear units move to the middle points, I can think of the “middle points” and “my units” as a bipartite graph and perform matching to minimize the total distance, while the remaining units are evaluated based on the distance to the nearest middle point.
However, it is better to match not all the middle points, but only about half of them in order of their distance smaller to my units (I will explain why below).

[Two type Attack strategies]
One of the interesting points of this game is that the strategy was divided into whether to first put multiple units together in the shortest path or to spread them out. The advantage of grouping units in one place is that it is easier to capture the squares at the point where you hit them, while the advantage of spreading out is that it is easier to attack from the edge of the map.
If I match all the middle points to my units, it is a very stretched out formation that is good for attacking from the edge of the map, but is bad for capturing center of the map.
The other way, if I match none of the middle points to my units, it will get a very compact formation that is good for capturing center cells, but is bad for attacking from the edge of the map.
I think the mixed strategy is better than either strategy. Matching only half of middle points, and rest units move to nearest middle point.

[Hashing for distance calculation]
I used ZobristHashing to calculate distances.
Specifically, if the recycler placement is the same, all distances on the map are the same, so we can calculate the recycler placement as a hash value.

11 Likes
Spring Challenge 2023 - Feedbacks & Strategies
#46

Thanks to CG for this great challenge!
#84 global (#26 Gold)

my approach for this contest is like a mini version of the @_Royale approach.

link to my postmortem: codingame_postmortems/Fall_Challenge_2022.md at master · Mustapha-Nawawi-T/codingame_postmortems · GitHub

1 Like