Life In 19x19

No worries perceval ... I still haven't submitted any code that takes time remaining into account ... in fact, my bot is the result of the Ants Tutorial in Python.

I should really get working on this. I have an idea of how I want to tackle the challenge, but I'm sure there are plenty of holes and bumps to overcome.

daniel_the_smith wrote:So far I spent most of my time writing awesome pathfinding. All my current bot does is pathfind for all my ants for all food, unexplored areas, and enemy hills.

Sounds like more of an HI challenge than an AI one...

Yeah, I'm always fuzzy on why a given thing counts as AI or not, but this is no more AI than programming chess, go or a war game (which is what it's most like).

I'm so terrible at this, my bot keeps timing out whenever I have about 40+ ants T_T
I can't find this information on the page but I speculate that I can only get Ilk type of visible Tile right? Maybe I should change my code to adapt to this >.<

If you use the java starter kit (which I assume you do, based on the class names), Water will be kept even if not visible anymore, but food and ants will not, if I remember well.

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

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

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.

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.

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.

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
We'll see.

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

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

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.

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

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 - 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 i'll deal with it when the rest is working.

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