umm.. Probably bot consider that not all 7 armies will be used by enamy to defend region. And for all cases of defend, with deploying 0, 1, 2... 7 armies it calculate average scores for attack. And this average score for attack becomes greater then average scores for my defence, calculated in same way (if I use 0, 1, .. 7 armies to defence). Tricky logic.. Some not trivial math standing behind this, and often it's hard to predict even for me what bot will do in next turn.

Edited 5/27/2014 18:26:32

Sometimes it's working when enemy start expanding in the same time when I attack.

Edited 5/27/2014 18:23:36

http://theaigames.com/competitions/warlight-ai-challenge/games/5384e1744b5ab2088e1bb90e
crap :'(

Hello

@Ikalgo:
The question you asked at stackexchange seems a bit strange to me. It's lacking the fact that you can place armies between the attacks. Furthermore I don't see you getting much gain from your calculations. If you just assume 0% luck you can easily calculate how many turns it will take you to break the opponent (I only find the question 'if' I break the opponent relevant). If you then have the minimum amount of needed armies I think that for each luck factor > 0% you have exactly a 50% chance of getting your break in a couple turns. Furthermore your bot has to answer the question if he really want's to keep hiting that one spot.


I don't think it's necessary to calculate with a brute fore attempt game states in the future. If you have good heuristics it should be possible to only calculate the next move. For example expansion: You don't wanna just attack random territories in a bonus but you wanna attack in a way that gets you closer to taking the bonus. Now you could calculate all possible expansion options for the next 3 turns and then pick the option that acutally let's you take the bonus. What I do however is just looking at which territory has the maximum amount of unknown neighbors in the bonus and then I attack that territory.

Same goes for fighting. A good heuristic could for example be that the closer a region is to your / the opponent bonus the more that region is worth. You can also try to attack those regions that get you closer to completely push the opponent out of the bonus.


I think it's more interesting in how I define a strong bot than how my bot acutally works:

First you need a function that tells you whether you are winning or losing:
GameState(ArmiesOnBoard,IncomeAndOpponentIncome,PositionOfArmies)
--> ArmiesOnBoard --> Your armies / guessed opponent armies
--> IncomeAndOpponentIncome --> Your income and the guessed opponent income
--> PositionOfArmies --> Maybe you have your armies somewhere in nomansland while the opponent has a huge stack that borders all your income on multiple borders.

Then you need a function telling you how many armies to use for expansion and how many for fight:
ExpansionFightArmies(FightingOptions, ExpansionOptions, GameState)
--> The amount of armies you use for expansion versus fighting has to depend on how much you can achieve this turn and how much armies you need to achieve this task. Furthermore the GameState is important. If you have the game won then stop taking bonus after bonus and finish off the opponent.

Then you need a function telling you how to expand properly:
Expand(GameState,ArmiesForExpanding)
For expanding it's also important to know where the opponent is what is a part of the GameState. You might wanna hit the spot bordering the opponent strongest or not expand into a bonus bordering the opponent.

Fight(ArmiesForFighting,Position,ArmyKillsAndLosses,GameState, GuessedOpponentMoves)
For me fight is everything that isn't expansion. When you march with a huge stack towards the opponent this also belongs to the fighting task.
--> ArmyKillsAndLosses: Killing opponent armies has a value on his own
--> GameState: Depending on whether you are winning or losing you have to take more risks fighting. When you are losing you might wanna accept a 70% chance of the opponent breaking your bonus with a full force attack while when you are winning you wan't to play safer.
--> Position is more abstract. You can give each territory a value depending on different factors. However the position not only depends on which territories you hold but it's also relevant how many armies you have there.
--> Guessed opponent moves is what all bots lack to some extent. Just because the opponent has a big stack sitting on a territory doesen't mean that this stack also has to be there at the end of the turn.

