dragontoothmg

README

Dragontooth Movegen | Dylan D. Hunn

Dragontooth Movegen is a fast, no-compromises chess move generator written entirely in Go. It provides a simple API for GenerateLegalMoves(). It also provides Board and Move types, Apply() and Unapply() functionality, and easy-to-use Zobrist-backed hashing of board positions. FEN parsing/serializing and Move parsing/serializing are supported out of the box.

Dragontoothmg is based on magic bitboards for maximum performance, and generates legal moves only using pinned piece tables.

This project is currently stable and fully functional. Optimizations are underway, to improve on the benchmarks listed below.

Repo summary

Here is a summary of the important files in the repo:

File	Description
movegen.go	This is the "primary" source file. Functions are located here if, and only if, they are performance critical and executed to generate moves in-game.
types.go	This file contains the Board and Moves types, along with some supporting helper functions and types.
constants.go	All constants for move generation are hard-coded here, along with functions to compute the magic bitboard lookup tables when the file loads.
util.go	This file contains supporting library functions, for FEN reading and conversions.
apply.go	This provides functions to apply and unapply moves to the board. (Useful for Perft as well.)
perft.go	The actual Perft implementation is contained in this file.

API

Here are significant API calls that this library provides. For invocation details, see the docs.

Function	Description
GenerateLegalMoves	A fast way to generate all moves in the current position.
Board.Apply	Apply a move to the board. Returns a function that allows it to be unapplied.
Perft	Standard "performance test," which recursively counts all of the moves from a position to a given depth.
ParseFen	Construct a Board from a standard chess FEN string.
Board.ToFen	Convert a Board to a standard FEN string.
Board.Hash	Generate a hash value for a Board, using the Zobrist method.
ParseMove	Parse a long-algbraic notation move from a string.
Move.String	Convert a Move to a string, in normal long-algebraic notation.

Installing and building the library

This project requires Go 1.9. As of the time of writing, 1.9 is still a pre-release version. You can get it by cloning the official Go Repo, and building it yourself. There are instructions for this. (Once Go 1.9 comes out in a few weeks, this will become unnecessary.)

To use this package in your own code, make sure your GO_PATH environment variable is correctly set, and install it using go get:

go get github.com/dylhunn/dragontoothmg

Then, you can include it in your project:

import "github.com/dylhunn/dragontoothmg"

Alternatively, you can clone it yourself:

git clone https://github.com/dylhunn/dragontoothmg.git

Testing and benchmarking

To run all tests, cd into the directory and use:

go test -v

The -v shows verbose progress output, since some of the Perft tests can take some time.

To run benchmarks:

go run bench/runbench.go

Current benchmark results are around 60 million NPS (nodes per second) on a modern Intel i5. This significantly outperforms the best current Go chess engines, and is about 40% of the performance of the Stockfish move generator. (Not bad for a garbage-collected language!) Improvements are continually underway, and results will vary on your machine.

Documentation and examples

You can find the documentation here.

Here is a simple example invocation:

// Read a position from a FEN string
board := dragontoothmg.ParseFen("1Q2rk2/2p2p2/1n4b1/N7/2B1Pp1q/2B4P/1QPP4/4K2R b K e3 4 30")
// Generate all legal moves
moveList := board.GenerateLegalMoves()
// For every legal move
for _, currMove := range moveList {
    // Apply it to the board
    unapplyFunc := board.Apply(currMove)
    // Print the move, the new position, and the hash of the new position
    fmt.Println("Moved to:", &currMove) // Reference converts Move to string automatically
    fmt.Println("New position is:", b.ToFen())
    fmt.Println("This new position has Zobrist hash:", board.Hash())
    // Unapply the move
    unapplyFunc()
}

Documentation

Overview

dragontoothmg is a fast chess legal move generator library based on magic bitboards.

Index

• Constants
• func AlgebraicToIndex(alg string) (uint8, error)
• func CalculateBishopMoveBitboard(currBishop uint8, allPieces uint64) uint64
• func CalculateRookMoveBitboard(currRook uint8, allPieces uint64) uint64
• func Divide(b *Board, n int)
• func IndexToAlgebraic(id Square) string
• func IsCapture(m Move, b *Board) bool
• func Perft(b *Board, n int) int64
• type Bitboards
• type Board
  • func ParseFen(fen string) Board
  • func (b *Board) Apply(m Move) func()
  • func (b *Board) Apply2(m Move) *MoveApplication
  • func (b *Board) ApplyNullMove() func()
  • func (b *Board) Enpassant() uint8
  • func (b *Board) GenerateLegalMoves() []Move
  • func (b *Board) GenerateLegalMoves2(onlyCapturesPromosCheckEvasion bool) ([]Move, bool)
  • func (b *Board) Hash() uint64
  • func (b *Board) OurKingInCheck() bool
  • func (b *Board) PieceAt(pos uint8) Piece
  • func (b *Board) ToFen() string
  • func (b *Board) UnderDirectAttack(byBlack bool, origin uint8) bool
• type Move
  • func ParseMove(movestr string) (Move, error)
  • func (m *Move) From() uint8
  • func (m *Move) Promote() Piece
  • func (m *Move) Setfrom(s Square) *Move
  • func (m *Move) Setpromote(p Piece) *Move
  • func (m *Move) Setto(s Square) *Move
  • func (m *Move) String() string
  • func (m *Move) To() uint8
• type MoveApplication
• type Piece
• type Square
• Bugs

Constants

const (
	Nothing = iota
	Pawn    = iota
	Knight  = iota // list before bishop for promotion loops
	Bishop  = iota
	Rook    = iota
	Queen   = iota
	King    = iota
)

const Startpos = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"

The starting position FEN

Functions

func AlgebraicToIndex

func AlgebraicToIndex(alg string) (uint8, error)

Accepts an algebraic notation chess square, and converts it to a square ID as used by Dragontooth (in both the board and move types).

func CalculateBishopMoveBitboard

func CalculateBishopMoveBitboard(currBishop uint8, allPieces uint64) uint64

Calculates the attack bitboard for a bishop. This might include targeted squares that are actually friendly pieces, so the proper usage is: bishopTargets := CalculateBishopMoveBitboard(myBishopLoc, allPieces) & (^myPieces) Externally useful for evaluation functions.

func CalculateRookMoveBitboard

func CalculateRookMoveBitboard(currRook uint8, allPieces uint64) uint64

Calculates the attack bitboard for a rook. This might include targeted squares that are actually friendly pieces, so the proper usage is: rookTargets := CalculateRookMoveBitboard(myRookLoc, allPieces) & (^myPieces) Externally useful for evaluation functions.

func Divide

func Divide(b *Board, n int)

Performs the Perft move count division operation. Useful for debugging.

func IndexToAlgebraic

func IndexToAlgebraic(id Square) string

Accepts a Dragontooth Square ID, and converts it to an algebraic square.

func IsCapture

func IsCapture(m Move, b *Board) bool

func Perft

func Perft(b *Board, n int) int64

Run perft to count the number of moves. Useful for testing and benchmarking.

Types

type Bitboards

type Bitboards struct {
	Pawns   uint64
	Bishops uint64
	Knights uint64
	Rooks   uint64
	Queens  uint64
	Kings   uint64
	All     uint64
}

Contains bitboard representations of all the pieces for a side.

type Board

type Board struct {
	Wtomove bool

	Halfmoveclock uint8
	Fullmoveno    uint16
	White         Bitboards
	Black         Bitboards
	// contains filtered or unexported fields
}

The board type, which uses little-endian rank-file mapping.

func ParseFen

func ParseFen(fen string) Board

Parse a board from a FEN string.

func (*Board) Apply

func (b *Board) Apply(m Move) func()

Applies a move to the board, and returns a function that can be used to unapply it. This function assumes that the given move is valid (i.e., is in the set of moves found by GenerateLegalMoves()). If the move is not valid, this function has undefined behavior.

func (*Board) Apply2

func (b *Board) Apply2(m Move) *MoveApplication

Applies a move to the board, and returns move application information and a function that can be used to unapply it. This function assumes that the given move is valid (i.e., is in the set of moves found by GenerateLegalMoves()). If the move is not valid, this function has undefined behavior.

func (*Board) ApplyNullMove

func (b *Board) ApplyNullMove() func()

Applies a null move to the board, and returns a function that can be used to unapply it. A null move is just that - the current player skips his move. Used for Null Move Heuristic in the search engine.

func (*Board) Enpassant

func (b *Board) Enpassant() uint8

func (*Board) GenerateLegalMoves

func (b *Board) GenerateLegalMoves() []Move

The main API entrypoint. Generates all legal moves for a given board.

func (*Board) GenerateLegalMoves2

func (b *Board) GenerateLegalMoves2(onlyCapturesPromosCheckEvasion bool) ([]Move, bool)

The main API entrypoint. Generates legal moves for a given board,

either all moves (onlyCapturesPromosCheckEvasion == false), or
limited to captures, promotions, and check evasion for quiescence search.

Return moves, isInCheck

func (*Board) Hash

func (b *Board) Hash() uint64

Return the Zobrist hash value for the board. The hash value does NOT change with the turn number, nor the draw move counter. All other elements of the Board type affect the hash. This function is cheap to call, since the hash is incrementally updated.

func (*Board) OurKingInCheck

func (b *Board) OurKingInCheck() bool

func (*Board) PieceAt

func (b *Board) PieceAt(pos uint8) Piece

func (*Board) ToFen

func (b *Board) ToFen() string

Serializes a board position to a Fen string.

func (*Board) UnderDirectAttack

func (b *Board) UnderDirectAttack(byBlack bool, origin uint8) bool

Determine if a square is under attack. Potentially expensive.

type Move

type Move uint16

Move bitwise structure; internal implementation is private.

func ParseMove

func ParseMove(movestr string) (Move, error)

Some example valid move strings: e1e2 b4d6 e7e8q a2a1n TODO(dylhunn): Make the parser more forgiving. Eg: 0-0, O-O-O, a2-a3, D3D4

func (*Move) From

func (m *Move) From() uint8

func (*Move) Promote

func (m *Move) Promote() Piece

Whether the move involves promoting a pawn.

func (*Move) Setfrom

func (m *Move) Setfrom(s Square) *Move

func (*Move) Setpromote

func (m *Move) Setpromote(p Piece) *Move

func (*Move) Setto

func (m *Move) Setto(s Square) *Move

func (*Move) String

func (m *Move) String() string

func (*Move) To

func (m *Move) To() uint8

type MoveApplication

type MoveApplication struct {
	Unapply           func()
	FromPieceType     Piece
	ToPieceType       Piece // Different from fromPieceType only for promotions
	CapturedPieceType Piece // Nothing if this is not a capture
	CaptureLocation   uint8
	IsCastling        bool
	RookCastleFrom    uint8 // Only valid if IsCastling
	RookCastleTo      uint8 // Only valid if IsCastling
}

Move application data

type Piece

type Piece uint8

Piece types; valid in range 0-6, as indicated by the constants for each piece.

type Square

type Square uint8

Square index values from 0-63.

Notes

Bugs

• This FEN parsing implementation doesn't handle malformed inputs.