chess/engine/engine_test.go

package engine

import (
	"context"
	"testing"
	"time"

	"github.com/zg/chess/chess"
)

func search(t *testing.T, fen string, depth int) SearchResult {
	t.Helper()
	b, err := chess.ParseFEN(fen)
	if err != nil {
		t.Fatalf("FEN: %v", err)
	}
	return New().Search(context.Background(), b, Options{MaxDepth: depth, MaxTime: 20 * time.Second})
}

func TestEvaluateStartingPositionIsBalanced(t *testing.T) {
	if got := Evaluate(chess.NewBoard()); got != 0 {
		t.Errorf("starting position evaluates to %d, want 0", got)
	}
}

// Evaluation is from the side to move's point of view, so the same position
// with the other side to move must negate.
func TestEvaluateIsSymmetric(t *testing.T) {
	// White is a queen up.
	white, _ := chess.ParseFEN("4k3/8/8/8/8/8/8/3QK3 w - - 0 1")
	black, _ := chess.ParseFEN("4k3/8/8/8/8/8/8/3QK3 b - - 0 1")

	w, bl := Evaluate(white), Evaluate(black)
	if w <= 0 {
		t.Errorf("white to move, a queen up, evaluates %d; want positive", w)
	}
	if bl >= 0 {
		t.Errorf("black to move, a queen down, evaluates %d; want negative", bl)
	}
	if w != -bl {
		t.Errorf("evaluation is not symmetric: %d vs %d", w, bl)
	}
}

func TestMaterialCounting(t *testing.T) {
	if got := Material(chess.NewBoard()); got != 0 {
		t.Errorf("starting material = %d, want 0", got)
	}
	// White has an extra queen.
	b, _ := chess.ParseFEN("4k3/8/8/8/8/8/8/3QK3 w - - 0 1")
	if got := Material(b); got != 900 {
		t.Errorf("material = %d, want 900", got)
	}
}

// The clearest possible test of search: a mate in one must be found.
// The assertion is on the *outcome* rather than a named move, because a
// position can have more than one mate and any of them is correct.
func TestFindsMateInOne(t *testing.T) {
	tests := []struct {
		name string
		fen  string
	}{
		{"back rank", "6k1/5ppp/8/8/8/8/8/R3K3 w - - 0 1"},
		{"queen mate", "7k/8/6K1/8/8/8/8/7Q w - - 0 1"},
		{"rook and king", "7k/8/6K1/8/8/8/8/7R w - - 0 1"},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			b, err := chess.ParseFEN(tt.fen)
			if err != nil {
				t.Fatal(err)
			}
			res := New().Search(context.Background(), b, Options{MaxDepth: 3, MaxTime: 20 * time.Second})

			if res.Score < MateScore-100 {
				t.Errorf("score %d does not indicate a forced mate", res.Score)
			}
			next, err := b.MakeMove(res.Best)
			if err != nil {
				t.Fatalf("returned an illegal move %s: %v", res.Best, err)
			}
			if next.Outcome() != chess.WhiteWins {
				t.Errorf("%s did not deliver mate; position is %v\n%s", res.Best, next.Outcome(), next)
			}
		})
	}
}

// A mate found must actually be mate on the board, not just a high score.
func TestMateScoreIsRealMate(t *testing.T) {
	b, _ := chess.ParseFEN("6k1/5ppp/8/8/8/8/8/R3K3 w - - 0 1")
	res := New().Search(context.Background(), b, Options{MaxDepth: 3})
	next, err := b.MakeMove(res.Best)
	if err != nil {
		t.Fatal(err)
	}
	if next.Outcome() != chess.WhiteWins {
		t.Errorf("engine claimed mate but the position is %v after %s", next.Outcome(), res.Best)
	}
}

// Free material must be taken. This is the most basic sanity check on
// search and evaluation working together.
func TestCapturesHangingPiece(t *testing.T) {
	// Black queen on d5 is undefended; white's rook on d1 can take it.
	b, _ := chess.ParseFEN("4k3/8/8/3q4/8/8/8/3RK3 w - - 0 1")
	res := New().Search(context.Background(), b, Options{MaxDepth: 4, MaxTime: 10 * time.Second})
	if res.Best.String() != "d1d5" {
		t.Errorf("played %s, want d1d5 to win the queen (score %d)", res.Best, res.Score)
	}
}

// Quiescence search exists for exactly this: the engine must not grab a
// defended piece when the recapture loses material.
func TestDoesNotTakeDefendedPiece(t *testing.T) {
	// White queen on d1, black pawn on d5 defended by a pawn on c6 and e6.
	// Qxd5 loses the queen for a pawn.
	b, _ := chess.ParseFEN("4k3/8/2p1p3/3p4/8/8/8/3QK3 w - - 0 1")
	res := New().Search(context.Background(), b, Options{MaxDepth: 4, MaxTime: 10 * time.Second})
	if res.Best.String() == "d1d5" {
		t.Errorf("engine took a defended pawn with its queen (score %d)", res.Score)
	}
}

// A stalemate must be scored as a draw, not as a loss or a win.
func TestStalemateScoredAsDraw(t *testing.T) {
	b, _ := chess.ParseFEN("7k/5Q2/6K1/8/8/8/8/8 b - - 0 1")
	res := New().Search(context.Background(), b, Options{MaxDepth: 2})
	if res.Depth == 0 && res.Best == (chess.Move{}) {
		return // no legal moves, which is the correct observation
	}
	if len(b.GenerateMoves()) != 0 {
		t.Fatal("test position is not actually stalemate")
	}
}

