Ants

[hyperpape]

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]

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: Select all

-- 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]

Code: Select all

-- 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]

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]

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]

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

[daniel_the_smith]

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]

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]

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]

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...

[perceval]

still no submission from me... i am a bit stuck on combat. I should submit anyway to see the issues i got with my current code i guess.

But i found a nifty algo for exploring / harvesting:
I put a superlattice on the grid, each 10 square, and i treat my ants as particules on a hubbard model, and i move them by monte carlo :
a "move" means assigning one of the supersite as a goal for a given ant: it then go there by shortest path
i can direct them away from my hills byadding a long range repulsive potential (sort of like an anderson impurity model), and an on site repulsion to keep them spread out, i can also put an attractive potential near ennemy hills etc.. When a ant is idle, i just attach it to he nearest supersite and let it diffuse ,so new ants naturally starts to drift away from the hill.

: in the end the code is very simple,flexible and without corner case.

i cache all ancestor graph on each supersite so path computaion is cheap

My previous code was complicated and full of weird behavior in some edge cases.

Now back to combat , monte carlo as lorill did sounds nice but i am not sure how to start. i ll stick to rul base for now i guess
i ll try to submit this WE

[Dusk Eagle]

I just wanted to throw out there that I'm also working on this in between schoolwork. I don't have anything ready to submit yet, but it's getting there.

My profile (like I said, nothing to see yet): http://aichallenge.org/profile.php?user=7714

[daniel_the_smith]

@perceval: Sounds cool!

@Dusk Eagle: Added you to my first post.

@everyone, Here's a cool image I made while writing my distance map making code.

[phrax]

This is me:

http://aichallenge.org/profile.php?user=2349

[Dusk Eagle]

Wow. Good job so far phrax! (Currently ranked 31st overall).