Ignoring path finding and using collaborative diffusion

[Darhuuk]

One more thing you might do to speed up diffusion calculations, is switching from floating to fixed point calculations. I can imagine that this might require quite a bit of debugging to find the sweet spot for the decimal point though, so I wouldn't recommend it unless you have extensively profiled your code, it's still too slow and you really can't find any other way of speeding it up.

For some tips/links to useful libraries, I suggest taking a lot on Stack Overflow. For example, here: http://stackoverflow.com/questions/2945 ... nt-library (note: this is all C++ based, since that's what I'm working in).

[mac]

First of all, you should be able to have a minimum of 100 diffusions a turn with no problem (I can do about ~300 although only do 200 to make sure I don't time out). If you're doing multiple maps for different scents, thats~20-30 diffusions per map. If you're not this efficient, figure out a better way to do it.

C'mon... the guy is asking for help, not for being bashed.

Here's a pointer: lists in python are heavy objects with a lot of overhead. All you want here is a data structure that is "barebone" and fast to be handled. The most common one for these kind of manipulations is numpy. Of course the specific implementation is where each of us is in competition, so I won't provide details either, but I can confirm that on a 200x200, map I get around 300 diffusion steps in ~400ms.

HTH!

[Darhuuk]

C'mon... the guy is asking for help, not for being bashed.

Actually, I had given up on improving my diffusion function, but reading about the speeds which ought to be possible, forced me to take another look at it and I found many places where lots of improvement was possible. So thank you for that .

[blue_iris]

People with slow languages might try using algorithms that approximate the effect of diffusion, but run much faster. I think that's what icefox was getting at in his message below.

(Obviously you have to do "something" to get the scent to diffuse in all directions, not just to the right. But that "something" doesn't have to be mathematically correct, it can just be a big hack.)

The benefit of this approach is that's it's O(r*c), so you can afford to do it every turn.

Lets say I have a 1d "world" and X means food and the numbers are the current food scent.

00X000

A simple example would be if i diffuse from 0 to n in the array. My world would look like the following at each step:

00X000
00X000
00X600
00X630
00X631

With a single pass through this world front to back everything to the right of the food will get a diffused food scent. After this diffusion any ant to the right would be able to find the food. On every turn I could reset the food diffused values back to 0 so only brand new food would be discovered by the ants. But for other things like enemy ants or areas to explore you might not want to reset it back to 0.

[Darhuuk]

<snip>
A simple example would be if i diffuse from 0 to n in the array. My world would look like the following at each step:

00X000
00X000
00X600
00X630
00X631

With a single pass through this world front to back everything to the right of the food will get a diffused food scent. After this diffusion any ant to the right would be able to find the food. On every turn I could reset the food diffused values back to 0 so only brand new food would be discovered by the ants. But for other things like enemy ants or areas to explore you might not want to reset it back to 0.

What you are suggesting is not diffusion and will cause your ants to do strange/very non-optimal movements. Furthermore, it will work very badly in mazes. And you would need to diffuse from right -> left, top -> bottom & bottom-> top as well to get at least a reasonably working potential field in the presence of water. Plus, water will stop the "fake" diffusion anyway, so you're going to need multiple passes over your grid no matter what.

The key difference between real diffusion and what you are suggesting is that with your approach, you store new values in the "old" grid. What you are supposed to do is create an empty grid, calculate the new value for each grid position using values from the old grid and then overwrite the old grid with the new one.

Of course, using the real diffusion algorithm after one pass your potentials will only be spread on 1 square, so you need multiple passes or your ants wont see any potential field changes until long after the events causing them have actually happened.

But, as stated above: even in Python it is possible to get 200-300 diffusion runs over a 200*200 grid without timeouts, so there shouldn't be any reason to implement an approximation of the real diffusion algorithm.

[codetiger]

I am using python to code my bot and just tuned my diffusion algo to some extend that I think should be optimal. I diffuse all foods, hills, exploring seeds etc on to the same diffusion map for every turn. Am running through every cell in the map to find the concentration of the scent. I've just completed optimizing my code to run without timeouts. To my surprise, even when I run with turn time settings with 500ms my bot performs well on most of the maps except large maps like 200x200. So I would guess my diffusion map only takes 200ms to 450ms.

[Darhuuk]

Ok, again, for those strugling with the speed of there diffusion function. I just applied my own tips and got a 10x speedup in diffusion calculations:

• Before: 36 diffusions/round, total time: 50-350 ms (mostly 200-350ms) (=> can do +-50 diffusions per round in worst case)
• After: 82 diffusions/round, total time: 45-70 ms (=> can do +-600 diffusions per round in the worst case)

Recap of what I did:

• Remove all ifs, function calls, ... from your inner diffusion. E.g.: if you calculate something different depending on a boolean (if one of your ants is blocking the scent for example), store it as an integer instead and do:
  
  

  Code: Select all

  result = ((1 - myBool) * someConstant + myBool * someOtherConstant) * value



• Optimize expressions like the one above, which could also have been written as:
  
  

  Code: Select all

  result = (1 - myBool) * someConstant * value + myBool * someOtherConstant * value

  
  However, as you can see, that expression as 4 multiplications, while the one above as only 3. Maybe your compiler will optimize it anyway, maybe it won't. Why take chances? It's trivial to rewrite the expression the "good" way.


• Precalculate all values that won't change. Storage is cheap, calculation time isn't.
  
  Two examples:
  1. Position of your ants: if you have a list of all of your ants and the "myBool" in the above example tells you if there is an ant at a location or not, then don't use a function call to find out. During all diffusion calculations in the same turn, the ant will stay in the same place and thus the bool will always have the same value for a given location. So create a 2D array and for every single location, set it to 0 or 1 depending on if there's an ant there or not.
  
  
  2. Potential sources: keep a list of fixed potential values (e.g. food location = 1) and set those locations back to their value after each diffusion run. Don't do this in your inner diffusion loop by calling some function, it will slow down the whole thing.

So, after you do all that, you should have some diffusion function like:

Code: Select all

precalcAllFixedThings();

for (int i = 0; i < numDiffusionSteps; ++i)
{
  newFieldValues = Grid(rows, cols); // All entries should be 0 after initialization.
  for (int row = 0; row < rows; ++row)
  {
    for (int col = 0; col < cols; ++col)
    {
      newFieldValues(row, col) = oldFieldValues(row, col) + diffusionCoef * (sum(oldFieldValues(neighborSquares)) - 4 * oldFieldValues(row, col)
    }
  }

  setFixedPotentialsToWhatTheyShouldBe();
}

That's it, no branches/function calls/... anywhere in the main diffusion loop. Do that and your diffusion will be lightning fast.

P.S.: I did not (yet) bother with fixed point implementations. The chance is pretty big that that might actually slow down the calculations on a modern PC.

[bluegaspode]

After: 82 diffusions/round, total time: 45-70 ms (=> can do +-600 diffusions per round in the worst case)

Just to get a better feeling:

what type of computer?
which language?
size of map?
how much of the map is visible (if this influences the calculations)?

[Darhuuk]

Just to get a better feeling:

what type of computer?
which language?
size of map?
how much of the map is visible (if this influences the calculations)?

• PC: Intel Core2 Duo E7400 (2.80GHz), 4 Gb RAM, Ubuntu 11.04 64-bit (hardware is 3 years old at least, I think)
  
• Language: C++ (using C++0x features like hash maps, but you could use the Boost libraries)
  
• Size of map: that example was on a 60 x 90 map, of course the time for a diffusion is linearly dependent on the size of the map, so the time for the same amount of diffusions on a 200 x 200 map would be +-7.5 times longer. For most of the maps my bot won't timeout, but the new cell_maze maps are kind of a problem, since they're huge (I've had a few timeouts), so now I just added a while loop that will diffuse as long as I have time left over or I reach a maximum number of diffusions.
  
• Visibility: My algorithm is indifferent to how much of the map is visible. I don't see the advantage, because if it can't handle a completely visible map in the allowed time, the bot will time out sooner or later anyway, doesn't matter if my bot can play perfectly on that map while only half of it is visible.

[bluegaspode]

I'm asking because the whole evening I started to optimize as well, because I had timeouts on the new cell_maze maps as well.

Wrote a testcase for myself:
200*200map (everything visible - so a full diffusion) with
100 enemy ants
100 friendly ants
100 food tiles

I'm getting 200diffusion-rounds in 330ms now.
(Unoptimized I took 1100ms)

Using Java, on a MacBookPro (2,4Ghz, Intel Core i5)