Saber Cherry AI suggestions
Published on Tuesday, December 27, 2005 By Brad Wardell In Galactic Civilizations II
Note, this was posted to the dev journal area which I removed since only GalCiv developers are supposed to be able to post to that area.
--
Artificial Intelligence, Tree Pruning, and Saving vs. Regenerating Trees
This is a suggestion about how to prune search trees in order to avoid doing AI calculations at execution time. It makes some assumptions, e.g. you are using branch-and-evaluate or A* to search a dynamically-generated tree when determining the next move at execution time (between AI ship moves).
The analogy: How do tell a very stupid, very nearsighted climber the best route to the top of 1000-branch redwood tree? Assume that any branch he tries to use might break off, forcing him to try a different approach.
GalCiv: Spend months evaluating possible paths, tell him which branch to start with, and let him feel his way from there.
GalCiv2: Give him a talking monkey who can explore the local area and tell him which branch to try next, at any time.
My suggestion: Spend months evaluating possible paths and branch-breaking probabilities. Clone the tree, and grow it in a cute little bonsai dish, trimming all the branches that are weak or inconvenient, until you are left with a tree that has only the branches for the best route, and the branches needed for contingencies (so he can still climb if a branch on the best route breaks). Give him this simplified bonsai model, with the correct routes marked, and tell him to follow it exactly (use only tree branches present in the bonsai, as indicated by the path) unless the main and nearby contingency branches all break. Then he can throw away the bonsai and use his talking monkey.
Technical stuff:
Since the (low priority) strategy thread has plenty of time to churn in the player phase, prior to execution, it can obviously make a very good initial move. However, in order to evaluate the move, I imagine you are making a tree deeper than the move of interest (as in chess AI routines) rather than simply acting on the scores of the leaves in a complete 1-deep tree. If you are indeed building a tree more than one level deep in the idle time (past the first ship move), why not save the highest-probability path(s) through the tree so it does not have to be recalculated at execution time?
For example, these ships are all within reach of each other:
Drengin: battleship, cruiser, destroyer, troop transport.
Human: destroyer, corvette, freighter, freighter.
Result: Idle thread builds a large tree and decides the best and most probable path is this:
D.Battleship attacks H.Destroyer (wins)
D.Cruiser attacks H.Corvette (wins)
D.Destroyer attacks H.Freighter (wins)
D.Transport moves toward planet
(human turn)
H.Freighter flees (but not far enough!)
(drengin turn)
D.Destoyer attacks H.Freighter
D.Transport captures planet
...Sector victory!
However, when only first move is saved, it might go like this:
D.Battleship attacks H.Destroyer (wins)
D.Cruiser attacks closest, weakest enemy, H.Freighter (wins)
D.Destroyer attacks closest, weakest enemy, H.Freighter (wins)
D.Transport moves toward planet
(human turn)
H.Corvette attacks D.Transport (wins)
(drengin turn)
D.Battleship attacks closest, weakest enemy, H.Corvette (wins)
...sector clear of enemy ships, but the invasion was thwarted!
Now, if I understand correctly, the proposed solution is to do more calculations (build deeper trees) at execution time. This is possible due to handling graphics on the GPU, and people upgrading CPUs over the last two years. However, these trees explode fast! Calculating the same tree 20 times for 20 ships in a sector will invariably limit the tree depth, and thus quality; if you want the AI to move all the ships in a sector in under 2 seconds, this would only give 100ms to generate each tree and evaluate the best path. HOWEVER - if the tree is only calculated once, using the idle time in a player's turn, a full 5 minutes might go into a tree, making it 3000x better! With ideal dynamic pruning, of course.
The problem is that such an immense tree cannot be saved, because it might take 200 GB of memory. Yet the "desired" path through the tree (which might be 2-100 levels deep, depending on how it is pruned, how many turns ahead it looks, and how many ships there are) can certainly be saved in a trivial amount of memory. Furthermore, the "second most probable" paths can ALSO be saved, since most battles are highly predictable ("biased"). For example, in the situation discussed, the entire tree-path of D.Battleship vs. H.Destroyer, D.Cruiser vs. H.Corvette, etc. is the ideal Drengin strategy and the desired outcome of each battle ("node") is perhaps 98% assured, giving a cumulative probability of 94% that the first three rounds will go as planned, meaning that the tree needs to be recalculated only 6% of the time.
What if something goes wrong? Well… recalculate the tree… or save backup paths! Let’s say that a node requires 32 bytes. If there are 16 possible moves per ship, 4 friendly and 3 enemy ships, and you look 2 turns ahead (your turn, enemy turn, your turn), and you cycle through ships in a fixed order, that makes a tree of maximal size ((2^4)^4)*((2^4)^3)*((2^4)^4) = 2^44 leaves or 2^49 bytes (more than an Opteron can address), compared to 2^24 bytes (16 MB) that I imagine Stardock has allocated to temporary AI storage. By "maximal" size, I mean that this assumes no combat and so ships are not dying each turn, which would make the tree smaller; the exact size of a tree that involves combat and movement on a 2D map cannot be determined without generating the tree. Comparatively, saving only the desired path in this 7-level tree would require 224 bytes, and not need recalculation 94% of the time (estimated, as the humans are hopelessly outgunned). To improve this accuracy, there could be a "tree trunk" - the desired and expected outcome - in which the most highly biased events (like battleship versus destroyer) are near the root, such that if reality deviates from expectations, it will do it later rather than sooner.
Furthermore, rather than just storing the trunk, every branch off the trunk can also be stored - you end up with something that looks more like a bunch of stacked octopi than a tree, in that octopus tentacles never branch after leaving the main body. This way, the semi-complete tree that you made for the sector would be reduced down to the "desired" path and "contingency" paths, such that there is a contingency plan for every unexpected event (like if the battleship loses to the destroyer). Note that there are no contingencies for a sequence of two unexpected events, so if the battleship lost and then the cruiser lost, a new tree would need to be created at execution time (smaller, though, due to having 2 fewer ships). Memory? Why, this would only require 224 bytes for the trunk nodes, and an additional 15*6*32+15*5*32... = 15*32*((6+1)*6)/2 =10080 bytes, for 10304 bytes to store the desired plan and a contingency for every unexpected outcome! If you limit unexpected outcomes to combat results (you shouldn’t have an unexpected result when moving a ship according to a plan, unless there are mines) then you only need 1 contingency per node, not 15; the resulting plans are 896 bytes (trunk and contingencies).
In the generic case, it seems wise to allocate a specific amount of memory - maybe 16KB - to the master battle plan for a sector; store the primary trunk (most probable and desirable outcome); and then store as many branches as possible (prioritizing the nodes that are most probable and closest to the root) until 16KB is exceeded. Once it is generate, and the AI still has time during the player’s turn, deeper exploration of the search-space is possible, which may lead to contingency nodes being added or removed from the plan, replacement of the trunk with a better one, or making the trunk longer. Alternately, generate the subtrees to the limits of the time allocated, and trim each one back to 16KB by truncating the lowest-probability, least desirable nodes (you end up with a "fan coral" or "fern leaf" shape, radiating out from the root).
I’m eager to hear whether such a system is already in place, or if it would not be applicable to your AI methodologies. I am currently doing a lot of programming related to NP-complete problems, computer branch prediction, and search, so I think about this sort of thing constantly; but as a result, sometimes I make assumptions that my listener(s) are immersed in the same world, and I skip parts of explanations. If my wording was confusing, I’d be happy to clarify.
-Cherry
This is a suggestion about how to prune search trees in order to avoid doing AI calculations at execution time. It makes some assumptions, e.g. you are using branch-and-evaluate or A* to search a dynamically-generated tree when determining the next move at execution time (between AI ship moves).
The analogy: How do tell a very stupid, very nearsighted climber the best route to the top of 1000-branch redwood tree? Assume that any branch he tries to use might break off, forcing him to try a different approach.
GalCiv: Spend months evaluating possible paths, tell him which branch to start with, and let him feel his way from there.
GalCiv2: Give him a talking monkey who can explore the local area and tell him which branch to try next, at any time.
My suggestion: Spend months evaluating possible paths and branch-breaking probabilities. Clone the tree, and grow it in a cute little bonsai dish, trimming all the branches that are weak or inconvenient, until you are left with a tree that has only the branches for the best route, and the branches needed for contingencies (so he can still climb if a branch on the best route breaks). Give him this simplified bonsai model, with the correct routes marked, and tell him to follow it exactly (use only tree branches present in the bonsai, as indicated by the path) unless the main and nearby contingency branches all break. Then he can throw away the bonsai and use his talking monkey.
Technical stuff:
Since the (low priority) strategy thread has plenty of time to churn in the player phase, prior to execution, it can obviously make a very good initial move. However, in order to evaluate the move, I imagine you are making a tree deeper than the move of interest (as in chess AI routines) rather than simply acting on the scores of the leaves in a complete 1-deep tree. If you are indeed building a tree more than one level deep in the idle time (past the first ship move), why not save the highest-probability path(s) through the tree so it does not have to be recalculated at execution time?
For example, these ships are all within reach of each other:
Drengin: battleship, cruiser, destroyer, troop transport.
Human: destroyer, corvette, freighter, freighter.
Result: Idle thread builds a large tree and decides the best and most probable path is this:
D.Battleship attacks H.Destroyer (wins)
D.Cruiser attacks H.Corvette (wins)
D.Destroyer attacks H.Freighter (wins)
D.Transport moves toward planet
(human turn)
H.Freighter flees (but not far enough!)
(drengin turn)
D.Destoyer attacks H.Freighter
D.Transport captures planet
...Sector victory!
However, when only first move is saved, it might go like this:
D.Battleship attacks H.Destroyer (wins)
D.Cruiser attacks closest, weakest enemy, H.Freighter (wins)
D.Destroyer attacks closest, weakest enemy, H.Freighter (wins)
D.Transport moves toward planet
(human turn)
H.Corvette attacks D.Transport (wins)
(drengin turn)
D.Battleship attacks closest, weakest enemy, H.Corvette (wins)
...sector clear of enemy ships, but the invasion was thwarted!
Now, if I understand correctly, the proposed solution is to do more calculations (build deeper trees) at execution time. This is possible due to handling graphics on the GPU, and people upgrading CPUs over the last two years. However, these trees explode fast! Calculating the same tree 20 times for 20 ships in a sector will invariably limit the tree depth, and thus quality; if you want the AI to move all the ships in a sector in under 2 seconds, this would only give 100ms to generate each tree and evaluate the best path. HOWEVER - if the tree is only calculated once, using the idle time in a player's turn, a full 5 minutes might go into a tree, making it 3000x better! With ideal dynamic pruning, of course.
The problem is that such an immense tree cannot be saved, because it might take 200 GB of memory. Yet the "desired" path through the tree (which might be 2-100 levels deep, depending on how it is pruned, how many turns ahead it looks, and how many ships there are) can certainly be saved in a trivial amount of memory. Furthermore, the "second most probable" paths can ALSO be saved, since most battles are highly predictable ("biased"). For example, in the situation discussed, the entire tree-path of D.Battleship vs. H.Destroyer, D.Cruiser vs. H.Corvette, etc. is the ideal Drengin strategy and the desired outcome of each battle ("node") is perhaps 98% assured, giving a cumulative probability of 94% that the first three rounds will go as planned, meaning that the tree needs to be recalculated only 6% of the time.
What if something goes wrong? Well… recalculate the tree… or save backup paths! Let’s say that a node requires 32 bytes. If there are 16 possible moves per ship, 4 friendly and 3 enemy ships, and you look 2 turns ahead (your turn, enemy turn, your turn), and you cycle through ships in a fixed order, that makes a tree of maximal size ((2^4)^4)*((2^4)^3)*((2^4)^4) = 2^44 leaves or 2^49 bytes (more than an Opteron can address), compared to 2^24 bytes (16 MB) that I imagine Stardock has allocated to temporary AI storage. By "maximal" size, I mean that this assumes no combat and so ships are not dying each turn, which would make the tree smaller; the exact size of a tree that involves combat and movement on a 2D map cannot be determined without generating the tree. Comparatively, saving only the desired path in this 7-level tree would require 224 bytes, and not need recalculation 94% of the time (estimated, as the humans are hopelessly outgunned). To improve this accuracy, there could be a "tree trunk" - the desired and expected outcome - in which the most highly biased events (like battleship versus destroyer) are near the root, such that if reality deviates from expectations, it will do it later rather than sooner.
Furthermore, rather than just storing the trunk, every branch off the trunk can also be stored - you end up with something that looks more like a bunch of stacked octopi than a tree, in that octopus tentacles never branch after leaving the main body. This way, the semi-complete tree that you made for the sector would be reduced down to the "desired" path and "contingency" paths, such that there is a contingency plan for every unexpected event (like if the battleship loses to the destroyer). Note that there are no contingencies for a sequence of two unexpected events, so if the battleship lost and then the cruiser lost, a new tree would need to be created at execution time (smaller, though, due to having 2 fewer ships). Memory? Why, this would only require 224 bytes for the trunk nodes, and an additional 15*6*32+15*5*32... = 15*32*((6+1)*6)/2 =10080 bytes, for 10304 bytes to store the desired plan and a contingency for every unexpected outcome! If you limit unexpected outcomes to combat results (you shouldn’t have an unexpected result when moving a ship according to a plan, unless there are mines) then you only need 1 contingency per node, not 15; the resulting plans are 896 bytes (trunk and contingencies).
In the generic case, it seems wise to allocate a specific amount of memory - maybe 16KB - to the master battle plan for a sector; store the primary trunk (most probable and desirable outcome); and then store as many branches as possible (prioritizing the nodes that are most probable and closest to the root) until 16KB is exceeded. Once it is generate, and the AI still has time during the player’s turn, deeper exploration of the search-space is possible, which may lead to contingency nodes being added or removed from the plan, replacement of the trunk with a better one, or making the trunk longer. Alternately, generate the subtrees to the limits of the time allocated, and trim each one back to 16KB by truncating the lowest-probability, least desirable nodes (you end up with a "fan coral" or "fern leaf" shape, radiating out from the root).
I’m eager to hear whether such a system is already in place, or if it would not be applicable to your AI methodologies. I am currently doing a lot of programming related to NP-complete problems, computer branch prediction, and search, so I think about this sort of thing constantly; but as a result, sometimes I make assumptions that my listener(s) are immersed in the same world, and I skip parts of explanations. If my wording was confusing, I’d be happy to clarify.
-Cherry
