Skip to content

Instantly share code, notes, and snippets.

@kelsny
Created July 22, 2023 05:20
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kelsny/0f821b3cc2f206649e22100f4fc07dd1 to your computer and use it in GitHub Desktop.
Save kelsny/0f821b3cc2f206649e22100f4fc07dd1 to your computer and use it in GitHub Desktop.
WHY DOESNT THIS SHIT WORK
import OpeningBook from "../book/dynamic.js";
import { Adversary, Bitboard, Board, GameState, Move, MoveGenerator, Piece, Zobrist } from "../index.js";
import { AdversaryBestMoveConfig } from "./Adversary.js";
const PawnValue = 100;
const KnightValue = 300;
const BishopValue = 320;
const RookValue = 500;
const QueenValue = 900;
const squareControlledByOpponentPawnPenalty = 350;
const capturedPieceValueMultiplier = 10;
const immediateMateScore = 100_000;
const PositiveInf = 9_999_999;
const NegativeInf = -PositiveInf;
/** extends previous iteration using quiescence search and check extensions */
export class v02_QuiescenceSearch extends Adversary {
#bestMove = Move.invalidMove();
#bestEval = NegativeInf;
#bestMoveThisIteration = Move.invalidMove();
#bestEvalThisIteration = NegativeInf;
#generator: MoveGenerator;
#signal: AbortSignal | undefined;
#repetitionHistory: bigint[];
#isBookEval = false;
constructor(readonly board: Board) {
super(board);
this.#generator = new MoveGenerator(this.board);
this.#repetitionHistory = [...board.repetitionHistory];
}
bestMove({ signal, maxDepth, debug, useBook }: AdversaryBestMoveConfig = {}): Move {
if (debug) console.time("bestMove");
this.#isBookEval = false;
if (useBook) {
const moves = OpeningBook[Zobrist.openingBookKey(this.board).toString()];
if (moves) {
const bookMove = moves[Math.floor(Math.random() * moves.length)];
this.#bestMove = new Move(bookMove);
this.#bestEval = 0;
this.#isBookEval = true;
return this.#bestMove;
}
}
this.#repetitionHistory = [...this.board.repetitionHistory];
const depth = maxDepth ?? 4; // 5 is 11x slower
this.#signal = signal;
for (let d = 1; d <= depth; d++) {
this.#bestMoveThisIteration = Move.invalidMove();
this.#bestEvalThisIteration = NegativeInf;
this.#search(d, 0, NegativeInf, PositiveInf);
this.#bestMove = this.#bestMoveThisIteration;
this.#bestEval = this.#bestEvalThisIteration;
if (this.#isMateScore(this.#bestEval)) break;
if (this.#signal?.aborted) break;
}
if (debug) console.timeEnd("bestMove");
return this.#bestMove;
}
getDiagnostics(): Record<string, unknown> {
if (Move.equals(this.#bestMove, Move.invalidMove())) throw new Error("bestMove must be called before getDiagnostics");
return {
bestMove: this.#bestMove,
bestEval: this.#bestEval,
isBookEval: this.#isBookEval,
};
}
#search(depth: number, plyFromRoot: number, alpha: number, beta: number): number {
if (this.#signal?.aborted) return 0;
this.#generator = new MoveGenerator(this.board);
if (plyFromRoot > 0) {
if (this.board.repetitionHistory.includes(this.board.zobristKey)) return 0;
if (this.board.fiftyMoveCounter >= 100) return 0;
alpha = Math.max(alpha, -immediateMateScore + plyFromRoot);
beta = Math.min(beta, immediateMateScore - plyFromRoot);
if (alpha >= beta) return alpha;
}
if (depth <= 0) return this.#quiescence(alpha, beta);
const moveToSearchFirst = plyFromRoot === 0 ? this.#bestMove : Move.invalidMove(); // use tt later
const moves = this.#generator
.generateMoves()
.map((move) => [move, this.#orderScore(move)] as const)
.sort(([am, a], [bm, b]) => (Move.equals(am, moveToSearchFirst) ? PositiveInf : Move.equals(bm, moveToSearchFirst) ? NegativeInf : a - b))
.map(([move]) => move);
const gameState = this.board.gameState();
if (GameState.isDraw(gameState)) return 0;
if (moves.length === 0) {
if (this.#generator.inCheck) {
const mateScore = immediateMateScore - plyFromRoot;
return -mateScore;
}
}
let bestEvaluation = NegativeInf;
for (const move of moves) {
this.board.makeMove(move, true);
this.#repetitionHistory.push(this.board.zobristKey);
const evaluation = -this.#search(depth - 1, plyFromRoot + 1, -beta, -alpha);
this.#repetitionHistory.pop();
this.board.unmakeMove(move, true);
if (this.#signal?.aborted) return 0;
if (evaluation > bestEvaluation) {
bestEvaluation = evaluation;
if (plyFromRoot === 0) {
this.#bestMoveThisIteration = move;
this.#bestEvalThisIteration = evaluation;
}
}
}
return bestEvaluation;
}
#quiescence(alpha: number, beta: number) {
if (this.#signal?.aborted) return 0;
let evaluation = this.#evaluate(this.board);
if (evaluation >= beta) return beta;
if (evaluation > alpha) alpha = evaluation;
const moves = this.#generator
.generateMoves({ excludeQuietMoves: true })
.map((move) => [move, this.#orderScore(move)] as const)
.sort(([, a], [, b]) => a - b)
.map(([move]) => move);
for (const move of moves) {
this.board.makeMove(move, true);
evaluation = -this.#quiescence(-beta, -alpha);
this.board.unmakeMove(move, true);
if (evaluation >= beta) return beta;
if (evaluation > alpha) alpha = evaluation;
}
return alpha;
}
#orderScore(move: Move) {
let score = 0;
const movedPieceType = Piece.getType(this.board.squares[move.startSquare]);
const capturedPieceType = Piece.getType(this.board.squares[move.targetSquare]);
const flag = move.moveFlag;
if (capturedPieceType !== Piece.None) {
score = capturedPieceValueMultiplier * this.#getPieceValue(capturedPieceType) - this.#getPieceValue(movedPieceType);
}
if (movedPieceType === Piece.Pawn) {
if (flag === Move.Flag.PromoteToQueen) score += QueenValue;
else if (flag === Move.Flag.PromoteToKnight) score += KnightValue;
else if (flag === Move.Flag.PromoteToRook) score += RookValue;
else if (flag === Move.Flag.PromoteToBishop) score += BishopValue;
} else {
if (Bitboard.containsSquare(this.#generator.opponentPawnAttackMap, move.targetSquare)) {
score -= squareControlledByOpponentPawnPenalty;
}
}
return score;
}
#isMateScore(score: number) {
const maxDepth = 1000;
return Math.abs(score) > immediateMateScore - maxDepth;
}
#evaluate(board: Board) {
const whiteMat = this.#countMaterial(board, Board.whiteIndex);
const blackMat = this.#countMaterial(board, Board.blackIndex);
const score = whiteMat - blackMat;
const sign = board.colorToMove === Piece.White ? 1 : -1;
return score * sign;
}
#countMaterial(board: Board, index: 0 | 1) {
let material = 0;
material += board.pawns[index].count * PawnValue;
material += board.knights[index].count * KnightValue;
material += board.bishops[index].count * BishopValue;
material += board.rooks[index].count * RookValue;
material += board.queens[index].count * QueenValue;
return material;
}
readonly #pieceValueLookup = [0, 0, PawnValue, KnightValue, 0, BishopValue, RookValue, QueenValue];
#getPieceValue(piece: number) {
return this.#pieceValueLookup[piece];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment