Introduced in iOS 9, GameplayKit provides classes for high-level game-playing mechanics such as pathfinding, rules engines (both fuzzy and classical), and a prebuilt AI opponent in the form of GKMinMaxStrategist.
The minimax theorem, first stated by John von Neumann in 1928, holds that in a two-person, zero-sum, game with finite strategies, there exists some optimal play (or plays) that simultaneously maximizes the expected value for the current player and minimizes the expected value for the opposing player. In other words, in such games, there is a "best move" (although, of course, even the best move might lead to a loss or a tie, depending upon the state of the game).
GameplayKit implements the minimax algorithm in its GKMinMaxStrategist class and related classes (especially GKGameModel). The GKMinMaxStrategist is an optimized version of the minimax algorithm that uses memory efficiently and pares the search-tree at terminal nodes, but developer's should be aware that the algorithm can be costly: minimax algorithm's time efficiency is O(b^m) where b is the number of states in a single look-ahead "ply" and m is the number of plies searched (see MonoTouch>GameplayKit.GKMinMaxStrategist.MaxLookAheadDepth). The algorithm's space efficiency is O(m).
The minimax theorem applies to a very large number of games, from trivial ones such as Nim and Tic-Tac-Toe, to complex games such as Chess and Go. However, games such as Chess and Go have so many possible game states and plies that the expense of calculating the optimal move quickly becomes astronomical. Even in such cases, the GKMinMaxStrategist may be used to evaluate several hundred or thousand moves and, if the developer can accurately program an estimate of the strength or weakness of a given game state, produce a strong opponent.
|IGKGameModel||Developers implement this interface in order to model the game and it's current state. In a board game, for instance, this will typically be the board and all pieces and a reference to the active player. In addition, if it is to be used with GKMinMaxStrategist, this class must implement the functions that describes potential moves (GKGameModule.GetGameModelUpdates) and evaluates them in terms of desirability (GKGameModel_Extensions.IsWin, GKGameModel_Extensions.IsLoss, GKGameModel_Extensions.GetScore).|
|IGKGameModelUpdate||This class describes a game "move" and contains enough information to transition the Monotouch.GameplayKit.IGKGameModel between it's current state and a valid new one. Many thousand instances of this class may be required by the GKMinMaxStrategist, so the developer should take care to make it lightweight.|
|IGKGameModelPlayer||The GKMinMaxStrategist relies on the value of IGKGameModelPlayer.GetPlayerID) to distinguish between players.|
First, the IGKGameModelPlayer objects are retrieved. Then, starting with the current game state, and while the ply depth is less than GKMinMaxStrategist.MaxLookAheadDepth, the set of legal possible moves from the current state is returned by GKMinMaxStrategist.GetGameModelUpdates. Then, for each of these moves, it may be necessary for the GKMinMaxStrategist to allocate new memory; if so, GKMinMaxStrategist.Copy is called. Then, on one of the many GKGameModel objects being managed by the GKMinMaxStrategist, a potential move is executed with calls to IGKGameModel.SetGameModel and IGKGameModel.ApplyGameState.
The GKMinMaxStrategist then evaluates each of the potential moves by calling, first, GKGameModel_Extensions.IsWin and GKGameModel_Extensions.IsLoss. If either of these methods returns true, the GKMinMaxStrategist marks that game state as a terminal node and will not attempt to investigate it further in later plies. If neither method returns true, though, the method GKGameModel_Extensions.Score is called.
The developer should write a GKGameModel_Extensions.Score method to return a value between GKGameModel.MinScore (-16777216) and GKGameModel.MaxScore (+16777216). Higher values represent game states that are better for the IGKGameModel.GetActivePlayer. In simple games where the entire game tree can be searched because GKGameModel_Extensions.IsWin or GKGameModel_Extensions.IsLoss always return true within GKMinMaxStrategist.MaxLookAheadDepth, the GKGameModel_Extensions.Score method can simply return 0, because the GKMinMaxStrategist can calculate the best move based on the winning and losing moves. However, this is only likely to be the case in quite-easy games and, in general, crafting a well-performing GKGameModel_Updates.Score function will require both game-playing and programming expertise. In terms of programming, the GKGameModel_Updates.Score method is called many times during the search of the game-tree and needs to be efficient, as well as accurate.
Developers should note that the GKMinMaxStrategist may allocate many copies of IGKGameModelPlayer and IGKGameModel as well as many IGKGameModelUpdate objects. Developers should rely on value, not reference, equality, and should exercise care when it comes to these objects manipulating global or static state.
|GKAgent||A GKComponent that can move and has goals.|
|GKAgent2D||A GKAgent whose movement is restricted to two dimensions.|
|GKAgentDelegate||Delegate object that provides methods relating to synchronizing the state of a GKAgent with external constraints, goals, and representations.|
|GKAgentDelegate_Extensions||Extension methods to the IGKAgentDelegate interface to support all the methods from the GKAgentDelegate protocol.|
|GKARC4RandomSource||Random generator based on the ARC4 algorithm. Often a good choice.|
|GKBehavior||A collection of GKGoal objects and weights, together defining a cohesive game behavior.|
|GKCircleObstacle||A GKObstacle defined by a location and a radius.|
|GKComponent||Abstract superclass for components, including GKAgent objects, in an Entity-Component architecture (see remarks).|
|GKComponentSystem<TComponent>||Holds GKComponent objects of a specific subtype and updates them periodically.|
|GKEntity||A type that is composed of a number of GKComponent objects in an Entity-Component architecture.|
|GKGameModel||Describes gameplay in a way that can be optimized with a GKMinmaxStrategist.|
|GKGameModel_Extensions||Extension methods to the IGKGameModel interface to support all the methods from the GKGameModel protocol.|
|GKGameModelPlayer_Extensions||Extension methods to the IGKGameModelPlayer interface to support all the methods from the GKGameModelPlayer protocol.|
|GKGaussianDistribution||A GKRandomDistribution that produces a Gaussian (normal) distribution.|
|GKGoal||Influences the movement of one or more GKAgent objects.|
|GKGraph||A mathematical graph used for navigability and pathfinding.|
|GKGraphNode||The base class for nodes in a GKGraph.|
|GKGraphNode2D||A GKGraphNode that contains a 2D floating-point position.|
|GKGridGraph||A GKGraph in which movement is constrained to an integer grid|
|GKGridGraphNode||A GKGraphNode that contains a 2D integer position.|
|GKHybridStrategist||A IGKStrategist that combines Monte Carlo Tree Search and local search via MinMax.|
|GKLinearCongruentialRandomSource||A fast GKRandomSource. Low-order bits are somewhat less random than in GKARC4RandomSource.|
|GKMersenneTwisterRandomSource||A slow GKRandomSource with very good randomness.|
|GKMinMaxStrategist||Game AI that evaluates potential game states, scores them, and attempts to maximize it's own score while minimizing it's opponents.|
|GKMonteCarloStrategist||A strategist that reaches a solution that is probably close to optimal in a deterministic amount of time.|
|GKNSPredicateRule||A GKRule that uses a NSPredicate to determine if it's action should be called.|
|GKObstacle||Abstract class representing areas that GKAgent objects cannot traverse.|
|GKObstacleGraph||A GKGraph in which movement is constrained to a plane, perhaps with impassible GKObstacles.|
|GKPath||Holds a 2D polygonal path that can be followed by a GKAgent.|
|GKPolygonObstacle||A GKObstacle with an arbitrarily complex shape.|
|GKQuadTreeNode||A node in a quadtree.|
|GKRandomDistribution||Defines a probability distribution. This class defines a uniform distribution (all values equally likely), while subclasses GKGaussianDistribuition and GKShuffledDistribution provide different likelihoods.|
|GKRandomSource||Base class for game-appropriate pseudo-random number generators. Do not use for cryptographic or security purposes.|
|GKRule||A single element, comprising a predicate and an action, that represents a discrete rule in a GKRuleSystem.|
|GKRuleSystem||Maintains a collection of GKRule objects, activating them as appropriate.|
|GKShuffledDistribution||A GKRandomDistribution that shuffles a collection in a manner that makes sequences of similar values unlikely (minimal hot/cold streaks).|
|GKState||An abstract class representing a discrete state in a GKStateMachine.|
|GKStateMachine||Holds GKState objects and manages transitions between them.|
|IGKAgentDelegate||Interface representing the required methods (if any) of the protocol GKAgentDelegate.|
|IGKGameModel||The current game state. Particularly useful in conjunction with GKMinMaxStrategist.|
|IGKGameModelPlayer||A uniquely-identified player of a game. Developers must implement GKGameModelPlayer.GetPlayerId.|
|IGKGameModelUpdate||A valid game move. The minimal data necessary to transition a valid IGKGameModel into a valid subsequent state.|
|IGKRandom||Interface for GameplayKit pseudo-random number generators.|
|IGKStrategist||Interface for a game strategist (AI).|