MadChess 2.0 Beta Build 040 (History Heuristic + Late Move Reductions)

I added a history heuristic and late move reductions to MadChess 2.0 Beta. When a move causes a beta cutoff, the move’s history value is incremented by the distance to the horizon squared. (Distance to the horizon squared is used to prevent moves deep in the search tree from having too much influence over move order.) A history value is saved for each combination of piece type and move destination square. Moves are ordered by their history values descending (after cached best move, capture victim, capture attacker, promoted piece, and killer moves). The search horizon is reduced for moves that appear late in the ordered move list. The later the move, the more the search horizon is reduced. Because the move does not have a history of causing a beta cutoff, it is likely to fail low and less time is spent searching it.

History values are aged (reduced by a percentage) during iterative deepening of the search, to prevent moves from shallow searches from having too much influence over the move order of deeper searches.

	public sealed class MoveHistory
	{
	private readonly Board _board;
	private readonly int[][] _moveHistory;
	public MoveHistory(Board Board)
	{
	_board = Board;
	_moveHistory = new int[Piece.BlackKing + 1][];
	for (int piece = Piece.WhitePawn; piece <= Piece.BlackKing; piece++)
	{
	_moveHistory[piece] = new int[64];
	for (int square = 0; square < 64; square++)
	{
	_moveHistory[piece][square] = 0;
	}
	}
	}
	public int GetValue(ulong Move)
	{
	int piece = _board.CurrentPosition.Squares[MadChess.Move.From(Move)];
	int toSquare = MadChess.Move.To(Move);
	return _moveHistory[piece][toSquare];
	}
	public void UpdateValue(ulong Move, int Increment)
	{
	int piece = _board.CurrentPosition.Squares[MadChess.Move.From(Move)];
	int toSquare = MadChess.Move.To(Move);
	_moveHistory[piece][toSquare] += Increment;
	}
	public void Reset()
	{
	Age(0, true);
	Age(0, false);
	}
	public void Age(int Percent, bool WhiteMove)
	{
	int pieceMin;
	int pieceMax;
	if (WhiteMove)
	{
	pieceMin = Piece.WhitePawn;
	pieceMax = Piece.WhiteKing;
	}
	else
	{
	pieceMin = Piece.BlackPawn;
	pieceMax = Piece.BlackKing;
	}
	for (int piece = pieceMin; piece <= pieceMax; piece++)
	{
	for (int square = 0; square < 64; square++)
	{
	_moveHistory[piece][square] = (_moveHistory[piece][square] * Percent) / 100;
	}
	}
	}
	}

