- Joined
- Jul 10, 2007
- Messages
- 6,306
My first idea for developing AI was to use a genetic algorithm. A genetic algorithm will continue to evolve itself until it comes across an appropriate solution. In this case, the solution would be to increase income and minimize the amount of lives lost. The solution for placing towers would be to increase the path the units have to traverse as much as possible. The solution for upgrading towers would be maximum exposure.
The problem with a genetic algorithm is the computation time. Warcraft 3 simply can't handle a genetic algorithm.
I then thought about what a neural network would be like in a Tower Wars game. It would work, but there are way too many scenarios to ever effectively code it.
So what is the next possible solution?
There are only 2 types of good mazes in Tower Wars. There is the maze that's specialized for low range towers and then there is the maze for everything else. Thus, I could create 4 queues with all of the coordinate data for all of the positions in the maze from order of the first tower to the last tower (the 2 mazes made for each team). Each maze also contains 2 possible bricks of towers for aa depending on the race, so I could then include aa mazes.
When the AI player wants to expand their maze, they can read the next position and build a tower there. When the AI player wants to build aa, they can read the next aa position and build a tower there.
The next problem is upgrades... every position would have to be scored based on its exposure and a tree would have to be populated using these scores. From here, when the AI player wants to upgrade a tower, they can look at the next best tower to upgrade by traversing the tree. The score would be the maximum range a tower can have before its score begins to deteriorate.
Example
The position at the top right corner of the dialog line would have a very high score for 128 range towers, but the score would be very low for something like a 1500 range tower. The score of that position would then be 128, meaning that it's good up to a 128 range tower. The score relative to the tower could be something like (range of tower)/(score of position) where 1 would be a perfect score and <1 is acceptable but not a good fit.
From here, the AI player would then know where to build towers, where to build aa, and where to upgrade towers. The next problem is what towers to upgrade. The score for upgrading a tower should be based on the tower's dps score compared to the total damage score of the maze (size of maze factored in) and the total health of all units. If the total health of all units is 1000 and the total damage the maze can put out is 1000, then the new tower should would be 1000/1000-1, or 0. If the unit total health was 2000 and the maze could only dish out 1000 damage, then the score would be 2000/1000-1, or 1. Any score higher than 0 means that an upgrade or maze extension is necessary. Any score under 0 means that the maze is currently overkill.
From here, the AI player would then calculate what it would cost to build new towers to respond to the wave vs what it would cost to upgrade existing towers to respond to the wave. It would continue to iterate over this until it found the cheapest solution (a genetic algorithm? Rather short, possible). From here, it would carry out its plans.
There is a weakness to this AI though... performing a very large mass send will end up crippling the AI's income as it will respond to that send in full. The AI needs to know when to sacrifice lives. Thus... rather than looking at the average health of all units, it should, exclude a number of units that have above avg health (perhaps lives/5 # of units). From here, it can then focus on the weaker units and ignore the larger units until the end. This will allow the AI player to successfully fend off mass sends w/o getting its income destroyed. The next thing it needs to do is learn when to fend off the waves. For example, it might wait until the next round to begin building and upgrading.
The next problem is what happens when the player doesn't send for 3 rounds and then masses? The AI player should build not based on what the player sends, but based on the potential send of the player.
How do tactical towers and sends with special abilities like attackers play into all of this? Well, this is where I'm a little bit stuck atm ^^.
Another issue is armor and attack types... for example, getting siege towers to target fortified sends ;p. I could make it so that each tower automatically targets its specialty regardless of the health of that specialty to maximize damage output, but this would cause some serious issues... I could increase the dps counter on that unit whenever a tower targets it and make it so that towers target different units if the dps counter - the targeting unit is >= the unit's remaining health. I can also use an instant damage counter (for slower towers) that does the same thing but using the actual damage of the tower. For example, if a 22 dmg tower that only attacks once every 3 seconds targets a 15 health unit, a second tower won't target that unit even though the dps is < 15. Also, I need to account for splash... for towers with splash, I need to enumerate over units around the targeted unit and increase their dps and instant damage counters based on the distance and splash and what not... I need to do this with bouncing attacks too... this will all give the AI player impeccable targeting skills.
My final problem is lowering the AI Player's abilities. I can modify the calculations by increasing the average health of all units, thus making the AI player overbuild. I can also lower the targeting calculations to make the AI player focus its towers less effectively. My big issue though is making the AI player's maze weaker... I could introduce different styles of mazes and then make the AI player use one of those mazes based on its score, but that just seems pretty bad.
Essentially, the AI Player at max ability would be the perfect player... I wouldn't even be able to beat it D:.
Anyways, once I finish this AI, it should be able to be put into any tower wars map. You just generate the mazes for the AI to follow and pass in all of the tower and send information and you are set. The only problem is again towers and sends with special abilities ;\.
The problem with a genetic algorithm is the computation time. Warcraft 3 simply can't handle a genetic algorithm.
I then thought about what a neural network would be like in a Tower Wars game. It would work, but there are way too many scenarios to ever effectively code it.
So what is the next possible solution?
There are only 2 types of good mazes in Tower Wars. There is the maze that's specialized for low range towers and then there is the maze for everything else. Thus, I could create 4 queues with all of the coordinate data for all of the positions in the maze from order of the first tower to the last tower (the 2 mazes made for each team). Each maze also contains 2 possible bricks of towers for aa depending on the race, so I could then include aa mazes.
When the AI player wants to expand their maze, they can read the next position and build a tower there. When the AI player wants to build aa, they can read the next aa position and build a tower there.
The next problem is upgrades... every position would have to be scored based on its exposure and a tree would have to be populated using these scores. From here, when the AI player wants to upgrade a tower, they can look at the next best tower to upgrade by traversing the tree. The score would be the maximum range a tower can have before its score begins to deteriorate.
Example
Code:
**********
** *
** *
** *
*
****The position at the top right corner of the dialog line would have a very high score for 128 range towers, but the score would be very low for something like a 1500 range tower. The score of that position would then be 128, meaning that it's good up to a 128 range tower. The score relative to the tower could be something like (range of tower)/(score of position) where 1 would be a perfect score and <1 is acceptable but not a good fit.
From here, the AI player would then know where to build towers, where to build aa, and where to upgrade towers. The next problem is what towers to upgrade. The score for upgrading a tower should be based on the tower's dps score compared to the total damage score of the maze (size of maze factored in) and the total health of all units. If the total health of all units is 1000 and the total damage the maze can put out is 1000, then the new tower should would be 1000/1000-1, or 0. If the unit total health was 2000 and the maze could only dish out 1000 damage, then the score would be 2000/1000-1, or 1. Any score higher than 0 means that an upgrade or maze extension is necessary. Any score under 0 means that the maze is currently overkill.
From here, the AI player would then calculate what it would cost to build new towers to respond to the wave vs what it would cost to upgrade existing towers to respond to the wave. It would continue to iterate over this until it found the cheapest solution (a genetic algorithm? Rather short, possible). From here, it would carry out its plans.
There is a weakness to this AI though... performing a very large mass send will end up crippling the AI's income as it will respond to that send in full. The AI needs to know when to sacrifice lives. Thus... rather than looking at the average health of all units, it should, exclude a number of units that have above avg health (perhaps lives/5 # of units). From here, it can then focus on the weaker units and ignore the larger units until the end. This will allow the AI player to successfully fend off mass sends w/o getting its income destroyed. The next thing it needs to do is learn when to fend off the waves. For example, it might wait until the next round to begin building and upgrading.
The next problem is what happens when the player doesn't send for 3 rounds and then masses? The AI player should build not based on what the player sends, but based on the potential send of the player.
How do tactical towers and sends with special abilities like attackers play into all of this? Well, this is where I'm a little bit stuck atm ^^.
Another issue is armor and attack types... for example, getting siege towers to target fortified sends ;p. I could make it so that each tower automatically targets its specialty regardless of the health of that specialty to maximize damage output, but this would cause some serious issues... I could increase the dps counter on that unit whenever a tower targets it and make it so that towers target different units if the dps counter - the targeting unit is >= the unit's remaining health. I can also use an instant damage counter (for slower towers) that does the same thing but using the actual damage of the tower. For example, if a 22 dmg tower that only attacks once every 3 seconds targets a 15 health unit, a second tower won't target that unit even though the dps is < 15. Also, I need to account for splash... for towers with splash, I need to enumerate over units around the targeted unit and increase their dps and instant damage counters based on the distance and splash and what not... I need to do this with bouncing attacks too... this will all give the AI player impeccable targeting skills.
My final problem is lowering the AI Player's abilities. I can modify the calculations by increasing the average health of all units, thus making the AI player overbuild. I can also lower the targeting calculations to make the AI player focus its towers less effectively. My big issue though is making the AI player's maze weaker... I could introduce different styles of mazes and then make the AI player use one of those mazes based on its score, but that just seems pretty bad.
Essentially, the AI Player at max ability would be the perfect player... I wouldn't even be able to beat it D:.
Anyways, once I finish this AI, it should be able to be put into any tower wars map. You just generate the mazes for the AI to follow and pass in all of the tower and send information and you are set. The only problem is again towers and sends with special abilities ;\.
