How to find a good AI strategy for a survival game?
Hi, I'm a college student here developing a tank survival game for the finals. I have had very little experience in AI strategies, so I wonder if anyone here can give me a hint or two to start.
Thanks.
The game's description is below:
Goal:
Develop a good AI strategy for survival.
Game Name: Tank Survival
How game starts: All tanks will be placed on the board in random position
How game ends: When we have only one tank surviving, that's the winner
When does a tank die? When the energy of a tank is zero, it dies.
Game environment: A 15x15 closed environment, like a chess board
Participants: 5 teams, 3 tanks per team
Game Basic Rule
For each tank, only 1 action is allowed each turn.
A tank can move with a shield on, but shield costs energy.
When one tank destroyed another one, it takes all the energy left of the victim
tank. *(Bonus from kill ?1000 + (1/2)*Enemy energy before kil)
The tank's weapon can only shoot in continuous linear way.
Facts about the tank
Initial Tank Energy - 10000
Life Support Energy cost ? 50
Missile yield multiplier - ?3
Shield multiplier - ?5
Radar Cost = [(distance * accuracy) ^1.3] * 3 + 100
Missile Cost ?yield + accuracy * distance * 7
Movement Cost = (distance^1.4) *50
Shield Cost = multiplier * Energy shielded
Maximum movement - distance ?5 (any direction)
Bonus from kill -?1000 + (1/2)*Enemy energy before kill
Missile accuracy -?not disclosed
Radar Accruacy ? not disclosed
Key problems
?I only have 3 tanks. . .
?I have to survive among the other 15 tanks.
?None of the actions, misile, radar, or shield are 100% working. There are always chances that they don't work.
[2102 byte] By [
nonamenoa] at [2007-10-2 21:15:46]
I think the first stage is to work out what constitutes a "state" and a "move." A state is the current board positions with all the tank energies and other parameters. A move is a transition from one state to another. Can you move around? Can you fire the gun and move the tank at the same time? If you fire the gun, does it miss sometimes?
You then have to have a way to evaluate a state. For instance, if you move closer to an enemy tank, does that put you in a better position or a worse position?
You can then draw a Moves Tree. This starts from where you are, shows all the moves you could make and the states you could end up in after one move. You can attach a value to each state.
Then you can extend the state tree by adding all the counter moves your enemy could make, and the states in which those moves would leave the game. Thus the transition from your state now, to your state after the enemy has moved, will show a gain or a loss, depending on whether you or the enemy gained more or lost less.
The strategy that wins the game will be the one that takes you from the start state to the goal state in such a way that your enemy cannot stop you. There are two possible strategies for choosing moves, Minimax and Maximin. Minimax means minimise your maximum loss; Maximim means maximise your minimum gain.
Try it first with a simple game like Nought and Crosses. The state tree grows very rapidly in the number of moves, so you may need some algorithm for pruning it or for generating only part of it at a time, as modern chess playing algorithms do.
Write in a computer language that is good at handling state trees. I used to use Prolog but some programmers swear by Lisp. You won't be able to solve the problem in a **** language like Basic, Pascal or anything like those.
You will need to read around the subject. If Alan Bundy has written anything recently, look at that first: he is an excellent writer and a very skilful practitioner as well.
xtxa at 2007-7-14 0:23:42 >
