Final Bot Structure Overview
The bot consisted mainly of two classes. A Game class which stored all the information for a single frame, and a Square object, which contains information on the Square.
I use SciPy’s Dijkstra’s algorithm to calculate the Recover Cost (Str / Production) from every cell to every other cell. This is the foundation of the heuristic I use to determine which cells to capture.
I also create a parity map which actually varies to try to keep strength moving forward. I removed checkerboard movement for the most part, but it still exists near the border to create space. I wasn’t comfortable completely removing it since initial testing indicated it performed slightly worse.
I break the turn out into 3 phases:
During the Update phase, I update all the maps that I use, some statistics that I calculate every turn, and update some parameters that I use in the bot.
Update – Maps:
The following is a complete list of maps (matrices) that I use in the bot:
- Strength/Production maps, actual values, along with values capped at 0.1, and 1.0
- Ownership maps: Own cells, neutral cells, all other enemy cells
- Border maps:
- Border map: Neutral cells that are adjacent to a cell we own
- Combat Zone map: Border map cells with strength == 0
- Strength Maps:
- Enemy strength maps & Own strength maps: Basically influence maps that sum the total strength of enemy or owned cells X tiles away. Used as a comparative reference for who is stronger here.
- Distance Maps:
- All distance maps do a flood fill of the cells to other cells to calculate how far away it is from the targets. These maps are also used for movement. If I want to move closer to the border, all I have to do is reference this map to see how far away it is from the border, then just check the adjacent squares and move to lower valued squares.
- Distance to Border
- Distance to Combat Zone
- Distance from enemy:
- This is slightly different from Distance to Combat Zone. I probably didn’t need this.
- Distance from Neutral:
- This was added at the end because of NAP. I had cells moving towards the border which would never be captured. Instead of reinforcing the walls, I use the strength to capture more cells. Risky, but no one was really busting through too much.
- Value Production Map:
- This is the main heuristic. Each Border Square is given a value that consists of two pieces. The base value of the square, then a modification for the global value of the square.
- The base value is calculated as Production / Strength of the cell.
- The global value is the SUM of ALL non-border neutral cells that are assigned to this border cell.
- A global cell is assigned to a neutral cell if capturing that border cell moves it closer to the global cell.
- The value of the global cell is the Base value of the cell divided by the recovery cost to get to this cell.
- This value is modified by a global multiplier which determines the weight given to global cells.
- The global multiplier is dependent upon the gini coefficient of the map.
- There is a lot of tweaking that can be done here. Certain maps different values of this perform better. This is just a weird hack which might not really work but seemed to produce better results so I left it in.
- Finally, the inverse of the sum of the base and global values is taken to produce a weighted Recovery Cost (or turns to recover capturing the cell).
- I hacked in the code for the non-aggression pact here. Any cells that were bordering a combat zone or enemy areas I set to 9999 so that my production function wouldn’t attempt to attack it.
Update – Stats:
Basic tracking of stats here. There’s nothing really interesting, but for the sake of documentation, I’ve listed it below:
- Turns left in game
- % of cells that I own
- Are we close to an enemy? (Any enemy strength within 4 squares of us?)
- Do we have the most production?
- Who are we in combat with currently?
- How many squares do we own?
- How many squares are in combat?
Update – Configs:
This was arguably the part where I wasted the most time on with probably the lowest benefit.
- The # of squares to go out to reserve for combat purposes. This varied between 6-8 for most of my bots. I don’t know what’s optimal or not.
- Ugh, this was a pain. So, I start off with a base of 5 for all squares.
- Then, depending on the distance to border, I actually reduce it for squares further away from the border.
- The thinking was that cells further from the border have a higher chance of wasting strength from capping if it waits too long. The converse would be, squares in the center take longer to get to the border so it should wait longer to build up more strength. Whenever I tried to remove this, the bot just performed worse so I left it in.
- If we are producing more than 10% than anyone else, then increase the buildup multiplier by 1. We can use the extra production to generate more strength since we have a production lead and not move things as much.
- If we own 10% of the board, then bump this up by 4. This was inspired by watching @mzotkiew’s bot. He had buildup multipliers as high as 9-12 sometimes! I played around with this a lot, trying to figure out when it should trigger, and what the value is. This seemed to work decently.
The main core logic. The Move phase goes through 3-5 steps. It used to be 3 until I hacked in 2 more.
Check Focus Territory -> Attack -> Expand -> Move -> End of Game Moves
Move – Attack:
This was a complete pain. I spent weeks trying to get this right. In the end, I sort of bastardized the thing and actually have it as a hybrid.
The get_moves_attack_old is actually the original checkerboard combat function. I use this when I have a lot of strength and don’t care about overkill. It’s actually pretty simple. I attack all available combat squares, then move all other squares towards the combat zone if it has built up enough strength.
The new get_moves_attack function has several parts.
Squares which are isolated (no friendly neighbors) and are of sufficient strength actually stay still. This is to punish checkerboard movement. I check that doing so doesn’t put us in a checkerboard position as well since then just moving it would be better. I also only keep it still if there are multiple squares that we can impact, otherwise we should just move it.
In here, all squares when they move call a mark unsafe function. This function is what determines safe spots to avoid overkill damage. The way I’ve implemented it right now, it basically just says: what are possible places enemies can move, and avoid placing pieces which would result in overkill damage if possible. Then find the best move given those constraints.
The main issue I have with the code is that it avoids combat too much, preferring to give up territory than to risk overkill. I never did get the balance right.
All other squares then just try to move closer to the border if possible.
Move – Expand:
The value_production_map contains what I call recovery costs. Or turns to recover the strength cost to capture this piece. I place all of the ones that I’m interested in into a list and then I add a range counter up to the # of cells that I want to look out (self.production_cells_out). I then sort by the sum of the recovery cost and # of cells out. I work well with examples, so imagine that we have three targets with values of 2.1, 5.0, and 8.2. If we look out 6 squares, we would add in 3.1, 4.1, 5.1, 6.1, 7.1, and 8.1 to the list. Same for square 2, values of 6-11, and square 3, values of 9.2 to 14.2. When it’s all sorted, we then do a search. The sorted tuple (Square, Cells Out, Value + Cells Out) would be:
[(1, 1, 3.1), (1, 2, 4.1), (1, 3, 5.1), (2, 1, 6.0), (1, 4, 6.1), (2, 2, 7.0), (1, 5, 7.1), (2, 3, 8.0), (1, 6, 8.1), (2, 4, 9.0), (3, 1, 9.2), ...]
Starting with the smallest value, we then try to capture Square 1, with squares 1 square away. Then 2 squares… so on and so forth. If we still can’t capture 4 squares out, square 2 then gets priority and tries to capture 2 squares out, then back to square 1 with 5 squares out. Once we find a square to be captured, we remove all copies of that square from the list and continue. We do this until we exhaust the list.
By controlling production_cells_out, we can hold squares to be captured up to 15 turns later, as long as it’s sufficiently valuable enough relative to other candidate border squares.
Move – Move:
This used to be more complicated, but now, I just move all squares towards the nearest “border”, where “border” depends on if we’re in combat or not and whether the NAP is in effect.
Move – Check Focus Territory & End of Game Moves –
The expansion function actually only tries to capture the most valuable 85% of cells. When we’re near the end of the game, remove this restriction.
Also, when we’re near the end of the game just go do an all-out attack to capture or deny enemy territory.
There used to be more here, but now we only do two things. Stop needless swapping between cells (this was never perfect, but good enough), and try to avoid moves that go over the 255 cap. I don’t find the code for these two to be particularly interesting so I will not go into further detail here.
Movement was a major pain. The way I have it implemented is also a major pain and very messy. I probably could have collapsed the 3-400 lines of movement code into 100 or so lines if I was good.
Movement is broken out into 3 main functions
- Move to target (moving to a far target)
- Move to target simple (move to a nearby target)
- Move based on a map
Given a source and a destination, do a BFS Flood-Fill search to figure out the up to 2 squares that are closest to the target.
This is actually pretty simple code, but very expensive. Doing this for every cell I want to move especially if the distances were sufficiently large would get very timely. So that’s why I had a second function:
This actually looks at the dx and dy moving to each neighbor, then determining which of the two works. We then try to prioritize based on production, and then have to determine if we have to move through friendly territory only or not. There’s a lot of logic here that swaps and then determines if we have a move or not that’s really messy, but the reality of it is that when I used this in future bots, I really only use it to move to an adjacent square anyway, so all the excess code is probably no longer needed.
Most of the collision avoidance code is actually handled in these two move functions. We only make the move if we can safely, otherwise if we can’t, then can we bump a piece that’s not moving somewhere else safely?
These just take the created distance maps, then move to the neighboring squares that are lower.
This is the function that I use to coordinate multi-cell attacks. Here’s the basic algorithm:
- Do a friendly flood fill N squares out from the target square.
- Keep squares that are currently not assigned a move, and meet the buildup threshold.
- Sum the strength of all those squares.
- Take the original flood fill and do N – distance from border. This is how many turns of production we have if we move the furthest squares in first.
- Multiply this new flood fill by the production map. This is how much strength from production we have available.
- If Available_Strength + Available_Production > Target.Strength, then we can attack.
- Start inwards. Calculate strength from cells that are not moving, along with future production. Subtract this from Target.Strength. The amount of strength left is what we need to move.
- Starting from the highest square, move it closer to the target and then subtract from the amount of strength needed. Repeat until 0 or less.