Ants

daniel_the_smith · **#21**

Nice, lorill made the top hundred! The highest my "stupid" bot ever got to was #110. Still working on a not-so-stupid one... :twisted:

lorill · **#22**

daniel_the_smith wrote:

Nice, lorill made the top hundred! The highest my "stupid" bot ever got to was #110. Still working on a not-so-stupid one... :twisted:

I think i can still gain some rank with this version.

My food gathering looks good enough, but I really need to improve my local fighting for the next one.

Chew Terr · **#23**

lorill wrote:

My food gathering looks good enough, but I really need to improve my local fighting for the next one.

I recommend L&D.

flOvermind · **#24**

Yesterday I uploaded my "random movement" bot.

I hope I find some time to work on a version that does something that actually makes sense

This time the game doesn't seem easy at all. While the general strategy of this game seems rather easy (for humans at least), there are lots of hard algorithmic problems hidden in there. For example, identifying and blocking choke points seems like it would give a huge advantage. I often see bots sending lots of ants to a choke point, and neither player makes any progress. In these cases, if the bot would realize that it can e.g. indefinitely block the choke point with just 3 stationary ants, it could free up lots of ants to do something else...

Another interesting algorithmic problem is the multi-shortest-path, that is, I have ants at positions s_1,...,s_n and I want them at d_1,...,d_n as fast as possible. That's different from just n BFS searches, it could easily be that no ant takes the locally shortest destination, but the total time is best.

lorill · **#25**

Chew Terr wrote:

lorill wrote:

My food gathering looks good enough, but I really need to improve my local fighting for the next one.

I recommend L&D.

Actually, I was dreaming of using a montecarlo like method :batman:

We'll see.

AVAVT · **#26**

I'm dying a little bit inside seeing how my ants keep bumping into dead end and moving for/backward over and over again. And when I try to expand the path searching area my bot would time out >.<
This is my first time coding AI and the only thing I know is A* Algorithm suggested by the site.
Anyone kind enough to show me a good direction to follow? Even some reading material that I would find useful is good enough :bow:

daniel_the_smith · **#27**

I thought about doing local fights via MCTS, but I just don't think I'll be able to get enough playouts for it to be useful. So far my only real accomplishment is an algorithm to split up the board into local fights in < 1ms. :/

AVAVT, you can modify A* to start from multiple sources. Depending on what you need to accomplish, you can also do multiple dests if you drop the heuristic (i.e., switch back to Dijkstra).

Lurking on their IRC channel is a good way to pick up strategy tips.

There is some good info on A* here: http://theory.stanford.edu/~amitp/GameP ... stics.html

hyperpape · **#28**

For the time being, I'm giving up on a real pathfinding algorithm and just trying to implement some dumb hacks that will avoid the worst behavior. Might be able to put up a new bot tonight.

perceval · **#29**

AVAVT wrote:

I'm dying a little bit inside seeing how my ants keep bumping into dead end and moving for/backward over and over again. And when I try to expand the path searching area my bot would time out >.<
This is my first time coding AI and the only thing I know is A* Algorithm suggested by the site.
Anyone kind enough to show me a good direction to follow? Even some reading material that I would find useful is good enough :bow:

A* is supposed to be optimal. Its weird that it take so long, unless you try to go very very far are you sure you do not get a bug ? otherwise if you cant reach the location you need to explore more, head towards the closest unknown tile for example.

For myself i still cant submit or i'll die of shame but i begin to be happy with my data structs.

