MadChess 2.0 Beta Build 038 (Killer Moves)

I added killer moves to MadChess 2.0 Beta. Killer moves are quiet moves (not captures or pawn promotions) that cause a beta cutoff. Two killer moves are saved for each ply. They are searched immediately after captures and pawn promotions.

	public class KillerMoves
	{
	private readonly Board _board;
	private readonly KillerMove[][] _killerMoves;
	public KillerMoves(Board Board, int MaxDepth)
	{
	_board = Board;
	_killerMoves = new KillerMove[MaxDepth + 1][];
	for (int depth = 0; depth <= MaxDepth; depth++)
	{
	_killerMoves[depth] = new KillerMove[2];
	_killerMoves[depth][0] = new KillerMove(Piece.None, Square.Illegal);
	_killerMoves[depth][1] = new KillerMove(Piece.None, Square.Illegal);
	}
	}
	public int GetValue(int Depth, uint Move)
	{
	if (Equals(_killerMoves[Depth][0], Move))
	{
	return 2;
	}
	return Equals(_killerMoves[Depth][1], Move) ? 1 : 0;
	}
	public void UpdateValue(int Depth, uint Move)
	{
	if (Equals(_killerMoves[Depth][0], Move))
	{
	// Move already is the best killer move.
	return;
	}
	// Shift killer moves.
	_killerMoves[Depth][1] = _killerMoves[Depth][0];
	// Update killer move.
	_killerMoves[Depth][0].Piece = _board.CurrentPosition.Squares[MadChess.Move.From(Move)];
	_killerMoves[Depth][0].ToSquare = MadChess.Move.To(Move);
	}
	private bool Equals(KillerMove KillerMove, uint Move)
	{
	return (KillerMove.Piece == _board.CurrentPosition.Squares[MadChess.Move.From(Move)]) &&
	(KillerMove.ToSquare == MadChess.Move.To(Move));
	}
	}

view raw KillerMoves.cs hosted with by GitHub

	if (score >= Beta)
	{
	// Position is not the result of best play by both players.
	if (quietMove)
	{
	// Update killer moves.
	_killerMoves.UpdateValue(Depth, move);
	}
	// Update best move cache.
	UpdateBestMoveCache(Depth, Horizon, move, score, Alpha, Beta);
	// Beta cutoff
	return Beta;
	}
	public uint GetNextMove(uint[] Moves, int Depth, int CandidateMoveNumber, out int MoveIndex)
	{
	for (int moveIndex = 0; moveIndex < _board.CurrentPosition.MoveIndex; moveIndex++)
	{
	uint move = Moves[moveIndex];
	if (move != 0u)
	{
	if (CandidateMoveNumber == 0)
	{
	// Prioritize killer moves.
	int killer = _killerMoves.GetValue(Depth, move);
	Move.SetKiller(ref move, killer);
	}
	// TODO: Prioritize by move history.
	}
	}
	// Find highest priority unplayed move.
	uint nextMove = 0u;
	MoveIndex = 0;
	for (int moveIndex = 0; moveIndex < _board.CurrentPosition.MoveIndex; moveIndex++)
	{
	uint 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

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

MadChess 2.0                   2065 :    800 (+396,=136,-268),  58.0 %

vs.                                 :  games (   +,   =,   -),   (%) :   Diff,  SD, CFS (%)
BikJump v2.01                       :    100 (  36,  21,  43),  46.5 :    -26,  11,    0.8
Matheus-2.3                         :    100 (  40,  20,  40),  50.0 :     -7,  11,   27.3
Monarch 1.7                         :    100 (  38,  19,  43),  47.5 :    +14,  11,   90.3
BigLion 2.23w                       :    100 (  49,  15,  36),  56.5 :    +44,  12,  100.0
Sharper 0.17                        :    100 (  61,   5,  34),  63.5 :    +60,  11,  100.0
Faile 1.4                           :    100 (  52,  23,  25),  63.5 :    +85,  11,  100.0
Jabba13032012                       :    100 (  62,  14,  24),  69.0 :   +117,  11,  100.0
Roce 0.0390                         :    100 (  58,  19,  23),  67.5 :   +182,  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