Ignoring path finding and using collaborative diffusion

[Darhuuk]

For those of you who are using diffusion for most of the stuff but something else for battle, locally: How do you bring the two together? When, exactly, do your ants switch to "battle mode"?

Ants can only enter battle when within 4 squares of an enemy ant. I still use my diffusion fields in combat mode, I move to the nearest square with highest potential that is still marked as accessible by my combat manager class.

[bluegaspode]

If there are within attack range, they switch to the combat code.
Sometime I just mark one direction as "don't go there, you might die" which still leaves three fields to choose by diffusion values.

Sometimes the battle code also takes over completely.

[tmseiler]

I put the entirety of my combat code inside of my move_to_goal() method. I'm using field-based combat, so it's kind of like another type of hill climbing that isn't diffused -- just safe or unsafe when attempting to move to a particular scent.

[pkmiec]

I used collaborative diffusion in my bot as well. Even though I'm happy with the results, I have some questions on whether I was doing things correctly.

I had two double arrays (for each type of scent, I had four scents in my bot: defend, explore, enemy_hills, and enemy_ants),
double[][] values - initialized to 0 at start of game
boolean[][] sources - initialized to false at start of each turn

On each turn, I place values in certain cells depending on state of the game (i.e. 100.0 for unexplored square) and at the same time I set the corresponding source boolean to true. I then proceed to diffuse in the following fashion,

Code: Select all

double tmpValues[][];

for (int row = 0; row < maxRows; row++) {
  for (int col = 0; col < maxCols; col++) {
    next if water[row][col]
    if sources[row][col] {
      tmpValues[row][col] = values[row][col]
    } else {
      tmpValues[row][col] = sum of values of neighbors(row,col) / number of neighbors(row,col)
    }
  }
}

values = tmpValues


When looking at neighbors, I would exclude water and thus a cell could have 4, 3, 2, 1, and in theory 0 neighbors. But for demonstration here, that's not important.

So starting with all 0 and placing a single 100 source at the center,

Code: Select all

   0    0    0    0    0
   0    0    0    0    0
   0    0  100    0    0
   0    0    0    0    0
   0    0    0    0    0

and after one step of diffusion, I would get,

Code: Select all

   0    0    0    0    0
   0    0   25    0    0
   0   25  100   25    0
   0    0   25    0    0   
   0    0    0    0    0

and after another step of diffusion, I would get,

Code: Select all

   0    0 6.25    0    0
   0 12.5   25 12.5    0
6.25   25  100   25 6.25
   0 12.5   25 12.5    0
   0    0 6.25    0    0

As you can see the numbers drop off very very fast (even though next iteration the 25 will actually become 12.5 + 100 + 12.5 + 6.25 / 4). In general, it takes many iteration to spread source information around. This becomes particularly a problem when trying to spread information about an ant hill far far away from that ant hill. In fact, I could not seem to iterate enough even in few turns to spread this information far and strongly enough. Eventually, I ended up using the following diffusion for ant hills,

Code: Select all

tmpValue[row][col] = max of values of neighbors(row,col) * decay factor

with high decay factor somewhere in the 0.95 - 0.99 range, the spread is very fast even over large maps.

I am wondering whether my diffusion function (average of 4 neighbors) was flawed? or are these normal problems of diffusion?

[codetiger]

Code: Select all

tmpValue[row][col] = max of values of neighbors(row,col) * decay factor

with high decay factor somewhere in the 0.95 - 0.99 range, the spread is very fast even over large maps.

This is exactly what I did to overcome the same problem. However, after few versions of improvement, I changed it to

Code: Select all

tmpValue[row][col] = max of values of neighbors(row,col) - 1

so the value also says the distance to the source. And I used 3 maps for prioritizing the sources.

Note: Food will travel only until it reaches the first ant. Otherwise, you will see all ants moving towards the same food.

[tmseiler]

I'd say you're definitely making a good hill to climb, but it doesn't look like it's actually diffusing because you're never subtracting or rounding out the difference between squares. When I first started, my formula was very additive. It made good hills, but it also resulted in values getting way too large ("smelly") or decaying too fast like you're showing there. When I finally fixed it, the results were very nice.

Here's the source to my diffusion bot, which has wound up around rank 100:

https://bitbucket.org/tmseiler/ants/src

[utoxin]

Here's my bot, which uses this methodology for everything it does.

https://github.com/utoxin/AIChallenge-Ants

It's currently doing decently in the finals, hovering around 500 rank at the moment. Considering it's my first Python code, and my first AI project, I'm quite pleased.

[katebus]

@tmseiler, well that code convinced me - I am starting to learn python today, it looks good, as a code and as a language. At least I can understand parts of it, which is not always easy.

[flux_w42]

My bot is using collaborative diffusion, the source can be found here.
Here are some gifs that shows an example of the diffusion maps:

Coverage:


Enemies:


Food:


Scouting:


And the mix of the previous maps. This is the actual map that's used for my ants if they're not raiding a hill

[zaphod]

Code: Select all

tmpValue[row][col] = max of values of neighbors(row,col) * decay factor

with high decay factor somewhere in the 0.95 - 0.99 range, the spread is very fast even over large maps.

This is exactly what I did to overcome the same problem. However, after few versions of improvement, I changed it to

Code: Select all

tmpValue[row][col] = max of values of neighbors(row,col) - 1

so the value also says the distance to the source. And I used 3 maps for prioritizing the sources.

Note: Food will travel only until it reaches the first ant. Otherwise, you will see all ants moving towards the same food.

I have used the same (max(neighbors) - 1) function. I thought it was a standard MDP. As an AI noob, I am not sure what the difference is between an MDP or Q learning for that matter and diffusion! Can somebody clear my confusion?