search

package
v0.89.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 18, 2022 License: MIT Imports: 14 Imported by: 0

Documentation

Overview

Package search contains search functionality and utilities.

Index

Constants

This section is empty.

Variables

View Source 
var EmptyContext = &Context{TT: NoTranspositionTable{}}
View Source 
var ErrHalted = errors.New("search halted")

ErrHalted is an error indicating that the search was halted.

Functions

func EnforceTimeControl 

func EnforceTimeControl(ctx context.Context, h Handle, tc *TimeControl, turn board.Color) (time.Duration, bool)

EnforceTimeControl enforces the time control limits, if any. Returns soft limit.

func IsAnyMove 

func IsAnyMove(ctx context.Context, m board.Move, b *board.Board) bool

IsAnyMove is a trivial selection of all moves. Default for full search.

func IsClosed 

func IsClosed(ch <-chan struct{}) bool

IsClosed return true iff the quit channel is closed.

func IsNotUnderPromotion 

func IsNotUnderPromotion(ctx context.Context, m board.Move, b *board.Board) bool

IsNotUnderPromotion selects any move, except under-promotions.

func IsQuickGain 

func IsQuickGain(ctx context.Context, m board.Move, b *board.Board) bool

IsQuickGain is a move selection for immediate material gain: promotions and captures.

Types

type AlphaBeta 

type AlphaBeta struct {
	Pick Selection
	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.

func (AlphaBeta) Search 

func (p AlphaBeta) Search(ctx context.Context, sctx *Context, b *board.Board, depth int, quit <-chan struct{}) (uint64, eval.Score, []board.Move, error)

type Bound 

type Bound uint8

Bound represents the bound of a -- possibly inexact -- search score. 

const (
	ExactBound Bound = iota
	LowerBound
)

func (Bound) String 

func (b Bound) String() string

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
}

Context holds optional context for search implementations.

type First 

type First board.Move

First puts the given move first. Otherwise uses MVVLVA.

func (First) MVVLVA 

func (f First) MVVLVA(m board.Move) Priority

type Handle 

type Handle interface {
	// Halt halts the search, if running. Idempotent.
	Halt() PV
}

Handle is an interface for the engine to manage searches. The engine is expected to spin off searches with forked boards and close/abandon them when no longer needed. This design keeps stopping conditions and re-synchronization trivial.

type Iterative 

type Iterative struct {
	Root Search
}

Iterative is a search harness for iterative deepening search.

func (*Iterative) Launch 

func (i *Iterative) Launch(ctx context.Context, b *board.Board, tt TranspositionTable, opt Options) (Handle, <-chan PV)

type Launcher 

type Launcher interface {
	// Launch a new search from the given position. It expects an exclusive (forked) board and
	// returns a PV channel for iteratively deeper searches. If the search is exhausted, the
	// channel is closed. The search can be stopped at any time.
	Launch(ctx context.Context, b *board.Board, tt TranspositionTable, opt Options) (Handle, <-chan PV)
}

Launcher is an interface for managing searches.

type Minimax 

type Minimax struct {
	Eval 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

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

func (Minimax) Search 

func (m Minimax) Search(ctx context.Context, sctx *Context, b *board.Board, depth int, quit <-chan struct{}) (uint64, eval.Score, []board.Move, error)

type MoveList 

type MoveList struct {
	// contains filtered or unexported fields
}

MoveList is move priority queue for move ordering.

func NewMoveList 

func NewMoveList(moves []board.Move, fn func(move board.Move) Priority) *MoveList

NewMoveList returns a new move list with the given priorities.

func (*MoveList) Next 

func (ml *MoveList) Next() (board.Move, bool)

Next returns the next move. It is the highest priority move in the list.

func (*MoveList) Size 

func (ml *MoveList) Size() int

func (*MoveList) String 

func (ml *MoveList) String() string

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

func (NoTranspositionTable) Write 

func (n NoTranspositionTable) Write(hash board.ZobristHash, bound Bound, ply, depth int, score eval.Score, move board.Move) bool

type Options 

type Options struct {
	// DepthLimit, if set, limits the search to the given ply depth.
	DepthLimit *int
	// TimeControl, if set, limits the search to the given time parameters.
	TimeControl *TimeControl
}

Options hold dynamic search options. The user may change these on a particular search.

func (Options) String 

func (o Options) String() string

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.

func (PV) String 

func (p PV) String() string

type Priority 

type Priority int16

Priority represents the move order priority.

func MVVLVA 

func MVVLVA(m board.Move) Priority

MVVLVA returns the MVV-LVA priority.

type Quiescence 

type Quiescence struct {
	Pick Selection
	Eval eval.Evaluator
}

Quiescence implements a configurable alpha-beta QuietSearch.

func (Quiescence) QuietSearch 

func (q Quiescence) QuietSearch(ctx context.Context, sctx *Context, b *board.Board, quit <-chan struct{}) (uint64, eval.Score)

type QuietSearch 

type QuietSearch interface {
	QuietSearch(ctx context.Context, sctx *Context, b *board.Board, quit <-chan struct{}) (uint64, eval.Score)
}

QuietSearch is a limited quiescence search, where standing pat is an option for evaluation purposes. Thread-safe. 

type Search interface {
	Search(ctx context.Context, sctx *Context, b *board.Board, depth int, quit <-chan struct{}) (uint64, eval.Score, []board.Move, error)
}

Search implements search of the game tree to a given depth. Thread-safe.

type Selection 

type Selection func(ctx context.Context, move board.Move, b *board.Board) bool

Selection defines move selection. It is required by quiescence search, but optional for full search. Selection turns true if the move just made should be explored.

type TimeControl 

type TimeControl struct {
	White, Black time.Duration
	Moves        int // 0 == rest of game
}

TimeControl represents time control information.

func (TimeControl) Limits 

func (t TimeControl) Limits(c board.Color) (time.Duration, time.Duration)

Limits returns a soft and hard limit for making move with the given color. The interpretation is that after the soft limit, no new search should be conducted.

func (TimeControl) String 

func (t TimeControl) String() string

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

func (WriteLimited) Write 

func (w WriteLimited) Write(hash board.ZobristHash, bound Bound, ply, depth int, score eval.Score, move board.Move) bool

type ZeroPly 

type ZeroPly struct {
	Eval eval.Evaluator
}

ZeroPly is an evaluator wrapped as a QuietSearch.

func (ZeroPly) QuietSearch 

func (z ZeroPly) QuietSearch(ctx context.Context, sctx *Context, b *board.Board, quit <-chan struct{}) (uint64, eval.Score)

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.