Just a couple of ideas regarding tactics for the Warlight AI Challenge. I haven’t had time to try all of them, and I’m not even sure whether I will, since the finals are approaching rather quickly, but I thought I’d pen them down anyway. Also note that my bot is open source, if you need a basis for yours.
Joint/Split invasions
Implemented: Yes.
The game takes place on a simple graph, rather than a straight line, so when you only consider attacking from a single region, you are missing a lot of opportunities. To see what I mean, consider the following situation:
This is a screenshot of round 99(!) of this match, and the blue bot is mine. I should definitely have lost, but my opponent’s attack logic probably looked something like this:
for each friendly region R
for each non-friendly neighbour N of R
if attack R -> N is feasible
attack N from R
Now consider the following attack sequence. The red bot is mine (yes, I cherrypicked the examples):
The bot determines that the region containing 17 armies actually has 2 potential targets, and it has sufficient armies to attack both. Additionally, there are 2 other regions that could potentially aid in the attack.
As you can see this can make quite a difference. Not only do you avoid situations like we saw in the first picture, but you also move across the board much faster. This is roughly how I do it:
for each non-friendly Region R
# Gauge how many armies would be available for an attack on R
for each friendly neighbor N of R
R.availableArmies += N.CanMiss(R)
# Attack if there are enough
if R.availableArmies >= R.requiredArmies
Attack R
The CanMiss(R) subroutine of N is essential here. It specifies how many armies the friendly region N could miss if region R wasn’t there. In other words, this function loops through the hostile neighbors of N that are not R, decides how many armies it needs to defend itself against them and subtracts that from the armies it actually has (clamping at zero of course).
This way, not only can you organize joint attacks on hostile regions, you can also do so without compromising the safety of the attacking regions.
However, there is a slight problem. Going back up, to the image sequence showcasing this behavior, notice how the region containing 17 armies splits a bit unevenly, at 15:1, rather than, say, 12:4? This is because there is some discrepancy between armies needed for an attack, and armies needed for defence.
To be more precies, the 17 army region R in question sees two neighboring regions: N1 containing 8 armies, and N2 containing 2 armies. It first of all decides that if it is going to attack N1, it still needs to be able to defend itself against N2. How many armies are needed for this? Let’s say two is enough. That means we can attack with fifteen!
Next up, it wants to attack N2. How many armies are necessary for the defence against N1? Uh, ten should be enough. Attack with seven!
I haven’t really implemented a solution to this sub-problem yet, but here are some ideas:
- Execute all attacks the region, in ascending order of how many armies the region provides. Simple to implement, but probably won’t really work that well. Note that occassionally (but very rarely), two regions might both be involved in two different attacks, and require them to be executed in opposite order.
- Once a region has attacked once, block all other attacks it is involved in (or, continue the attack without the relevant region, if possible).
- Run over the final set of attacks several times, and recalculate attacks where the total amount of armies required from a region exceeds the available, potentially discarding one or more attacks if necessary.
Move idle armies to frontlines
Implemented: Yes.
Another thing I notice a lot is that when bots are done in an area, they just leave their excess armies there. For example:
And on the opposite side, look how this match progresses. Really, there is nothing too fancy going on. All you need is a simple implementation of breadth-first search that searches for regions in a specific list, rather than a single target. Just run all frontline regions through it and head to the closest.
Again, people are really missing opportunities here, especially since you can make as many moves as you want in a turn. As long as you do all the transferring after the attacking, you have nothing to lose.
Properly handle a fragmented playing field
Implemented: No.
Consider the following situation:
Not so good, right? In this case it would probably be best to give up the regions in Asia and North America, and focus on defending Australia. However, currently my bot (and probably many others) only cares that Ontario is significantly threatened, and gives it some extra armies.
Obviously, it should instead follow the US and give up on conquering Canada. This is actually harder than it looks because it requires the bot to look at the Big Picture. Currently my bot only does this by looking at how much of a region’s superregion is owned (proportionally), which evidently is not enough.
Ideally, the bot would pick a certain network of friendly regions (in this case Australia), and only focus on regions that are directly connected to it. I’m not yet sure how to react to this network being split up (as happened in China in the image above), but the best option is probably to continue with the largest network, or the network that contains the most (nearly) completed superregions.
Either way, that’s it for now. If you have any other ideas or comments on the tactics proposed above, let me know in the comments!