A Code of Ice & Fire - Feedbacks and Strategies

_CG_SaiksyApo · May 27, 2019, 8:05am

The topic where you can tell how you liked the challenge, & how you solved it.

=> https://www.codingame.com/leaderboards/challenge/a-code-of-ice-and-fire/global

Thanks again to the creators Azkellas and Tehelka and to the testers .

Nixerrr · May 27, 2019, 8:28am

Big thanks to Azkellas, Tehelka and CG for the contest. Great job, guys!

This was my first contest and my first c++ bot, and I enjoyed it immensely. My aim was to make it to top 100. Although I didn’t make it to legend, I managed to get into top 100 so I’m content. Looking forward to the next contest and playing CIF as a multi!

Magus · May 27, 2019, 8:39am

Good contest. Simple rules, interesting problems to solve. A “bad start” because the referee was very bugged, fixed on monday. Maybe the tower are too strong, bug reCurse seems to prove that it is not the case.

I will finish probably somewhere around the 15h rank.

For the first turns, i use a Monte Carlo on 10 moves (1 move = a unit move or i train a new unit) algorithm to maximize the number of cells i own. When i can reach my opponent territory, i stop this phase.

My code will test all the possibilities for the current turn. Each possibility is :

Performing a cut to any cell i can reach (more informations after)
Build a tower anywhere i can
Build a mine

A cut is a chain of 1 move and X trains to reach a specific cell. I always cut using the cheapest path to this cell. For each possibility, i try all possible cuts of my opponent. You can imagine my code as a minmax depth 2 (one turn for me, on turn for him). But this is true only for 40ms. At 40ms, my code has a safety break and then i only do a bruteforce force of my moves (i don’t check my opponent possibilities). This safey break exists because on some turn with many units (and many golds in bank), i can’t test all possibilities in 50ms.

My evaluation function has some basic criterias like number of cells, income, gold, covered cells … But my main criteria is what i call the “Time To Win”.

The Time To Win (ttw) can be summarize by “If i just sit and wait, how many turn i will wait before winning ?”. In fact the calcul is simple. Find the cheapest way to the ennemy HQ and check in how many turns you can afford this path based on your gold and income.

BlitzProg · May 27, 2019, 9:50am

BlitzProg - 87th (C++)

I’ve had a wonderful time. Antiyoy is a game I am playing and have been playing for years to kill time, so naturally seeing this challenge was very inspiring for me! I had many ideas to improve my AI and didn’t have time to code everything, but overall I’m still quite happy with what I’ve come up with. I tried to go for legend this time, but alas, the gold boss was way too powerful to remotely get close. And the other players were so strong too!

Here are the strategies I used:

Started off by testing the waters using Wood 3 rules For each unit, order to move toward unclaimed space, or move toward enemy HQ if not possible. Also spend money accordingly. This got me promoted to bronze.
Porting to C++ from PHP, I made it so I was also updating my data as I was giving out orders, so it wouldn’t ask two units to move to the same place or buy over a space it just asked an unit to move to. This was enough to get into silver league.
I’ve ranked up in the silver league by implementing bought attacks. This means my AI would detect that buying a particular chain of level 1 units would end up cutting an enemy territory from their HQ. Another function would also calculate how to buy the game and do it if enough money available. (buying chain of units until HQ is reached).

The search for game win is made with Dijkstra. If a win is found, I backtrack to output the required kill commands. Cells are weighted according to the cost needed to buy an unit. Later in the development I found a way to integrate a discount for taking a tower, based on how much this would save money.
My search for territory uses Bruteforce: I call a function on each enemy cell that borders a cell I own, and pass it two diagonals and a binary number of given length. I test every binary number with every diagonals. For each bit of this binary number, if it’s zero, it tries to extend the chain horizontally, if it’s 1, it tries to, vertically. This will easily search all possible cuts from the cell I’m starting the attack, using two directions.

Promoted to gold with implementation of defense. after moving my units, calculate which border cells the enemy could move to (or buy over my units if they have the gold) and try to place towers accordingly. This made it much harder for the enemy to take or split my territories and made it much simpler to tank until I had the money to finish the game.

The rest of the challenge was about trying to progress with the minimum goal to stay in the top 100. Some of what I did:

checks to see if buying a level 2 unit over a level 1 would kill an attacking chain of units
fixes for the tower defense logic for a few specific cases (like: don’t build right in front of a level 3)
update my kill dijkstra so it works with downed towers (if you buy a lv3 over a tower it immediately stops protecting the cells behind it)
Staller and stalled checks (need a lv3 to go to HQ). If we are stalling each others, I try to save money to buy a kill, and buy towers to increase the cost needed to kill me.
Last minute pathfind so my units with no neighboring empty tiles don’t run in circles.

