# GameplayKit Namespace

The GameplayKit namespace provides classes for high-level game-playing mechanics such as pathfinding, rules engines, and AI opponents.

## Remarks

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.

## AI Opponent

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.

The GKMinMaxStrategist does not need to be subclassed by the developer. Rather, the developer implements three interfaces and passes these to the GKMinMaxStrategist:

ClassPurpose
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 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.

The key method of the GKMinMaxStrategist is GKMinMaxStrategist.GetBestMove. When this method is called, the following sequence of calls occurs:

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.

## Classes

TypeReason
GKAgentA GKComponent that can move and has goals.
GKAgent2DA GKAgent whose movement is restricted to two dimensions.
GKAgent3DA 3D agent that responds to goals.
GKAgentDelegateDelegate object that provides methods relating to synchronizing the state of a GKAgent with external constraints, goals, and representations.
GKAgentDelegate_ExtensionsExtension methods to the IGKAgentDelegate interface to support all the methods from the GKAgentDelegate protocol.
GKARC4RandomSourceRandom generator based on the ARC4 algorithm. Often a good choice.
GKBehaviorA collection of GKGoal objects and weights, together defining a cohesive game behavior.
GKBillowNoiseSourceA GKCoherentNoiseSource whose output is similar to Perlin noise but with more rounded features.
GKBoxAn axis-aligned rectangular three-dimensional box.
GKCheckerboardNoiseSourceA GKNoiseSource whose output consists of alternating black and white squares.
GKCircleObstacleA GKObstacle defined by a location and a radius.
GKCoherentNoiseSourceA GKNoiseSource whose output varies smoothly and continuously.
GKComponentAbstract 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.
GKCompositeBehaviorA GKBehavior that combines other GKBehavior objects.
GKConstantNoiseSourceA GKNoiseSource whose output is a single value.
GKCylindersNoiseSourceA GKNoiseSource whose output consists of concentric cylindrical shells. Appropriate for wood-grain textures.
GKDecisionNodeAn element in a GKDecisionTree.
GKDecisionTreeA tree of questions, answers, and actions.
GKEntityA type that is composed of a number of GKComponent objects in an Entity-Component architecture.
GKGameModelDescribes gameplay in a way that can be optimized with a GKMinmaxStrategist.
GKGameModel_ExtensionsExtension methods to the IGKGameModel interface to support all the methods from the GKGameModel protocol.
GKGameModelPlayer_ExtensionsExtension methods to the IGKGameModelPlayer interface to support all the methods from the GKGameModelPlayer protocol.
GKGaussianDistributionA GKRandomDistribution that produces a Gaussian (normal) distribution.
GKGoalInfluences the movement of one or more GKAgent objects.
GKGraphA mathematical graph used for navigability and pathfinding.
GKGraphNodeThe base class for nodes in a GKGraph.
GKGraphNode2DA GKGraphNode that contains a 2D floating-point position.
GKGraphNode3DA GKGraphNode that exists in three-dimensional space.
GKGridGraphA GKGraph in which movement is constrained to an integer grid
GKGridGraphNodeA GKGraphNode that contains a 2D integer position.
GKHybridStrategistA IGKStrategist that combines Monte Carlo Tree Search and local search via MinMax.
GKLinearCongruentialRandomSourceA fast GKRandomSource. Low-order bits are somewhat less random than in GKARC4RandomSource.
GKMersenneTwisterRandomSourceA slow GKRandomSource with very good randomness.
GKMeshGraph<NodeType>
GKMeshGraphTriangulationModeHolds options for how nodes should be generated in a GKMeshGraph.
GKMinMaxStrategistGame AI that evaluates potential game states, scores them, and attempts to maximize it's own score while minimizing it's opponents.
GKMonteCarloStrategistA strategist that reaches a solution that is probably close to optimal in a deterministic amount of time.
GKNoiseUses a GKNoiseSource to procedurally generate an infinite three-dimensional noise field.
GKNoiseMapSlices a finite, two-dimensional rectangle from a GKNoise object's infinite, three-dimensional noise field.
GKNoiseSourceAbstract base class for procedural noise generators.
GKNSPredicateRuleA GKRule that uses a NSPredicate to determine if it's action should be called.
GKObstacleAbstract class representing areas that GKAgent objects cannot traverse.
GKObstacleGraphA GKGraph that generates a space-filling network for representation, allowing smooth, but inefficient, paths.
GKObstacleGraph<NodeType>
GKOctree<ElementType>A data structure that efficiently organizes three-dimensional elements.
GKOctreeNodeA node in a GKOctree. Automatically managed by the GKOctree as objects are added and removed.
GKPathHolds a 2D polygonal path that can be followed by a GKAgent.
GKPerlinNoiseSourceA GKCoherentNoiseSource that generates improved Perlin noise.
GKPolygonObstacleA GKObstacle with an arbitrarily complex shape.
GKQuadTreeA data structure that efficiently organizes objects in two-dimensional space.
GKRandomDistributionDefines a probability distribution. This class defines a uniform distribution (all values equally likely), while subclasses GKGaussianDistribuition and GKShuffledDistribution provide different likelihoods.
GKRandomSourceBase class for game-appropriate pseudo-random number generators. Do not use for cryptographic or security purposes.
GKRidgedNoiseSourceA GKCoherentNoiseSource whose output is similar to Perlin noise but with sharp boundaries.
GKRTree<ElementType>A data structure for efficiently searching objects arranged in two-dimensional space.
GKRTreeSplitStrategy
GKRuleA single element, comprising a predicate and an action, that represents a discrete rule in a GKRuleSystem.
GKRuleSystemMaintains a collection of GKRule objects, activating them as appropriate.
GKSceneAssociates GameplayKit objects with a SpriteKit SKScene.
GKSCNNodeComponentA GKComponent that operates on a SCNNode.
GKShuffledDistributionA GKRandomDistribution that shuffles a collection in a manner that makes sequences of similar values unlikely (minimal hot/cold streaks).
GKSKNodeComponent
GKSphereObstacleA GKObstacle that is an impassable spherical volume.
GKSpheresNoiseSourceA GKNoiseSource whose output consists of concentric shells. Appropriate for wood-grain textures.
GKStateAn abstract class representing a discrete state in a GKStateMachine.
GKStateMachineHolds GKState objects and manages transitions between them.
GKTriangle
GKVoronoiNoiseSourceA GKNoiseSource whose output divides space into cells surrounding seed points. Appropriate for crystalline textures.
IGKAgentDelegateInterface representing the required methods (if any) of the protocol GKAgentDelegate.
IGKGameModelThe current game state. Particularly useful in conjunction with GKMinMaxStrategist.
IGKGameModelPlayerA uniquely-identified player of a game. Developers must implement GKGameModelPlayer.GetPlayerId.
IGKGameModelUpdateA valid game move. The minimal data necessary to transition a valid IGKGameModel into a valid subsequent state.
IGKRandomInterface for GameplayKit pseudo-random number generators.
IGKSceneRootNodeType
IGKStrategistInterface for a game strategist (AI).
NSArray_GameplayKit
SCNNode_GameplayKit
SKNode_GameplayKit