MadChess

I added futility pruning to MadChess 2.0 Beta. In the main search, for non-capture moves, if the static score plus the futility margin is less than alpha, the move is considered too weak and is skipped. In the quiescence search, for capture moves, if the static score plus the material value of the captured piece plus the futility margin is less than alpha, the move is considered too weak and is skipped. The futility margin depends on the distance to the horizon, and is subject to other constraints, illustrated in the code below.

	// Create search parameters.
	_aspirationWindows = new[] {50, 200, 500};
	_futilityMargins = new[] {100, 150, 250, 400, 600};
	// Search
	// Determine if move is legal.
	if (_board.IsMoveLegal(ref move))
	{
	// Move is legal.
	legalMoveNumber++;
	if (Depth == 0)
	{
	// Update root move.
	_rootMove = move;
	_rootMoveNumber = legalMoveNumber;
	}
	}
	else
	{
	// Move is illegal.
	// Mark move as played.
	Move.SetPlayed(ref move, true);
	moves[moveIndex] = move;
	// Skip illegal move.
	continue;
	}
	if (IsMoveFutile(Depth, Horizon, move, legalMoveNumber, staticScore, Alpha, Beta))
	{
	// Move is futile.
	// Mark move as played.
	Move.SetPlayed(ref move, true);
	moves[moveIndex] = move;
	// Skip move.
	continue;
	}
	// ...
	private bool IsMoveFutile(int Depth, int Horizon, uint Move, int LegalMoveNumber, int StaticScore,
	int Alpha, int Beta)
	{
	if (Depth == 0)
	{
	// Root move is not futile.
	return false;
	}
	if (LegalMoveNumber == 1)
	{
	// First move is not futile.
	return false;
	}
	if (_board.CurrentPosition.KingInCheck)
	{
	// Move when king is in check is not futile.
	return false;
	}
	if (MadChess.Move.IsCheck(Move))
	{
	// Check is not futile.
	return false;
	}
	int fromSquare = MadChess.Move.From(Move);
	byte piece = _board.CurrentPosition.Squares[fromSquare];
	byte pawn;
	int rank;
	if (_board.CurrentPosition.WhiteMove)
	{
	pawn = Piece.WhitePawn;
	rank = _board.WhiteRanks[fromSquare];
	}
	else
	{
	pawn = Piece.BlackPawn;
	rank = _board.BlackRanks[fromSquare];
	}
	if ((piece == pawn) && (rank >= 6))
	{
	// Pawn push or promotion is not futile.
	return false;
	}
	if ((Math.Abs(Alpha) >= Score.Checkmate) || (Math.Abs(Beta) >= Score.Checkmate))
	{
	// Move under threat of checkmate is not futile.
	return false;
	}
	int toHorizon = Horizon - Depth;
	byte captureVictim = MadChess.Move.CaptureVictim(Move);
	if ((toHorizon > 0) && (MadChess.Move.CaptureVictim(Move) != Piece.None))
	{
	// Capture in main search is not futile.
	return false;
	}
	if (toHorizon >= _futilityMargins.Length)
	{
	// Move far from search horizon is not futile.
	return false;
	}
	// Determine futility margin.
	int futilityMargin = toHorizon <= 0 ? _futilityMargins[0] : _futilityMargins[toHorizon];
	if (futilityMargin == 0)
	{
	// Futility margin not enabled.
	return false;
	}
	int materialValueCapturedPiece;
	switch (captureVictim)
	{
	case Piece.Pawn:
	materialValueCapturedPiece = Evaluation.PawnMaterialScore;
	break;
	case Piece.Knight:
	materialValueCapturedPiece = Evaluation.KnightMaterialScore;
	break;
	case Piece.Bishop:
	materialValueCapturedPiece = Evaluation.BishopMaterialScore;
	break;
	case Piece.Rook:
	materialValueCapturedPiece = Evaluation.RookMaterialScore;
	break;
	case Piece.Queen:
	materialValueCapturedPiece = Evaluation.QueenMaterialScore;
	break;
	default:
	materialValueCapturedPiece = 0;
	break;
	}
	bool couldPassAlpha = ((StaticScore + materialValueCapturedPiece + futilityMargin) > Alpha);
	return !couldPassAlpha;
	}

view raw FutilityPruning.cs hosted with by GitHub

This added 54 Elo to the playing strength of MadChess 2.0 Beta.

MadChess 2.0                   2004 :    800 (+322,=144,-334),  49.3 %

vs.                                 :  games (   +,   =,   -),   (%) :   Diff,  SD, CFS (%)
BikJump v2.01                       :    100 (  18,  18,  64),  27.0 :    -98,  12,    0.0
Matheus-2.3                         :    100 (  28,  17,  55),  36.5 :    -75,  11,    0.0
Monarch 1.7                         :    100 (  26,  16,  58),  34.0 :    -54,  13,    0.0
BigLion 2.23w                       :    100 (  45,  11,  44),  50.5 :    -17,  10,    5.6
Sharper 0.17                        :    100 (  50,  13,  37),  56.5 :     -1,  12,   46.4
Faile 1.4                           :    100 (  42,  32,  26),  58.0 :    +24,  10,   98.8
Jabba13032012                       :    100 (  54,  22,  24),  65.0 :    +58,  11,  100.0
Roce 0.0390                         :    100 (  59,  15,  26),  66.5 :   +123,  11,  100.0

1. Subversion source code revision
2. Win At Chess position test, 3 seconds per position
3. Bullet chess, 2 min / game + 1 sec / move