MadChess

I improved MadChess 3.0 Beta’s time management. I added code that increases MoveTimeSoftLimit, a TimeSpan variable that controls how long the engine examines a position (in a timed game) before responding with its move. The code increases MoveTimeSoftLimit 25% each ply (depth >= 9) if the score decreases at least one third of a pawn from the prior ply. In some engines this is known as “panic time.” The engine notices the score dropping and- to anthropomorphize it- panics like a human chess player would, spending more time than usual searching for a move that prevents its position from crumbling.

	private const int _minMovesRemaining = 8;
	private const int _piecesMovesPer128 = 160;
	private const int _materialAdvantageMovesPer1024 = 25;
	private const int _moveTimeHardLimitPer128 = 512;
	private const int _adjustMoveTimeMinDepth = 9;
	private const int _adjustMoveTimeMinScoreDecrease = 33;
	private const int _adjustMoveTimePer128 = 32;
	private const int _haveTimeSearchNextPlyPer128 = 70;
	private ScoredMove[] _bestMoves; // ScoredMove is a struct the binds together ulong Move and int Score.
	// _originalHorizon is the search depth, also known as ply.
	// ...
	public ulong FindBestMove(Board Board)
	{
	// ...
	// Iteratively deepen search.
	_originalHorizon = 0;
	var bestMove = new ScoredMove(Move.Null, -StaticScore.Max);
	do
	{
	_originalHorizon++;
	_selectiveHorizon = 0;
	// Clear principal variations and age move history.
	// The Dictionary enumerator allocates memory which is not desirable when searching positions.
	// However, this occurs only once per ply.
	using (var pvEnumerator = _principalVariations.GetEnumerator())
	{
	while (pvEnumerator.MoveNext()) pvEnumerator.Current.Value[0] = Move.Null;
	}
	_moveHistory.Age(Board.CurrentPosition.WhiteMove);
	// Get score within aspiration window.
	var score = GetScoreWithinAspirationWindow(Board, principalVariations);
	if (Math.Abs(score) == StaticScore.Interrupted) break; // Stop searching.
	// Find best moves.
	SortMovesByScore(_rootMoves, Board.CurrentPosition.MoveIndex - 1);
	var bestMoves = _scoreError == 0 ? principalVariations : legalMoveIndex;
	for (var moveIndex = 0; moveIndex < bestMoves; moveIndex++)
	{
	_bestMoves[moveIndex] = _rootMoves[moveIndex];
	}
	if (PvInfoUpdate) UpdateInfo(Board, principalVariations, true);
	bestMove = _bestMoves[0];
	_bestMovePlies[_originalHorizon] = bestMove;
	if (MateInMoves.HasValue && (Math.Abs(bestMove.Score) >= StaticScore.Checkmate) &&
	(Evaluation.GetMateDistance(bestMove.Score) <= MateInMoves.Value))
	{
	// Found checkmate in correct number of moves.
	break;
	}
	AdjustMoveTime();
	if (!HaveTimeForNextHorizon()) break; // Do not have time to search next ply.
	} while (Continue && (_originalHorizon < HorizonLimit));
	_stopwatch.Stop();
	if (_debug()) _writeMessageLine(
	$"info string Stopping search at {_stopwatch.Elapsed.TotalMilliseconds:0} milliseconds.");
	return _scoreError == 0 ? bestMove.Move : GetInferiorMove(Board.CurrentPosition);
	}
	private void AdjustMoveTime()
	{
	if (!CanAdjustMoveTime || (_originalHorizon < _adjustMoveTimeMinDepth) ||
	(MoveTimeSoftLimit == MoveTimeHardLimit)) return;
	if (_bestMovePlies[_originalHorizon].Score >= (_bestMovePlies[_originalHorizon - 1].Score -
	_adjustMoveTimeMinScoreDecrease)) return;
	// Score has decreased significantly from last ply.
	if (_debug()) _writeMessageLine(
	"Adjusting move time because score has decreased significantly from previous ply.");
	MoveTimeSoftLimit += TimeSpan.FromMilliseconds((MoveTimeSoftLimit.TotalMilliseconds *
	_adjustMoveTimePer128) / 128);
	if (MoveTimeSoftLimit > MoveTimeHardLimit) MoveTimeSoftLimit = MoveTimeHardLimit;
	}
	private bool HaveTimeForNextHorizon()
	{
	if (MoveTimeSoftLimit == TimeSpan.MaxValue) return true;
	var moveTimePer128 = (int)((128 * _stopwatch.Elapsed.TotalMilliseconds) /
	MoveTimeSoftLimit.TotalMilliseconds);
	return moveTimePer128 <= _haveTimeSearchNextPlyPer128;
	}

view raw AdjustMoveTime.cs hosted with by GitHub

In MadChess 3.0 Beta, when it’s the engine’s turn to move (in a timed game), it allots time to search for a best move. It calculates MoveTimeSoftLimit by examining the game clock and the current position. It then calculates MoveTimeHardLimit simply by multiplying MoveTimeSoftLimit by four. The soft time limit is examined each ply. If the engine already has used 70 / 128ths of the allotted time (55%) or more, it replies with the best move found so far rather than begin searching the next ply (because it anticipates not having enough time to complete the search). Once MadChess begins searching a ply, it will not interrupt the search unless it’s reached or exceeded the MoveTimeHardLimit.

In addition, I improved code that calculates move time limits when playing a game with a traditional clock (non Fischer clock). Previously, MadChess 3.0 Beta mismanaged time in non Fischer clock games and occasionally lost on time. Now its playing strength in non Fischer clock games is on par with its strength in Fischer clock games. Usually I test MadChess in tournaments that use a Fischer clock (my computer opponent rating lists all use a Fischer clock), so playing games at 20 moves / 1 min (repeating) was special testing I did for this feature- but don’t intend to continue- to eliminate an engine deficiency. Considering “taste and comfort are personal,” as my father says, I recognize other people may prefer games with a traditional clock. So I’ve ensured MadChess plays well in those time controls.

I did not test sudden death time controls. Why? Because time scrambles don’t produce quality chess by humans or computer chess engines. In my opinion, MadChess’ performance in sudden death time control is not worth testing.

This “panic time” code increased the playing strength of MadChess 3.0 Beta by 8 Elo.

1. GitHub commit (hash) or Subversion source code revision (integer)
2. Win At Chess position test, 3 seconds per position
3. Bullet chess, 2 min / game + 1 sec / move