GreenTea: Ah, well yea I used monte carlo / markov chain application for obtaining the probabilities. It is very useful and I believe it to be the ultimate solution. Each of the 2 million cases I have simulated were simulated 1000 times each. I need up until Round 10 to load in everything (given that I'm using Python).

I'm wondering about you working with "a map of a few rounds ahead". Do you have any idea how those predictions fare, are they spot on usually?

And yes, Ad has also escaped from me before :(

Sigh, I was writing a long post and the page got refreshed.

Anyway, indeed it does not make much sense to simulate without taking into account income. I did in my actual simulations though.

Just some examples:

5 5 99 110 0.689
5 5 99 111 0.774
5 5 99 112 0.829
5 5 99 113 0.844

For example, the second line states that when both attacker and defender have an income of 5, the defender has 99 troops and the attacker has 112 troops, the attacker has 77.4% to break the enemy over time. It is not possible to use any linear formula to produce a result similar to this. You can imagine though how useful it is know these numbers at any given moment.

If you compare it for example:

5 5 6 7 0.402
5 5 6 8 0.701
5 5 6 9 0.91
5 5 6 10 0.973
5 5 6 11 0.996
5 5 6 12 0.997

You could simply find out for each placement of a troop where it adds the most probability.
In fact, if you would also add in your priorities per region of the map, this could get really sick!

Also, please look at our recent games (SA/AU). I can freely expand because I know how many troops I need to be safe in North Africa. Unfortunately I didn't have time to finish the tactic of capturing australia behind your back, an earlier version did better :/ It now just wanders around in Asia which ends up getting me killed.

So yea, basically what I'm trying to say is that you need good heuristics AND you need the math for the best strategy. Your decisions will be even better when backed up with the right numbers.

In the strategy part I can certainly learn a lot from you and the things you bring up are interesting, I only started playing Warlight during this competition.
I made a breakthrough with Europe recently, as I'm not trying to capture Brazil, but instead immediately go for Australia. I'm having mixed feelings as my bot is playing Europe as well as SA/AU, and I'm thinking I should have just polished one strategy instead.

Main problems with Europe has been solving the graph to optimize capturing Europe, sadly, I haven't solved it (but yea, that's where heuristics come into play). The opportunity for North Africa to attack 2 regions in Europe is something else I have struggled with.

Lastly, I'm interested in how you assigned values to regions? I assume it is very difficult to fine tune the weights, though it surely seem to be a superior solution! I read you wrote about it but I figured it is really difficult to find rules for assigning these values.

Edited 5/27/2014 22:00:13

Hello

Lastly, I'm interested in how you assigned values to regions? I assume it is very difficult to fine tune the weights, though it surely seem to be a superior solution! I read you wrote about it but I figured it is really difficult to find rules for assigning these values.

The only thing I cared about when assigning region values is whether they help my bot making smart moves or not. There is no true of false, just helpful and not helpful. Before I updated my fighting mechanics about two months ago the only information my bot used when performing attack moves were the region values and the opponent was some sort of an obstacle hindering me from taking my preferred regions. Basing all your moves on a simple integer value however doesen't result in very good moves. You also need to distinguish different situations. In fact I never fine tuned my region values and the situations that my bot distinguishes are far to less. However my region values work like this: The exact value of a region is unimportant. The information is just that region A has a higher value than region B. Since I don't want unimportant stuff to interfere with the important stuff I sometimes give some pretty high numbers but this is just to make the modeling easier.

The heuristics for giving values are pretty simple. However the values being good depends on if you know what is going on behind the fog.

For example when expanding in a SuperBonus:
- Give each neutral region +1 for each bordering unknown region in the same SuperRegion
- Give each neutral region +1000 for each possible opponent bordering SuperRegion

For the fighting part you have to ask yourself where do you want your bot to fight, for example:
- The more territories still owned by neutral in a bonus the less worthwile it's for you to fight for it.
- Regions that border the opponent SuperRegion / your own SuperRegion are especially worthwile
- Regions that belong to the opponent SuperRegion / your own SuperRegion are even more worthwile
- It's more worthwile to fight for small bonuses than for big bonuses.
- If you get the chance to completely push the oppoent out of a bonus then the remaining spots of the opponent in the bonus are worthwile (and vice versa). This is especially the case when there aren't any neutrals in the bonus.
- The closer a region is to your bonus / the opponent bonus the more worthwile it is

If you only use the region values to guide your moves you will get into trouble. The problem is that you want to perform different tasks each move. If one of them is extremely important like breaking the opponent bonus then it's better if you put a huge amount of armies to this task. My bot only distinguishes three different situations what isn't enough, I call them high important, medium important and low important.
- High importance --> Defending own bonus / breaking opponent bonus / taking over last spot in opponent bonus / not losing last spot in otherwise completely owned opponent bonus
- Medium importance --> Protecting entry to bonus
- Low importance --> All other stuff

The problem is that most games are to static / not messy enough so you don't see that well how me priorizing the regions comes into play.
http://theaigames.com/competitions/warlight-ai-challenge/games/53841d8f4b5ab2088e1ba896
http://theaigames.com/competitions/warlight-ai-challenge/games/5381ae1a4b5ab2583f2427bb

I like your general approach more though, just I feared it would take too long to fine tune these priorities and basically that it would be roughly the same as just writing down strategies like this. Each of your items makes a lot of sense though.

Below how I did my placements. Note that I have "tentacles" (created from playing Europe). These are spots I wish to obtain because I expect the enemy to be there or because it would give me an advantage to obtain this spot (for example, North Africa). I will use the find shortest path from all my regions and the region that is closest would be considered the tentacle ending.

In order:

PlaceDefendAtMostOnePerContinent - try to stay alive in all supers
PlaceAttackEnemyWithinOwnedContinent - one enemy in otherwise owned super
PlaceDefendOneVOneContinent - priority to defend if enemy can only attack 1 region
PlaceAttackNeutralInContinent('3')
PlaceDefendTwoVOne - if one region can attack 2 regions of mine in super, defend
PlaceTentacleDefend - defend a tentacle starting or ending region
PlaceTentacleAttackEnemy - try to go through enemy to go to goal
PlaceTentacleAttackNeutral - go through neutral to go to goal
PlaceDestroyEnemy
PlaceSeekEnemy

Attack transfers for Europe strategy (these are prioritized like that):

I also care about the order; either "begin", "doesn't matter", "last". The importance of the order is taken into account as well (so within each subcategory those with higher importance are done first/last)

In order:

self.decideExpansionTargets([["North Africa"], ["Indonesia"], ["Brazil", "Greenland"]], anyRegionInSuperIsOK=False)
self.ATAttackEnemyInContinent('3', p_min=0.2)
self.ATAttackNeutralInContinent('3')
self.ATDefendTwoVOne('3')
self.ATDefendOwnedContinents()
self.ATTentacle() - expand, defend
self.ATDestroyEnemy()
self.ATAttackNeutralInContinent('6')
self.ATAttackNeutralInContinent('2')
self.transferTroops()
self.ATSeekEnemy()

My transfer troops is also quite interesting. Leftover troops will move either to the strongest enemy nearby (< 4 regions away) if my troops could use reinforcements, otherwise move to close neutral, and otherwise move towards closest (but perhaps far away) enemy.

Edited 5/28/2014 07:51:11

Edit: My bad, looks like it is actually something very different than I thought. Phew. Still a couple mistakes, but stupid logic bug on my part, not an operation error

Edited 5/29/2014 18:21:28

Dang you guys got all advanced. I started working on my bot pretty late (about a week into May). So I had to keep things simple so went with a real cheesy solution. I just place, with a little bit of randomness, some cheese on the map and have my mice (army stacks) find the cheese. Then new cheese is placed and this is repeated. I didn't know how else to keep my bot fed. When I tried doing it the non-cheesy way it seemed to just lock up and go on strike, malnutrition bug or something. How did you guys keep your bots fed so they wouldn't lock up? I was a noob programmer coming into this so it took me a while to even figure out my bot needed to eat. I just assumed they were machines without needs. Guess I really learned something taking part in this competition.

I just place, with a little bit of randomness, some cheese on the map and have my mice (army stacks) find the cheese.

Brilliant :)

