Engine CodeIf you're enjoying SharpChess, then perhaps $5 isn't a lot to ask? Thank you, Peter Hughes.
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;
}
private int AlphaBeta(Player player, int depth, int alpha, int beta, bool verify, ref Move moveAnalysed)
{
int val = int.MinValue;
HashTable.enmHashType hashType = HashTable.enmHashType.Alpha;
Move moveBest = null;
Move moveHash = null;
bool blnPVNode = false;
int intScoreAtEntry = 0;
bool blnAllMovesWereGenerated;
int intLegalMovesAttempted = 0;
m_intPositionsSearched++;
if ( (val = HashTable.ProbeHash(Board.HashCodeA, Board.HashCodeB, depth, alpha, beta, player.Colour)) != HashTable.UNKNOWN )
{
// High values of "val" indicate that a checkmate has been found
if (val>1000000 || val<-1000000)
{
val /= (m_intMaxSearchDepth-depth);
}
return val;
}
if (player.CanClaimThreeMoveRepetition)
{
return -player.OtherPlayer.Score;
}
// Depth <=0 means we're into Quiescence searching
if (depth <= 0)
{
if (depth < m_intMaxQDepth)
{
m_intMaxQDepth = depth;
if (m_intMaxQDepth<0)
{
m_intMaxQDepth+=0;
}
}
intScoreAtEntry = val = -player.OtherPlayer.Score; m_intEvaluations++;
if (val>100000000 || val<-100000000)
{
val /= (m_intMaxSearchDepth-depth);
}
// Allow a deeper ply of search if a piece was captured or if a pawn was promoted,
// or either side is in check.
if ( !(
moveAnalysed.PieceTaken != null
||
moveAnalysed.Name == Move.enmName.PawnPromotion
||
( moveAnalysed.IsInCheck || moveAnalysed.IsEnemyInCheck )
)
)
{
return val;
}
}
Move moveThis = null;
// Get last iteration's best move from the Transition Table
moveHash = HashTable.ProbeForBestMove(player.Colour);
// "Adaptive" Null-move forward pruning
R = (depth>6 && Game.Stage!=Game.enmStage.End) ? 3 : 2; // << This is the "adaptive" bit
// The rest is normal Null-move forward pruning
if (depth >= 3 )
{
Move moveNull = new Move(Game.TurnNo, 0, Move.enmName.NullMove, null, null, null, null, 0, 0);
val = -AlphaBeta(player.OtherPlayer, depth - R - 1, -beta, -beta + 1, verify, ref moveNull);
if ((DateTime.Now-m_PlayerClock.TurnStartTime) > m_tsnThinkingTimeMaxAllowed) goto TimeExpired;
if (val >= beta)
{
return beta;
}
}
// Generate moves
Moves movesPossible = new Moves();
blnAllMovesWereGenerated=( depth>0 || (moveAnalysed.IsInCheck || moveAnalysed.IsEnemyInCheck));
if ( blnAllMovesWereGenerated )
{
player.GenerateLazyMoves(depth, movesPossible, Moves.enmMovesType.All, null);
}
else
{
// Captures only
player.GenerateLazyMoves(depth, movesPossible, Moves.enmMovesType.Recaptures_Promotions, moveAnalysed.To);
}
// Enhanced Transposition Cutoff
foreach (Move movex in movesPossible)
{
if ( ((val = HashTable.ProbeHash(movex.HashCodeA, movex.HashCodeB, depth, alpha, beta, player.Colour)) != HashTable.UNKNOWN) && val>=beta)
{
return beta;
}
}
// Sort moves
foreach (Move movex in movesPossible)
{
movex.Score = 0;
if (moveHash!=null && movex.From.Ordinal==moveHash.From.Ordinal && movex.To.Ordinal==moveHash.To.Ordinal)
{
movex.Score += 1000000;
}
if (movex.Name==Move.enmName.PawnPromotion)
{
movex.Score += 10000;
}
if (movex.PieceTaken!=null)
{
// MVV/LVA (Most Valuable Victim/Least Valuable Attacker)
movex.Score += (movex.PieceTaken.Value - movex.Piece.Value/10);
}
else
{
movex.Score += (History.Retrieve(player.Colour, movex.From.Ordinal, movex.To.Ordinal)>>6);
}
}
movesPossible.SortByScore();
foreach (Move move in movesPossible)
{
moveThis = move.Piece.Move(move.Name, move.To);
if (moveThis.IsInCheck) { Move.Undo(moveThis); continue; }
intLegalMovesAttempted++;
if (moveBest==null)
{
moveBest = moveThis;
}
if (blnPVNode)
{
val = -AlphaBeta(player.OtherPlayer, depth - 1, -alpha-1, -alpha, verify, ref moveThis);
if ((DateTime.Now-m_PlayerClock.TurnStartTime) > m_tsnThinkingTimeMaxAllowed) { Move.Undo(moveThis); goto TimeExpired;}
if ((val > alpha) && (val < beta)) /* fail */
{
val = -AlphaBeta(player.OtherPlayer, depth - 1, -beta, -alpha, verify, ref moveThis);
if ((DateTime.Now-m_PlayerClock.TurnStartTime) > m_tsnThinkingTimeMaxAllowed) { Move.Undo(moveThis); goto TimeExpired;}
}
}
else
{
val = -AlphaBeta(player.OtherPlayer, depth - 1, -beta, -alpha, verify, ref moveThis);
if ((DateTime.Now-m_PlayerClock.TurnStartTime) > m_tsnThinkingTimeMaxAllowed) { Move.Undo(moveThis); goto TimeExpired;}
}
if (!blnAllMovesWereGenerated && val= beta)
{
alpha = beta;
moveThis.Beta = beta;
hashType = HashTable.enmHashType.Beta;
moveBest = moveThis;
goto Exit;
}
if (val > alpha)
{
blnPVNode = true; /* This is a PV node */
alpha = val;
hashType = HashTable.enmHashType.Exact;
moveBest = moveThis;
}
moveThis.Alpha = alpha;
moveThis.Beta = beta;
}
// Check for Stalemate
if (intLegalMovesAttempted==0) // depth>0 && !player.OtherPlayer.IsInCheck
{
// alpha = this.Score;
alpha = -player.OtherPlayer.Score;
}
Exit:
// Record best move
if (moveBest!=null)
{
History.Record(player.Colour, moveBest.From.Ordinal, moveBest.To.Ordinal, 0, 1<<(depth+6));
HashTable.RecordHash(Board.HashCodeA, Board.HashCodeB, depth, alpha, hashType, moveBest.From.Ordinal, moveBest.To.Ordinal, moveBest.Name, player.Colour);
}
else
HashTable.RecordHash(Board.HashCodeA, Board.HashCodeB, depth, alpha, hashType, -1, -1, Move.enmName.NullMove, player.Colour);
TimeExpired:
return alpha;
}
