jcaisearchagent.java

这是自己在学习编写下象棋时参考过的很好的程序。

/**************************************************************************
 * jcAISearchAgent - An object which picks a best move according to a
 *                   variant of alphabeta search or another
 *
 * Purpose:
 * This is the object which picks a move for the computer player.  Implemented
 * as an abstract class to allow multiple search strategies to be played with.
 *
 * History
 * 07.08.00 Creation
 * 05.10.00 Added statistics and some corrections
 *************************************************************************/

package javachess;
import javachess.jcBoard;
import javachess.jcBoardEvaluator;
import javachess.jcAISearchAgentMTDF;
import javachess.jcAISearchAgentAlphabeta;
import javachess.jcTranspositionTable;
import java.util.Random;

public abstract class jcAISearchAgent
{
  /***************************************************************************
   * DATA MEMBERS
   **************************************************************************/

  // A transposition table for this object
  jcTranspositionTable TransTable;

  // A handle to the system's history table
  jcHistoryTable HistoryTable;

  // How will we assess position strengths?
  protected jcBoardEvaluator Evaluator;
  protected int FromWhosePerspective;

  // ID's for concrete subclasses; jcAISearchAgent works as a factory for its
  // concrete subclasses
  public static final int AISEARCH_ALPHABETA = 0;
  public static final int AISEARCH_MTDF = 1;

  // Search node types: MAXNODEs are nodes where the computer player is the
  // one to move; MINNODEs are positions where the opponent is to move.
  protected static final boolean MAXNODE = true;
  protected static final boolean MINNODE = false;

  // Alphabeta search boundaries
  protected static final int ALPHABETA_MAXVAL = 30000;
  protected static final int ALPHABETA_MINVAL = -30000;
  protected static final int ALPHABETA_ILLEGAL = -31000;

  // An approximate upper bound on the total value of all positional
  // terms in the evaluation function
  protected static final int EVAL_THRESHOLD = 200;

  // A score below which we give up: if Alphabeta ever returns a value lower
  // than this threshold, then all is lost and we might as well resign.  Here,
  // the value is equivalent to "mated by the opponent in 3 moves or less".
  protected static final int ALPHABETA_GIVEUP = -29995;

  Random Rnd;

  // Statistics
  int NumRegularNodes;
  int NumQuiescenceNodes;
  int NumRegularTTHits;
  int NumQuiescenceTTHits;
  int NumRegularCutoffs;
  int NumQuiescenceCutoffs;

  // A move counter, so that the agent knows when it can delete old stuff from
  // its transposition table
  int MoveCounter;

  /***************************************************************************
   * PUBLIC METHODS
   **************************************************************************/

  // Construction
  public jcAISearchAgent()
  {
    TransTable = new jcTranspositionTable();
    HistoryTable = jcHistoryTable.GetInstance();
    Evaluator = new jcBoardEvaluator();
    Rnd = new Random();
    MoveCounter = 0;
  }

  public jcAISearchAgent( jcBoardEvaluator eval )
  {
    AttachEvaluator( eval );
  }

  // boolean AttachEvaluator( jcBoardEvaluator eval )
  // Pick a function which the agent will use to assess the potency of a
  // position.  This may change during the game; for example, a special
  // "mop-up" evaluator may replace the standard when it comes time to drive
  // a decisive advantage home at the end of the game.
  public boolean AttachEvaluator( jcBoardEvaluator eval )
  {
    Evaluator = eval;
    return true;
  }

