[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4586: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4588: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4589: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4590: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
AI Challenge Forums • View topic - A simple approach to combat

It is currently Tue Sep 26, 2017 5:38 am Advanced search

A simple approach to combat

Share and discuss ideas for your entries here.

Re: A simple approach to combat

Postby erdman » Fri Dec 16, 2011 10:53 pm

erdman
Major
 
Posts: 34
Joined: Thu Oct 27, 2011 12:52 am

Re: A simple approach to combat

Postby stupidquestions » Fri Dec 16, 2011 11:03 pm

I think I understand the concept, but... How exactly do you figure out which tiles on the map some ant can attack after one move? I mean, I have some ideas, but I'm kinda hoping there's a *simple* way to do that.
stupidquestions
Captain
 
Posts: 23
Joined: Wed Nov 16, 2011 1:02 pm

Re: A simple approach to combat

Postby codetiger » Fri Dec 16, 2011 11:33 pm


codetiger
Lieutenant-Colonel
 
Posts: 47
Joined: Sun Aug 21, 2011 4:47 am

Re: A simple approach to combat

Postby stupidquestions » Fri Dec 16, 2011 11:53 pm

Oh, so you store THAT? Or do you store the union of combat zones for those 5 cells (that's how I originally understood the idea)?
stupidquestions
Captain
 
Posts: 23
Joined: Wed Nov 16, 2011 1:02 pm

Re: A simple approach to combat

Postby codetiger » Sat Dec 17, 2011 12:29 am


codetiger
Lieutenant-Colonel
 
Posts: 47
Joined: Sun Aug 21, 2011 4:47 am

Re: A simple approach to combat

Postby errbeg » Sat Dec 17, 2011 12:56 am

errbeg
Cadet
 
Posts: 2
Joined: Fri Dec 02, 2011 10:54 am

Re: A simple approach to combat

Postby codetiger » Sat Dec 17, 2011 1:53 am


codetiger
Lieutenant-Colonel
 
Posts: 47
Joined: Sun Aug 21, 2011 4:47 am

Re: A simple approach to combat

Postby erdman » Mon Dec 19, 2011 8:57 pm

Memetix:

Enjoyed reading more details from your code write-up on your homepage (http://www.blackmoor.org.uk/AI.htm). I also used a a tile-scoring system that required maximizing total score across all ant-destination pairs, while not allowing ants to collide.

This is an example of the assignment problem: http://en.wikipedia.org/wiki/Assignment_problem

An exact optimal solution to the assignment problem can be found in O(n^3) with the Hungarian algorithm (which I used in my bot, but it turns out to too demanding with 150+ ants for a language as slow as Python or even pypy, but may be fine in compiled languages -- but anyway my bot is susceptible to timing out as a result). Googling will also find some faster, approximation algorithms; I considered the auction algorithm and "deep greedy switching". Finally, there is simply plain-old greedy algo, which most people probably used, but I was finding the number of colliding ants (when in tightly packed space) to be too onerous -- in fact, when I corrected for collisions, my performance improved materially.

Anyway, the heuristics the you describe for solving the problem were pretty bright, and I never considered a solution of that type. I think I was mentally boxed-in, because I had prior experience with the Hungarian algo. I'd be curious to know how your heuristics compared to optimal solutions, if you ever studied that.

Your writeup is really enjoyable to read -- I had many "oh!!" moments, where a solution you describe seems so obvious after you tell it to me that I feel I should have been able to think of it myself -- but I didn't. So, thanks for the write-up. Since I won't be competitive with the very top bots -- I'm rooting for you.
erdman
Major
 
Posts: 34
Joined: Thu Oct 27, 2011 12:52 am

Good enough

Postby Memetix » Mon Dec 19, 2011 10:46 pm

Thanks for your kind words Erdman - I enjoyed writing it.

I didn't know how to create an optimum solution for the ant moves. I did look up constraint optimisation on wikipedia but got very confused, very quickly.
Anyway, I like to solve things my own way, even if it involves reinventing the wheel. For me that was where I had the most fun. I'm afraid I didn't consider comparing my results with the optimum solution so I have no statistics to share with you.

My combat code was an approximation of what "could" happen (it turns out it performs better against the top bots as they tend to avoid the 1:1 swaps that my solution sometimes commits to). The results were good enough.
My exploration code was also good enough. I knew that sometimes 2 ants would go for the same food if they were the same distance away but I wanted the code to stay simple and to not code any special cases.
The issue order code, though not perfect was again good enough once I implemented the "push" concept.

I guess my overall approach was to keep it simple enough for me to understand and therefore simple enough to debug.
Memetix
Major
 
Posts: 39
Joined: Tue Nov 08, 2011 3:53 pm

Re: A simple approach to combat

Postby Nefbrethilion » Thu Dec 22, 2011 9:39 pm

As a "software engineer", I'm also impressed by your out-of-the-box thinking, Memetix... you leave me stunned and inspired! :-)

And a big thanks for sharing your combat strategy. I had been tinkering with something like that but couldn't get it to work 100% correctly. You proved/showed that it's not needed to have a perfect combat solution!
Nefbrethilion
Cadet
 
Posts: 7
Joined: Sun Oct 30, 2011 10:16 pm

Previous

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron