-
Notifications
You must be signed in to change notification settings - Fork 11
AI Development
In the tile-based game genre, there has always been compelling stories, engaging game play, and stress on developing tactical prowess through perfect management of the unit objects. However, these types of games never had a need for a strong or developed AI due to map design playing a distinct role in game difficulty. It is due to this fact why campaigns were the focus of these games completely. Multiplayer AI didn't have the need to be developed past a certain point as long as the map design was good enough to overcome the weaknesses of the AI.
This development page is an attempt to break the spell of designing lazy AI for tile-based games. Unlike in other iterations, campaigns will not be cared for by a central group. There is no guarantee that an AI will have the advantage in every map. This means that AI will have to be able to hold its own in a great number of maps with or without the aid of map design.
Our goal in this document is to answer this question... "What do we need to make a successful yet difficult AI?"
The goal of this development document is to compile as many ideas about AI Development as possible into one page.
Unlike other documents, this one is made specifically for expansion. I highly recommend we compile as much ideas as we can into one place so we can further our research for AI and AI development for all tile-based games. This is the current syntax I recommend for contributions on this page...
This is my take on AI implementation. All stated here are ideas and inquiries that have been done overtime. I am putting this up as a reference for ideas regarding an AI that'll be able to pass along to anyone. But also as a reference for myself.
This is a opinionated essay. I'm writing this as a brainstorming draft instead of a research document because, they are much more fun to read. I ask that you only take these ideas with a grain of salt, and only take things which are important to you.
For tile based games, I decided to look for ideas from its closest neighbor, Real-time strategy games. Unlike tile based games, there is a wide array of AI algorithms for RTS that tile based games can learn from.
Below is some relevant articles regarding the subject...
and a prototype engine...
plus there are also some great books on the subject...
However vast the information, tile based AI isn't easily accomplished. The main problem being that not only does the AI have to deal with the enemy human player, but changing environments, positioning, and management of all units and funding.
In order to keep things easy to absorb. I'm splitting the AI into parts that we must focus on. Micro-management, Positioning & Adaptivity, and Important Units.
Underneath current implementation of most computer controlled AI the basis of attack was done by damage. Even though this is good for the short term, units usually have a mind of their own and don't strive to protect other units.
In other tile based games, The AI would ususally target your weakest unit. This is also bad because the weakest unit can be put in a arbitrary location causing the units to fall quickly in line.
The last main implementation is the AI heading for specific part or building in the map. Similar to targeting the weakest unit, it causes the computer to make a steady decision and lose all the units quickly.
It is okay for campaigns because difficulty is decided by the map. These methods are not going to cut it for an AI that'll take on a human player.
The main difference between people and AI is the ability to change strategies depending on the situation. The current AI implementations do not try to adapt, but instead try to force the issue.
On a 1-on-1 game, the AI needs a deeper meaning... let's go back in time...
When it comes to dealing with a horde of units, we usually would turn to micromanagement. When it comes down to micromanagement, I think nothing better states this than Sun Tsu's Art of War...
The key to an AI being able to do well against a human player completely depends on how well each and every unit is managed. The difference between a basic AI and a smarter AI is the ability to be able to maximize the potential of each unit. If each unit is maximizing its potential, then the AI will have a lot more power.
And what is the power behind a game, what else but the resources you collect. In CW, there is only one way to measure how well an AI is doing, and that is through the amount of funding the computer has in comparison to the amount of funding his enemies have.
AI has to put a strong basis within the resources. It should always try to emulate strategies based on the amount of resources it has. Each unit and building has to react to a situation based on funding.
So, resources is the best way to measure the effectiveness of an AI. The better the AI manages its units, the more resources it'll have. Also, the more resources the AI has at the end of a battle, it'll show how good or bad an AI is during a particular situation.
Of course, in the current implementations of AI. Positioning takes a back step to brute force. The AI is a lot more concerned about the health of each individual unit and striking against yours than trying to position itself.
This is the main thing missing in AI. No one focuses on positioning, therefore... the AI has no way to adapt.
In chess, winning is always guaranteed by how the user positions himself on the board. Good early decisions make strong end games. CW is very similar to chess in that effect in where the AI has to focus on a strong early game.
Regardless the map, we must try and give the computer as much information about the map as possible so it has a greater chance of making a good decision. Coupled with an AI that focuses on keeping it's funding managed, it'll make a very difficult contender.
Everything that has to do with positioning has to do with data. The AI has to get as much data from the map as it can. That includes everything and anything about the map you can think of. Location of sea patches, the current path to the nearest base, the current path to the Enemy HQ. etc.
The more information you feed to the AI, the better off it'll be in the long run. We can then base algorithms on those bits of data in order for the AI to make a smarter decision. Enemy Units, Neutral Units, and Even friendlies should be accounted for. Not to mention the map demographics.
But, not only do we have to focus on the map. But the units that make them up as well. Each unit has a strength and a weakness. It is time to take the focus to them...
In the current implementation of AI, there is a different AI for each unit type. In CW... there is essentially four types of units. Direct Attacker, Indirect Attacker, Capturer, and Transport.
Each one of these units are ran differently from each other and follows its own rules. Also, the priorities of these units is also structured not only for building, but the movement order and striking order as well.
The movement striking order usually goes...
- Indirect -> Direct -> Transports -> Capturers
In this game, each unit is important in order to achieve victory. By following Sun Tsu's reference. The best units are the ones that can strike without retaliation, followed by ones that can strike, followed by civilians.
- Indirect -> Direct -> Capturers -> Transports
However, in terms of units that get the most bank for the buck, the order changes.
- Capturers -> Indirect -> Directs -> Transports
Basically, it means the AI has to not only deal with unit movement & striking, but also how, what, and where to build units. It is a lot of small things the AI must focus on, and there is no easy way to deal with it.
So, it all boils down to this.
- AI needs a lot of data in order to adapt to situations.
- The more data the AI gets from all elements in the map, the better the algorithms for planning will be.
- AI must focus on maximizing the funding potential of all elements it owns at all times.
In order to focus more on the third point, the buildings and units need to be able to maximize thier potential as well.
In current implementations, the computer tries its best to build from all bases, but save the strongest units for the closest base. Or, it'll try to maximize the funds for all the bases.
This is the hardest part of the AI development circle, because decisions made in the building process are even more important than the movement of those units.
If I were to give advice... I'd say the best way to handle it.
- Have a separate AI controller for each building that'll try and prioritize which structure has the most pressure.
- Always try and build from each structure whenever possible, especially from every base
- Keep the focus on building a percentage of each group rather than anything else.
Each unit has its own effect on the map and the decision the opponent will make to it. An AI should not try and be reactive, but instead adaptive. It should always be trying to maximize potential instead of reacting to the opponents actions, unless that action will cause dramatic funding loss to the AI.
Each unit has a basic influence on the map, but instead of the focus being on just creating an AI for each specific unit type, it should be focused on the jobs instead. Each unit can multi-task and has the ability to do different jobs depending on the situation. So, my idea is the AI base its AI off of the actions it can perform, rather than the type of unit it is.
So... instead of a generic AI for lets say...
- Capturers
- Indirect
- Directs
- Transports
We'll have one for...
- Attack
- Wait
- Capture
- Load
- Unload
- etc..
To further define jobs, we can append sub-types to the jobs.
- Attack - Defender
- Attack - Assualt
- Attack - General
- Attack - Striker
That way, the AI will have a choice of how it'll deal with a unit based on the options available rather than the type that it is. It is not every time an infantry should try to capture, or a Tank should try to fire. Priorities can be good for determining how the unit reacts to data.
We have a whole host of information, but sometimes the AI would need a booster. By having the save files as portable replay systems, we can read off of them to figure out which moves and actions caused players to win more.
This is a very rough approach to AI, but those willing to contribute to the research would help create better priorities for AI. The AI can adapt forever in this way and make smarter decisions every single time it plays a map.
However, this'll probably take longer to implement than just to write a straight AI.
Anyway, these are very generalized. But I hope it'll get your head juices flowing for a smarter AI. There is little out there for Tile based AI, but I think a smarter AI is possible as long as you put your minds to it.
Author: eazar001
As mentioned above, strategy games are not only dependent on micromanagement of resources and maximization of unit potential, but also heavily contingent upon positional play as well. As a matter of fact, micromanagement of short-term unit power and movement is commonly referred to in Chess as "tactics." On the other end of the spectrum is broader, more strategic play, that is geared towards long-term acquisition of space, resources, and the eventual procurement of the desired victory. Hence, sometimes the best overall strategic move can be to sacrifice a piece, in order to accelerate acquisition of resources, or a large step towards checkmating the opponent. Micromanagement is important, but grasping the entire portrait of long-term victory is equally important.
Modern Chess engines such as Houdini (link above), have been observed to employ 3-pawn gambits in exchange for hyper-accelerated development and piece quality! This kind of AI behavior was unheard of in the days of brute-force analysis engines. Brute-force is only as good as your hardware allows it to be. An optimal algorithm unites tactics with position; this means sometimes making counter-intuitive moves. Victory cannot be attained without a careful balance between these two concepts. One of the greatest Chess Grand Masters Gary Kasparov, has agreed in his book "How Life Imitates Chess" with Sun Tzu's wise maxim: "Strategy without tactics is the slowest route to victory. Tactics without strategy is the noise before defeat."
Author: JakeSamiRulz
This is a very generalized basic document covering the basics of AI programming. Nothing extremely useful here, but could help beginning programmers understand the concepts behind AI programming.
This very complicated research about AI development actually is very simple. AI is contained within each unit type, and behaviors are given to each type of unit. It then compares the rock/paper/scissors nature of using this method to control unit AI. One of the only documents so far which references dealing with tile-based AW game play.
Some small topics of interest is contained in this book. Some of those smaller topics can be searched for more information.
This is a site for one of the most popular books in AI Development.
This is OpenNero, a testing program for Artificial Intelligence and its many forms.
This is Watson, a super AI made to play against humans using humans native language. It has a lot of videos pertaining to advnaced AI topics, and how to produce AI based on a loosely based connection of facts.
The site in general is indispensable for AI questions in general. Lots can be found out about AI from real game developers articles on this page.
This video (split into 3 parts) speaks about behavior trees used in next-gen gaming. This video breaks down AI building to its core and gives a practical solution for building AI algorithms. All 3 parts are very insightful and recommended.
This document goes a bit more into hierarchical trees in AI building. The concept is very similar to behavior trees.
Pathfinding: Link by chom-chom (appletvdesign)
This game, called Rising Empires, is also a turn-based strategy game written in Java. It has a good laid out plan for how to write an AI, and though it is not too smart yet. It implements a lot of interesting features.
This game, called AI War, is a game that takes a different approach to AI and building AI. They are not looking into the design of books, but rather using basic concepts to create great results. A great amount of information can be found on the page and his blog (located within that link).
Link by MaraSargon
These concepts are commonly used to make AI easier to handle. They can get pretty bulky in terms of size, but the key would be to use the concepts to make the AI process a bit smoother.
Links by urusan
Or you can learn about both the Minimax and Alpha-Beta pruning algorithms by just watching this hour long presentation on the matter. Pretty informative if you do not like to read, or if you are more of a visual learner.
Checkmark Games - Building a Strategy Game AI Series - By Harvicus
- Part I
- Part II
- Part III
- Part IV
- Part V
- Part VI
- Part VII
- Part VIII
- Part IX
- Part IX - B
- Part X
- Part XI
A pretty comprehensive look at Artificial Intelligence by someone who started from scratch trying to understand the concept. It is almost fully complete, and has a lot of source code to weave through to get to the good parts. Overall, it is a pretty extensive guide to understanding tile based AI.
Building a Learning AI off the screen [BRAND NEW]
- https://towardsdatascience.com/creating-ai-for-gameboy-part-4-q-learning-and-variations-2a0d35dd0b1c
By: JakeSamiRulz
This section of the AI development goes a little bit deeper than the previous document, outlining some discrete planning about how to create a more competitive AI. These concepts happened during a string of discussions regarding the subject of making the AI, and I will share a lot of the concepts here.
The most important part of the Custom Wars AI is the ability to mill data from the map. For this current version of AI, we will provide tag functions that'll let the AI gather more information from the map. It should give the AI a stronger basis for making decisions. The goal of the Custom Wars Tactics AI is to be able to adapt to the situation on the turn it is moving, without having the need to look too far ahead, but still remain competitive. Some of the higher end milling tags will be documented below.
These tags focus on checking to see how a unit can reach a current destination. These particular tags can greatly affect how the AI controls its units, and what production facilities it will prioritize.
- Land Path to HQ - Checks to see if there is a land path to the HQTR by land from production factory.
- Sea Path to HQ - Checks to see if there is a dock and/or shoal path to HQTR from production factory.
- Air Path to HQ - Checks to see if there is an accessible airport (APRT) on the map.
- Nearest Neutral Factory - Checks the path to the nearest neutral factory (BASE).
- Nearest Neutral Airport - Checks the path to the nearest neutral airport (APRT).
- Nearest Neutral Seaport - Checks the path to the nearest neutral seaport (SPRT).
- Nearest Enemy Factory - Checks the path to the nearest enemy factory (BASE).
- Nearest Enemy Airport - Checks the path to the nearest enemy airport (APRT).
- Nearest Enemy Seaport - Checks the path to the nearest enemy seaport (SPRT).
These tags focus on telling a unit exactly how much of an object is within its range. These tags can help units figure out whether it is effective to move within a certain spot, or if it needs to rethink the order in which it proceeds with its units.
- Number of Neutral Props - Checks to see how many neutral properties are in ? x ? range of a unit.
- Number of Enemy Props - Checks to see how many enemy properties are in ? x ? range of a unit.
- Number of Enemy Indirects - Checks to see how many indirect units are in ? x ? range of unit.
- Number of Enemy Capturers - Checks to see how many capturing units are in ? x ? range of unit.
- Number of Enemy Directs - Checks to see how many direct units are in ? x ? range of unit.
- Number of Land Units - Checks to see how many land units are in ? x ? range of unit.
- Etc
These tags focus on whether a object is within range of a specific unit or building. It can be useful for unit positioning as well as whether a unit should perform fight or flight in a certain situation.
- Within move range of HQ - Checks to see if an object is within move range of an HQTR.
- Within range of enemy indirect - Checks to see if an object is within attack range of indirect.
- Within range of enemy direct - Checks to see if an object is within attack range of direct.
- Etc
These tags focus on getting the monetary value of items in the map. It can be useful for looking into whether a battle is worth taking, or exactly which units should be built in a location.
- Income percentage - How much of the map income the AI is making (Enemy vs. Allied)
- Total Funding Percentage - How much total funds the AI owns (Enemy vs. Allied)
- Total Damage - How much monetary damage total the AI took (Enemy vs. Allied)
These tags focus on getting statistics of objects in the map. It can be useful for looking into whether a battle is worth taking, or exactly which units should be built in a location.
- Object HP - How much HP an object has
- Object Fuel - How much fuel an object has
- Object Ammo - How much ammo an object has
- Object Capture - How far an object captures a property
- Etc
These tags focus on tracking the metrics of the Commanding Officers and their effects on the battlefield for both the allied and opponent units. It can be useful for figuring out when exactly would be the right time to use a specific power, or also used to delay an opponents CO power.
- Enemy Morale Metric - How many power an enemy CO morale bar has stored up
- Allied Morale Metric - How much power an allied CO morale bar has stored up
The second part of strengthening Custom Wars AI is to speak about the aspect of prioritization. Basically, it is a way of choosing a decision if both decisions have an equal weight on the system. Using this system will improve the pruning cycle, make it easier to implement behaviors, and overall make the AI even faster to implement decisions.
In short, using the advanced tags, we can set a priority to which action has more prevalence in a certain situation. The best time to do this is after a decision tree has reached two or more decisions that are equally in the AI's favor. (Right after the MiniMax and Alpha-Beta Pruning has been reached.) There are a few ways that priorities can be decided.
- Unit Behavior: How the AI unit is programmed to react to a situation (aggressive, passive, etc.)
- Monetary Benefits: How much monetary loss/gain is in the given situation.
- Overcrowding: How important the enemy feels a position is important in the map.
In short, the only time a behavioral tree or behavior pattern becomes used is if the first method of pruning fails to get an exact decision. We can always make sure the AI will be producing the best moves for each unit.
Another use for this system is to choose the order in which units are moved and units from properties are built. We can use the strategy above to choose the order of how the computer deals with actions of each group of units before they are done.
- Priority is given from the list of options currently available.
- Each option is given a weight value based on the number of positive tags given (0 - 10)
- If the weight is tied for two or more items, then the action is randomly chosen.
The AI will always try to do the best course of action, but we can structure the priorities do the AI doesn't act in the same way every time due to random actions. The weight system can essentially keep the AI fresh and allow it to perform different actions during the course of the game. It isn't truly adapting, but it will be close.
Using these techniques will improve the speed in which the AI can make decisions. It can also help influence much more powerful AI algorithms. In terms of raw suggestion, I believe we should have separate AI controllers for the menu, and also for the individual unit decisions.
This AI is for the units, it counts very highly on MiniMax and Alpha-Beta Pruning to make decisions. In the event of a tie, it should consult the behavioral trees for further instruction to help decide the best action.
This AI controls the build order and movement order for units, as well as when to activate a CO power or end the turn. Decisions for this AI is strongly dependent on behavior trees and using the advanced tags to make decisions.
This section will be very short as learning AI would probably be out-of-scope, but here it goes. It is a running idea that a learning AI can be made using the metrics from the users online. These metrics can be taken in tags, like above, and be used to help the AI make a better weighted decision.
This system can be complicated, but the base of it is that you can use user actions to decide how much weight any decision a AI makes has. You can store the decisions made that a particular user is having for each type of unit and use it within the AI.
The AI will adapt and make better decisions mimicking the best players, and will pretty soon be able to make better decisions itself. However, it needs to work in full conjunction with the metrics listed above in order to work.
This concludes the Advanced AI construction excerpt. Most of this information comes from stories and experience working with little robots, as well as studying a bit about Chess AI. Thanks for taking the time to read this excerpt.
Test AI in Javascript.
- Prepare
- Move and Capture,Attack or Wait
- Build Units
- End Turn
Prepare AI stuff.
Every unit of the AI player will make a move. The type of the move will be decided by the following order:
- If you're an infantry
- If a city is nearby and neutral or enemy controlled then capture it
- If a enemy is nearby, then attack it
- Else move to next near city neutral or enemy controlled city
- If you're an indirect unit
- If enemy is in sight then attack directly without move
- If enemy is not in sight but near, then move onto a tile where you can attack next turn
- Else move a bit to the next neutral or enemy controlled city
- Else
- If enemy is in sight then attack directly without move
- If enemy is not in sight but near, then move onto a tile where your distance is lower, but defense possible very high
- Else move a bit to the next neutral or enemy controlled city
The AI should analyse the situation. If there's still some uncaptured cities then it should produce infantries. On top of that the AI should calc how many enemy power exists and react to that. E.g. enemy has a lot of tanks, then build tanks and artilleries.
Simply invokes a shared next turn call.
- Resources
- Tools
- Development
- Design Documents
- Archive