My weakest point was probably how I was moving around my units. I’ve lost many games because of how dumb my logic is, and the last improvement above barely improved it. (Decent tower placement helped a lot to save them, probably why my defense helped ranking up so much)
I lacked inspiration there and was never sure of the best logic to use there and most of the starting code stayed around until the very end of the challenge. I hope I can read other people’s strategies so I can see how I should have approached it.

Thanks for the challenge!

eulerscheZahl · May 27, 2019, 10:19am

I finished on the 4th place

My bot is mostly heuristics, guided by some simulation to help making decisions.
I have the following functions, which I apply one after another:
Doing a lethal attack, then avoiding it, moving my units, handling cuts, building towers, spawning units, building mines, undoing moves.

Lethal attacks

You often see bots collecting a lot of gold and then building a long chain to the opponent headquarter. My bot does that as well, starting a Dijkstra search at the own headquarter, going towards the opponent. Here connections to my one cells as well as one movement are free. All other connections are equal to the spawn cost of the target cell (beware of towers getting destroyed, they no longer protect their neighbor cells).
If I can’t find a way to kill my opponent, I check if he can kill me - and bruteforce possible tower locations to stop him.

Moving units

Moving several units requires some coordination, to avoid them blocking each other. I have a score matrix, where the rows are the individual units and the columns are the cells of the board. An entry contains the score of a unit being on a given cell. Here I reward conquering new regions, cutting off some opponents with my move and also closeness to a target cell (which is the opponent base for my front line and the closest cell which isn’t mine for the units in the back).
As each unit can only move to one cell and each cell can only be occupied by one unit, there is an efficient way to find the maximum possible score: the Hungarian method.
Edit: you can find a more detailed explanation on this below.
The downside is, that it only optimizes for the current turn. Units can easily end up in a situation with no free cells to conquer next to them. The Hungarian method gives one optimal solution among many that exist. So I try to reassign the target of each unit - one after another - and ensure that the score stays the same. If that reduces the amount of stuck units for the next turn, I keep that solution.
Then I move the units one after another. The order matters, as some units have to move first, to create free spots for the others.

Cuts

Breaking the connection between the opponent headquarter and some cells of his is an effective way to kill his units and also reduce his income.
I do a full search of depth 5 as well as another search of depth 10 with only one corner along that path (that is forming an L-shape), starting from every cell next to my own territory. For each of those possible cuts I check the cells and units still active. I take the best cut possible, the scoring being:
regionScore = 2*tilesDeactivated + 3*unitLevel (of units killed/deactivated) + 2*towerInactive + 6*towerDestroyed
cutCost = sum of pow(spawnLevel, 1.3) for each spawn of the cut
cutScore = regionScore / cutCost
The exponent ensures that a level 3 unit is more expensive than 3 level 1 units, although they have the same spawn cost. This is to take the upkeep into account.
With my own cut applied I try to find an opponent counter attack. If the counter has a higher score than my cut, I try to block instead. I do so by placing a tower or a level 1 unit.
I repeat this as long as I find good cuts and have enough gold.
Other players like Magus or dbdr find more potential cuts. So I fail defending them some times, as I don’t see them coming.

Coward strategy

Some players tend not to attack, but collect gold for one single lethal attack. When the opponent gold is greater than the income + 20, I assume that my opponent is doing that. In this case I stop the turn here, not calling the functions listed below. I also do so, when I can collect the money for a lethal wave before my opponent (with 1 extra turn for a safety margin).

Building towers

I also build towers beside countering cuts. I place them next to the border or at a spot where they can protect my border level 1 units from hostile level 2 ones.

Spawning units

At the beginning I have an offensive spawn, trying to get as close as possible to the opponent base. When the opponent is close enough, I try to expand my own territory instead. I exclude cells as spawn candidates, which are going to be visited in my next 2 move turns (running the Hungarian method again to figure that out).

Building mines

If I have some gold remaining, I build mines as far away to the opponent as possible. I’m not sure if this is helpful in any way or not.

Undoing moves

As the bot just runs some functions in a certain order, without them knowing about each other, this can result in bad decisions: a unit moves away from a cell to capture another one - but leaves the previous cell unprotected. The tower building repairs this in most cases. However if the move endangers the previous tile of a level 1 unit, I undo the move not to give up my territory next to the border.

About the game

