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!
Disclaimer The opinions expressed herein are my own personal opinions and do not represent my employer's view in any way.