-
Notifications
You must be signed in to change notification settings - Fork 57
Notes on AI
An overview of the OpenCiv3 approach to AI, some general notes on AI, and related miscellany.
The plan is to build a modular, layered in-game AI. The layers will interact, we the interactions and interfaces between components require some careful design.
For example, a city production AI routine that decides what cities will build, will need to be informed by the priorities of an overarching strategy AI. If the strategic priority is expansion, building settlers is more likely; if it's the space race, building libraries is more likely; if it's securing a source of horses, military units are more likely.
We'll cover here some of the AI components that have at least an initial implementation.
The Strategic Priority AI decides what the AI's high-level goals are. As currently defined, the AI re-evaluates its strategic priorities every 15-24 turns (the interval will eventually be made configurable). It goes through all possible priorities, asks them to calculate a weight of how important they are based on the AI player's current game knowledge, and then uses those weights to choose one of them as its top priority.
It then repeats this process for a secondary priority, and, if the weights for possible priorities are close enough together, potentially for a tertiary and quaternary priority.
Although as of right now (6/6/22) the priorities are only calculated and not used, we expect that to change, initially with the City Production AI allowing the chosen priorities to affect the likelihood of constructing units. Each strategic priority that has been chosen will be able to affect a multiplier to the likelihood of choosing a particular unit. The effect of this multiplier will be lessened for secondary and lower priorities.
There are currently three possible strategic priorities. We plan to add more, and they are designed so that once we figure out how mods can be added, more could be added via mods. I suspect moving a strategic priority AI out into a separate mod module will be an early proof-of-concept mod.
This strategic priority will encourage the AI players to build settlers, and will be very common early in the game.
Eventually, expansionist civilizations will be even more likely to choose this priority.
This strategic priority will encourage building fast units for exploration, and will also be common early in the game. At some point, the unit AI will be more likely to assign units to exploration (versus defense or offense) if this priority is active.
Eventually, Seafaring civilizations will be more likely to choose this priority if they have the appropriate technology to explore by sea.
This strategic priority indicates that the AI is or is planning to be at war. Currently, it will only be chosen once the expansion phase is finished, and future enhancements are needed to make it have an effect. It will also need more AI components to be built to result in an effective combat AI.
Currently, once the expansion phase is over, a random enemy is chosen to go to war with. As we evolve, this will be chosen more intelligently.
Eventually, Militaristic civilizations will be more likely to choose this priority; the likelihood will also be impacted by the civilization's Aggressiveness setting.
Eventually, there will likely be several Military AI modules for AI players to make use of.
Many other strategic priorities are envisioned. This is not an exhaustive list, and items on this list may be modified or dropped as the situation evolves.
Currently, the AI doesn't try to clear barbarian camps near their cities. Sometimes they do by chance, but not by planning. This should be a priority whose likelihood is highly influenced by the proximity of barbarian camps.
AIs should have an awareness of how advanced or not advanced they are, just as the human does through the Science Advisor. My vision for this is using the same tiers (backwards/moderately advanced/advanced), and having the backwards one, and if it's late game, the advanced one, make this priority more likely. The "scientific" AI trait will also make this one more likely. It will result in building more science-producing buildings, as well as roads.
This will be a primarily mid-game priority that the AI is more likely to choose if they cannot sustain a high science rate. They'll build more roads and commerce-boosting buildings. It will also be more likely to be chosen by Commercial civilizations.
This will focus on improving city productivity, by either building mines or constructing buildings to do so. An AI may choose this if it ranks poorly in productivity, if it's in war and feels it has the luxury of focusing on long-term productivity over short-term unit production, or simply because it is Industrious.
This may be combined to some extent with Boost Economy.
If an AI believes it can win a certain victory condition, it may choose that victory type as a strategic priority. This will make it take actions that further that goal, such as building more cultural buildings, building spaceship components, or refusing to trade away space-related technologies.
Conversely, if an AI believes another player is getting close to victory, it may choose as its priority preventing that outcome. This could take a variety of forms, such as attempting to capture relevant cities to slow or stop the victory, trying to boost its culture enough to prevent another player from winning a cultural victory, or seeking alliances (defensive or otherwise), or being more willing to enter into diplomatic agreements with rivals of the player who is approaching victory.
Some general notes on AI, to aid design.
One may ask, AI is so advanced nowadays, can we just find an AI program and turn it loose on our game? I believe the answer is "no" for several reasons. One is it would have to be able to interact with the game, e.g. knowing which buttons are which. Another is we haven't added any goal conditions (you can't win yet). A third is that the game has a combinatorial explosion of possibilities. A fourth is it would have to play an extremely large number of games to help it figure out which strategies work, and we don't have any supercomputers. If it were that easy, Civilization VI would probably have taken a similar approach and had a better AI.
With that out of the way, the following contains notes on AI design, some of which may be decades old, but still helpful as the fundamental building blocks in some cases carry forward. The approach of "study old things first" is not just to get those fundamental building blocks, but in recognition that the things modern AIs are good at - big data, identifying birds in photographs, displaying ads that are more likely to result in a human buying something - are not necessarily the same things that will help it win a strategy game. Even in the cases where AI is good at winning a strategy game, such as chess, the game is different.
First, some terminology. The search space is the set of all possible searches. The search graph or search tree are the paths of that search space that has been explored (Barr, p. 26).
In chess, the search space is the set of all possible positions possible on a chess board from the starting position. So in our game, it's the set of all possible games resulting from one starting configuration. Even on a tiny (60x60) map, you can see that this is a nearly infinite space - not just which cities are settled where, but which units and improvements are built, which tiles are worked, where units are moved. Chess has an estimated 10^120 possible plays in an average length game (Shannon, 1950, 1956), and our game will have more. We can't explore all the possibilities.
Instead, we must limit search. Several high-level possibilities exist to help with this.
Planning is "the sense of defining and solving problems in a search space from which unimportant details have been omitted. The details of the solution are filled in (by smaller searches within the more detailed space) only after a satisfactory outline of the solution, or plan, has been found" (Barr, p. 28).
This fits in well with our plan to have a Strategic Priority AI. That part of the AI's responsibility is to figure out at the highest level what its goal is. The planning approach suggests that a logical next step to improving it would be for the Strategic Priority AI to figure out a rough outline of that plan. If it identifies its goal as "eliminate these three barbarian camps in order", that may be a satisfactory outline. If it identifies its goal as "secure a source of iron, then a source of horses", that may again be an outline. The details would be filled in by a military AI that finds the units to accomplish those goals, or perhaps by a city AI if the goal is to pursue scientific research.
To be added: heuristics
This will be important for pathing (especially on larger maps), but likely other areas as well.
Barr (p. 27) quotes a great example of problem representations:
Suppose two diagonally opposite corner squares are removed from a standard 8 by 8 square chessboard. Can 31 rectangular dominoes, each the size of exactly two squares, be so placed as to cover precisely the remaining board? (Raphael, 1976, p. 31)
The straightforward, but inefficient, approach is to start placing dominoes in various configurations. But as Barr notes, if one realizes that each domino must be on one black and one red square, and two red squares have been removed, it becomes immediately apparent that the answer is "no". This is an example of representing the problem differently.
Barr notes that "Unfortunately, little theory exists about how to find good problem representations," and notes Amarel (1968) as a citation for more on the topic. Still, it is a good reminder that if we're struggling to get a performant AI (either in results or time efficiency), it may help to consider whether there's another way to look at the general problem.
Barr = The Handbook of Artificial Intelligence, Barr & Feigenbaum
If not listed above, the citations refer to papers written by the authors in the given year.
Improving pathing is no longer a major priority for OpenCiv3. There are other things such as gameplay features that are more important.
Class DijkstrasAlgorithm.cs is the heart of our pathfinding.
If run with the stopWhenReachingDestination parameter, which is true by default, our Dijkstra's is in fact equivalent to Uniform Cost Search (UCS). We add nodes to the queue as we encounter them and, with that parameter, stop once we find our goal, which are the distinguishing characteristics of UCS. These were added as intuitive optimizations, as at least Quintillus had not heard of UCS at the time they were added. The benefits are lower memory requirements due to adding nodes as they are encountered, and quicker run time due to not having to calculate to all goals.
A* pathing requires a heuristic that indicates which paths are likely to be inexpensive. How can we determine what that heuristic is? Great question!
Amit at Stanford has written some detailed articles on pathing, and his heuristic page is a great reference. Some salient points:
- If we set the heuristic at or below the actual minimal cost, A* will always find the best path
- If we set the heuristic somewhat above the actual minimal cost, A* will run faster, but may not find the absolute fastest path
- There is a tradeoff between speed and accuracy; we may give A* a higher heuristic for more speed on slower computers or as turn times slow down, for example.
- Dijkstra's will never be faster than A* (though with a heuristic of 0 it will be equal), and will always find the optimal path
(Note that in this case I am referring to Dijkstra's where it stops after finding its goal, as our implementation currently does in the default case)
What does this mean for us? It depends on the rules. If we have no roads, the heuristic can be set to 1 and it will always produce an optimal result, while being somewhat better than Dijkstra's due to not having to explore as far in the "wrong" direction. If we have roads (but no rails) and the default road cost, setting the heuristic to 1/3 will accomplish the same. Setting it to a higher value, such as 1/2, may result in sub-optimal routing, e.g. going over a mountain when it would have been quicker to go around that mountain, and the higher the value, the more likely that is to happen but the quicker the algorithm will run.
Since railroads, by default, have a cost of 0, the heuristic would have to be 0 to be lower than or equal to the actual minimal cost. In that case, there is no benefit to using A* over UCS/our implementation of Dijkstra's.
This presents an interesting conundrum where the later in the game we are, the less optimal A* can be at pathing, slowing the game down at the same time that the explosion of units, cities, and everything else is also slowing the game down. This may be related to why Civilization III has noticeably slow path re-calculation in the late game every time a road is built or destroyed; its cost design actively inhibits optimization. Nevertheless, the fact that it sometimes does use sub-optimal routes suggests that at least to some extent it does try to use A* optimization, with a heuristic set higher than the actual minimum cost.
This is an area where we may want to consider configurability. Thankfully, Amit has lots of writing on that topic as well (he also has writing on other topics that may be of interest, such as map generation.
In addition to linear distance based heuristics, we can use landmark heuristics. This is an approach Quintillus had thought might help, and it turns out others had already thought of the idea, decades ago. In our case, the intuitive landmarks may well be cities. By precomputing the absolute cost between cities, the overall algorithm can be optimized.
Whether that would be a net savings after the precomputation is debatable and likely depends on how often the cost of navigating between those landmarks changes. Road and rail construction could invalidate the cache frequently, so it might not be a net savings, and if we try to restrict the precomputation to nearby cities and only recalculate if nearby infrastructure changes - probably necessary to avoid the slowdowns Civ3 has late-game - then we risk being unaware of a newly-enabled circuitous but quick route. In other words, to avoid precomputation being too expensive, we may have to apply heuristics that themselves have a chance of being inaccurate.
Factorio Friday Facts 317 has a good explanation including animations showing how they optimized their A* path-finding by means of using an improved heuristic, which used chunking and a simplified approach to provide an improved heuristic.
In Factorio's case, the simplified heuristic algorithm looks at chunks of land tiles - water tiles are impassable (except to Spidertrons, which are a later addition, but Spidertrons are not long-distance-pathed as biters are). In C7, water tiles may be passable, but unless units of both land and sea classes are implemented, or we implement some sort of embarkment/combine-with-ships routing, we'd still be able to divide based on a land/water division.
There are also some differences. In Factorio, the heuristic ignores cliffs and other entities (walls, etc.) which may significantly lengthen the path. In our case, a heuristic would/may ignore roads/railroads, which could significantly shorten a path - the same problem described above where a very circuitous route could be the shortest. Still, it could be of use, especially in cases involving impassible or unimproveable terrain.
This comment also makes an important note - by running pathfinding from start to end and end to start at the same time, they will meet in the middle, but if either end is e.g. an unconnectable island, that is discovered much more quickly. This is relevant for us as that case may apply - the user trying to tell a unit to move from an island to another landmass, for example.
Our current Dijkstra's uses a binary heap. This is pretty good. However, a D-ary heap would be the optimal structure, where D is calculated based on the ratio of edges to vertices. The Fibonacci heap is also (theoretically) faster than the binary.
How much of a difference this makes and whether it's worth the effort are debatable. We shouldn't just replace what we have because of theoretical improvements, but if and when we do so, make detailed comparisons. To so this we likely need the game to evolve first, so at most we could introduce alternatives (pluggable heaps?) without removing what we have now prior to that point.