Game and AI - Board Games
Learning:
Artificial Intelligence – Board Games:
Zero Sum: are games where there is a state of wining or losing, with the aim to win - the system is designed in a way that as a player tries to win the game, they are also in the process of making the other player or players lose the game. This can involve information types such as Perfect Information, where a player knows every move that they and the other player or players can make – even if they do not know which move the other player will select. This contrasts with Imperfect Information, which can be a randomised dice roll; due to players not being able to predict or know what the outcome will be.
Board games and especially those that are Zero Sum, make use of Static Evaluation functionality: this gives a score to each move; the AI uses this form of evaluation of compare movements against each other, and make moves that decrease this score for the opposing player; essentially, allowing the AI to make the best move it can, and aim to win the game, while decreasing the opposing players ability to win the game.
Game Trees: nodes represent all possible board positions, allowing AI to strategize and focus on the pathological order that the game will take. However, in games like Chess, and due to pieces ability to move when the board has less pieces on it, some nodes may be replicated in other tree branches; however, there are algorithms that deal with this, such as the MT algorithm. Game Trees are also used for constraint satisfaction games, (Carnegie Mellon University, 2018) would agree that multiplayer card games like Eight queen or Rummy demonstrate this, as well as the use of both game trees, in a imperfect information system. Players use, their knowledge of the cards in their hands and possibility of other players hands to constrain each other while trying to win the game; and increasing their knowledge as cards are swapped.
Core capabilities of AI: Typically, these are tree search algorithms, that associate scores with nodes or grid locations, and run searches over them for the best movements; however, this form of AI also needs more resources such as memory and CPU/ GPU processing to function at its best.
AI techniques:
Mini Max: is an algorithm that makes use of static evaluation functions to maximise the AI movement score, and decrease the score given to the player for movements they make. It is the basic AI for games like Chess. (Millington & Funge, 2009) agrees that Mini Max is considered O(d) in memory, where d is the depth of the tree search; and O(nd) in time, where n is the possible moves at each board position multiplied by the depth of tree. People tend to forget both that O(n) and O(d) are the same thing, and that both O(d) and O(nd) are fast search times considering how big a game tree can be.
MT Algorithm: Solve the issue of dealing with messy game trees, that have huge depths or the same nodes on different branches; by making use of memory to record node locations and analyse for the best movements to make.
Reflections:
Board game AI, is typically defined by tree search algorithms and reactions based on the nodes or branches a game will undeniably take place within. They are resource draining, and question the status quo, where designers have limited CPU resource access, which has typically been reserved for graphic capacities of the game. Min Max and MT algorithms answer queries of using a game tree, with game trees being better suited to a board games; however, a game could be created using FSM or HFSM, and simplify the process with each game object's interaction with each other game objects through the board. Something systemic games such are Far Cry are taking advantage of
References:
Carnegie Mellon University, 2018. Game Trees. [Online] Available at: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Game%20Trees/Game%20Trees.html [Accessed 22 February 2018].
Millington, I. & Funge, J., 2009. Mini Max. In: Artificial Intelligence for games. 2nd ed. Burlington: Morgan Kaufmann, p. 678.
