Documentation
¶
Index ¶
- Variables
- func FullExploration(ctx context.Context, b *board.Board) (board.MovePriorityFn, board.MovePredicateFn)
- func IsAnyMove(m board.Move) bool
- func MVVLVA(m board.Move) board.MovePriority
- func Selection(list []board.Move) (board.MovePriorityFn, board.MovePredicateFn)
- type AlphaBeta
- type Bound
- type Context
- type Evaluator
- type Exploration
- type Leaf
- type Minimax
- type NoTranspositionTable
- func (n NoTranspositionTable) Read(hash board.ZobristHash) (Bound, int, eval.Score, board.Move, bool)
- func (n NoTranspositionTable) Size() uint64
- func (n NoTranspositionTable) Used() float64
- func (n NoTranspositionTable) Write(hash board.ZobristHash, bound Bound, ply, depth int, score eval.Score, ...) bool
- type PV
- type Quiescence
- type QuietSearch
- type Search
- type TranspositionTable
- type TranspositionTableFactory
- type WriteFilter
- type WriteLimited
Constants ¶
This section is empty.
Variables ¶
var EmptyContext = &Context{TT: NoTranspositionTable{}}
var ErrHalted = errors.New("search halted")
ErrHalted is an error indicating that the search was halted.
Functions ¶
func FullExploration ¶ added in v0.90.1
func FullExploration(ctx context.Context, b *board.Board) (board.MovePriorityFn, board.MovePredicateFn)
func MVVLVA ¶
func MVVLVA(m board.Move) board.MovePriority
MVVLVA implements the MVV-LVA move priority.
func Selection ¶
func Selection(list []board.Move) (board.MovePriorityFn, board.MovePredicateFn)
Selection returns a move order and priority for exploring the given moves.
Types ¶
type AlphaBeta ¶
type AlphaBeta struct {
Explore Exploration
Eval QuietSearch
}
AlphaBeta implements alpha-beta pruning. Pseudo-code:
function alphabeta(node, depth, α, β, maximizingPlayer) is
if depth = 0 or node is a terminal node then
return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
α := max(α, value)
if α ≥ β then
break (* β cutoff *)
return value
else
value := +∞
for each child of node do
value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
β := min(β, value)
if β ≤ α then
break (* α cutoff *)
return value
See: https://en.wikipedia.org/wiki/Alpha–beta_pruning.
type Context ¶
type Context struct {
Alpha, Beta eval.Score // Limit search to a [Alpha;Beta] Window
Ponder []board.Move // Limit search to variation, if present.
TT TranspositionTable // HashTable (user configurable)
Noise eval.Random // Evaluation noise (user configurable)
}
Context holds optional context for search implementations.
type Evaluator ¶ added in v0.89.2
type Evaluator interface {
// Evaluate returns the position score in Pawns.
Evaluate(ctx context.Context, sctx *Context, b *board.Board) eval.Pawns
}
Evaluator is a static evaluator in a search context.
type Exploration ¶ added in v0.90.1
type Exploration func(ctx context.Context, b *board.Board) (board.MovePriorityFn, board.MovePredicateFn)
Exploration defines move selection and priority in a given position. Limited exploration is required by quiescence search and can be used for forward pruning in full search. Default: explore all moves in MVVLVA order.
type Leaf ¶ added in v0.89.2
Leaf is a leaf evaluator in a search context. It implicitly adds user-configurable evaluation noise.
type Minimax ¶
type Minimax struct {
Eval Evaluator
}
Minimax implements naive minimax search. Useful for comparison and validation. Pseudo-code:
function minimax(node, depth, maximizingPlayer) is
if depth = 0 or node is a terminal node then
return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max(value, minimax(child, depth − 1, FALSE))
return value
else (* minimizing player *)
value := +∞
for each child of node do
value := min(value, minimax(child, depth − 1, TRUE))
return value
type NoTranspositionTable ¶
type NoTranspositionTable struct{}
NoTranspositionTable is a Nop implementation.
func (NoTranspositionTable) Read ¶
func (n NoTranspositionTable) Read(hash board.ZobristHash) (Bound, int, eval.Score, board.Move, bool)
func (NoTranspositionTable) Size ¶
func (n NoTranspositionTable) Size() uint64
func (NoTranspositionTable) Used ¶
func (n NoTranspositionTable) Used() float64
type PV ¶
type PV struct {
Depth int // depth of search
Moves []board.Move // principal variation
Score eval.Score // evaluation at depth
Nodes uint64 // interior/leaf nodes searched
Time time.Duration // time taken by search
Hash float64 // hash table used [0;1]
}
PV represents the principal variation for some search depth.
type Quiescence ¶
type Quiescence struct {
Explore Exploration
Eval Evaluator
}
Quiescence implements a configurable alpha-beta QuietSearch.
type QuietSearch ¶
type QuietSearch interface {
QuietSearch(ctx context.Context, sctx *Context, b *board.Board) (uint64, eval.Score)
}
QuietSearch is a limited quiescence search, where standing pat is an option for evaluation purposes. Context is cancelled if halted. Thread-safe.
type Search ¶
type Search interface {
Search(ctx context.Context, sctx *Context, b *board.Board, depth int) (uint64, eval.Score, []board.Move, error)
}
Search implements search of the game tree to a given depth. Context is cancelled if halted. Thread-safe.
type TranspositionTable ¶
type TranspositionTable interface {
// Read returns the bound, depth, score and best move for the given position hash, if present.
Read(hash board.ZobristHash) (Bound, int, eval.Score, board.Move, bool)
// Write stores the entry into the table, depending on table semantics and replacement policy.
Write(hash board.ZobristHash, bound Bound, ply, depth int, score eval.Score, move board.Move) bool
// Size returns the size of the table in bytes.
Size() uint64
// Used returns the utilization as a fraction [0;1].
Used() float64
}
TranspositionTable represents a transposition table to speed up search performance. Caveat: evaluation heuristics that depend on the game history (notably, hasCastled or last move) may be unsuitable for position-keyed caching. If the recent history is short, then the table may only be used for depth greater than some limit. Must be thread-safe.
func NewTranspositionTable ¶
func NewTranspositionTable(ctx context.Context, size uint64) TranspositionTable
type TranspositionTableFactory ¶
type TranspositionTableFactory func(ctx context.Context, size uint64) TranspositionTable
func NewMinDepthTranspositionTable ¶
func NewMinDepthTranspositionTable(min int) TranspositionTableFactory
NewMinDepthTranspositionTable creates depth-limited TranspositionTables.
type WriteFilter ¶
type WriteFilter func(hash board.ZobristHash, bound Bound, ply, depth int, score eval.Score, move board.Move) bool
WriteFilter is a predicate on the Write operation.
type WriteLimited ¶
type WriteLimited struct {
Filter WriteFilter
TT TranspositionTable
}
WriteLimited is a TranspositionTable wrapper that ignores certain writes, such as less than a given minimum depth. Useful if evaluation uses recent move history.
func (WriteLimited) Read ¶
func (w WriteLimited) Read(hash board.ZobristHash) (Bound, int, eval.Score, board.Move, bool)
func (WriteLimited) Size ¶
func (w WriteLimited) Size() uint64
func (WriteLimited) Used ¶
func (w WriteLimited) Used() float64
Source Files
Directories