Week Four
Introduction:
This week we have covered AI techniques in board games. These include transposition, Minimax, MT algorithms and game design principles. We also dwelt deeper into way point tactics, the use of condensation algorithm in games and how to simulate AI knowledge to make realistic decisions.
Board Games:
Board games primarily use MiniMax and MT algorithms to calculate AI behaviour. There are three main board game designs which include: zero-sum, two player and perfect information. MiniMax algorithm focuses on maximizing the player’s score and minimizing the opponent’s. The recursive algorithm weights the most successful moves, the results of those moves and so on, like in a game tree, until all possible values are calculated or the computer runs out of time, at which point they are sent back up the tree. The computer then picks the move with the best outcome.
Game Design:
Most turn-based board games are limited by time to complete necessary calculations to make the best decision, especially in games like chess, where the number of possible moves might be infinite. Transposition tables can be used to store board positions and the results of search algorithms to avoid searching the same position again. The memory-enhanced test (MT) uses transposition tables to jump between search tree branches to consider the optimal route first. Ultimately, it uses stored memory to search through the entire tree to make the best decision.
1. Zero-sum games mean that you win when your opponent loses. In some, winning might not be guaranteed (e.g. casino games). In games other than two player, multiple people may lose which might make it useful to gang up on the strongest player. Non-zero-sum games are similar, except all players can win.
2. Perfect information games means that a player does not know what the opponent might do but he knows the result of every move (e.g. chess). Imperfect information games are similar, but they involve a dice roll which makes the game unpredictable.
Lab:
Chess is an example of perfect information board game. It is a two player zero-sum game where you win only when the other player losses. Although, we do not know what the player will do next, we know the results of every move.
Computers tend to find it easier to play deep trees with a small branch factor. Branch factor defines the number of possible moves that the player can make on his turn. Whereas, the depth of a tree defines the number of moves the player can make in the entire game. In a game like chess, this number is infinite (without the 50 move rule). This means the computer has to make an infinite number of calculations to account for each scenario. However, the computer cannot perform all of the calculations and has to leave a number of moves unaccounted for. Instead, a partial-tree is searched in the given time frame from the current position down deeper in the tree.
Coursework:
Although I am not developing a board game, and the discussed techniques won't be useful for my game, transposition has made me consider the 'memory' of AI. My game has to incorporate 'senses' so that the AI can made realistic decisions based on its environment. By storing values (e.g. which rooms have been checked - where the intruder is not), the AI can make appropriate decisions.
Tactical Locations:
A way point is a single location in the game. It can represent a cover position or a defensive location. They are used in pathfinding algorithms as intermediate points to calculate a strategic route, also known as rally points. In first person shooters way points are chosen based on a specific AI goal. A sniper might want cover but also wants a clear line of sight. These are referred to as compound tactics. These tactical locations can be linked and used when cover, exit, attack positions are needed. It enables for more dynamic and sophisticated algorithm which analyses the best path based on the environment and scenario. Although, this technique can become complicated with the introduction of more way points.
To decide on the best way point, it uses a similar process as board games. It weighs the values of the best and worst way points and the algorithm chooses the best suited one. This technique can be used within a decision making tree. For example, if a soldier needs to reload a weapon, the algorithm will first take him in a good cover position where the reload animation would be played. It creates better decisions and adds to the immersion of the game. Although it can use up more memory.
Lab:
Tactical locations are used in games to allow AI determine the best escape routes and cover positions on the map. Typically, certain locations are equated with a value which represents how good the particular location is. It is not enough to only pick the best 50 locations, as it may be that there are many points which are concentrated and the locations that might be more important are overlooked.
The Condensation Algorithm is used to overcome this. It condenses locations in close proximity to one another. To do this, a dense grid is used. First, the grid is tested to see if each space can be occupied by the AI. For example, spaces which are already occupied by obstacles or walls are removed. The remaining locations are passed through the threshold test. Each location that does not meet this threshold are discarded at the outset. It is worth to keep in mind that the threshold should be low enough for more locations to pass than needed. For example, in a room where cover is scarce, any cover is highly valued which will automatically pass through the threshold. However, more locations might be needed, which will remain for the condensation algorithm to sort.
The AI in chess acts just like you do. It overlooks the chess board and assesses the best chess strategy to defend the king and to attack the opponent. The AI is constantly looking for a way to improve the defenses and regroup to protect. creates formation in combination of all the pieces to protect the king when king is in danger and in attack formation when the AI is winning or even.
Coursework:
Tactical locations will be used in my game to determine the best routes for the AI to follow. These will include lit areas, where the AI can see an intruder clearly. If the AI has to flee, he will do so by planning out an escape route (e.g. where the other guards are patrolling) for backup. Due to the simplicity of the game, the condensation algorithm might not be worth implementing to save processing power and memory.
Knowledge:
To develop a smart AI, it must do more than react to events. It must plan and remember information about the world. To do this, the AI has to gather data about the world. It may be sights or sounds that the AI has been exposed to, and act upon that knowledge. For example, the AI might know that the shooter fired a gun six times. He knows that the gun can only have six bullets. So the shooter is either reloading his gun or is out of ammo. The AI might then report this to his squad members to close in on him. There are four main types of memory:
1. Working memory: AI reacts to current events as they are happening.
2. Short-term memory: The AI might remember where the intruder was last heard, but this will decay with time. Requires small use of memory but creates realism.
3. Long-term memory: The AI remembers events for a long time, using up more memory an
4. Episodic memory: Memory lasts for an entire episode/level in a game. Poses heavier consequences to the player and provides the most realistic simulation. However, it requires heavy memory resources.
The information can be taken and assessed based on how confident the AI is about the knowledge of certain data (e.g. sure where the sound came from), the assessment of salience and AI needs (e.g. healing, ammo). Most importantly, the realistic behaviour of AI may lie in prediction of future events based on previously acquired knowledge. For example, if the civilian is armed with a weapon and is pointing it at someone - he means harm. Although, these techniques improve the immersion and experience of a game, it might also be inefficient and produce inconsistent results.
Lab & Coursework:
My game assignment focuses on stealth which relies solely upon light and sound in the environment. The guard AI will use short-term memory to store this data which will enable the guards to enter the search state as discussed in previous blogs. Any sounds that the guard hears will be matched with a confidence rating to determine if the guard should pursue it. The AI should also remember where the intruder was last seen and use stored way points to determine the best location for the intruder to hide behind. Is he hiding behind a crate? The guard would be able to predict intruder behaviour and act accordingly. This will create an immersive game and make the game more difficult to complete. Each of AI's observations will be represented with the use of sound and animation changes. For example, of a guard hears something, he will begin to walk slower to make him appear alert. Knowledge will be used for the AI to notice if a light has been distinguished or an object has been knocked over. This will put the guard in a search state automatically even when no sound was heard.
References:
1. Millington, I. and Funge, J., 2012. Artificial intelligence for games. CRC Press.