So the first time I ever made into first place was with a pretty small bot without a lot of logic that only knew to take SA and take advantage of people not knowing how to play AU (ironic, right?). This took me from 50th or so place straight to first. Once there, it became obvious that I was playing against bots that actually knew what they were doing (and competing with other smart SA bots) and really had to step up my game.

I will say, every time I played against Dalek was frustrating as all hell. Even in my final bots. Screw you and your better-than-me-at-warlight coding efforts :P (that was sarcasm in case you missed it. I actually have great respect for Norman and his bot)

Anyways, I'm no where near as good of a WL player as the rest of the top guys in the AI challenge, so I basically had to adapt by copying. I see something awesome your bot did that was awesome, I would code up something similar.

...or against. Perfect example here is Gadzbot's notorious ability to take Indonesia from Siam turn 1 and me not be totally prepared for it. I coded up a whole routine to not only protect against that scenario (I'm sure you noticed 125ch209), but start taking advantage of those picks that can sabotage the opponent early. Of course, I forgot one small detail before submitting my final code that keeps making me sad every time I see it happen: When Siam is available and Central America isn't, make South America picks my 1st and 2nd. Whoops! This is the functionality I was referring to when I said "I actually named some of my routines after the offending player. Before calling it "CheckForPossibleSabotage" it was "GoF***UpGadzbot", haha.

