What strategies did you guys use?
- Updated Monday, September 14th 2015 @ 23:06:50
Now that submissions are locked, do you guys want to discuss how you implemented your bot? I am curious how you guys approached the problem.
For my bot, I viewed the challenge as a network flow problem. I viewed each region as "source" nodes in a graph and all enemy and neutral regions as sink nodes. And the idea was to push as much troops (flow) from my regions to opponent regions each turn. I had to make some modifications to the algorithm so that I would never send insufficient troops to an unfriendly region.
I also implemented a Edge scorer which scores every possible attack move and defend move I could make on a given turn. I watched a lot of games and came up with a scoring system through a lot of experimentation. I just give points for certain characteristics I see about an attack/defend move (if it's in a good superRegion, if it breaks an opponent superRegion, if it borders an opponent superRegion etc.) Then I divide this raw score by the number of troops I think it will take to capture this region.
I also wrote a superRegion tracker which tries to guess which superRegions my opponents own. It is very basic. I just assume that my opponent has access to all superRegions that are not visible or have some unvisible territories. Then I assume he will spend troops in the best one that is unvisible. Going by this assumption, I make guesses about what superRegions he owns and what his troop income is. And this information is used in the Edge Scorer.
Finally the way my bot works is as follows:
Evaluate all the attacks I can make from each of my regions. If I don't have enough troops in that region to make that attack, place troops there.
Now run the network flow algorithm and maximize the number of attacks to make. I have made modifications to the algorithm to prioritize choosing attacks with the highest scores and also to send enough troops for an attack.
And then repeat.
This is my bot's general strategy. There are a lot of edge cases and things to account for, which I had to make adjustments for. If you have any questions feel free to ask.
Good luck to everyone in the competition!
- Created Monday, September 14th 2015 @ 23:34:00
The last thing I implemented was stalling a loss by running around. The next thing I wanted to implement before I decided to stop updating my bot was the thing you showed in following game: http://theaigames.com/competitions/warlight-ai-challenge-2/games/55f72e1b35ec1d06d15e205b ... just that I would finally eliminate him the turn before the timer runs out of course.
- Created Tuesday, September 15th 2015 @ 00:22:23
Good idea Zoulander!
Here is my bot's (Anila8) strategy in a nutshell. I used the same basic idea for Warlight 1, but it has become far more sophisticated for Warlight 2.
I have several strategies, which only focus on a very specific goal, such as: - Conquer strategy: conquer a (specific) superregion: I have such a strategy for each superregion with a positive bonus - Attack strategy: attack a (specific) superregion, if it is owned by the opponent, or move in the direction of such a superregion - Defend strategy: defend a (specific) superregion, if it is owned by me - LastManStanding strategy: make sure to stay present in a superregion, which opponent could otherwise conquer this turn But also specific start game strategies: - Region picker / Round 1 strategy: focus on conquering the best superregion in one or two turns - Round 1 honeypot strategy: attack opponent in the first round in a bonus-3 superregion, which he thinks he can take in one turn - Round 2 strategy: same as round 1 strategy, but also try to block the opponent's best superregion, if possible Also end game strategies: - Win soon strategy: finish the game by attacking the opponent everywhere I can, if I'm sure that I'm going to win
All of these strategies are basically independent of each other. Each turn, each strategy generates a number of plans. A plan consists of: - A number of army placements - A number of moves (including null moves, which means "don't move these armies") - A score: the score represents the expected gain of the move. It's as much as possible based on probabilities. For example, the score for conquering a superregion is calculated as:
score = multiplier * P * bonus,
where multiplier is a constant, P is the estimated probability that the attack succeeds, and bonus is the superregion's bonus. For estimating P, I have to guess how many armies my opponent will place in his regions. I have some simple heuristics for that.
The strategies generate plans for different values of "startingArmies", the number of armies that they are allowed to place. Of course, generally more starting armies leads to a higher score.
After that, my decision maker component combines the plans and tries to maximize the total score, taking into account all possible smart combinations and conflicting plans.
One of the problems with these independent strategies is that their scores must be balanced very carefully. In earlier versions for example, I lost many games because halfway the game, the decision maker component suddenly decided that I had to conquer a big neutral superregion with a wasteland, right next to my opponent. Therefore I decided (last week) to disable the conquer strategy for superregions with an opponent neighbor. An exception is rounds 1 and 2, where sometimes you have to take the risk.
I have a similar thing like the superRegion tracker that Zoulander mentions. For all armies, which my opponent places outside of my sight, I guess where he will place them in order to conquer a good superregion. This works pretty well. If however, later on in the game, it turns out that my guess was wrong, I reestimate which superregions my opponent is likely to have.
Well, that's it in a nutshell.
Also from my side, good luck in the semi-finals and finals, and may the best win!
- Updated Tuesday, September 15th 2015 @ 01:06:25
My favorite part of my bot is that it considers the "shadow of worth" for each superregion (for both me and my opponent).
It purely calculates the potential in terms of "if I would try and conquer now, how many troops will it give me netto (taking in account numbers of troops lost) after 5 turns" (or vice versa for the opponent). This 5 turns is adapted for the starting turns, where we need to favor the smaller superregions.
E.g. it counts how many "moves" it need to fully capture, how many troops are totally needed (so how many reinforcements are needed), it takes into account "expected global income" of enemy etc. Also it considers the distance of the enemy.
This gave the defensive and offensive scores, and it really helps guide where I should go next. It also has similar "plans" (as we all started calling it) to you Ad, but I stopped developing my bot because it was too annoying to come up with a better structure internally. I did not have a way to consider multiple plans.
It was just a greedy implementation, sort on superregion values, see what plan is required for that super, if I can reasonably execute that plan, then use all the placements required and use what is left for the next plans.
Very unfortunate, that is why the bot is subtop.
Though I'm still very happy with the result of the metric: keeping the score in terms of countable "troops" only adds to its awesomeness. It often leads to very interesting breaking attacks in the first 1-2 turns as blue.
It's a very efficient metric -- my bot is just quite bad.
Also, lack of planning made it difficult to think ahead what the enemy would do, I didn't work yet with multiple "maps", but only a single one with projections/reasoning on top.
But hey, at least it is not the mostly hardcoded Europe strategy :-)
Good luck to all!
- Updated Tuesday, September 15th 2015 @ 04:23:05
@Dualinity Haha, that sounds very cool. It is impressive how successful that metric is! Maybe with some tweaking or further adjustments you could have made your bot even better!
@Anila8 Nice, I thought the way you designed your bot is very interesting. I wish I had done something like that; I think the model of my strategy limited itself a lot. I had a lot of trouble trying to make improvements and implement advanced strategy.
Hey so one question I have is how did you guys optimize how you attacked neutral regions?
Like for example, let's say:
Region A borders Region C and D
Region B borders Region D
So the optimal matching would be for A to attack C and B to attack D. If you had A attack D then you wouldn't be able to capture C that turn. How did you guys produce that matching with {A attack C, B attack D}?
- Updated Tuesday, September 15th 2015 @ 07:54:51
@Zoulander: what I do in this case is first select the attacks, which can only be done in one way: in this case that is attack C from A. After that, I select the remaining attacks, based on remaining armies after the first attacks. So it depends: if B has much more armies than A, then I would attack D from B, else from A. If I have more armies available for this plan, then I place them at the borders where I know or expect my opponent is.
- Updated Tuesday, September 15th 2015 @ 08:21:17
@cowzow Indeed interesting. I did some complex sorting strategy with a lot of condition checking earlier on (and also in the previous Warlight). I sort both the regions to attack within a super, as well as sorting my regions that are able to attack. Typical things to sort on are how many unoccupied within super regions are bordering. You would start with those that are having limited options :)
For capturing a super, I do however consider ALL possibilities :) Including enemy reinforcements etc. Pretty brute, but with some optimizations. E.g. if you have 5 regions involved in capturing a super (2 inside the super, 3 bordering), then it will consider putting reinforcements on each.... (0,0,0,0,1) up until (5,0,0,0,0) if we have 5 reinforcements to spend (that's the simplified explanation), while at the same time checking that the attacks would most likely be succesful (counting extra enemy reinforcements etc). .
But your bot is very impressive itself! Do you also have "plans"? Only execute a lot of moves when you think the overall "plan" would work?
- Created Tuesday, September 15th 2015 @ 11:56:30
@AdsRiskbot Haven't updated my bot in quite a while but I used a strategy similar to this, except with a much more convoluted "worth"-calculation, that takes into account vulnerability and stuff like that. So for every possible move it divides payoff by cost, which means that for example sole none-owned region in a superregion otherwise owned will have a huge value.
My bot never does "grand plans", every order is carried out individually, so the first thing it does it try to find the highest value move, and when it is decided the bot tries to guess how the outcome will be for the whole map. All "proposals" for moves are then recalculated and the old ones thrown away. If for example a region in a superregion is about to be attacked with a considerable force, the bot will consider that region taken for the other orders that turn, which means that other attacks against the same superregion will be preffered, since it is now cheaper to take. This makes it seem like the attacks and plans are coordinated, while they in fact are not.
- Created Tuesday, September 15th 2015 @ 13:23:42
Hello
@AdsRiskbot: Your stuff is kinda the straight forward approach of a software engineer (breaking down the big problem into multiple small problems and then throwing stuff together again) while some other guys here are transfering their special domain background to this challenge.
How do you handle the problem of possible synergy effects? For example: Your "Defend SuperRegion" strategy finds it more more worthwile to defend the +5 than the +4 SuperRegion. However if you would defend the +4 SuperRegion instead then your "Attack SuperRegion" strategy could use those armies used for defense to break another +4 opponent SuperRegion.
- Updated Tuesday, September 15th 2015 @ 13:40:51
@Norman: Quoting Ad:
After that, my decision maker component combines the plans and tries to maximize the total score, taking into account all possible smart combinations and conflicting plans.
So the situation you (Norma) describe will have a higher value because the grand total is higher.
This is exactly what Bolt lacks.
- Updated Tuesday, September 15th 2015 @ 17:21:45
Hi all. For future - sorry for my english. I also will try to explain in general how my bot works. My bot i think most complex, and this complexity is born from warlight 1 challenge. However many things are need to be rewriten since that.
The reason why I not started bot from scratch - is thousands of unit tests on different game situations on Small Earth map, which will be broken for new bot, and it would be very complex to fix them all.it consist of such modules as:
- Piker of starting positions: using minimax + alpha beta pruning
- Battle AI v2: coordinates all modules below + many other stuff. It extends from Battle AI v1 which was developed for warlight 1 challange, reuses and overrides many functions.
- Strategic scores analyzer - it evaluates strategic score of every region and potentional scores of all regions. Also it calculate best strategic move plans for enemy and me, where strategic plan is sequence of moves with big stack to break enemy superregion, or defend my superregion.
- Region pair analyzer. Region pair is pair of near region where region1 - is my, and region2 - is enemy region. For each such pair, basing of strategic scores of region I calculate attack and defend scores with specified number of armies. For example if region has big strategic score (as part of superregion) then it will have higher defence scores, compared to region which is not part of my superregion. The same if region2 is part of enemy superregion then I will have high attack scores to attack it.
- Combinatoric selector of best battle move: basing on analyzer region pairs I generate all (almost) possible combinations of placement armies on every my region. For every combination I calculate best move for every my region. Then from all combination I select the one with max score. Possible moves for one region are (without details): defend, regular attack, spread attack, carefull attack, strategic move, help with defence to near region, prevent enemy expand move.
- Expand AI - calculation of optimal expand, taking into account: how many turns need to expand, armies used for expand, income of bonus. It produces many possible seqences of expand moves, and then selects best from them. It could take into account the wastelans, which are situated in the way to superregion (but not part of them), and avoid them.
- Enemy predictor - predicts where are enemy regions which are hidden from me.I have 3 types of tasks:
- battle moves
- expand moves
- moves to enemy (toward enemy regions and bonuses)I caculated this tasks for every income I can use on them. For example if I have 9 income then i produce 10 bettle moves, 10 expand moves etc (for every income i can spand on it 0 .. 9) For each task I calculate the score, and then select 3 tasks with max sum of score. So for instance bot could decide to use 'expand' task which uses 3 income, and 'battle' task which uses 6 income and no 'move to enemy' task.
Most interesting part of my bot which significantly increased its power, is that every new round I try to calculate best move for enemy with 'swap' of players. So I set that enemy is me and me is enemy, and run all logic of bot. It gives me some approximated best move for enemy. Then I 'swap' players back and calculate best move for me, to counter best move of opponent. Using this function I can predict and track where enemy expands in hidden regions etc.
The problem with Anila8 last days was that my bot is generally defencive, and Anila8 is very aggressive. It always attack bonuses, etc. So by 'swap' players function I wrongly predicting that enemy will not attack and place low armies on defence. Thats required from me to code additinal logic to defence from such aggressive moves.
- Created Tuesday, September 15th 2015 @ 22:37:31
@Norman What do you mean with "transfering their special domain background to this challenge"?
Regarding your example: I don't have only one "Defend superregion" strategy, I have one for each superregion, so there will be plans for both the defense-superregion strategies and for the attack-superregion strategy. Furthermore, my defend strategy generates two types of plans: plans where I only defend, and plans where I defend by attacking my opponent. In this example, the decision maker will select both the attack plan and the (identical) 4-bonus defend plan, because the combined score will be higher than just defending the 5-bonus superregion. You can see this more or less in game http://theaigames.com/competitions/warlight-ai-challenge-2/games/55f4f32c35ec1d06d15e03fc, against your bot, in round 14. Here I have superregions 2 and 3, both with bonus 4. You have superregion 1 (bonus 2), which has some neighbors with 2. Although I place armies in both superregions 2 and 3, most are placed at 2, because they do not only defend 2, but at the same time attack 1.
@GreenTea OK, so swapping players is your secret. I do it a bit in my bot as well, but only for predicting where my opponent is placing armies outside of my sight. I considered to use it in more situations, but I had no clear idea what to do with the information, and then suddenly time was up.
Question to all of you: does anyone have some kind of opponent recognition in place, and specific strategies for a specific opponent? Speaking for myself: I had this once in my bot, for RealityBomb. He had a very recognizable strategy in round 1 and 2, so I knew exactly how to counter him in round 2. After a while, I generalized that to my Round 2 strategy, because it turned out to be more generically applicable.
- Updated Wednesday, September 16th 2015 @ 00:38:41
@AdsRiskBot. "does anyone have some kind of opponent recognition in place" No. Just In the end, while thinking about how to counter Anila8, I only had idea about some king of prediction of enemy agression. For example, if enemy near border of my superregion, will it attack it or not in case when I have incomoe to defence? My bot never attacks, becuase it expects that enemy will defence, and I only lose armies on attack. But Anila8 does attack no matter what.
So at the beginning of game enemy predicted agression score will be on max value, because its more safe. So bot will put all in defence. Then If I see that enemy is not attacking, I should decrease predicted agression value, and in next turns will expect that enemy most likely will not attack in similar situation, and I could put much less armies on defence, etc. But had no time to implement it..
- Created Wednesday, September 16th 2015 @ 00:52:42
@AdsRiskBot.: "In this example, the decision maker will select both the attack plan and the (identical) 4-bonus defend plan, because the combined score will be higher than just defending the 5-bonus superregion. You can see this more or less in game "
Defence with attack with big delay is very nice idea.. And yes in this case more correct is to sum scores of defence and attack. In given game your bot should only try to make more delay.
- Created Wednesday, September 16th 2015 @ 21:33:13
@GreenTea: Nice to hear that Anila8 caused you headaches:). But please note that the opposite was true as well.
About the delayed attacks: that is something that my bot is really lacking. I had it on my TODO list, but it did not fit easily in my architecture.