MadChess 3.0 Beta Build 103 (Passed Pawns)

I added passed pawn evaluation to MadChess 3.0 Beta. The passed pawn evaluation code scores the following features:

  • Passed Pawns
  • Free Passed Pawns (no pieces blocking promotion path)
  • King Escorted Passed Pawns
  • Unstoppable Passed Pawns (Rule of the Square)

private void EvaluatePawns(Position Position)
{
    // White pawns
    ulong pawns = Position.WhitePawns;
    int kingSquare = Bitwise.FindFirstSetBit(Position.WhiteKing);
    int enemyKingSquare = Bitwise.FindFirstSetBit(Position.BlackKing);
    int pawnSquare;
    int rank;
    while ((pawnSquare = Bitwise.FindFirstSetBit(pawns)) != Square.Illegal)
    {
        if (_isPassedPawn(pawnSquare, true))
        {
            rank = Board.WhiteRanks[pawnSquare];
            _staticScore.WhiteEgKingEscortedPassedPawns += (Board.SquareDistances[pawnSquare][enemyKingSquare] - Board.SquareDistances[pawnSquare][kingSquare]) * Config.EgKingEscortedPassedPawn;
            if (_isFreePawn(pawnSquare, true))
            {
                if (IsPawnUnstoppable(Position, pawnSquare, enemyKingSquare, truetrue)) _staticScore.WhiteUnstoppablePassedPawns += Config.UnstoppablePassedPawn; // Pawn is unstoppable.
                else _staticScore.WhiteEgFreePassedPawns += _egFreePassedPawns[rank]; // Pawn is passed and free.
            }
            else
            {
                // Pawn is passed.
                _staticScore.WhiteMgPassedPawns += _mgPassedPawns[rank];
                _staticScore.WhiteEgPassedPawns += _egPassedPawns[rank];
            }
        }
        Bitwise.ClearBit(ref pawns, pawnSquare);
    }
    // Black pawns
    pawns = Position.BlackPawns;
    kingSquare = Bitwise.FindFirstSetBit(Position.BlackKing);
    enemyKingSquare = Bitwise.FindFirstSetBit(Position.WhiteKing);
    while ((pawnSquare = Bitwise.FindFirstSetBit(pawns)) != Square.Illegal)
    {
        if (_isPassedPawn(pawnSquare, false))
        {
            rank = Board.BlackRanks[pawnSquare];
            _staticScore.BlackEgKingEscortedPassedPawns += (Board.SquareDistances[pawnSquare][enemyKingSquare] - Board.SquareDistances[pawnSquare][kingSquare]) * Config.EgKingEscortedPassedPawn;
            if (_isFreePawn(pawnSquare, false))
            {
                if (IsPawnUnstoppable(Position, pawnSquare, enemyKingSquare, falsetrue)) _staticScore.BlackUnstoppablePassedPawns += Config.UnstoppablePassedPawn; // Pawn is unstoppable.
                else _staticScore.BlackEgFreePassedPawns += _egFreePassedPawns[rank]; // Pawn is passed and free.
            }
            else
            {
                // Pawn is passed.
                _staticScore.BlackMgPassedPawns += _mgPassedPawns[rank];
                _staticScore.BlackEgPassedPawns += _egPassedPawns[rank];
            }
        }
        Bitwise.ClearBit(ref pawns, pawnSquare);
    }
}

// Passed Pawns
public int MgPassedPawnScalePercent = 97;
public int EgPassedPawnScalePercent = 473;
public int EgFreePassedPawnScalePercent = 866;
public int EgKingEscortedPassedPawn = 11;
public int UnstoppablePassedPawn => QueenMaterial - (2 * Evaluation.PawnMaterial);  // Incentivize engine to promote pawn.

// Calculate passed pawn values.
double mgScale = Config.MgPassedPawnScalePercent / 100d;
double egScale = Config.EgPassedPawnScalePercent / 100d;
double egFreeScale = Config.EgFreePassedPawnScalePercent / 100d;
for (int rank = 1; rank < 7; rank++)
{
    _mgPassedPawns[rank] = GetNonLinearBonus(rank, mgScale, _passedPawnPower, 0);
    _egPassedPawns[rank] = GetNonLinearBonus(rank, egScale, _passedPawnPower, 0);
    _egFreePassedPawns[rank] = GetNonLinearBonus(rank, egFreeScale, _passedPawnPower, 0);
}

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int GetNonLinearBonus(double Bonus, double Scale, double Power, int Constant) => (int)(Scale * Math.Pow(Bonus, Power)) + Constant;

Middlegame Passed Pawns:            000  000  003  008  015  024  034  000
Endgame Passed Pawns:               000  004  018  042  075  118  170  000
Endgame Free Passed Pawns:          000  008  034  077  138  216  311  000
Endgame King Escorted Passed Pawn:  11
Unstoppable Passed Pawn:            775

 

This code improved the engine’s understanding of threats created by pushing passed pawns. It increased MadChess’ playing strength by 119 ELO.

 

Feature Category Date SVN1 WAC2 ELO Rating3 Improvement
Passed Pawns Evaluation 2018 Dec 27 103 279 2329 +119
Staged Move Generation Search 2018 Dec 15 93 275 2210 +39
History Heuristics Search 2018 Dec 03 84 275 2171 +28
Eval Param Tuning Evaluation 2018 Nov 24 75 272 2143 +47
Sophisticated Search
Material and Piece Location
Baseline 2018 Nov 08 58 269 2096 0
  1. Subversion source code revision (for my own use)
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move

MadChess 3.0 Beta Build 093 (Staged Move Generation)

I increased the speed at which MadChess 3.0 Beta examines nodes by implementing staged move generation. Previously, in the main search, the chess engine would generate all pseudo-legal moves, sort them by move priority, then iterate through them: testing move legality (does move expose own king to check) and playing the legal moves. This is wasteful if a beta cutoff occurs early in the move list. Usually a capture is responsible for a beta cutoff, so time is wasted generating non-captures. Now the chess engine generates moves in stages.