My biggest weaknesses in WL is early game and large frontiers. The latter I didn't have to worry too much in this map, thankfully. But the early game, even at the end of the coding challenge, is something that causes me strife. A main issue with my bot is that it didn't detect when I lost a bonus on turn 2 or 3 due to a good luck roll by my opponent (11 took a 9. I mean, c'mon, who does that?).

Eventually I moved my bot over to an AU-pick first bot - hard coded, but I like the idea someone proposed earlier about using the "harder to get to" method - mostly because I started using the knowledge of knowing where you were to my advantage. For example, if you had both SA picks and our 3rd picks were kissing in Africa, I knew you needed at least 5 armies to take South America. So, I would sit there and count what you lay down every turn that wasn't in SA and know that you were still at a 5-army income. If I get my first three picks or only see one of your armies, I guess your last two picks are in Europe and do the same thing, hopefully interrupting you in time. Australia was only ever given priority over SA if: I received both picks in AU, or; I received a starting region in 3 different continents. Other than that, my bot was actually still an SA bot, just with AU picked first.

Genius, right?

Anyways, I keep seeing you guys talking about how you're calculating attacks and percentages and statistics and blah blah blah... Here, I 100% agree with Norman and I only code battles for 0% luck. On average, it's what will statistically happen more often. No matter what, you're going to lose to a perfect roll by your opponent even if you calculate everything exact.

public enum BattleRegions
{
    Attacker,
    Defender,
    Neither
}

private BattleRegions WhoWinsOnAttack(BotState currentState, int fromRegionArmies, int toRegionArmies, int opponentIncome, bool noOpponentIncomeThisRound)
{
    var attackingArmies = fromRegionArmies;
    var defendingArmies = toRegionArmies + (noOpponentIncomeThisRound ? 0 : opponentIncome);
    var defendersDestroyed = attackingArmies * .6;
    var attackersDestroyed = defendingArmies * .7;

    var attackingArmiesLeft = attackingArmies - attackersDestroyed;
    var defendingArmiesLeft = defendingArmies - defendersDestroyed;
    if (attackingArmiesLeft <= 0)
        return BattleRegions.Defender;

    if (defendingArmiesLeft <= 0)
        return BattleRegions.Attacker;

    if ((int)attackingArmiesLeft + currentState.StartingArmies == fromRegionArmies && (int)defendingArmiesLeft == toRegionArmies)
        return BattleRegions.Neither;

    return WhoWinsOnAttack(currentState, (int)attackingArmiesLeft + currentState.StartingArmies, (int)defendingArmiesLeft, opponentIncome, false);
}

private BattleRegions WhoWinsOnDefend(BotState currentState, int toRegionArmies, int fromRegionArmies, int opponentIncome, bool noOpponentIncomeThisRound)
{
    var attackingArmies = fromRegionArmies + (noOpponentIncomeThisRound ? 0 : opponentIncome);
    var defendingArmies = toRegionArmies;
    var defendersDestroyed = attackingArmies * .6;
    var attackersDestroyed = defendingArmies * .7;

    var attackingArmiesLeft = attackingArmies - attackersDestroyed;
    var defendingArmiesLeft = defendingArmies - defendersDestroyed;
    if (attackingArmiesLeft <= 0)
        return BattleRegions.Defender;

    if (defendingArmiesLeft <= 0)
        return BattleRegions.Attacker;

    if ((int)attackingArmiesLeft - 1 == toRegionArmies && (int)defendingArmiesLeft + currentState.StartingArmies == fromRegionArmies)
        return BattleRegions.Neither;

    return WhoWinsOnDefend(currentState, (int)defendingArmiesLeft + currentState.StartingArmies, (int)attackingArmiesLeft - 1, opponentIncome, false);
}

As you can see, I'm a big fan of recursive functions :)

The boolean noOpponentIncomeThisRound comes from a private class-level variable that tells me if I calculated or guessed where you are placing your armies for the turn. Basically, these routines simulate the attack, take what armies are left over, and plug them back in assuming that you and I are going to put all of our armies on these stacks again. Keep going until one region loses all their armies. If you're going to say "It should be until the attacker has 1 army left, not zero" -- maybe for your code, not mine. That's taken into consideration on the number of armies initially passed in.

Not perfect (if these regions don't get army placements, they might not next turn, etc), but it seems to do the trick for what I need it to do.

This can be quite easily modified to determine the number of turns it will take to get to desired defeat by creating a class level variable that is reset in the calling function and then gets incremented every time the routine is called recursively.

I also use these routines to detect stalemates (if the winner for both regions is always the defender, we're most likely in a stalemate on that region).

One last final piece of advise I truly want to recommend: Learn how to figure out your opponent's income. I notice a lot of you try to "hide" your income -- which is smart unless you've already given it away to me 5 turns ago :) If I calculate that you have South America, I also know you're going to have it until I own a Region in South America. The method to calculate opponent income is actually a lot less trivial than you think!

First, determine what super regions you don't know anything about, meaning ALL regions are owned by player "unknown" (if you see a neutral region, you already have enough information on that super region to know it's unowned).

If your opponent lays down more than 5 armies in your field of sight, figure it out according to those unknown owned super region how many armies your opponent put down:

foreach (var unknownSuper in state.UnknownStatusSuper)
{
    switch (unknownSuper.Id)
    {
        case (int)SuperRegionNames.Africa:
            if (VisibleIncome > 7)
                AddOwnedSuperRegion(unknownSuper.Id, state.FullMap, state.RoundNumber);
            break;

        case (int)SuperRegionNames.Asia:
            if (VisibleIncome > 14)
                AddOwnedSuperRegion(unknownSuper.Id, state.FullMap, state.RoundNumber);
            break;

        case (int)SuperRegionNames.Australia:
            AddOwnedSuperRegion(unknownSuper.Id, state.FullMap, state.RoundNumber);
            break;

        case (int)SuperRegionNames.Europe:
            if (VisibleIncome > 9)
                AddOwnedSuperRegion(unknownSuper.Id, state.FullMap, state.RoundNumber);
            break;

        case (int)SuperRegionNames.NorthAmerica:
            if (VisibleIncome > 10)
                AddOwnedSuperRegion(unknownSuper.Id, state.FullMap, state.RoundNumber);
            break;

        case (int)SuperRegionNames.SouthAmerica:
            AddOwnedSuperRegion(unknownSuper.Id, state.FullMap, state.RoundNumber);
            break;
    }
}

(Note, I have an enum set up for both Regions and SuperRegions to identify their IDs by name)

If you think the numbers above won't work in certain situations, you're probably right, but those situations are games you've already lost. When I detect the opponent owns, I have a routine that takes care of adding important opponent information to my opponent tracking class, you can put whatever you want in between the "case:" and the "break;" :D

Anyways, that's a quick peek into the guts of Trogabot. I'll bring more to the party later and I hope I taught you new coders something :)

