[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/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 - Effective AI techniques

It is currently Sat Jan 20, 2018 1:08 pm Advanced search

Effective AI techniques

Share and discuss ideas for your entries here.

Effective AI techniques

Postby zulkose » Fri Oct 08, 2010 2:20 am

I'm curious what people are finding effective in regard to some of the "standard AI techniques" such as minimax, genetic algorithms, etc. Granted I am likely not finding much use for a lot of them due to my limited AI background, but I can imagine using genetic algorithms to grow a decent attacking function could be pretty effective. I'm sitting around 100 right now but the extent of my bot is just effectively determining when fleets will hit my planets and how much I will have left over to attack with after defending, at which point I look for higher growth planets and "sniping" opportunities. Has anyone had any luck with particular algorithms?
zulkose
Cadet
 
Posts: 2
Joined: Tue Oct 05, 2010 9:22 pm

Re: Effective AI techniques

Postby sigh » Fri Oct 08, 2010 5:55 am

I've found it hard to apply the "standard AI techniques", although I am constantly thinking about it. At the moment my bot is bunch of heuristics.

For example, applying minimax is not trivial because of the huge branching factor requiring you to do a large amount of pruning for the search to even be feasible. Thus you need to get an intuition for what heuristics work for the game to get any sort of decent implementation. On top of that it might not pan out because the assumption that your opponent knows your moves might be too pessimistic.

However, simpler sub-problems can be solved (such as modeling ship allocation as the knapsack problem). I think McLeopold tried generalising this to the whole game in one of his bots and it did well on the tcp server, but certainly no where near his best bot.

From chatting in the channel I think this is the same for a lot of people, even people near the top (although, obviously I can't speak for everyone). I know that people are trying to apply the standard techniques; and now that people are getting more familiar with that works and what doesn't I hope these ideas will start panning out :).
sigh
Cadet
 
Posts: 3
Joined: Tue Sep 07, 2010 1:10 am

Re: Effective AI techniques

Postby yasith » Sat Oct 09, 2010 12:10 pm

Just a random thought;

Maybe there is an effective way to apply the minimax algorithm. You select about 5 best moves, according to some scoring system, so the branching would be limited. And (I know this is far from perfect), but you can run an iterative deepening DFS, to search through the tree, while using time as the limiting factor. I haven't implemented this yet. But maybe this is doable ? Any ideas ?
yasith
Cadet
 
Posts: 5
Joined: Tue Sep 28, 2010 9:44 am

Re: Effective AI techniques

Postby P_Hansson » Sun Oct 10, 2010 1:21 am

Explain how you intend to play efficiently with just five moves. :!: Check the top bots and their supply lines for instance.

Furthermore, in chess you are just selecting one move per turn. In this game, you are selecting several. So in effect, you have the options: SEND_FLEET(src, dest, num) and END_TURN available. Even with a hard cap of "just" five moves per turn you have branching factor^5 because doing a SEND_FLEET introduces a new node.

At least, this is my understanding of it.

I did consider minimax where I'd generate a few different set of orders based on various strategies for each turn (thus reducing the branching factor per turn to a sane number), but I think that falls flat due to how a difference of a single ship can completely change the outcome of a battle. Thus, because realistically the opponent will never take exactly the same set of moves the search quickly will quickly diverge from reality (quicker than it would with less drastic battle outcomes).
P_Hansson
Captain
 
Posts: 27
Joined: Thu Oct 07, 2010 2:12 am

Re: Effective AI techniques

Postby yasith » Sun Oct 10, 2010 4:29 pm

Yes, true. That would limit the usability of the algorithm very much. I think I overlooked that factor. But I can't think of any other ways to successfully implement a minimax on this, other than by limiting the number of branches.
yasith
Cadet
 
Posts: 5
Joined: Tue Sep 28, 2010 9:44 am

Re: Effective AI techniques

Postby iouri_ » Sun Oct 10, 2010 6:33 pm

Yeah, I'd say that it's hard to apply minimax here because there are so many possible moves to choose from, and anything like genetic algorithms or simulated annealing comes up with a solution at a glacial place and will certainly fail here.

I found that so far the best thing to start with is to make sure that the ships are allocated most efficiently towards capturing planets. Specifically, pick the invading fleet combinations that produce most return in ships over the next n turns (where n is selected by tweaking; my number is pretty arbitrary at the moment). That put me into top 100; everything else was just some extra magic ingredients (more obvious of which is using supply lines).
iouri_
Brigadier-General
 
Posts: 105
Joined: Thu Feb 11, 2010 4:16 pm
Location: Toronto, Canada

Re: Effective AI techniques

Postby jmange » Mon Oct 11, 2010 4:13 pm

jmange
Cadet
 
Posts: 5
Joined: Tue Sep 28, 2010 8:02 pm

Re: Effective AI techniques

Postby P_Hansson » Tue Oct 12, 2010 5:45 am

P_Hansson
Captain
 
Posts: 27
Joined: Thu Oct 07, 2010 2:12 am

Re: Effective AI techniques

Postby delt0r » Tue Oct 12, 2010 11:29 am

I think its important to realize that a "collection of strategy heuristics" closely matches how people often solve problems. Its not elegant mathematically, but it does work in the absence of "boring" searches. ;)
It was like that when I got here.
User avatar
delt0r
Colonel
 
Posts: 89
Joined: Sun Sep 12, 2010 8:03 am

Re: Effective AI techniques

Postby Demerzel » Thu Oct 21, 2010 3:40 pm

Demerzel
Colonel
 
Posts: 72
Joined: Sat Oct 02, 2010 6:06 am
Location: themendios at gee mail

Next

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron