go-chess-minimax, v1.2

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

Use the transposition table and refactor.

Change Log

• optimize move searching via the transposition table:
  • store transpositions in a hash table;
  • hash a transposition by its representation in Forsyth–Edwards Notation;
  • always replace same transpositions on storing;
  • reset a transposition table on every search;
• refactoring.

Features

• move searcher used the negamax algorithm;
• optimizations:
  • alpha-beta pruning;
  • transposition table:
    • storing transpositions in a hash table;
    • hashing a transposition by its representation in Forsyth–Edwards Notation;
    • replacing same transpositions on storing in all cases;
    • resetting a transposition table on every search;
• 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.CachedSearcher.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"
)

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

    var generator models.MoveGenerator
    var evaluator evaluators.MaterialEvaluator
    terminator := terminators.NewDeepTerminator(1)
    innerSearcher := minimax.NewAlphaBetaSearcher(generator, terminator, evaluator)

    cache := make(caches.FENHashingCache)
    searcher := minimax.NewCachedSearcher(cache, innerSearcher)

    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.CachedSearcher:

BenchmarkCachedSearcher_1Ply-8               500       2504426 ns/op
BenchmarkCachedSearcher_2Ply-8               200       6653656 ns/op
BenchmarkCachedSearcher_3Ply-8                30      42010273 ns/op

Repository

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

Content: code.

License: MIT.

Screenshots

Tournament between the alpha-beta algorithm and its memoized version