public enum MoveGenerationStage
{
    BestMove,
    Captures,
    NonCaptures,
    End
}

I could have implemented more stages (QueenCaptures, RookCaptures, BishopKnightCaptures, etc) but I wanted to keep the code simple. Implementing a stage for captures of each piece type involves calculating all attacks to a square, not from a square as the engine already does. To test move legality I have already implemented an IsSquareAttacked(int Square) method that returns a boolean value. This does not generate moves though. If I were to implement a GetAttackingMoves(int Square) method I’d need to write debug code that validates the captures generated by calling GetAttackingMoves for all enemy pieces matches the captures generated by calling GenerateMoves(MoveGeneration.OnlyCaptures). Perhaps I’ll investigate this more fine-grained staged move generation later. For now, the code remains simple.

public enum MoveGeneration
{
    AllMoves,
    OnlyCaptures,
    OnlyNonCaptures
}

public void GenerateMoves(MoveGeneration MoveGeneration)
{
    GeneratePawnMoves(MoveGeneration);
    GenerateKnightMoves(MoveGeneration);
    GenerateBishopMoves(MoveGeneration);
    GenerateRookMoves(MoveGeneration);
    GenerateQueenMoves(MoveGeneration);
    GenerateKingMoves(MoveGeneration);
}

Search.cs

private readonly Delegates.GetNextMove _getNextMove;
private readonly Delegates.GetNextMove _getNextCapture;

