Class Minimax<GS, M, D>

Class for performing a minimax search.

Probability based searches coming soon

Usage

See the Negamax documentation for general usage, its is very similar.

The differences are as follows:

The optimal flag is not supported (and won't be)
The pruneByPathLength, randomBest and randomWeight options are not yet available.
In the CreateChildNode callback, the NodeAim must be explicitly set according to the players turn. This allows repeated turns, i.e setting it as MAX two turns in a row.

Type Parameters

GS

The object representing the state of the game
M

The object representing a move in the game
D

Extra data used in evaluation not suitable for storing in the gamestate

Hierarchy

SearchTree<GS, M, D>
- Minimax

Constructors

constructor

new Minimax<GS, M, D>(root: Node<GS, M, D>, opts?: MinimaxOpts): Minimax<GS, M, D>
Type Parameters
- GS
- M
- D
Parameters
- root: Node<GS, M, D>
  
  Root node to start the tree from
- opts: MinimaxOpts = ...
  
  Optional options to configure the minimax algorithm
Returns Minimax<GS, M, D>
Overrides SearchTree<GS, M, D>.constructor
- Defined in minimax/minimax.ts:34

Methods

`Protected` evalDepth

evalDepth(depth?: number): MinimaxResult<M>
Returns
The result of the search
Parameters
- depth: number = ...
  
  Overide the depth property in depth
Returns MinimaxResult<M>
Overrides SearchTree.evalDepth
- Defined in minimax/minimax.ts:43

`Protected` minimax

minimax(node: Node<GS, M, D>, depth: number, alpha: number, beta: number): SearchExit
Implements the minimax algorithm up to a given depth of search. Recursively calls itself until depth is 0 or LEAF node is reached and evaluated.

Node values and best child are chosen according to the NodeAim of the parent nodes.

Returns early if timeout occurs

Returns
Reason for returning.
Parameters
- node: Node<GS, M, D>
  
  Node to evaluate or search children
- depth: number
  
  Depth to search from this node
- alpha: number
  
  minimum guaranteed score
- beta: number
  
  maximum guaranteed score from minimising player
Returns SearchExit
- Defined in minimax/minimax.ts:79

`Protected` minimumBestChild

minimumBestChild(node: Node<GS, M, D>, depth: number): {
exit: SearchExit;
best: undefined | Node<GS, M, D>;
}
Goes through all of nodes children to find child with minimum inherited value
Parameters
- node: Node<GS, M, D>
- depth: number
Returns {
exit: SearchExit;
best: undefined | Node<GS, M, D>;
}
- exit: SearchExit
- best: undefined | Node<GS, M, D>
- Defined in minimax/minimax.ts:130

`Protected` maximumBestChild

maximumBestChild(node: Node<GS, M, D>, depth: number): {
exit: SearchExit;
best: undefined | Node<GS, M, D>;
}
Goes through all of nodes children to find child with minimum inherited value
Parameters
- node: Node<GS, M, D>
- depth: number
Returns {
exit: SearchExit;
best: undefined | Node<GS, M, D>;
}
- exit: SearchExit
- best: undefined | Node<GS, M, D>
- Defined in minimax/minimax.ts:153

`Protected` alphaBetaBestChild

alphaBetaBestChild(node: Node<GS, M, D>, depth: number, alpha: number, beta: number): {
exit: SearchExit;
best: undefined | Node<GS, M, D>;
}
Find the best child of a node using alpha beta pruning

Returns
Reason for exit and opional best child
Parameters
- node: Node<GS, M, D>
  
  Node to find best child of
- depth: number
  
  Depth to limit search to
- alpha: number
  
  Current alpha value
- beta: number
  
  current beta value
Returns {
exit: SearchExit;
best: undefined | Node<GS, M, D>;
}
- exit: SearchExit
- best: undefined | Node<GS, M, D>
- Defined in minimax/minimax.ts:180

`Protected` assignNodeValue

assignNodeValue(node: Node<GS, M, D>, leaf: boolean): SearchExit
Returns
reason for exit. Either FULL_DEPTH or DEPTH.
Parameters
- node: Node<GS, M, D>
  
  Node to assign value to
- leaf: boolean
  
  true if node is a leaf
Returns SearchExit
- Defined in minimax/minimax.ts:235

`Protected` evalDeepening

evalDeepening(): SearchResult<M>
Searches the tree repeatedly, incrementing the depth each time. Returns after reaching target depth, or early if tree is complete or time exceeded.

Relevant options
- depth | Maximum depth to search for. 0 for unlimited
- timeout | Maximum time to search for. 0 for unlimited
- pruning
- initialDepth
- genBased (Only if pruning is not NONE)
- presort
Returns
The result of the search
Returns SearchResult<M>
Inherited from SearchTree.evalDeepening
- Defined in tree/searchtree.ts:56

evaluate

evaluate(): SearchResult<M>
Search the tree according to the options specified by the options (opts).

Returns
Result from the tree search

Returns SearchResult<M>
Inherited from SearchTree.evaluate
- Defined in tree/searchtree.ts:94

depthCallback

depthCallback(tree: SearchTree<GS, M, D>, result: SearchResult<M>): void
Called during deepening search between each depth. Does nothing until overidden
Parameters
- tree: SearchTree<GS, M, D>
- result: SearchResult<M>
Returns void
Inherited from SearchTree.depthCallback
- Defined in tree/searchtree.ts:124

`Protected` checkExpiry

checkExpiry(): boolean
Checks if expiry is enable and has happened

Returns
true if time has expired, otherwise false

Returns boolean
Inherited from SearchTree.checkExpiry
- Defined in tree/searchtree.ts:132

`Protected` checkNodeLimit

checkNodeLimit(): boolean
Checks if node limit is enabled and returns true if it has been exceeded, otherwise returns false.

Returns boolean
Inherited from SearchTree.checkNodeLimit
- Defined in tree/searchtree.ts:148

`Protected` getChildren

getChildren(node: Node<GS, M, D>): Iterable<Node<GS, M, D>>
Returns either the array of node children or a generator which may create children on the fly Also presorts children if enabled

Returns
An iterable for going through children of node
Parameters
- node: Node<GS, M, D>
  
  Node to return an iterable of children
Returns Iterable<Node<GS, M, D>>
Inherited from SearchTree.getChildren
- Defined in tree/searchtree.ts:166

`Protected` sortChildren

sortChildren(node: Node<GS, M, D>, reverse?: boolean): Node<GS, M, D>
Sorts the child nodes of given parent Node according to inherited value. Sort is descending by default

Sorts using the method specififed in opts.SearchOpts.SortMethod.

Returns
The child with the highest value
Parameters
- node: Node<GS, M, D>
  
  parent Node of children to sort
- Optional reverse: boolean
  
  Optionally sort ascending instead
Returns Node<GS, M, D>
Inherited from SearchTree.sortChildren
- Defined in tree/searchtree.ts:198

`Protected` randomBestChild

randomBestChild(node: Node<GS, M, D>): Node<GS, M, D>
Selects from the nodes children which all have an equal best value (and depth) Uniform random weighting Node.child must already represent best child

Returns
randomly selected best child with same value as best
Parameters
- node: Node<GS, M, D>
  
  Parent to select best child from
Returns Node<GS, M, D>
Inherited from SearchTree.randomBestChild
- Defined in tree/searchtree.ts:234

`Protected` randomWeightedChild

randomWeightedChild(node: Node<GS, M, D>, weight: number): Node<GS, M, D>
Selects best child from nodes children according to the weighting factor
Parameters
- node: Node<GS, M, D>
- weight: number
Returns Node<GS, M, D>
Inherited from SearchTree.randomWeightedChild
- Defined in tree/searchtree.ts:252

`Protected` routeGen

routeGen(node: Node<GS, M, D>): Generator<Node<GS, M, D>, any, unknown>
Generator that yields all the nodes along the optimal path, starting from and including node
Parameters
- node: Node<GS, M, D>
Returns Generator<Node<GS, M, D>, any, unknown>
Inherited from SearchTree.routeGen
- Defined in tree/searchtree.ts:287

`Protected` optimalMoveGen

optimalMoveGen(node: Node<GS, M, D>): Generator<M, any, unknown>
Generator that yields all the moves along the optimal path
Parameters
- node: Node<GS, M, D>
Returns Generator<M, any, unknown>
Inherited from SearchTree.optimalMoveGen
- Defined in tree/searchtree.ts:295

getOptimalMoves

getOptimalMoves(): M[]
Function to return the list of moves starting from the root that are the 'optimal' path.

Must be called after evaluating the tree.

Returns
A list of moves from the active root Node that represent the optimal sequence through the game.

Returns M[]
Inherited from SearchTree.getOptimalMoves
- Defined in tree/searchtree.ts:310

removeNodes

removeNodes(): number
Returns number
Inherited from SearchTree.removeNodes
- Defined in tree/searchtree.ts:314

`Protected` removeNonBestNodes

removeNonBestNodes(node: Node<GS, M, D>, depth: number, keep: boolean): number
Recursively go through node and its children removing all nodes that are not best
Parameters
- node: Node<GS, M, D>
- depth: number
- keep: boolean
Returns number
Inherited from SearchTree.removeNonBestNodes
- Defined in tree/searchtree.ts:324

`Protected` createChildren

createChildren(node: Node<GS, M, D>): boolean
Generates all children of given node. Does nothing if branches and children already present

Returns
true if nodes created, false if already existed
Parameters
- node: Node<GS, M, D>
  
  Node to create children for
Returns boolean
Inherited from SearchTree.createChildren
- Defined in tree/tree.ts:52

`Protected` createTree

createTree(node: Node<GS, M, D>): void
Creates the full game tree recursively starting from given node
Parameters
- node: Node<GS, M, D>
  
  Parent node
Returns void
Inherited from SearchTree.createTree
- Defined in tree/tree.ts:83

createFullTree

createFullTree(): void
Creates the full game tree starting from activeRoot.

Uses the GetMoves and CreateChildNode callbacks.

Returns void
Inherited from SearchTree.createFullTree
- Defined in tree/tree.ts:100

`Protected` childGen

childGen(node: Node<GS, M, D>): Generator<Node<GS, M, D>, any, unknown>
Generate all the children of node, starting from those already created
Parameters
- node: Node<GS, M, D>
  
  Node to create children for
Returns Generator<Node<GS, M, D>, any, unknown>
Inherited from SearchTree.childGen
- Defined in tree/tree.ts:109

Properties

`Protected` expired

expired: boolean = false

Tracks whether a searched has expired due to time

`Protected` expireTime

expireTime: number = 0

Time the search will expire. 0 disables expiry

`Protected` fullDepth

fullDepth: boolean = true

Flags that full depth has not been reached when set to false

`Protected` presortEnable

presortEnable: boolean = false

Enables presort of children internally

`Protected` outcomes

outcomes: number = 0

Number of leaf or depth = 0 reached during current call

`Protected` nodeLimitExceeded

nodeLimitExceeded: boolean = false

Flag set if node limit has been reached

opts

opts: SearchOpts = ...

EvaluateNode

EvaluateNode: EvaluateNodeFunc<GS, M, D> = ...

Callback to evaluate the value of gamestate attached to node

root

root: Node<GS, M, D>

Original root when tree was created

activeRoot

activeRoot: Node<GS, M, D>

Active root used for the creation and searching of tree. Set to root in constructor.

nodeCount

nodeCount: number = 0

Number of nodes in tree

leafCount

leafCount: number = 0

Number of leaf nodes in tree

`Protected` activeDepth

activeDepth: number = 0

Maximum depth of current search

GetMoves

GetMoves: GetMovesFunc<GS, M, D> = ...

Callback to get the moves for a gamestate attached to a Node.

CreateChildNode

CreateChildNode: CreateChildNodeFunc<GS, M, D> = ...

Callback to create a child of a parent node using a move

Class Minimax<GS, M, D>

Usage

Type Parameters

GS

M

D

Hierarchy

Index

Constructors

Methods

Properties

Constructors

constructor

Type Parameters

GS

M

D

Parameters

root: Node<GS, M, D>

opts: MinimaxOpts = ...

Returns Minimax<GS, M, D>

Methods

Protected evalDepth

Returns

Parameters

depth: number = ...

Returns MinimaxResult<M>

Protected minimax

Returns

Parameters

node: Node<GS, M, D>

depth: number

alpha: number

beta: number

Returns SearchExit

Protected minimumBestChild

Parameters

node: Node<GS, M, D>

depth: number

Returns { exit: SearchExit; best: undefined | Node<GS, M, D>; }

exit: SearchExit

best: undefined | Node<GS, M, D>

Protected maximumBestChild

Parameters

node: Node<GS, M, D>

depth: number

Returns { exit: SearchExit; best: undefined | Node<GS, M, D>; }

exit: SearchExit

best: undefined | Node<GS, M, D>

Protected alphaBetaBestChild

Returns

Parameters

node: Node<GS, M, D>

depth: number

alpha: number

beta: number

Returns { exit: SearchExit; best: undefined | Node<GS, M, D>; }

exit: SearchExit

best: undefined | Node<GS, M, D>

Protected assignNodeValue

Returns

Parameters

node: Node<GS, M, D>

leaf: boolean

Returns SearchExit

Protected evalDeepening

Relevant options

Returns

Returns SearchResult<M>

evaluate

Returns

Returns SearchResult<M>

depthCallback

Parameters

tree: SearchTree<GS, M, D>

result: SearchResult<M>

Returns void

Protected checkExpiry

Returns

Returns boolean

`Protected` evalDepth

`Protected` minimax

`Protected` minimumBestChild

Returns {
exit: SearchExit;
best: undefined | Node<GS, M, D>;
}

`Protected` maximumBestChild

Returns {
exit: SearchExit;
best: undefined | Node<GS, M, D>;
}

`Protected` alphaBetaBestChild

Returns {
exit: SearchExit;
best: undefined | Node<GS, M, D>;
}

`Protected` assignNodeValue

`Protected` evalDeepening

`Protected` checkExpiry

`Protected` checkNodeLimit

`Protected` getChildren

`Protected` sortChildren

`Optional` reverse: boolean

`Protected` randomBestChild

`Protected` randomWeightedChild

`Protected` routeGen

`Protected` optimalMoveGen

`Protected` removeNonBestNodes

`Protected` createChildren

`Protected` createTree

`Protected` childGen

`Protected` expired

`Protected` expireTime

`Protected` fullDepth

`Protected` presortEnable

`Protected` outcomes

`Protected` nodeLimitExceeded