Fall Challenge 2022 - Feedbacks & Strategies

[Lysk]

#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 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

[R4N4R4M4]

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 !

[ValGrowth]

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.

2. 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.

3. 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.

4. 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.

[TN19N]

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