public Search(Cache Cache, KillerMoves KillerMoves, MoveHistory MoveHistory, Evaluation Evaluation, Func<bool> Debug, Delegates.WriteMessageLine WriteMessageLine)
{
    _cache = Cache;
    _killerMoves = KillerMoves;
    _moveHistory = MoveHistory;
    this.Evaluation = Evaluation;
    _debug = Debug;
    _writeMessageLine = WriteMessageLine;
    _getNextMove = GetNextMove;
    _getNextCapture = GetNextCapture;

private (ulong Move, int MoveIndex) GetNextMove(Position Position, int Depth, ulong BestMove)
{
    while (true)
    {
        int firstMoveIndex;
        int lastMoveIndex;
        if (Position.CurrentMoveIndex < Position.MoveIndex)
        {
            ulong move = Position.Moves[Position.CurrentMoveIndex];
            if (Move.Played(move))
            {
                // Don't play best move twice.
                Position.CurrentMoveIndex++;
                continue
            }
            (ulong Move, int MoveIndex) nextMove = (move, Position.CurrentMoveIndex);
            Position.CurrentMoveIndex++;
            return nextMove;
        }
        switch (Position.MoveGenerationStage)
        {
            case MoveGenerationStage.BestMove:
                Position.FindPotentiallyPinnedPieces();
                if (BestMove != Move.Null)
                {
                    Position.Moves[Position.MoveIndex] = BestMove;
                    Position.MoveIndex++;
                }
                Position.MoveGenerationStage++;
                continue;
            case MoveGenerationStage.Captures:
                firstMoveIndex = Position.MoveIndex;
                Position.GenerateMoves(MoveGeneration.OnlyCaptures);
                lastMoveIndex = Math.Max(firstMoveIndex, Position.MoveIndex - 1);
                if (lastMoveIndex > firstMoveIndex)
                {
                    PrioritizeMoves(Position, Position.Moves, firstMoveIndex, lastMoveIndex, BestMove, Depth);
                    SortMovesByPriority(Position.Moves, firstMoveIndex, lastMoveIndex);
                }
                Position.MoveGenerationStage++;
                continue;
            case MoveGenerationStage.NonCaptures:
                firstMoveIndex = Position.MoveIndex;
                Position.GenerateMoves(MoveGeneration.OnlyNonCaptures);
                lastMoveIndex = Math.Max(firstMoveIndex, Position.MoveIndex - 1);
                if (lastMoveIndex > firstMoveIndex)
                {
                    PrioritizeMoves(Position, Position.Moves, firstMoveIndex, lastMoveIndex, BestMove, Depth);
                    SortMovesByPriority(Position.Moves, firstMoveIndex, lastMoveIndex);
                }
                Position.MoveGenerationStage++;
                continue;
            case MoveGenerationStage.End:
                return (Move.Null, Position.CurrentMoveIndex);
        }
        break;
    }
    return (Move.Null, Position.CurrentMoveIndex);
}

private (ulong Move, int MoveIndex) GetNextCapture(Position Position, int Depth, ulong BestMove)
{
    while (true)
    {
        if (Position.CurrentMoveIndex < Position.MoveIndex)
        {
            (ulong Move, int MoveIndex) nextMove = (Position.Moves[Position.CurrentMoveIndex], Position.CurrentMoveIndex);
            Position.CurrentMoveIndex++;
            return nextMove;
        }
        switch (Position.MoveGenerationStage)
        {
            case MoveGenerationStage.BestMove:
            case MoveGenerationStage.Captures:
                Position.FindPotentiallyPinnedPieces();
                int firstMoveIndex = Position.MoveIndex;
                Position.GenerateMoves(MoveGeneration.OnlyCaptures);
                int lastMoveIndex = Math.Max(firstMoveIndex, Position.MoveIndex - 1);
                if (lastMoveIndex > firstMoveIndex) SortMovesByPriority(Position.Moves, firstMoveIndex, lastMoveIndex); // Don't prioritize moves.  MVV / LVA is good enough when ordering captures.
                Position.MoveGenerationStage = MoveGenerationStage.End;
                continue;
            case MoveGenerationStage.End:
                return (Move.Null, Position.CurrentMoveIndex);
        }
        break;
    }
    return (Move.Null, Position.CurrentMoveIndex);
}

Search.cs GetDynamicScore

do
{
    ulong move;
    if (Depth == 0)
    {
        // Search root moves.
        moveIndex++;
        if (moveIndex == 0)
        {
            PrioritizeMoves(Board.CurrentPosition, _rootMoves, lastMoveIndex, bestMove, Depth);
            SortMovesByPriority(_rootMoves, _rootScores, lastMoveIndex);
        }
        if (moveIndex > lastMoveIndex) break;
        move = _rootMoves[moveIndex];
    }
    else
    {
        // Search moves at current position.
        (move, moveIndex) = GetNextMove(Board.CurrentPosition, Depth, bestMove);
        if (move == Move.Null) break;
    }
    if ((Depth == 0|| Board.IsMoveLegal(ref move))
    {
        // Move is legal.
        legalMoveNumber++;
        if (Depth == 0)
        {
            // Update root move.
            _rootMove = move;
            _rootMoveNumber = legalMoveNumber;
        }
    }
    else continue// Skip illegal move.

Search.cs GetQuietScore

public int GetQuietScore(Board Board, int Depth, int Horizon, int Alpha, int Beta)
{
    if ((Board.Nodes > Board.NodesExamineTime) || NodesPerSecond.HasValue)
    {
        // Examine time.
        ExamineTime(Board.Nodes);
        long intervals = Board.Nodes / UciStream.NodesTimeInterval;
        Board.NodesExamineTime = UciStream.NodesTimeInterval * (intervals + 1);
    }
    if (!Continue && (_bestMoves[0!= Move.Null)) return StaticScore.Interrupted; // Search was interrupted.
    (bool terminalDraw, _) = Evaluation.IsTerminalDraw(Board.CurrentPosition);
    if ((Depth > 0&& terminalDraw) return 0// Terminal node (games ends on this move)
    // Search for a quiet position where no captures are possible.
    _selectiveHorizon = Math.Max(Depth, _selectiveHorizon);
    bool drawnEndgame = Evaluation.IsDrawnEndgame(Board.CurrentPosition);
    Delegates.GetNextMove getNextMove;
    int staticScore;
    if (Board.CurrentPosition.KingInCheck)
    {
        // King is in check.  Search all moves.
        getNextMove = _getNextMove;
        // Don't evaluate static score since moves when king is in check are not futile.
        staticScore = 0;
    }
    else
    {
        // King is not in check.  Search only captures.
        getNextMove = _getNextCapture;
        staticScore = drawnEndgame ? 0 : Evaluation.GetStaticScore(Board.CurrentPosition);
        if (staticScore >= Beta) return Beta; // Prevent worsening of position by making a bad capture.  Stand pat.
        Alpha = Math.Max(staticScore, Alpha);
    }
    int legalMoveNumber = 0;
    Board.CurrentPosition.PrepareMoveGeneration();
    do
    {
        (ulong move, _) = getNextMove(Board.CurrentPosition, Depth, Move.Null); // Don't retrieve (or update) best move from the cache.  Rely on MVV / LVA move order.
        if (move == Move.Null) break;
        if (Board.IsMoveLegal(ref move)) legalMoveNumber++// Move is legal.
        else continue// Skip illegal move.
        if (IsMoveFutile(Board.CurrentPosition, Depth, Horizon, move, legalMoveNumber, staticScore, drawnEndgame, Alpha, Beta)) continue// Move is futile.  Skip move.
        // Play and search move.
        Board.PlayMove(move);
        int score = -GetQuietScore(Board, Depth + 1, Horizon, -Beta, -Alpha);
        Board.UndoMove();
        if (Math.Abs(score) == StaticScore.Interrupted) return score; // Stop searching.
        if (score >= Beta) return Beta; // Position is not the result of best play by both players.
        Alpha = Math.Max(score, Alpha);
    } while (true);
    if ((legalMoveNumber == 0&& Board.CurrentPosition.KingInCheck) return Evaluation.GetMateScore(Depth); // Terminal node (games ends on this move)
    // Return score of best move.
    return Alpha;
}

This improved MadChess 3.0 Beta’s move generation speed (Nodes Per Second) while searching and gained 39 ELO points. MadChess 3.0 Beta searches typical middlegame positions at > 5 million NPS. The evaluation function still is limited to material, piece location, draw detection, and checkmate.

 

Feature Category Date SVN1 WAC2 ELO Rating3 Improvement
Staged Move Generation Search 2018 Dec 15 93 275 2210 +39
History Heuristics Search 2018 Dec 03 84 275 2171 +28
Eval Param Tuning Evaluation 2018 Nov 24 75 272 2143 +47
Sophisticated Search
Material and Piece Location
Baseline 2018 Nov 08 58 269 2096 0
  1. Subversion source code revision (for my own use)
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move

MadChess 3.0 Beta Build 084 (History Heuristics)

I increased the playing strength of MadChess 3.0 by improving the history heuristics used by Late Move Reductions (LMR).

First, I added a flag that indicates if a move was played during search (indicated below with “!”). This implies the move is legal (doesn’t expose own king to check) and search examined it (as opposed to moves appearing in the move list after a move that causes a beta cutoff). Moves are encoded as ulong primitives like so:

// Move bits
// Higher priority moves have higher ulong value.
// 6 6 6 6 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
// 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
// B|CapV   |CapA   |Promo  |Kil|History                                              |!|O|K|E|D|P|C|Q|From         |To           
// B =     Best Move
// CapV =  Capture Victim
// CapA =  Capture Attacker (inverted)
// Promo = Promoted Piece
// Kil  =  Killer Move
// ! =     Played
// O =     Castling
// K =     King Move
// E =     En Passant Capture
// D =     Double Pawn Move
// P =     Pawn Move
// C =     Check
// Q =     Quiet (not capture, pawn promotion, castling, or check)
// From =  From (one extra bit for illegal square)
// To =    To (one extra bit for illegal square)

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static bool Played(ulong Move) => (Move & _playedMask) >> _playedShift > 0;

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void SetPlayed(ref ulong Move, bool Played)
{
    ulong played = Played ? 1ul : 0;
    // Clear
    Move &= _playedUnmask;
    // Set
    Move |= played << _playedShift;
    // Validate move.
    Debug.Assert(Engine.Move.Played(Move) == Played);
    Debug.Assert(IsValid(Move));
}

Next, I altered the search function to flag played moves.

if ((Depth == 0) || Board.IsMoveLegal(ref move))
{
    // Move is legal.
    legalMoveNumber++;
    if (Depth == 0)
    {
        // Update root move.
        _rootMove = move;
        _rootMoveNumber = legalMoveNumber;
    }
}
else  continue; // Skip illegal move.
if (IsMoveFutile(Board.CurrentPosition, Depth, Horizon, move, legalMoveNumber, staticScore, drawnEndgame, Alpha, Beta)) continue; // Move is futile.  Skip move.
if (Move.IsQuiet(move)) quietMoveNumber++;
int searchHorizon = GetSearchHorizon(Board.CurrentPosition, Horizon, move, quietMoveNumber, drawnEndgame);
int moveBeta;
if ((legalMoveNumber == 1) || (toHorizon < _pvsMinToHorizon)) moveBeta = Beta; // Search with full alpha / beta window.
else moveBeta = bestScore + 1; // Search with zero alpha / beta window.
// Play and search move.
Move.SetPlayed(ref move, true);
Board.CurrentPosition.Moves[moveIndex] = move;
Board.PlayMove(move);
score = -GetDynamicScore(Board, Depth + 1, searchHorizon, true, -moveBeta, -Alpha);

Then I modified the search function so it not only increments move history for quiet moves that cause a beta cutoff, but also decrements move history for quiet moves that failed to cause a beta cutoff. The decrement is applied only if a later quiet move actually caused a beta cutoff.

if (score >= Beta)
{
    // Position is not the result of best play by both players.
    Stats.BetaCutoffs++;
    if (legalMoveNumber == 1) Stats.BetaCutoffFirstMove++;
    Stats.BetaCutoffMoveNumber += legalMoveNumber;
    if (Move.IsQuiet(move))
    {
        // Update move heuristics.
        int historyIncrement = toHorizon * toHorizon;
        _killerMoves.UpdateValue(Board.CurrentPosition, Depth, move);
        _moveHistory.UpdateValue(Board.CurrentPosition, move, historyIncrement);
        // Decrement move index immediately so as not to include the quiet move that caused the beta cutoff.
        moveIndex--;
        while (moveIndex >= 0)
        {
            ulong quietMove = Board.CurrentPosition.Moves[moveIndex];
            if (Move.IsQuiet(quietMove) && Move.Played(quietMove))
            {
                // Update history of prior quiet move that failed to produce cutoff.
                _moveHistory.UpdateValue(Board.CurrentPosition, quietMove, -historyIncrement);
            }
            moveIndex--;
        }
    }
    UpdateBestMoveCache(Board.CurrentPosition, cachedPosition, Depth, Horizon, move, score, Alpha, Beta);
    return Beta;

Finally, I modified the Move class to allow negative history values (though stored internally as a positive value to avoid complications with twos complement bit notation used by the .NET Core runtime to represent negative integers).

private const int _historyPadding = 67_108_864; // History has 48 - 22 + 1 = 27 bits.  2 Pow 27 = 134_217_728.

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int History(ulong Move) => (int) ((Move & _historyMask) >> _historyShift) - _historyPadding; // History score is a positive number.

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void SetHistory(ref ulong Move, int History)
{
    // Ensure history score is a positive number.
    int history = History + _historyPadding;
    // Clear
    Move &= _historyUnmask;
    // Set
    Move |= (ulong) history << _historyShift;
    // Validate move.
    Debug.Assert(Engine.Move.History(Move) == History);
    Debug.Assert(IsValid(Move));
}

The listmoves command demonstrates the search function will assign negative history values.

listmoves
Rank   Move  Best  Cap Victim  Cap Attacker  Promo  Killer  History              Priority
====  =====  ====  ==========  ============  =====  ======  =======  ====================
  01   d7d4  True       Queen         Queen              0       -1  12141986070363407779
  02   f6d5                                              2     2857    433752951094266523
  03   h7h5                                              1      -56    433189988923033503
  04   f8e7                                              0    15940    432627106061501068
  05   e8e7                                              0     7705    432627071521931788
  06   a8b8                                              0     2985    432627051724292097
  07   d7d6                                              0      794    432627042534573459
  08   c6c5                                              0       -1    432627039200168218
  09   d7d5                                              0       -6    432627039179130267
  10   a8a7                                              0       -8    432627039170740232
  11   f6g4                                              0       -9    432627039166548646
  12   f6g8                                              0      -10    432627039162354310
  13   f6e4                                              0      -11    432627039158160036
  14   f6h5                                              0      -13    432627039149771423
  15   f8d6                                              0      -13    432627039149769363
  16   d7e7                                              0      -20    432627039120409996
  17   d7c7                                              0      -20    432627039120409994
  18   d7b7                                              0      -21    432627039116215689
  19   f8c5                                              0      -24    432627039103632026
  20   c8b7                                              0      -24    432627039103631625
  21   d7a7                                              0      -34    432627039061689736
  22   d7d8                                              0      -34    432627039061689731
  23   g7g5                                              0      -41    432627039032526622
  24   e6e5                                              0      -44    432627039019813404
  25   g7g6                                              0      -53    432627038982063894
  26   b4b3                                              0      -56    432627038969483433
  27   a6a5                                              0      -56    432627038969481240
  28   h7h6                                              0      -56    432627038969481111
  29   h8g8                                              0      -56    432627038969414534

29 legal moves

This improved MadChess 3.0 Beta’s tactical awareness and gained 28 ELO points. The evaluation function still is limited to material, piece location, draw detection, and checkmate.

I made two other changes that did not greatly affect the strength of MadChess 3.0 Beta. I added detection of drawish (pawnless) endgames. This may have contributed 5 of the 28 ELO, but I don’t really know because the error margins for 4,000 games are +/- 20 ELO. If a drawish endgame is encountered, MadChess 3.0 Beta assigns a zero score but allows the search to continue (as opposed to dead drawn endgames such as Kk, KBk, or KNk; threefold repetition; 50 moves without a capture or pawn move; or insufficient material to checkmate, where the search is terminated).

  • KQkq
  • KQkrr
  • KRRkrr
  • KRBkrb
  • KRBkrn
  • KRNkrn
  • KRBkr
  • KRNkr
  • KRBNkr
  • KRkr
  • KRkb
  • KRkn
  • KNNkb
  • KNNkn
  • KNNk

Also, I changed the Board.IsMoveLegal function so it plays a null move when determining if a move checks the enemy king. Previously, Board.IsMoveLegal had determined check without actually playing a null move. This caused a subtle bug, though. As a consequence of this change, move legality checking searches an additional node, so the engine reports increased search speed in Nodes Per Second (NPS). This of course is an artificial speed increase, but it does align MadChess 3.0 Beta’s node counting with MadChess 2.x’s. MadChess 3.0 Beta searches the WAC position test at 4.31 million NPS on my PC.

 

Feature Category Date SVN1 WAC2 ELO Rating3 Improvement
History Heuristics Search 2018 Dec 03 84 275 2171 +28
Eval Param Tuning Evaluation 2018 Nov 24 75 272 2143 +47
Sophisticated Search
Material and Piece Location
Baseline 2018 Nov 08 58 269 2096 0
  1. Subversion source code revision (for my own use)
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move

MadChess 3.0 Beta Build 075 (Eval Param Tuning)

I ported my particle swarm tuning code from MadChess 2.x to MadChess 3.0 Beta, then simplified and improved it. My code uses the Texel tuning technique described by Peter Österlund in a TalkChess forum post. I improved my particle swarm algorithm in the following manner.

  • Simplified update of evaluation parameters via EvaluationConfig class.
  • Run the Iterate method of each ParticleSwarm on the .NET Core threadpool instead of using dedicated threads.
  • Locate global best particle (among all particle swarms) and update particle velocities after all Iterate methods have completed. This eliminates need to synchronize reads and writes of global state via a lock (to make code thread-safe). Algorithm performs best if number of particle swarms <= number of physical CPU cores.
  • Randomize location of all particles, except the global best, if 10 iterations fail to improve evaluation error. Retaining the global best causes other particles to be drawn back towards it, though their motions are randomized- they’re also drawn towards their individual best and swarm best with random magnitudes, so they jitter in particle-space. They may encounter a new global best on their path towards the last known global best.

In his post, Peter describes how to calibrate evaluation parameters by examining a large collection of games played by strong Grandmasters or engines. By scoring every position in every game, mapping the score (which represents fractional pawn units) to a winning percentage using a sigmoid function, then summing the square of the difference between the winning percentage and the actual result of the game (0 = player-to-move loses, 1/2 = draw, 1 = win), the chess engine’s strength can be improved by minimizing the evaluation error. Peter does not describe how to minimize the error- that effort is left for the chess engine programmer. The minimization effort is challenging because the parameter space is huge. MadChess 3.0 Beta’s evaluation function considers only material and piece square location, and yet, given reasonable minimum and maximum integer values for all evaluation parameters, 1.75 x 1068 discrete parameter combinations are possible.

Skip Code, Go To Results

Particle.cs

public void ConfigureEvaluation(Evaluation Evaluation)
{
    EvaluationConfig evalConfig = Evaluation.Config;
    // Middlegame
    // Pawns
    evalConfig.MgPawnAdvancement = Parameters[nameof(EvaluationConfig.MgPawnAdvancement)].Value;
    evalConfig.MgPawnCentrality = Parameters[nameof(EvaluationConfig.MgPawnCentrality)].Value;
    // Knights
    evalConfig.MgKnightAdvancement = Parameters[nameof(EvaluationConfig.MgKnightAdvancement)].Value;
    evalConfig.MgKnightCentrality = Parameters[nameof(EvaluationConfig.MgKnightCentrality)].Value;
    evalConfig.MgKnightCorner = Parameters[nameof(EvaluationConfig.MgKnightCorner)].Value;
    evalConfig.MgKnightConstant = Parameters[nameof(EvaluationConfig.MgKnightConstant)].Value;
    // Bishops
    evalConfig.MgBishopAdvancement = Parameters[nameof(EvaluationConfig.MgBishopAdvancement)].Value;
    evalConfig.MgBishopCentrality = Parameters[nameof(EvaluationConfig.MgBishopCentrality)].Value;
    evalConfig.MgBishopCorner = Parameters[nameof(EvaluationConfig.MgBishopCorner)].Value;
    evalConfig.MgBishopConstant = Parameters[nameof(EvaluationConfig.MgBishopConstant)].Value;
    // Rooks
    evalConfig.MgRookAdvancement = Parameters[nameof(EvaluationConfig.MgRookAdvancement)].Value;
    evalConfig.MgRookCentrality = Parameters[nameof(EvaluationConfig.MgRookCentrality)].Value;
    evalConfig.MgRookCorner = Parameters[nameof(EvaluationConfig.MgRookCorner)].Value;
    evalConfig.MgRookConstant = Parameters[nameof(EvaluationConfig.MgRookConstant)].Value;
    // Queens
    evalConfig.MgQueenAdvancement = Parameters[nameof(EvaluationConfig.MgQueenAdvancement)].Value;
    evalConfig.MgQueenCentrality = Parameters[nameof(EvaluationConfig.MgQueenCentrality)].Value;
    evalConfig.MgQueenCorner = Parameters[nameof(EvaluationConfig.MgQueenCorner)].Value;
    evalConfig.MgQueenConstant = Parameters[nameof(EvaluationConfig.MgQueenConstant)].Value;
    // King
    evalConfig.MgKingAdvancement = Parameters[nameof(EvaluationConfig.MgKingAdvancement)].Value;
    evalConfig.MgKingCentrality = Parameters[nameof(EvaluationConfig.MgKingCentrality)].Value;
    evalConfig.MgKingCorner = Parameters[nameof(EvaluationConfig.MgKingCorner)].Value;
    // Endgame
    // Pawns
    evalConfig.EgPawnAdvancement = Parameters[nameof(EvaluationConfig.EgPawnAdvancement)].Value;
    evalConfig.EgPawnCentrality = Parameters[nameof(EvaluationConfig.EgPawnCentrality)].Value;
    // Knights
    evalConfig.EgKnightAdvancement = Parameters[nameof(EvaluationConfig.EgKnightAdvancement)].Value;
    evalConfig.EgKnightCentrality = Parameters[nameof(EvaluationConfig.EgKnightCentrality)].Value;
    evalConfig.EgKnightCorner = Parameters[nameof(EvaluationConfig.EgKnightCorner)].Value;
    evalConfig.EgKnightConstant = Parameters[nameof(EvaluationConfig.EgKnightConstant)].Value;
    // Bishops
    evalConfig.EgBishopAdvancement = Parameters[nameof(EvaluationConfig.EgBishopAdvancement)].Value;
    evalConfig.EgBishopCentrality = Parameters[nameof(EvaluationConfig.EgBishopCentrality)].Value;
    evalConfig.EgBishopCorner = Parameters[nameof(EvaluationConfig.EgBishopCorner)].Value;
    evalConfig.EgBishopConstant = Parameters[nameof(EvaluationConfig.EgBishopConstant)].Value;
    // Rooks
    evalConfig.EgRookAdvancement = Parameters[nameof(EvaluationConfig.EgRookAdvancement)].Value;
    evalConfig.EgRookCentrality = Parameters[nameof(EvaluationConfig.EgRookCentrality)].Value;
    evalConfig.EgRookCorner = Parameters[nameof(EvaluationConfig.EgRookCorner)].Value;
    evalConfig.EgRookConstant = Parameters[nameof(EvaluationConfig.EgRookConstant)].Value;
    // Queens
    evalConfig.EgQueenAdvancement = Parameters[nameof(EvaluationConfig.EgQueenAdvancement)].Value;
    evalConfig.EgQueenCentrality = Parameters[nameof(EvaluationConfig.EgQueenCentrality)].Value;
    evalConfig.EgQueenCorner = Parameters[nameof(EvaluationConfig.EgQueenCorner)].Value;
    evalConfig.EgQueenConstant = Parameters[nameof(EvaluationConfig.EgQueenConstant)].Value;
    // King
    evalConfig.EgKingAdvancement = Parameters[nameof(EvaluationConfig.EgKingAdvancement)].Value;
    evalConfig.EgKingCentrality = Parameters[nameof(EvaluationConfig.EgKingCentrality)].Value;
    evalConfig.EgKingCorner = Parameters[nameof(EvaluationConfig.EgKingCorner)].Value;
    Evaluation.Configure();
}

How large is 1.75 x 1068? I need add only a few more evaluation parameters for the number of discrete parameter combinations to surpass the number of atoms in the universe.

I majored in physics in college, but it’s been a while since I’ve read math-intensive scientific papers, so rather than implement ADAM or other multivariate, derivative-free gradient descent algorithms (or determine how to plug the MadChess 3.0 Beta evaluation error cost function into a third-party optimization library), I decided to trust the particles. They succeeded in finding better evaluation parameters for MadChess 2.x, and they’ve succeeded again for MadChess 3.0 Beta.

While not a complete listing, here’s code that illustrates my implementation of a multi-threaded particle swarm optimizer.

UciStream.cs

private void Tune(IList<string> Tokens)
{
    string pgnFilename = Tokens[1].Trim();
    int particleSwarmsCount = int.Parse(Tokens[2].Trim());
    int particlesPerSwarm = int.Parse(Tokens[3].Trim());
    int winPercentScale = int.Parse(Tokens[4].Trim()); // Use 661 for Gm2700EloGamesSince2000.pgn.
    int iterations = int.Parse(Tokens[5].Trim());
    _commandStopwatch.Restart();
    ParticleSwarms particleSwarms = new ParticleSwarms(pgnFilename, particleSwarmsCount, particlesPerSwarm, winPercentScale, WriteMessageLine);
    particleSwarms.Optimize(iterations);
    _commandStopwatch.Stop();
}

ParticleSwarms.cs

public void Optimize(int Iterations)
{
    // Determine size of parameter space.
    double parameterSpace = 1d;
    Particle firstParticleInFirstSwarm = this[0].Particles[0];
    for (int index = 0; index < firstParticleInFirstSwarm.Parameters.Count; index++)
    {
        Parameter parameter = firstParticleInFirstSwarm.Parameters[index];
        parameterSpace *= parameter.MaxValue - parameter.MinValue + 1;
    }
    _writeMessageLine($"Optimizing {firstParticleInFirstSwarm.Parameters.Count} parameters in a space of {parameterSpace:e2} discrete parameter combinations.");
    // Create game objects for each particle swarm.
    Board[] boards = new Board[Count];
    Search[] searches = new Search[Count];
    Evaluation[] evaluations = new Evaluation[Count];
    for (int index = 0; index < Count; index++)
    {
        Board board = new Board(_writeMessageLine);
        board.PrecalculatedMoves = new PrecalculatedMoves(board.BishopMoveMasks, board.RookMoveMasks, board.CreateMoveDestinationsMask, _writeMessageLine);
        boards[index] = board;
        Cache cache = new Cache(1, board.ValidateMove);
        KillerMoves killerMoves = new KillerMoves(Search.MaxHorizon);
        MoveHistory moveHistory = new MoveHistory();
        Evaluation evaluation = new Evaluation(new EvaluationConfig(), board.GetPositionCount);
        evaluations[index] = evaluation;
        searches[index] = new Search(cache, killerMoves, moveHistory, evaluation, () => false, _writeMessageLine);
    }
    Task[] tasks = new Task[Count];
    int iterationsWithoutProgress = 0;
    double bestEvaluationError = double.MaxValue;
    for (int iteration = 1; iteration <= Iterations; iteration++)
    {
        // Run iteration tasks on threadpool.
        _iterations = iteration;
        for (int index = 0; index < Count; index++)
        {
            ParticleSwarm particleSwarm = this[index];
            Board board = boards[index];
            Search search = searches[index];
            Evaluation evaluation = evaluations[index];
            tasks[index] = Task.Run(() => particleSwarm.Iterate(board, search, evaluation));
        }
        // Wait for all particle swarms to complete an iteration.
        Task.WaitAll(tasks);
        Particle bestParticle = GetBestParticle();
        if (bestParticle.EvaluationError < bestEvaluationError)
        {
            bestEvaluationError = bestParticle.BestEvaluationError;
            iterationsWithoutProgress = 0;
        }
        else iterationsWithoutProgress++;
        if (iterationsWithoutProgress == _maxIterationsWithoutProgress)
        {
            RandomizeParticles(bestParticle);
            iterationsWithoutProgress = 0;
        }
        else UpdateVelocity();
        UpdateStatus();
    }
}

ParticleSwarm.cs

public void Iterate(Board Board, Search Search, Evaluation Evaluation)
{
    Particle bestParticle = GetBestParticle();
    for (int index = 0; index < Particles.Count; index++)
    {
        Particle particle = Particles[index];
        if (!ReferenceEquals(particle, bestParticle) && (SafeRandom.NextDouble() <= _particleDeathPercent))
        {
            // Recreate particle at random location.
            particle = new Particle(particle.PgnGames, particle.Parameters.DuplicateWithRandomValues());
            Particles[index] = particle;
        }
        particle.Move();
        particle.ConfigureEvaluation(Evaluation);
        particle.CalculateEvaluationError(Board, Search, _winPercentScale);
    }
}

Particle.cs

public void Move()
{
    // Move particle in parameter space.
    for (int index = 0; index < Parameters.Count; index++)
    {
        Parameter parameter = Parameters[index];
        parameter.Value += (int) _velocities[index];
        if (parameter.Value < parameter.MinValue)
        {
            parameter.Value = parameter.MinValue;
            _velocities[index] = 0;
        }
        if (parameter.Value > parameter.MaxValue)
        {
            parameter.Value = parameter.MaxValue;
            _velocities[index] = 0;
        }
    }
}

public void CalculateEvaluationError(Board Board, Search Search, int WinPercentScale)
{
    // Sum the square of evaluation error over all games.
    double evaluationError = 0d;
    for (int gameIndex = 0; gameIndex < PgnGames.Count; gameIndex++)
    {
        PgnGame game = PgnGames[gameIndex];
        Board.SetPosition(Board.StartPositionFen, true);
        for (int moveIndex = 0; moveIndex < game.Moves.Count; moveIndex++)
        {
            ulong move = game.Moves[moveIndex];
            // Play move.
            Board.PlayMove(move);
            // Get quiet score.
            Board.NodesExamineTime = long.MaxValue;
            Search.PvInfoUpdate = false;
            Search.Continue = true;
            int quietScore = Search.GetQuietScore(Board, 00-StaticScore.Max, StaticScore.Max);
            // Convert quiet score to win percent.
            double winPercent = GetWinPercent(quietScore, WinPercentScale);
            // Compare win percent to game result.
            double result;
            // ReSharper disable once SwitchStatementMissingSomeCases
            switch (game.Result)
            {
                case GameResult.WhiteWon:
                    result = Board.CurrentPosition.WhiteMove ? 1d : 0;
                    break;
                case GameResult.Draw:
                    result = 0.5d;
                    break;
                case GameResult.BlackWon:
                    result = Board.CurrentPosition.WhiteMove ? 0 : 1d;
                    break;
                default:
                    throw new InvalidOperationException($"{game.Result} game result not supported.");
            }
            evaluationError += Math.Pow(winPercent - result, 2);
        }
    }
    EvaluationError = evaluationError;
    if (EvaluationError < BestEvaluationError)
    {
        BestEvaluationError = EvaluationError;
        Parameters.CopyValuesTo(BestParameters);
    }
}

public void UpdateVelocity(Particle BestSwarmParticle, Particle GloballyBestParticle)
{
    for (int index = 0; index < Parameters.Count; index++)
    {
        Parameter parameter = Parameters[index];
        Parameter bestParameter = BestParameters[index];
        Parameter bestSwarmParameter = BestSwarmParticle.BestParameters[index];
        Parameter globallyBestParameter = GloballyBestParticle.BestParameters[index];
        double velocity = _inertia * _velocities[index];
        double particleMagnitude = SafeRandom.NextDouble() * _influence;
        velocity += particleMagnitude * (bestParameter.Value - parameter.Value);
        double swarmMagnitude = SafeRandom.NextDouble() * ParticleSwarm.Influence;
        velocity += swarmMagnitude * (bestSwarmParameter.Value - parameter.Value);
        double allSwarmsMagnitude = SafeRandom.NextDouble() * ParticleSwarms.Influence;
        velocity += allSwarmsMagnitude * (globallyBestParameter.Value - parameter.Value);
        _velocities[index] = velocity;
    }
}

private static double GetWinPercent(int Score, int WinPercentScale) => 1d / (1d + Math.Pow(10d-1d * Score / WinPercentScale));

Evaluation.cs

public void Configure()
{
    // Calculate piece location values.
    for (int square = 0; square < 64; square++)
    {
        int rank = Board.WhiteRanks[square];
        int file = Board.Files[square];
        int squareCentrality = 3 - Board.GetShortestDistance(square, Board.CentralSquares);
        int fileCentrality = 3 - Math.Min(Math.Abs(3 - file), Math.Abs(4 - file));
        int nearCorner = 3 - Board.GetShortestDistance(square, Board.CornerSquares);
        // Middlegame
        _mgPawnLocations[square] = rank * Config.MgPawnAdvancement + squareCentrality * Config.MgPawnCentrality;
        _mgKnightLocations[square] = rank * Config.MgKnightAdvancement + squareCentrality * Config.MgKnightCentrality + nearCorner * Config.MgKnightCorner + Config.MgKnightConstant;
        _mgBishopLocations[square] = rank * Config.MgBishopAdvancement + squareCentrality * Config.MgBishopCentrality + nearCorner * Config.MgBishopCorner + Config.MgBishopConstant;
        _mgRookLocations[square] = rank * Config.MgRookAdvancement + fileCentrality * Config.MgRookCentrality + nearCorner * Config.MgRookCorner + Config.MgRookConstant;
        _mgQueenLocations[square] = rank * Config.MgQueenAdvancement + squareCentrality * Config.MgQueenCentrality + nearCorner * Config.MgQueenCorner + Config.MgQueenConstant;
        _mgKingLocations[square] = rank * Config.MgKingAdvancement + squareCentrality * Config.MgKingCentrality + nearCorner * Config.MgKingCorner;
        // Endgame
        _egPawnLocations[square] = rank * Config.EgPawnAdvancement + squareCentrality * Config.EgPawnCentrality + Config.EgPawnConstant;
        _egKnightLocations[square] = rank * Config.EgKnightAdvancement + squareCentrality * Config.EgKnightCentrality + nearCorner * Config.EgKnightCorner + Config.EgKnightConstant;
        _egBishopLocations[square] = rank * Config.EgBishopAdvancement + squareCentrality * Config.EgBishopCentrality + nearCorner * Config.EgBishopCorner + Config.EgBishopConstant;
        _egRookLocations[square] = rank * Config.EgRookAdvancement + fileCentrality * Config.EgRookCentrality + nearCorner * Config.EgRookCorner + Config.EgRookConstant;
        _egQueenLocations[square] = rank * Config.EgQueenAdvancement + squareCentrality * Config.EgQueenCentrality + nearCorner * Config.EgQueenCorner + Config.EgQueenConstant;
        _egKingLocations[square] = rank * Config.EgKingAdvancement + squareCentrality * Config.EgKingCentrality + nearCorner * Config.EgKingCorner;
    }
}

 

Tuning Results

I used Chessbase to export all games played between two Grandmasters rated >= 2700 ELO since the year 2000. I realize I could tune MadChess’ evaluation function using games played by stronger engines, such as Stockfish or Komodo. However, I wish to avoid biasing my engine’s playing style towards that of other engines. I’d rather have it emulate a more human playing style. I fed my optimization algorithm the games played by 2700+ ELO Grandmasters since the year 2000 and the particles found new evaluation parameters worth 47 ELO in playing strength.

 

Feature Category Date SVN1 WAC2 ELO Rating3 Improvement
Eval Param Tuning Evaluation 2018 Nov 24 75 272 2143 +47
Sophisticated Search
Material and Piece Location
Baseline 2018 Nov 08 58 269 2096 0
  1. Subversion source code revision (for my own use)
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move

Graham Banks 70th Amateur Tournament Division 7

MadChess 2.2 participated in Graham Banks’ 70th Amateur Tournament in Division 7.

70th Amateur D7  2018
                                 1    2    3    4    5    6    7    8    9    0    1    2    
1   Bagatur 1.5e 64-bit          **** 11½½ 0½½½ ½½11 0½½1 1011 ½1½½ 01½½ ½001 01½1 ½110 1½1½  26.5/44  574.00
2   MadChess 2.2 64-bit          00½½ **** ½½00 1½1½ ½0½1 1011 1½0½ 1½½1 111½ 1½1½ ½½½1 110½  26.5/44  554.25
3   Drosophila 1.5.1 64-bit      1½½½ ½½11 **** 1000 ½100 ½½0½ ½½10 01½½ 111½ 0½11 ½110 ½½11  25.0/44
4   Lozza 1.18 64-bit            ½½00 0½0½ 0111 **** 1011 101½ 10½½ ½0½1 1½½1 00½1 11½½ ½0½1  24.0/44  515.75
5   Shallow r694 64-bit          1½½0 ½1½0 ½011 0100 **** ½½1½ 100½ 01½1 0101 ½½11 11½½ 0011  24.0/44  514.25
6   Jumbo 0.6.45 64-bit          0100 0100 ½½1½ 010½ ½½0½ **** ½100 ½101 1½1½ 11½1 11½½ 101½  23.5/44
7   RomiChess P3n 64-bit         ½0½½ 0½1½ ½½01 01½½ 011½ ½011 **** ½½½1 0½1½ 1010 010½ ½101  23.0/44
8   RookieMonster 1.5.13 64-bit  10½½ 0½½0 10½½ ½1½0 10½0 ½010 ½½½0 **** 1000 1000 1½1½ ½101  19.0/44  418.00
9   Waxman 2017                  ½110 000½ 000½ 0½½0 1010 0½0½ 1½0½ 0111 **** ½100 01½1 1½01  19.0/44  406.25
10  Topple 0.2.1 64-bit          10½0 0½0½ 1½00 11½0 ½½00 00½0 0101 0111 ½011 **** ½1½0 ½000  18.0/44  394.75
11  Nemeton 1.7                  ½001 ½½½0 ½001 00½½ 00½½ 00½½ 101½ 0½0½ 10½0 ½0½1 **** 11½1  18.0/44  390.75
12  Galjoen 0.39.2 64-bit        0½0½ 001½ ½½00 ½1½0 1100 010½ ½010 ½010 0½10 ½111 00½0 ****  17.5/44

Games