Edited 5/29/2014 16:31:10

foreach (var unknownSuper in state.UnknownStatusSuper)
{
switch (unknownSuper.Id)
{
case (int)SuperRegionNames.Africa:
...

This is what im calling hardcoded bot :)
Can't wait when we will start fight on random maps.

Yeah, but with 6 supers to choose from, it's easy in this map to pick. I'm hoping that we get a 10-map random generation, but this is something easy to make into a generic method. It was coded so long ago that I never got around to modifying it since there were more pressing matters to fix, like who is GreenTea and what is he doing better to beat me??? :)

A quick glance at my code tells me that it would just be using what bonuses I know you have, calculate which give me a higher total than what was know previous round. If you control SA and I'm in AF, you're likely to have taken NA, etc.

There's a small bit of hard-coding from lower numbered versions that never got fixed, like in this example. Again, all due to priorities.

Another bit slap on the hand I gave myself for my code was setting up my place army routines to seamlessly transition over into a Strategy pattern. All the signatures on the methods are the same, so I could have made them generic, created a decision class, and let the pattern go at it. Alas, it was not meant to be.

I'd really like to see if Jim could set up a separate environment so that we can keep playing around with our bots in a non-competitive environment because I want to clean up my code so bad, but I don't want to break anything. Perhaps giving us the ability to queue up our bots against selected opponents or up the range of opponents to +50 and -50

