Game and AI - Week 4 Lab 1
Binary Tree – suitable algorithms
Game: Connect four, is a Zero-Sum game in which the player either wins or loses, whilst having the capacity for a draw, there is no score system. Players use piece that are to opposing colours that they must drop into a grid to get an broken line of four pieces to win. This means algorithms are essentially going to be search algorithms, the need to quickly go through a space of positions that unlike a binary tree have 4 leaf’s per node until reaching the lower end of the (rather deep) tree, as shown in the tree diagram drawn.
It is a Perfect Information game: because players know the full scope of any move they can make with pieces, even if they don’t know what move the other player will make, they know the choices they have as well. With a medium branching factor of 16, which does decreases over time, meaning the difficulty of the game is not that high; and there is not the possible of an infinite turns, such as chess where the more piece taken can result in a game that never ends.
Difficulties: the depth of trees and branches increases in order of magnitudes, the AI will need to find the correct leaf and keep track of each pathological leaf branch and node, as well as the positions players pieces take in the game; this in itself requires the AI to require sufficient CPU resources, and memory.
Appropriate Algorithms: Mini Max is best, suited as there are no duplicated transitions ( game object movements), and it uses the static evaluation of player moves to find the position which gives the lowest score to the move the player made - allowing the AI to chose the best move for decreasing the players ability to win the game. This algorithm is response based,
responding to player moves, the foundation of Static Evaluation - scoring player moves between -1 and 1, to place value on the moves made, allowing the AI to evaluate moves, and find suitable moves that lead to a state of winning. And using the Transposition Table, to record results and position in the game tree, preventing completely new tree searches per turn. Finally AB Pruning, results in keeping the best score a player can achieve in mind.
Tactical AI week 4 lab
Condensation Algorithm: in the gaming industry is designed to condense checks, for automatically placing waypoints in a game across a level; for example, in a similar fashion water is formed from other liquids by condensation, a list of waypoints and their strategic use, can be condensed with this algorithm. This is done by evaluating, the specific tactic for the way point - such as the level of shadow a waypoint is in, with a scoring system that evaluates the level of shadow the waypoint is in, waypoint proximity to one another and changing the values of way points accordingly, such that waypoints best suited to shadowed areas have higher values, and those least suited to shadow given lower values per shadow tactic. Additionally, whether the waypoint position is valid (e.g. can the player access the point) is also evaluated. (Millington & Funge, 2009) would agree with the above. Additionally the exits and rooms Waypoint are next to and in can also be part of a strategic calculation - especially if the aim is sniping, something prevalent in most First Person Shooter (FPS) games.
Group coordination in games: animal simulations and city streets with traffic and pedestrians, tend to use a form of group coordination, rendering specific groups at specific times with the according density.
Hierarchies and message passed: for instance in grand theft auto, you could have criminal mob bosses, lieutenants and grunts, and pedestrians, alongside a grid and influence map, that allows navigation and values placed on position; leading to higher level messages such as attack the player, and with Lieutenants having extra options for passing across to other lieutenants, and down how to attack to grunts, and all enemies communicating position and attack data via broadcasts. With influence maps changing individual decisional making, and message context.
References:
Millington, I. & Funge, J., 2009. Artificial Intelligence for Games. 2nd ed. Burlington: Morgan Kaufmann.