I liked the game for its simplistic rules. I didn’t even try pulling off a fully search based bot, as the branching factor is enormous.
The biggest issue, the advantage of the red player, was addressed at the opening of silver - thank you for that.
I’m still not sure how to use mines the right way. There are some games lasting over many turns, where they can help for sure. But in other cases you will be better off just saving the money for the next turn.
I had a lot of fun competing, despite my disappointing ending.

anon4743054 · May 27, 2019, 10:19am

I liked the contest. Looking forward to the multi version.

It reminds me a lot of A*craft, however i didn’t have much time to convert my bot for this contest.

That’s subjective.

The tower area and the fact that you can only capture units with a higher level unit except for level 3 which can capture other units of same level for example were needless complications. You also have different upkeeps to take into account.

dbdr · May 27, 2019, 10:26am

I don’t think that’s needless. If level 3 could not kill level 3, the border would get stuck very soon. If level 1 could kill level 1, there would be very few units left and the game would look very different, and I suspect less interesting.

Bahrani · May 27, 2019, 10:50am

Hi,

Thanks to Azkellas and Tehelka and everybody who helped getting this contest live.

I really liked this contest. The rules are simple, and yet, for the first few days, I did not have a clear clue how to approach it. I finished in top 200, with the least amount of hours spent in all of my contests (I tend to be busy lately and sleep > coding).

Easiest bronze ever - use the starter kit and change the rushing target from mid to opponent base.

I did these steps in every turn:

Move Units
Build Towers
Train Units
Build Mines

I only used opponent’s current position, and did not predict the enemy moves at all (I never do, maybe I should start )

For moves, I scored all five possible tiles (up / down / left / right / stay), based on who owns the tile, what level unit is in the tile and distance to enemy base. Of all possible moves, I selected the target tile with highest score for any unit that could reach it, and tried to use unit with no other options.
Finally I resolved order of movement so that the units don’t prevent each other from moving to their desired destinations.

Very early I realized that placing towers in (1, 1) Fire or (10, 10) Ice would give some edge.

Later, I placed towers in all active tiles that I owned and were immediately accessible by level 1 or level 2 enemy unit, in order of distance from my base. Adding this tower code got me out of Silver (and actually this was the final change for me).

Placing new units: I scored each tile with minimal cost it would take me to get it and selected the tile with max cost that was feasible with my gold and income. If reaching enemy base was possible, went for it, otherwise I did as many placements as possible.

This strat didn’t do any good in early stages of game (obvious long lines of unprotected units deep into enemy territory), so I added placing L1 units into the neutral cells close to the edge.

I didn’t buy mines in early turns and when I ever built them, I did so as far from enemy as possible.

And that would be all.

Thanks to everyone who participated.

Jahz · May 27, 2019, 11:20am

Great game !
Finished at the bottom of gold without building towers, mines, and without chain-train for kills nor any kind of cut implementation.
Just moving towards enemy HQ while capturing as many cells as possible, then training aggressively level 1 (closest possible to enemy HQ until I don’t have gold anymore). When things are stabilized (no neutral cell available anymore), I may build level 2 or 3.

Nice to see some Java in the top for once ! I’m curious to see if they were pure heuristic bots, or if they managed to perform some kind of simulation & search with Java.
And GG reCurse once more, large gap with n2 so your winrates are probably amazing.

Neumann · May 27, 2019, 11:40am

I finished #12 in Legend, here are my AI’s details

Phases

My AI has several phases, executed in that order :

1- Cut search

Cuts detection (for me as well as for the enemy) was crucial in this game. The easiest way to find those cuts is bruteforce. My cut search worked like this :

For each cell that has a neighbor not owned, and each cell on which I have a unit :
	Start a DFS from that cell, copying the state and simulating TRAINs along the way.

The scoring of a cut was :

(<number of disabled enemy cells> * 2 + sum of <10 + level of each killed unit>) - (sum of spawn costs)

If the last cell of the cut if the enemy HQ, then the score becomes +INFINITY; this algo detects cuts and lethals at the same time.

I have no depth limit (the money one can spend is the limit) and a single restriction on the directions : when jumping from one cell to another, if the next considered cell has more than N already owned neigbors cells, it’s ignored.
I used N=2, or N=1 if the player had more than 140 golds to reduce the branching factor (I’d rather limit the directions than the depth of the search).

EDIT :
To illustrate this, here are some few weird-shaped cuts that my AI could find :
my favorite
replay
replay
replay
replay
bonus long-ass lethal

So the first step of my AI is to look for cuts from my POV, and applying the one that has the biggest positive score.

