GKMinMaxStrategist.GetBestMove(IGKGameModelPlayer) Method

Definition

Calculates the IGKGameModelUpdate that provides the greatest advantage to player, constrained by MaxLookAheadDepth.

[Foundation.Export("bestMoveForPlayer:")]
public virtual GameplayKit.IGKGameModelUpdate GetBestMove (GameplayKit.IGKGameModelPlayer player);
abstract member GetBestMove : GameplayKit.IGKGameModelPlayer -> GameplayKit.IGKGameModelUpdate
override this.GetBestMove : GameplayKit.IGKGameModelPlayer -> GameplayKit.IGKGameModelUpdate

Parameters

Returns

Configuration or implementation defects may result in this method returning null.

Attributes

Remarks

This method returns, within the constraints of MaxLookAheadDepth, the IGKGameModelUpdate that maximizes the expected value for player even in the face of optimal play by the opponent.

This is done via a tree-search of possible game states, modeled by IGKGameModel objects. These states are either game-ending (if either IsWin(IGKGameModel, IGKGameModelPlayer) or IsLoss(IGKGameModel, IGKGameModelPlayer) return true) or can generate subsequent moves (see GetGameModelUpdates(IGKGameModelPlayer)). The MaxLookAheadDepth determines the number of possible moves ahead (plies) in the tree are searched.

The underlying 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 MaxLookAheadDepth). The algorithm's space efficiency is O(m).

If multiple IGKGameModelUpdate objects have identical Value values and RandomSource is not null, the IGKGameModelUpdate returned is chosen randomly from those with maximum values. If RandomSource, this method is deterministic and returns the first move calculated with that value. (The order in which moves from a given state are calculated is the same order as that of the moves returned by GetGameModelUpdates(IGKGameModelPlayer).)

This method does not favor shorter outcomes to longer outcomes. For instance, if two moves both produce guaranteed wins, but one requires five rounds to guarantee the win and the other requires just one more round to win, both moves are equally valued and equally likely to be returned by GetBestMove(IGKGameModelPlayer) with a non-nullRandomSource.

Before this call returns, the internal state of the GameModel may be changed transiently, but before this method returns, the state will be returned to it's state prior to the call. To actually apply the best move to the game, developers should call ApplyGameModelUpdate(IGKGameModelUpdate), as shown in the following:

game = new TicTacToe ();

var strategist = new GKMinMaxStrategist {
	GameModel = game,
	MaxLookAheadDepth = 9,
	RandomSource = new GKARC4RandomSource ()
};

while (game.IsActive ()) {
	var bestMove = strategist.GetBestMove (game.GetActivePlayer()) as TicTacToeMove;
	game.ApplyGameModelUpdate (bestMove);
	UpdateDisplay (ticTacToe, bestMove);
	Thread.Sleep (200);
}

In the previous example, the game variable refers to a subtype of IGKGameModel. Note that in this case, the GKMinMaxStrategist is playing both sides. Not shown is that this code is being run in a background T:System.Threading.Tasks.Task and that application code is holding on a reference to the game object so that it is not garbage-collected.

Applies to