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.

#Score Source

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

See: https://en.wikipedia.org/wiki/Extended_real_number_line

Constructors

Instances

#Node Source

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

#isTerminalDefault Source

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

A default implementation for isTerminal.

#Result Source

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.

#minmax Source

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.

#bestMove Source

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