Sign in to follow this  

gold collecting pirate AI

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by TheUltimatePirate
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.
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Thanks CWenner. I may have to read that a few times to understand it.. :) I will probably continue with my current method and then try to implement a minimax solution. I can then easily make them combat each other to see which is better :)

Sorry I did not mention this earlier, but moves are performed simultanously, that is all six players are asked for the next move at the same time on each iteration. I'm not sure if that affects your solution..

Also, there's more than two players so I'm not sure how that affects things.

Share this post


Link to post
Share on other sites
Another approach is to simply think about how you would decide where to move if you were directly controlling a pirate. You can do this with each pirate on the board to try to improve your understanding of the game and your strategy. Then try to implement this strategy as part of your solution. If you come across some weights that you're not sure how to set, you could either fiddle with them manually or try to use a genetic algorithm to set them if you really want to wedge a genetic algorithm in somewhere.

Share this post


Link to post
Share on other sites
[QUOTE]
Sorry I did not mention this earlier, but moves are performed simultanously, that is all six players are asked for the next move at the same time on each iteration. I'm not sure if that affects your solution..

Also, there's more than two players so I'm not sure how that affects things.
[/QUOTE]
Minimax can easily be extended to n-players, you merely keep track of the value of a state for each player. Normally it's applied to 2-player constant-sum games (which this is as well: whether you win or not, not the actual gold you obtain. gold is good for heuristics though). There, you keep track of the value, u, of either the first player or the player to act and you thereby know that the other player has c - u. c is normally 0. For this case, you merely need u1, u2, ...
That moves are made simultanously doesn't affect minimax (exept you do not do move updates between each player) but it will affect certain pruning techniques such as alpha-beta. You should still be able to get fairly good results but the pruning seems limited, a possiblity then is Monte Carlo.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
A variation of min-max might work well with this game. There are not many decisions other players can make. Just operate your pirate on the assumption that at each turn the other players will make a decision that has the highest utility. It is likely they will try to get all the treasure in the fewest moves possible. Be sure to keep track of whether or not another pirate may have that boat powerup. It is likely you will want to avoid those players. The same goes for you being able to reach a boat powerup and stealing the gold from another pirate.

Share this post


Link to post
Share on other sites
i was working on the same problem and changed it a little bit to solve again.

let say all the players choose their initial conditions, and they move sequentially. (first player moves, every one sees, then second player moves..)
so how can one decide for best initial condition?? (possibly different algorithms for the first and other players)

and let say the amount of gold is not equal for every gold piece.
so what is the position evaluation function for such a situation? how can i decide where to go???

and what is the best data structer for such a problem??


----
are there any references to check for this kind of problems? i couldn't find any similar thing in the internet..

[Edited by - someWhereLost on January 7, 2007 1:27:39 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Im thinking the best strategy is Not to chase the gold, but to get the 'powerups' instead, then spend your time robbing the other pirates.
Pretty sure it's a winning strategy. how can any individual compete with the guy who skims off the productivity of everyone else?

Might want to prioritize to chase the other pirate with the most points, since by robbing him you also remove your largest threat.
Are player's powerup and gold ratings visible btw? you'll also want to avoid guys stronger than yourself(they might be using the same strategy)

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this