go-chess-minimax, v1.5

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

Implement a parallel search (Lazy SMP) and refactor.

Change Log

• optimize move searching via a parallel search (Lazy SMP):
  • launch concurrent searches with same depths;
• make a transposition table safe for concurrent use (via a mutual exclusion lock over a whole storage);
• support searching termination by calling a special method (it's safe for concurrent use);
• refactoring.

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;
    • transposition table is safe for concurrent use (via a mutual exclusion lock over a whole storage);
  • iterative deepening;
  • parallel search (Lazy SMP):
    • launch concurrent searches with same depths;
• searching termination:
  • by a deep;
  • by a time;
  • by calling a special method (it's safe for concurrent use);
• 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.ParallelSearcher.SearchMove():

package main

import (
    "fmt"
    "log"
    "runtime"

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

    cache := caches.NewStringHashingCache(1e6, uci.EncodePieceStorage)
    baseTerminator := terminators.NewDeepTerminator(1)
    searcher := minimax.NewParallelSearcher(
        runtime.NumCPU(),
        func(parallelTerminator terminators.SearchTerminator) minimax.MoveSearcher {
            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
            minimax.NewCachedSearcher(innerSearcher, cache)

            terminator :=
                terminators.NewGroupTerminator(baseTerminator, parallelTerminator)
            return 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.ParallelSearcher:

BenchmarkParallelSearcher_1Ply-8             300       4589800 ns/op
BenchmarkParallelSearcher_2Ply-8            1000       2183554 ns/op
BenchmarkParallelSearcher_3Ply-8             500       3028536 ns/op

Repository

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

Content: code.

License: MIT.

Screenshots

Tournament between iterative and parallel algorithms