view raw MoveHistory.cs hosted with by GitHub

	int[] _lateMoveReductions = new[] {3, 7, 15};
	// Play move.
	_board.PlayMove(move);
	// Mark move as played.
	Move.SetPlayed(ref move, true);
	moves[moveIndex] = move;
	// Get move horizon.
	int moveHorizon = GetMoveHorizon(Horizon, move, pawnPush, pawnPromotion, quietMoveNumber);
	// Search move.
	int score = -GetDynamicScore(Depth + 1, moveHorizon, OriginalHorizon, true, -moveBeta, -Alpha);
	if (score > bestScore)
	{
	// Move may be stronger than principal variation.
	bool windowNarrowed = moveBeta < Beta;
	bool horizonReduced = moveHorizon < Horizon;
	if (windowNarrowed || horizonReduced)
	{
	// Search move with full alpha / beta window at unreduced horizon.
	score = -GetDynamicScore(Depth + 1, Horizon, OriginalHorizon, true, -Beta, -Alpha);
	}
	}
	// Undo move.
	_board.UndoMove();
	if ((score > Alpha) && (score < Beta))
	{
	if (Depth == 0)
	{
	// Update root move score.
	_rootScores[moveIndex] = score;
	}
	}
	if (score >= Beta)
	{
	// Position is not the result of best play by both players.
	if (quietMove)
	{
	// Update killer moves.
	_killerMoves.UpdateValue(Depth, move);
	// Update move history.
	_moveHistory.UpdateValue(move, toHorizon * toHorizon);
	}
	// Update best move cache.
	UpdateBestMoveCache(Depth, Horizon, move, score, Alpha, Beta);
	// Beta cutoff
	return Beta;
	}
	private int GetMoveHorizon(int Horizon, ulong Move, bool PawnPush, bool PawnPromotion, int QuietMoveNumber)
	{
	if (PawnPush || PawnPromotion || (MadChess.Move.CaptureVictim(Move) != Piece.None) ||
	MadChess.Move.IsCheck(Move) || _board.CurrentPosition.KingInCheck)
	{
	// Do not reduce search horizon of pawn pushes, pawn promotions, captures,
	// checking moves, or when king is in check.
	return Horizon;
	}
	for (int index = _lateMoveReductions.Length - 1; index >= 0; index--)
	{
	int lateMove = _lateMoveReductions[index];
	if (QuietMoveNumber >= lateMove)
	{
	// Reduce search horizon of late move.
	return Horizon - index - 1;
	}
	}
	return Horizon;
	}
	public ulong GetNextMove(ulong[] Moves, int Depth, int CandidateMoveNumber, out int MoveIndex)
	{
	for (int moveIndex = 0; moveIndex < _board.CurrentPosition.MoveIndex; moveIndex++)
	{
	ulong move = Moves[moveIndex];
	if (move != 0ul)
	{
	if (CandidateMoveNumber == 0)
	{
	// Prioritize killer moves.
	int killer = _killerMoves.GetValue(Depth, move);
	Move.SetKiller(ref move, killer);
	}
	// Prioritize by move history.
	Move.SetHistory(ref move, _moveHistory.GetValue(move));
	Moves[moveIndex] = move;
	}
	}
	// Find highest priority unplayed move.
	ulong nextMove = 0ul;
	MoveIndex = 0;
	for (int moveIndex = 0; moveIndex < _board.CurrentPosition.MoveIndex; moveIndex++)
	{
	ulong move = Moves[moveIndex];
	if (!Move.Played(move))
	{
	// Move has not been played.
	if (move > nextMove)
	{
	nextMove = move;
	MoveIndex = moveIndex;
	}
	}
	}
	return nextMove;
	}

view raw Search.cs hosted with by GitHub

In addition, I changed the move representation from unsigned integers to unsigned longs to provide more bits for recording move history values.

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

MadChess 2.0                   2115 :    800 (+305,=170,-325),  48.8 %

vs.                                 :  games (   +,   =,   -),   (%) :   Diff,  SD, CFS (%)
Glass 1.6                           :     50 (   3,  10,  37),  16.0 :   -273,  24,    0.0
Capivara LK 0.09a01a                :     50 (   3,  18,  29),  24.0 :   -196,  14,    0.0
Sungorus 1.4                        :     50 (  12,   9,  29),  33.0 :   -195,  11,    0.0
Mediocre v0.34                      :     50 (  14,   7,  29),  35.0 :    -99,  14,    0.0
FireFly v2.6.0                      :     50 (  13,  10,  27),  36.0 :    -93,  13,    0.0
ZCT 0.3.2450                        :     50 (  14,  13,  23),  41.0 :    -86,  15,    0.0
Jazz v444                           :     50 (  11,  12,  27),  34.0 :    -75,  13,    0.0
Wing 2.0                            :     50 (  19,   9,  22),  47.0 :     -6,  13,   32.2
BikJump v2.01                       :     50 (  20,   6,  24),  46.0 :    +18,  14,   89.2
Matheus-2.3                         :     50 (  19,  14,  17),  52.0 :    +37,  13,   99.7
Monarch 1.7                         :     50 (  20,   8,  22),  48.0 :    +60,  13,  100.0
BigLion 2.23w                       :     50 (  24,  17,   9),  65.0 :    +92,  12,  100.0
Sharper 0.17                        :     50 (  39,   4,   7),  82.0 :   +110,  12,  100.0
Faile 1.4                           :     50 (  29,  16,   5),  74.0 :   +135,  11,  100.0
Jabba13032012                       :     50 (  30,  10,  10),  70.0 :   +162,  13,  100.0
Roce 0.0390                         :     50 (  35,   7,   8),  77.0 :   +233,  12,  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