The basis is that all my path finding for food are done on a very small window (15 in mannathan dist by fly distance ie barely more than seeing distance) so usually there are few ants at that distance(i have code to keep ants appart and my A* are short as a result.
my reasoning is that if a food is farther chances are some other ant will get it before.
also i just send the closest ant (real dist not fly distance so i still do a multi source A * to determine that) because i suppose (but might be wrong) that the case where you have a lot of food and lot of ants close by is rare : with efficient bots most of the map should be covered quick and food harvested soon after appearance.

i also keep track of my ants long term goal and i recompute only if it disappears (in theory. right now if a food disappear the ant that goes to it just stop until its killed :sad:

- one of the reason i dont dare submit yet).

i am struggling with dealing with collisions: if 2 ants want to go the same spot you need to change one, but which and to where ? so each ant have goal and i compute the distance with all 4 movements (+staying put), and if 2 ants need to go to the same place i try the second move. i guess in combat situation where all ants are close it might become complicated because you risk a secondary collisions :scratch:

i'll deal with it when the rest is working.

perceval · **#30**

daniel_the_smith wrote:

There is some good info on A* here: http://theory.stanford.edu/~amitp/GameP ... stics.html

Thanks for the link, i was unaware of the tie breaking trick, i think it will do wonder to speed things up in a non maze situation

hyperpape · **#31**

Looked at those links, Daniel, and it seems that I should have done some searching. This isn't half as bad as I thought. Luckily, I enjoy the sensation of making it up as I go then finding out I was doing things badly.

AVAVT · **#32**

daniel_the_smith wrote:

I thought about doing local fights via MCTS, but I just don't think I'll be able to get enough playouts for it to be useful. So far my only real accomplishment is an algorithm to split up the board into local fights in < 1ms. :/

AVAVT, you can modify A* to start from multiple sources. Depending on what you need to accomplish, you can also do multiple dests if you drop the heuristic (i.e., switch back to Dijkstra).

Lurking on their IRC channel is a good way to pick up strategy tips.

There is some good info on A* here: http://theory.stanford.edu/~amitp/GameP ... stics.html

It's midnight here so I will check out your link tomorrow when I get up

For the time being I'll briefly describe my idea here, if my problem is answered already in the link please just tell me so

Code:

-- each turn
foodList = get all visible food;
for each ant{
   A* search from all food in foodList to the ant;
   if foodList not empty && a short enough path (10 steps away) is found{
      order the ant toward nearest food according to A*;
      remove the food from foodList; 
   }
   else if enemy hill found{
      order the ant toward the first hill
   }
   else{
      order the ant to explore map
   }
}

The problem with this is because every turn I have to do A* search from all available food to each ant (not to mention A* search from ant to hill and unexplored area), my bot is timed out every time I have 30+ ants

So I then record the job an ant was doing along with its current path and optimize/recalculate that path when needed. But then I face a millions null pointer exceptions (which is quite easily solved actually) and also a mysterious problem where my bot would send a huge cluster of ants toward a dead end and stack them there for the rest of the game or at least several hundreds turns. +_+

So... did you have any of these problems in the past?

daniel_the_smith · **#33**

AVAVT wrote:

Code:

-- each turn
foodList = get all visible food;
for each ant{
   A* search from all food in foodList to the ant;

The run time of that is O(ants * food). You won't be able to call A* that many times no matter how efficiently you wrote it. So... you'll have to find something more efficient. You can't really beat A* for 1 to 1 pathfinding, but for 1 to N, N to 1, or N to M problems you can find/invent another (related) algorithm. Ants to food is an N to M problem...

PS: nullpointers/other stuff: find a good debugger, step through, and figure out how what you told it to do differs from what you thought you told it to do!

perceval · **#34**

to avast: first, debug.
Then, you mention that you keep a path if is shorter than 10steps/ it means that the manattan dist between ant and food is less than 10 to begin with => so you should only do search for food close enough which typically should be few (2 -3 per ant maybe)

AVAVT · **#35**

I'm reading the Heuristics article right now, very informative, thanks daniel

According to your answers I guess what I'm currently doing is a N food to 1 ant search. It is quite easy since I just have to add all nearby foods into the open set as start points for the search. But I still can't get a good idea for N to M search, gotta think some more about it

Also, how exactly do you guys debug your bot? I don't know python and I never wrote a system using multiple languages (and debugging them) before

Don't know if I should use JUnit or study a Python debugger ~.~

@perceval: yeah I only check for food within the ant's vision (8 steps away), just didn't write it down yesterday (too sleepy >.<)

lorill · **#36**

daniel_the_smith wrote:

I thought about doing local fights via MCTS, but I just don't think I'll be able to get enough playouts for it to be useful. So far my only real accomplishment is an algorithm to split up the board into local fights in < 1ms. :/

I replaced my attack/retreat mechanism by a simple montecarlo simulation, the number of playouts depends on the time available and the number of local fights. I can do 60 playouts by millisecond on a slow computer. I don't use MCTS, since I look for only one move deep. We don't need to finish the game to score it as in go.

The results are quite encouraging, this is what I got playing against my current released bot, on all 1vs1 maps for 5 rounds:
draws: 14
wins: 14
losses: 2

The improvement should be slightly better if more players are involved.

It's not perfect yet, I don't use known movement from the current turn, so my playouts include some illegal moves (ants that have already moved). I'll try to improve this before releasing, but I'm already quite happy :tmbup:

daniel_the_smith · **#37**

lorill wrote:

I replaced my attack/retreat mechanism by a simple montecarlo simulation, the number of playouts depends on the time available and the number of local fights. I can do 60 playouts by millisecond on a slow computer. I don't use MCTS, since I look for only one move deep. We don't need to finish the game to score it as in go.

So basically, you try a bunch of random moves, score the position, and repeat? Hm. How does it do in mass battles?

lorill · **#38**

daniel_the_smith wrote:

So basically, you try a bunch of random moves, score the position, and repeat? Hm. How does it do in mass battles?

Yup, I do exactly this for all directions. This is the first game played with this version :
http://ants.fluxid.pl/replay.18826

Too bad I didn't manage to explore better to enter berserk-mode

daniel_the_smith · **#39**

lorill wrote:

daniel_the_smith wrote:

So basically, you try a bunch of random moves, score the position, and repeat? Hm. How does it do in mass battles?

Yup, I do exactly this for all directions. This is the first game played with this version :
http://ants.fluxid.pl/replay.18826

Too bad I didn't manage to explore better to enter berserk-mode

Not bad at all. But it doesn't seem quite as good as whatever Xathis is doing... :/

lorill · **#40**

daniel_the_smith wrote:

Not bad at all. But it doesn't seem quite as good as whatever Xathis is doing... :/

heh. I don't think I'll ever be the first bot

Well, that algorithm is good enough for me, fighting is not the weakest part of my games anymore. Version 19 was 86th when I uploaded the new v20. We'll see how it goes...

Ants

Who is online