  // int AlphaBeta
  // The basic alpha-beta algorithm, used in one disguise or another by
  // every search agent class
  public int AlphaBeta( boolean nodeType, jcBoard theBoard, int depth,
                        int alpha, int beta )
  {
    jcMove mov = new jcMove();

    // Count the number of nodes visited in the full-width search
    NumRegularNodes++;

    // First things first: let's see if there is already something useful
    // in the transposition table, which might save us from having to search
    // anything at all
    if ( TransTable.LookupBoard( theBoard, mov ) && ( mov.SearchDepth >= depth ) )
    {
      if ( nodeType == MAXNODE )
      {
        if ( ( mov.MoveEvaluationType == jcMove.EVALTYPE_ACCURATE ) ||
             ( mov.MoveEvaluationType == jcMove.EVALTYPE_LOWERBOUND ) )
        {
          if ( mov.MoveEvaluation >= beta )
          {
            NumRegularTTHits++;
            return mov.MoveEvaluation;
          }
        }
      }
      else
      {
        if ( ( mov.MoveEvaluationType == jcMove.EVALTYPE_ACCURATE ) ||
             ( mov.MoveEvaluationType == jcMove.EVALTYPE_UPPERBOUND ) )
        {
          if ( mov.MoveEvaluation <= alpha )
          {
            NumRegularTTHits++;
            return mov.MoveEvaluation;
          }
        }
      }
    }

    // If we have reached the maximum depth of the search, stop recursion
    // and begin quiescence search
    if ( depth == 0 )
    {
      return QuiescenceSearch( nodeType, theBoard, alpha, beta );
    }

    // Otherwise, generate successors and search them in turn
    // If ComputeLegalMoves returns false, then the current position is illegal
    // because one or more moves could capture a king!
    // In order to slant the computer's strategy in favor of quick mates, we
    // give a bonus to king captures which occur at shallow depths, i.e., the
    // more plies left, the better.  On the other hand, if you are losing, it
    // really doesn't matter how fast...
    jcMoveListGenerator movegen = new jcMoveListGenerator();
    if ( !movegen.ComputeLegalMoves( theBoard ) )
    {
      return ALPHABETA_ILLEGAL;
    }

    // Sort the moves according to History heuristic values
    HistoryTable.SortMoveList( movegen, theBoard.GetCurrentPlayer() );


    // OK, now, get ready to search
    jcBoard newBoard = new jcBoard();
    int bestSoFar;

    // Case #1: We are searching a Max Node
    if ( nodeType == jcAISearchAgent.MAXNODE )
    {
      bestSoFar = ALPHABETA_MINVAL;
      int currentAlpha = alpha;

      // Loop on the successors
      while( ( mov = movegen.Next() ) != null )
      {
        // Compute a board position resulting from the current successor
        newBoard.Clone( theBoard );
        newBoard.ApplyMove( mov );

        // And search it in turn
        int movScore = AlphaBeta( !nodeType, newBoard, depth - 1, currentAlpha,
                                  beta );
        // Ignore illegal moves in the alphabeta evaluation
        if ( movScore == ALPHABETA_ILLEGAL )
          continue;

        currentAlpha = Math.max( currentAlpha, movScore );

        // Is the current successor better than the previous best?
        if ( movScore > bestSoFar )
        {
          bestSoFar = movScore;
          // Can we cutoff now?
          if ( bestSoFar >= beta )
          {
            // Store this best move in the TransTable
            TransTable.StoreBoard( theBoard, bestSoFar, jcMove.EVALTYPE_UPPERBOUND, depth, MoveCounter );

            // Add this move's efficiency in the HistoryTable
            HistoryTable.AddCount( theBoard.GetCurrentPlayer(), mov );
            NumRegularCutoffs++;
            return bestSoFar;
          }
        }
      }

      // Test for checkmate or stalemate
      // Both cases occur if and only if there is no legal move for MAX, i.e.,
      // if "bestSoFar" is ALPHABETA_MINVAL.  There are two cases: we
      // have checkmate (in which case the score is accurate) or stalemate (in
      // which case the position should be re-scored as a draw with value 0.
      if ( bestSoFar <= ALPHABETA_MINVAL )
      {
        // Can MIN capture MAX's king?  First, ask the machine to generate
        // moves for MIN
        newBoard.Clone( theBoard );
        if( newBoard.GetCurrentPlayer() == FromWhosePerspective )
          newBoard.SwitchSides();

        // And if one of MIN's moves is a king capture, indicating that the
        // position is illegal, we have checkmate and must return MINVAL.  We
        // add the depth simply to "favor" delaying tactics: a mate in 5 will
        // score higher than a mate in 3, because the likelihood that the
        // opponent will miss it is higher; might as well make life difficult!
        if ( !movegen.ComputeLegalMoves( newBoard ) )
          return bestSoFar + depth;
        else
          return 0;
      }
    }