go-chess-minimax, v1.4

The library that implements a chess engine based on the minimax algorithm.

Implement the iterative deepening.

Change Log

• optimize move searching via the iterative deepening.

Features

• move searcher used the negamax algorithm;
• optimizations:
  • alpha-beta pruning;
  • transposition table:
    • storing transpositions in an LRU cache;
    • hashing a transposition by its representation in Forsyth–Edwards Notation;
    • replacing same transpositions on storing in all cases;
    • sharing a transposition table between searches;
  • iterative deepening;
• searching termination:
  • by a deep;
  • by a time;
• position evaluation only by a material (based on an evaluation function of Claude Shannon);
• architecture features:
  • easily extensible and composable architecture of searching;
  • composable searching terminators.

Examples

chessminimax.IterativeSearcher.SearchMove():

package main

import (
    "fmt"
    "log"

    minimax "github.com/thewizardplusplus/go-chess-minimax"
    "github.com/thewizardplusplus/go-chess-minimax/caches"
    "github.com/thewizardplusplus/go-chess-minimax/evaluators"
    moves "github.com/thewizardplusplus/go-chess-minimax/models"
    "github.com/thewizardplusplus/go-chess-minimax/terminators"
    models "github.com/thewizardplusplus/go-chess-models"
    "github.com/thewizardplusplus/go-chess-models/pieces"
    "github.com/thewizardplusplus/go-chess-models/uci"
)

func main() {
    storage, err :=
        uci.DecodePieceStorage("7K/8/7q/8/8/8/8/k7", pieces.NewPiece, models.NewBoard)
    if err != nil {
        log.Fatal(err)
    }

    var generator models.MoveGenerator
    var evaluator evaluators.MaterialEvaluator
    innerSearcher := minimax.NewAlphaBetaSearcher(
        generator,
        nil, // terminator will be set automatically by the iterative searcher
        evaluator,
    )

    // make and bind a cached searcher to inner one
    cache := caches.NewStringHashingCache(1e6, uci.EncodePieceStorage)
    minimax.NewCachedSearcher(innerSearcher, cache)

    terminator := terminators.NewDeepTerminator(1)
    searcher := minimax.NewIterativeSearcher(innerSearcher, terminator)

    scoredMove, err :=
        searcher.SearchMove(storage, models.White, 0, moves.NewBounds())
    if err != nil {
        log.Fatal(err)
    }

    fmt.Printf("%+v\n", scoredMove)

    // Output: {Move:{Start:{File:7 Rank:7} Finish:{File:6 Rank:7}} Score:-9}
}

Benchmarks

chessminimax.IterativeSearcher:

BenchmarkIterativeSearcher_1Ply-8           1000       2297422 ns/op
BenchmarkIterativeSearcher_2Ply-8           2000        666838 ns/op
BenchmarkIterativeSearcher_3Ply-8           2000       1004648 ns/op

Repository

Link: https://github.com/thewizardplusplus/go-chess-minimax/tree/v1.4.

Content: code.

License: MIT.

Screenshots

Tournament between memoized alpha-beta and iterative algorithms