Module

# Data.GameTree

Package
purescript-gametree
Repository
sharkdp/purescript-gametree

This module defines a type class for nodes in a tree of game states (two-player zero-sum games) and provides algorithms to search the game trees for optimal strategies.

### #ScoreSource

``data Score``

The (heuristic) value of a node in the game tree. `Lose` and `Win` can be thought of as -infinity and +infinity.

Mathematically, `Score` is analogous to the extended real number line, which is a totally ordered set (see `Ord` instance). `Score` is not a `Semiring`, but supports negation (`negateScore`).

#### Constructors

• `Lose`
• `Score Number`
• `Win`

#### Instances

• `Eq Score`
• `Ord Score`
• `Show Score`

### #PliesSource

``type Plies = Int``

The number of moves to look ahead.

### #NodeSource

``class Node a  where``

A node in a game tree, typically representing a given game state. `isTerminal` returns `true` if the node refers to a game state that is either a win, a lose, or a draw. The `score` of a node is the (heuristic) value of the given node and is always defined from the viewpoint of the 'first' player (the one that calls the search algorithm). Finally, `children` returns a list of game states that can be reached through valid moves.

Law:

``````  isTerminal n == null (children n)
``````

#### Members

• `isTerminal :: a -> Boolean`
• `score :: a -> Score`
• `children :: a -> List a`

### #isTerminalDefaultSource

``isTerminalDefault :: forall a. Node a => a -> Boolean``

A default implementation for `isTerminal`.

### #ResultSource

``type Result a = { principalVariation :: NonEmpty List a, score :: Score }``

The result of a game tree search. The principal variation is a list of game states (including the root node) that would result in the given score.

### #minmaxSource

``minmax :: forall a. Node a => Plies -> a -> Result a``

An implementation of the MinMax algorithm (in Negamax formulation). Computes the principal variation and the best possible score for the player that is about to make a move at the given root node.

### #bestMoveSource

``bestMove :: forall a. Node a => (a -> Result a) -> a -> Maybe a``

Returns the child node that results from the best move from a given root node in the game tree. Returns `Nothing` if the node is terminal.

Example: 3-ply minmax:

``````bestMove (minmax 3) rootNode
``````
Modules
Data.GameTree