I'm entering a fun tournament where you have to design the AI for a gold collecting pirate and you compete against other AI characters developed by other programmers. There is no prize and this is not for any class - just for fun. The rules are very simple: 1) The map is a simple overhead tile map (where each tile is either a floor or a wall). 2) Players spawn in random locations (up to 6 other AI players are in the map). 2) You know the map and the position of all the players and gold. 3) There are a few "boat" powerups on the map which let you steal other players gold. 4) Each iteration, you need to compute your next move. You have ~10 seconds to compute the move. Can you give me some ideas on how you would implement the AI for such a game? It's been a few years since I took a course on AI. I remember minimax, but I don't think we ever applied it to more than two players. I was thinking of using a genetic algorithm and computing the best possible next move on every iteration. So I guess the encoding would be something like: U D L R L R U (where U = Up, D = Down, L = Left, R = Right) where it represented the order of moves, ie Up, Down, Left Right, Left, Right, Up and it computes the amount of total gold collected using those moves. But it seems like it would try alot of impossible moves since the pirate cannot move in all directions at will - he'll run into a bunch of walls. I guess it's kind of like the traveling salesman problem except that the pirate does not have to return to the starting point and nodes (x,y positions) can be visited more than once. The pirate should simply visit the most amount of gold in the shortest amount of moves. Going in this direction would not account for other players though. So I may move into another pirate's territory only to find out he already took the gold. Any ideas would be appreciated. Thanks!

Genetic algorithms and neural networks are not the be-all and the end-all of artificial intelligence. They're very little of it, actually. There's a few things they're good for and otherwise they mostly suck. When there are domain-specific techniques (such as minimax) which can be applied, they WILL work better than GA, NN, and other such "trendy" catchalls of AI.

Thanks. I'm most familiar with GA's as I have used them in general programming several times, which is why I was leaning towards them. Can minimax be applied to a game with more than two opponents though? The algorithm would have to account for the 5 other AI players collecting gold.

It seems like the heuristic would still require some path finding, ie:

h = tileHasGold? + distance_to_nearest_gold + gold_density_around_that_gold

Thanks wodinoneeye. The map is simple, ~20x20 with little open areas.

The only combat is the boat powerup which takes other pirate's gold and disables them for N moves. You will know which pirates have powerups, etc.

Extrarius, that sounds like a really good solution. It doesn't sound too complicated for my novice AI skills and it seems to make perfect sense. I'll let you know how it goes :)

I'd adopt the strategy of seeking out as many 'boat' powerups as possible
then spend my time stealing gold from other agents

-who cares who wins the game if you can win the Meta-game
(as you might imagine, I get flamed a lot when I play Halo2 XBL)

If the number of tiles with events are small, the approximation that it's always better to move to a target, rather than standing still, you could do a Minimax search through the order of possible targets and thereby reduce the space significantly.
Basically:
Player 1: Move to A, B, C, ...
Player 2: Move to A, B, C, ...
Since you know the distance for each player to a target, you may from this determine who will be able to reach it first and (ignoring a few details), could then abort the actions that will clearly fail and order the actions by when they may first move again.
For instance
(*)Player 1 (time 0, 0 gold): Move to A (time 3, min inf), B (time 1, min inf), C (time 5, min inf)
Branch A, new time 3
(**)Player 2 (time 0, 0 gold): Move to A (time 2, min 3 (player 1)), B (time 4, min inf), C (time 8, min inf)
Branch A - greater than current min and pop player 1's time.
(***) Player 1 (time 0, 0 gold): Move to B (time 1, min inf), C (time 5, min inf) (A not available, cur. time + move time > min time).
Branch B
Player 1 (time 1, 1 gold): Move to C (time 5, min inf)
Branch C
Player 2 (time 2, 1 gold): No actions (Time to C is 8, 2 already used and Player 1 will be there at 1 + 5).
Player 1 steals gold, result 3 vs. 0 gold.

That would be one branch, now the execution should return to (***), after covering those, (**), et.c. This isn't how minimax works, easier to show the thought this way. If the number of targets are small, an exhaustive search will be possible, actually, if the number of targets are less than 11 or so you can do an exhaustive search even without alpha-beta, with alpha-beta you might be able to move it as far as to 22 (15 more realistic). My guess is that it would do quite well up to about a 100 targets.
If you merely precompute the distances between the initial position of the players and the possible targets and each length of each target pair (i.e. from one target to another), each move update will take constant time. Since you can use lazy eval this should do very well.
It does ignore certain complexities but unless the opponents are highly sophisticated and small differences does a lot, and the levels aren't designed specifically to beat it, I think it should do quite well.

Extrarius, I believe I implemented your solution correctly. However, it's not giving the results I was hoping for. Basically, the tile with the lowest cost is the tile that's in the most dense area. It may not necesarily contain gold. (Note: Right now I'm not accounting for "tile distance from opponent" and "tile distance from powerup").

Now that I actually stopped programming and started thinking about it, perhaps my problem is I'm taking the absolute lowest cost tile where I should be iterating over a list of just gold and powerup tiles. That would definately speed up my algorithm (right now it takes 64-125ms and it calculates A* 1+NUM_GOLD tiles (5 times in the screenshot below) for each non-wall-tile). I guess that's not the solution you proposed though... Actually, I'm not even sure what an influence map is :) I quickly wikipediaed it and it looks like, for each tile, I should be modifying the cost of that tile based on the cost of its neighborgh tiles.. I'm not doing anything like that. Should I be?

Another problem is... I'm not sure how to modify my A* implementation to be weighted. For example, in the screenshot it seems like my pirate should veer off the path and obtain the gold in the center of the map (cost 62). After picking up the gold, it should backtrack to the main route and continue going to the north gold. Can A* revisit nodes? Any links to articles on weighted A* algorithms?

My idea to implement weighting was just to reduce the cost of the tile if that tile contains gold. But if I do that, couldn't my heuristic (which is the manhattan method) overestimate the cost and therefore be inadmissable?

Here's a screenshot (sorry it's very large if I make it any smaller the text will be unreadable... only 20k). The yellow tile is the start node (current position). The top number is the total cost. The bottom numbers are: distance-from-start-tile and distance-from-tile-to-each-gold. The dark tiles represent the non-weighted A* path to the lowest cost tile.