// Every move the engine returns must be legal in the position it was given.
func TestReturnedMoveIsAlwaysLegal(t *testing.T) {
	fens := []string{
		chess.StartingFEN,
		"r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1",
		"8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1",
		"r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 10",
	}
	for _, fen := range fens {
		t.Run(fen, func(t *testing.T) {
			b, err := chess.ParseFEN(fen)
			if err != nil {
				t.Fatal(err)
			}
			res := New().Search(context.Background(), b, Options{MaxDepth: 3, MaxTime: 10 * time.Second})
			if _, err := b.MakeMove(res.Best); err != nil {
				t.Errorf("engine returned an illegal move %s: %v", res.Best, err)
			}
		})
	}
}

// Deeper search must not make the engine worse at a tactic it already sees.
func TestDeeperSearchStillFindsMate(t *testing.T) {
	for depth := 1; depth <= 4; depth++ {
		res := search(t, "6k1/5ppp/8/8/8/8/8/R3K3 w - - 0 1", depth)
		if res.Best.String() != "a1a8" {
			t.Errorf("depth %d played %s, want a1a8", depth, res.Best)
		}
	}
}

// The principal variation must be a playable sequence, not an arbitrary
// list of moves.
func TestPrincipalVariationIsPlayable(t *testing.T) {
	b, _ := chess.ParseFEN("r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 10")
	res := New().Search(context.Background(), b, Options{MaxDepth: 4, MaxTime: 15 * time.Second})
	if len(res.PV) == 0 {
		t.Fatal("search returned an empty principal variation")
	}
	cur := b
	for i, m := range res.PV {
		next, err := cur.MakeMove(m)
		if err != nil {
			t.Fatalf("PV move %d (%s) is illegal: %v", i, m, err)
		}
		cur = next
	}
}

// A time limit must actually stop the search.
func TestRespectsTimeLimit(t *testing.T) {
	b := chess.NewBoard()
	start := time.Now()
	res := New().Search(context.Background(), b, Options{MaxDepth: 99, MaxTime: 200 * time.Millisecond})
	elapsed := time.Since(start)

	if elapsed > 3*time.Second {
		t.Errorf("search ran for %v despite a 200ms limit", elapsed)
	}
	// It must still return something usable.
	if _, err := b.MakeMove(res.Best); err != nil {
		t.Errorf("search under a time limit returned an illegal move: %v", err)
	}
}

func TestRespectsContextCancellation(t *testing.T) {
	b := chess.NewBoard()
	ctx, cancel := context.WithCancel(context.Background())
	cancel()

	res := New().Search(ctx, b, Options{MaxDepth: 99})
	// Even cancelled immediately, a legal move must come back.
	if _, err := b.MakeMove(res.Best); err != nil {
		t.Errorf("cancelled search returned an illegal move %s: %v", res.Best, err)
	}
}

// With no legal moves there is nothing to return, and the search must not
// panic trying.
func TestSearchWithNoLegalMoves(t *testing.T) {
	b, _ := chess.ParseFEN("7k/5Q2/6K1/8/8/8/8/8 b - - 0 1")
	res := New().Search(context.Background(), b, Options{MaxDepth: 3})
	if res.Depth != 0 {
		t.Errorf("depth = %d, want 0 when there are no moves", res.Depth)
	}
}

// Alpha-beta must prune: a searched-with-ordering tree should visit far
// fewer nodes than the full width of the tree.
func TestSearchPrunes(t *testing.T) {
	b := chess.NewBoard()
	e := New()
	e.Search(context.Background(), b, Options{MaxDepth: 4, MaxTime: 30 * time.Second})

	// Perft(4) from the start is 197,281 positions. With alpha-beta and
	// move ordering the search should see a small fraction of that.
	if e.Nodes() > 100_000 {
		t.Errorf("visited %d nodes at depth 4; pruning is not working", e.Nodes())
	}
	if e.Nodes() == 0 {
		t.Error("visited no nodes")
	}
}

func TestIsEndgameDetection(t *testing.T) {
	if isEndgame(chess.NewBoard()) {
		t.Error("the starting position is not an endgame")
	}
	b, _ := chess.ParseFEN("4k3/8/8/8/8/8/8/4K3 w - - 0 1")
	if !isEndgame(b) {
		t.Error("king versus king is an endgame")
	}
}

func TestMirror(t *testing.T) {
	// a1 (0) mirrors to a8 (56); e2 (12) mirrors to e7 (52).
	if got := mirror(0); got != 56 {
		t.Errorf("mirror(a1) = %d, want 56", got)
	}
	if got := mirror(12); got != 52 {
		t.Errorf("mirror(e2) = %d, want 52", got)
	}
	// Mirroring twice is the identity.
	for sq := range 64 {
		if mirror(mirror(sq)) != sq {
			t.Fatalf("mirror is not an involution at %d", sq)
		}
	}
}

func BenchmarkSearchDepth4(b *testing.B) {
	board := chess.NewBoard()
	bench := New()
	b.ResetTimer()
	for b.Loop() {
		bench.Search(context.Background(), board, Options{MaxDepth: 4})
	}
}

func BenchmarkEvaluate(b *testing.B) {
	board := chess.NewBoard()
	b.ResetTimer()
	for b.Loop() {
		Evaluate(board)
	}
}