Blog of a Filipino Developer about C#, VB.NET, ASP.NET, Java, PHP, SQL Server, MySql and Oracle RSS 2.0
 Thursday, June 09, 2005

SharpChess is an Open-Source game wholely developed using C#. This application was developed by Peter Hughes.

I'm really impressed on how he implemented some stuff in the program. One thing that really captured my eyes is clarity of how he implemented the computation of the best possible move. the function he used is listed below:

public Move ComputeBestMove()
{
    //
    //    Returns the best move available for "this" player instance, from the current board position.
    //

    m_blnIsThinking = true;        // Set thinking to true while best move is being computed
    Player player = this;        // Set the player, whose move is to be computed, to "this" player object instance
    m_moveBest = null;            // Best move found so far. Used for display purposes.
    Move moveHash = null;        // The previous iteration's best move from the hash table.
    Move moveDepthBest = null;    // Best move at the last complete depth searched
    int alpha = MIN_SCORE;        // The score of the best move found so far
    int beta = MAX_SCORE;        // The score of the best move found by the enemy

    // Normal time allowed for this player to think
    m_tsnThinkingTimeAllotted = new TimeSpan( this.m_PlayerClock.TimeRemaining.Ticks / Math.Max(m_intGameMoves-(Game.TurnNo/2), 1) );
    
    // The computer only stops "thinking" when it has finished a full ply of thought,
    // UNLESS m_tsnThinkingTimeMaxAllowed is exceeded, then it stops right away.
    m_tsnThinkingTimeMaxAllowed = new TimeSpan( m_tsnThinkingTimeAllotted.Ticks*3 );
    
    // A new deeper ply of search will only be started, IF the cutoff time hasnt been reached yet.
    m_tsnThinkingTimeCutoff = new TimeSpan( m_tsnThinkingTimeAllotted.Ticks/3);

    m_intPositionsSearched = 0; // Total number of positions considered so far
    m_intEvaluations = 0;        // Total number of times the evaluation function has been called (May be less than PositonsSearched if hashtable works well)

    HashTable.ResetStats();        // Reset the main hash table hit stats
    //    HashTable.Clear(); Uncomment this to clear the hashtable at the beginning of each move
    HashTableCheck.ResetStats();// We also have a hash table in which we just store the check status for both players
    HashTablePawn.ResetStats();    // And finally a hash table that stores the positional score of just the pawns.
    History.Clear();            // Clear down the History Heuristic info, at the start of each move.


    // Here begins the main Iteractive Deepening loop of the entire search algorithm. (Cue dramitic music!)
    for (m_intSearchDepth=m_intMinSearchDepth; m_intSearchDepth<=m_intMaxSearchDepth; m_intSearchDepth++)
    {


        m_intMaxQDepth = m_intSearchDepth;    // A little counter to record the deepest Quiescence depth searched.

        // Get last iteration's best move from the HashTable
        moveHash = HashTable.ProbeForBestMove(player.Colour);

        // Generate and sort moves
        Moves movesPossible = new Moves();
        player.GenerateLegalMoves(movesPossible);    // movesPossible is an array (Moves container class) of Move objects that
        m_intTotalPositionsToSearch = movesPossible.Count;        // is passed in ByRef and gets populated by the various Piece objects

        // If only one move is available, then just play it!
        if (movesPossible.Count==1)
        {
            moveDepthBest = m_moveCurrent = movesPossible.Item(0);
            goto MoveSelected;
        }

        // Moves are now sorted in "hopefully" best move first, worse move last order.
        // The nature of the alpha/beta search, with its "beta cutoffs" means that the
        // more acuately we can "guess" the probable best moves, the fewer moves
        // that we'll then be considered, and the faster/deeper we'll be able to search.
        // I cant stress enough how important good "Move Ordering" is to a chess program.

        // Got through all the moves and assign a score to each one, then sort by this score
        foreach (Move movex in movesPossible)
        {
            movex.Score = 0;

            // If there is a "best move" in the hash table for this position, then give that maximum score
            if (moveHash!=null && movex.From.Ordinal==moveHash.From.Ordinal && movex.To.Ordinal==moveHash.To.Ordinal)
            {
                movex.Score += 1000000;
            }

            // Then any pawn promotions
            if (movex.Name==Move.enmName.PawnPromotion)
            {
                movex.Score += 10000;
            }
            
            // Then Captures
            if (movex.PieceTaken!=null)
            {
                // Use a "Static Exchange Evaluation (SEE)" to sort the captures.
                // This is basically a process of resolving all possible capture from this position,
                // in all various orders to see which permitation would result in winning the most material.
                // Similarly, moves that lead to the highest "loss" of material, for us, as sorted to the bottom.
                Move moveSee = movex.Piece.SEEMove(movex.Name, movex.To);
                movex.Score += -SEE(player.OtherPlayer, int.MinValue, int.MaxValue, movex.To);
                Move.SEEUndo(moveSee);
            }
            else
            {
                // Then finally non-capturing moves use the info from the History Heuristic table
                movex.Score += History.Retrieve(player.Colour, movex.From.Ordinal, movex.To.Ordinal);
            }
        }
        movesPossible.SortByScore();

        alpha = MIN_SCORE;    // The famous Alpha & Beta are set to their initial values
        beta = MAX_SCORE;    // at the start of each increasing search depth iteration

        m_intSearchPositionNo = 0;    // A counter that increments through the total root moves that can be played. Used to update the search progress bar.

        foreach (Move move in movesPossible)
        {
            // Actually "Make" the move we want to analyse
            m_moveCurrent = move.Piece.Move(move.Name, move.To);

            // Then use Alpha/Beta to work out its Score
            // Here in the 5 lines, is what is called a PVS (Prinicple Variation Search), whic is an optimisation
            // of the basic Alpha/Beta search. Rather than passing in the usual (-beta, -alpha) values, we instead
            // first try a zero window search of (-alpha-1, -alpha). Only if the search "fails", do we then try the
            // whole search again with the proper values.
            // PVS optimisation is MEGA, and speeded up my search no end!
            move.Score = m_moveCurrent.Score = -AlphaBeta(player.OtherPlayer, m_intSearchDepth-1, -alpha-1, -alpha, true, ref m_moveCurrent);
            if ((DateTime.Now-m_PlayerClock.TurnStartTime) > m_tsnThinkingTimeMaxAllowed) { Move.Undo(m_moveCurrent); goto TimeExpired;}
            if ((move.Score > alpha) && (move.Score < beta)) /* fail */
            {
                move.Score = m_moveCurrent.Score = -AlphaBeta(player.OtherPlayer, m_intSearchDepth-1, -beta, -alpha, true, ref m_moveCurrent);
                if ((DateTime.Now-m_PlayerClock.TurnStartTime) > m_tsnThinkingTimeMaxAllowed) { Move.Undo(m_moveCurrent); goto TimeExpired;}
            }
            
            this.MoveConsidered(); // Send an update event to the GUI.

            Move.Undo(m_moveCurrent);    // Undo the move, to get the board back to its original state

            m_intSearchPositionNo++;    // Move progress bar along one notch!

            // If the score of the move we just tried is better than the score of the best move we had
            // so far, at this depth, then make this the best move.
            if (m_moveCurrent.Score > alpha)
            {
                alpha = m_moveCurrent.Score;
                moveDepthBest = m_moveCurrent;
                // Update History Heuristic info
                History.Record(player.Colour, m_moveCurrent.From.Ordinal, m_moveCurrent.To.Ordinal, 1<<(m_intSearchDepth+6)); // Update history heuristic data
            }

            m_moveCurrent.Alpha = alpha;    // Store the alpha beta values so that we can look at them in the GUI Analysis Tree
            m_moveCurrent.Beta = beta;

        }

    MoveSelected:

        m_moveBest = moveDepthBest; // THE BEST MOVE is then recorded

        // Record, now discovered, best move for this position, in the hash table
        HashTable.RecordHash(Board.HashCodeA, Board.HashCodeB, m_intSearchDepth, m_moveBest.Score, HashTable.enmHashType.Exact, m_moveBest.From.Ordinal, m_moveBest.To.Ordinal, m_moveBest.Name, player.Colour);

        this.MoveConsidered();

        if ((DateTime.Now-m_PlayerClock.TurnStartTime) > m_tsnThinkingTimeCutoff && m_intSearchDepth >= m_intMinimumPlys ) goto TimeExpired;

        if (m_moveBest.Score > 99999) break; // Checkmate found so dont bother searching any deeper
    }


    TimeExpired:
    this.MoveConsidered();

    m_blnIsThinking = false;
    this.MoveConsidered();

    return m_moveBest;
}

The source code and executable is readily available for download from his site.

Check it out! I gave this one 5 stars!

Thursday, June 09, 2005 6:40:49 PM (GMT Standard Time, UTC+00:00)  #    Comments [0] -
.NET | Tech News and Issues
Comments are closed.
On this page
Archive
<December 2008>
SunMonTueWedThuFriSat
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910
About the author/Disclaimer

Disclaimer
The opinions expressed herein are my own personal opinions and do not represent my employer's view in any way.

© Copyright 2008
Keith Rull
Sign In
Statistics
Total Posts: 260
This Year: 57
This Month: 0
This Week: 0
Comments: 116
Themes
Pick a theme:
Ads
All Content © 2008, Keith Rull
DasBlog theme 'Business' created by Christoph De Baene (delarou)