gold collecting pirate AI

This topic is 4179 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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!

Share on other sites
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.

Share on other sites

1) a pathfinder to simplify issuing orders (the function would return a path and the expected travel time) A* or a simpler pathfinder (if the maps are simple).

2) an analysis system using the pathfinder to estimate whether targets are closer to the pirate or the others (to evaluate/pick what 'best' targets are)

3) another analysis to try to predict which targets the opponents are going to (watch for a trend that indicates which target).

Depending if their are other factors like combat, and what the ability modifiers
do and if one pirate can see that the power up is being used (can probably watch the other pirates grab them, so would then be able to adjust the predictions).

Powerups would be targets just like gold and high level strategies would be built
around how they work (grab them on opportunity/deny them to enemy/enhancement as a goal etc...).

For a full blown system a planner could be used to evaluate and enact fairly complex tactics (with constant reevaluation cycles to adapt to a changing sitiation). Depending on the game mechanics the estimations for likelyhood of success might be greatest for actions that have the greatest flexibility in the games changing situations. Finite state machines are used to impliment chosen 'solutions'.

Without more details of how complex the game mechanics are I cant see what might be done.

Share on other sites
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

Share on other sites
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.

Share on other sites
Quote:
 Original post by TheUltimatePirateThanks 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.
With maps that small, it seems like you could easily compute several complete influence maps on every turn. For example, on one map, give each tile a value based on the distance to each gold coin (thus lower numbers have more nearby gold coins), then on another map give each tile a value based on the distance to each opponent, and another give each tile a value based on the distance to powerups, and finally make a map with the movement distance to each tile from where you currently are. Note that when I say 'distance', I mean 'length of the shortest path' and not simple sqrt(dx^2+dy^2). After you have each of those maps, you can do something like (((GoldMap + PowerUpMap) - EnemyMap) - DistanceMap) and then just go to the tile with the lowest value. Once you decide where to go, you probably want to perform pathfinding using weights based on some of the maps you constructed so your pirate will make sure to collect gold coins along the way, etc.

Share on other sites
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 :)

Share on other sites
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)

Share on other sites
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.

Share on other sites
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.

• 40
• 12
• 10
• 10
• 9
• Forum Statistics

• Total Topics
631368
• Total Posts
2999595
×