2- Move units

I list my units from closest to enemy HQ to farthest, and I bruteforce every legal moves combinations on 1 turn.
The evaluation I used for moves was :

<number of owned active cells> + <sum of upkeeps of killed units> + 0.01 * <number of dominated neutral cells> - 0.1 * (<sum of distances to neutral cells> / <number of dominated neutral cells>)

Dominated cells were computed using Voronoi.

When there were too much units, I would timeout, so I capped the search to the first 10 units (the 10 closer to enemy HQ, which are the ones you need to manipulate the more carefuly). I used a deterministic heuristic for the rest of the units in the backlane.

3- Protection

The next step is dedicated to the enemy cut protection. It works like this :

for (5 times)
	Use the cut search from enemy POV
	if (cut.score > 0)
		find the best spot to build a tower (ie the spots that covers the most spots of the found cut's path) and build a tower on it

This part could have been improved, especially because a cut can have several declinations, and building a tower on its path doesn’t necessarily increase its cost.

4- Unit training

Last part was unit training.
In this phase, I only consider training level 1 units. level 2 and 3 units are handled exlusively in the first phase (ie I only build lvl 2 and 3 units while executing a cut)

int maxUnitSize = <number of neutral cells> / 12
while (i have money && unitSize <= maxUnitSize) {
	find the best spot and build a level 1 on it
}

The scoring for spots was :

<number of adjcacent cells that I will be able to move on> - <distance to enemyHQ>

The whole AI used rarely more than 2ms, except in crowded late game situations.

Conclusion

The fact that most of the AIs used heuristics, and were deterministic, eased the debugging a LOT (and shortened the benchmarks :P)
The game was really fun and interesting, thanks to Azkellas and Tehelka
And congratz to reCurse for winning with such a margin

adecuq · May 27, 2019, 12:00pm

For the tower, is it really anywhere or in more strategic point or nearer to the opponent HQ?

Magus · May 27, 2019, 12:04pm

Anywhere. Since i after test all possible cuts for the opponent, i can check if the tower is useful or not.

adecuq · May 27, 2019, 12:32pm

I watched one of your game: https://www.codingame.com/replay/391596504
At your turn 8 you built a tower even if at the next opponent turn he can’t afford yet that cut (x=5 column)?

adecuq · May 27, 2019, 12:43pm

so in that game https://www.codingame.com/replay/391601535 it’s by chance you spanwed a tower in (2,5) at turn 10?

Magus · May 27, 2019, 1:08pm

There’s no chance. I test all possibilities and i found that this is the best place for a tower.

IloIlo_JRFerguson · May 27, 2019, 1:48pm

Euler, congrats, you did a great job in this contest ! I found it interesting but didn’t quite understand your move search. Can you provide an example of how the matrix and algo worked ?

Thanks !

_CG_SaiksyApo · May 27, 2019, 2:47pm

I’m not euler, but I found this one (https://www.geeksforgeeks.org/hungarian-algorithm-assignment-problem-set-1-introduction/).

eulerscheZahl · May 27, 2019, 3:11pm

Let’s take the following board as an example:

We see some units (1-4) and cells (A-K).
Both unit 3 and 4 would like to move to cell B. So we could send unit 3 there and let unit 4 wait.
The alternative is to make unit 4 take cell B and 3 waiting or going up to D. Let’s assume that D is the closest to the opponent, so moving unit 3 upwards and letting 4 take the empty cell would be the best.

So we assign a score for each unit in combination with each cell:

Empty cells are 0, left out for readability.

As the Hungarian method requires a square matrix, we have to add additional rows (units) to it.
These are just 0s everywhere (no score for doing anything).
Then we can just feed it into our algorithm, that we copied from github
This requires O(n^3) time and gives us one optimal assignment for units to cells.
Note: most implementations use a cost matrix rather than score, so we have to multiply every value by -1.

In my example I used the same score for any unit occupying a cell. You can vary the function, e.g. prioritizing high level units at the front over low level ones or not giving a reward for a lvl3 unit entering a neutral cell.

Edit: the forum was lagging, I didn’t even see that @_CG_SaiksyApo replied before me

Neumann · May 27, 2019, 3:17pm

Here is what I have in my logs for this turret :

his cut gain=28 cost=20 move unit 9 to 5:4, build 5:3, build 6:3

This cut would have lost me two units.

The turrets I build does not necessarily prevent the enemy to make lethal, sometimes it’s just to prevent a regular cut.

adecuq · May 27, 2019, 3:32pm

Okay thanks for your explanations Neumann, your strategy is very clear!