I had made improvement which gives 56% of wins vs version on site.. :'(

Edited 5/30/2014 17:56:32

56% wins vs current version? Not bad, but my new version gives 7% more cheese. That's less hungry botting. Can't beat that.

ps, I don't think either of our bots expected this and had no idea what to do:

http://theaigames.com/competitions/warlight-ai-challenge/games/538915d24b5ab20a0172afe6

ps's bot seems to dominates mine. Played him 6 times and he's beat me every time. This is the best I've done: http://theaigames.com/competitions/warlight-ai-challenge/games/53879cca4b5ab20a017292c8
I might have actually tied (or possibly even won) in that game except he had two lucky attacks that gave him the advantage. The other 5 games he's won in 15 to 30 turns. Perhaps I'm just saving my lucky victory over him for later :P

I doubt he feeds his bot cheese so I figure some of these bots will be a bit anemic by the semifinals and I'll be able to have a lucky streak with my well fed bot. Atleast I assume your prior method of feeding your bots was doing it manually and then updating it and since you can't do that during the competition I figure my lone advantage lies in my cheesiness.

Trogatog: mine should have started expanding into europe once the stacks were high on SA, no idea why it didn't, would have to debug it, but there is no motivation to do that now that the competition is closed :)

Ikalgo: does your bot deploy his newly acquired North America income out of my sight on purpose? To "hide" the bonus? Well done.

http://theaigames.com/competitions/warlight-ai-challenge/games/538a38e44b5ab20a0172c687

pedrito: Yes! I was making specific changes on the last day to counter you and GreenTea; he actually immediately rushed me in North America as soon as he found out the income. So I went for 2 changes, hiding income and going for Australia to attack.

First to hold the border region in Asia so I can protect in time (GreenTea was building a large army in Australia in preparation of going to North America). Secondly, obtain North America, and then finally rush Australia. Note that my calculations allow me to nicely expand. I also monitor Europe at the same time; whenever 2 regions are held in Europe at the same time bordering North Africa, I would "smartly" try to break the bonus.

My main problem was that I wasn't able to test building an army in Asia. In the end, the troops just wander off rather than go for Australia, and they've ran into Dalek so many times causing me to lose (which is very frustrating!), and it happens not only against him. I was trying to keep it safe by implementing those 2 changes, but I believe against the current competition I could just hide income and instead simply first capture North America and then rush Australia; no need to hold Asia because you guys won't be checking unless you see my income.

Ah well, lesson learned.

Edited 5/31/2014 22:48:01