Which algorithm used in Advance Wars type turn based games
- by Jan de Lange
Has anyone tried to develop, or know of an algorithm such as used in a typical turn based game like Advance Wars, where the number of objects and the number of moves per object may be too large to search through up to a reasonable depth like one would do in a game with a smaller search base like chess?
There is some path-finding needed to to engage into combat, harvest, or move to an object, so that in the next move such actions are possible.
With this you can build a search tree for each item, resulting in a large tree for all items. With a cost function one can determine the best moves.
Then the board flips over to the player role (min/max) and the computer searches the best player move, and flips back etc. upto a number of cycles deep.
Finally it has found the best move and now it's the players turn. But he may be asleep by now...
So how is this done in practice?
I have found several good sources on A*, DFS, BFS, evaluation / cost functions etc. But as of yet I do not see how I can put it all together.
