I'm familiar with ant colony optimization algorythms (i studied optimization algorythms a few years ago when i was taking my masters). i think it will be overkill for this specific scenario of finding the shortest path though. A more simple A* path finding algorythm is easier to implement and gives you what you want (the shortest path). Ant colony optimization would have big advantages to calculate new routes when something is blocked (it's used heavily in network traffic balancing for example) i guess in warlight this could be when your opponent has a large enough stack protecting a key area, which might be better to go around it instead of going through it, but in this particular map it would backfire on you, the opponent would use the stack to keep expanding against you while you're wasting armies attacking neutrals trying to flank him. so, no, i think ant colony would not be your best option.
I recently implemented a simpler version of a star on my bot. I use it to figure out where to expand into next (following the list of suspected places the enemy started in), and i only apply it when there is no enemy in sight. the c# code is online (like the rest of my bot, which is all open source (
https://github.com/psenough/warlight_ai_challenge), even though it's becoming an ugly spaghetti code from hell after all the hacks i been throwing at it trying to debug different problems).
Anyways, the code i implemented attempts to figure out what bordering neutral to attack next on the shortest way to unknown territory with id dest. It's in C#:
public int FindNextStep(int dest)
{
// reset
foreach (Region reg in fullMap.regions)
{
reg.tempSortValue = 0;
}
// initial list
List<Region> list = new List<Region>();
foreach (Region reg in FullMap.GetRegion(dest).Neighbors)
{
list.Add(reg);
}
// first iteration
int it = 1;
while ( list.Count > 0 )
{
List<Region> newlist = new List<Region>();
foreach (Region testRegion in list)
{
Region reg = fullMap.GetRegion(testRegion.Id);
if (reg.OwnedByPlayer(myName))
{
// found home, now backtrack to find which neighbour to attack, should be the one with lowest it that is not 0
int lowest = 50;
int index = -1;
foreach (Region neigh in reg.Neighbors)
{
Region regn = fullMap.GetRegion(neigh.Id);
if ((regn.tempSortValue < lowest) && (regn.tempSortValue != 0)) index = regn.Id;
}
return index;
}
else
{
// havent found home yet, prepare next iteration
if (reg.tempSortValue == 0)
{
reg.tempSortValue = it;
foreach(Region neigh in reg.Neighbors) {
newlist.Add(neigh);
}
}
}
}
list.Clear();
foreach (Region nl in newlist)
{
list.Add(nl);
}
it++;
}
return -1; // failed to find home
}
It's giving each region of the map an initial temp value of 0, then starting from the target is checks all the neighbours to see if any of them belongs to us, if it doesn't, it stores all the neighbours of that region (disregarding the ones that have already been checked) and proceeds to the next iteration. Until it either finds something or has run out of areas to check.
I haven't tested this algorythm properly in the wild yet with the C# bug affecting the server and all. But i think it was working (can't remember for sure anymore to tell you the truth). I recall i wanted to check it working on real games, but then never managed to get around to it, not sure if it was to check how well it did or if it was working at all.
Anyways, if it's of any use to anyone, knock yourself out porting it to java or whatever you're using.
Edited 5/1/2014 15:59:23
