jcaisearchagent.java

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

    else
    // Case #2: Min Node
    {
      bestSoFar = ALPHABETA_MAXVAL;
      int currentBeta = beta;
      while( ( mov = movegen.Next() ) != null )
      {
        newBoard.Clone( theBoard );
        newBoard.ApplyMove( mov );

        int movScore = AlphaBeta( !nodeType, newBoard, depth - 1, alpha,
                                  currentBeta );
        if ( movScore == ALPHABETA_ILLEGAL )
          continue;
        currentBeta = Math.min( currentBeta, movScore );
        if ( movScore < bestSoFar )
        {
          bestSoFar = movScore;
          // Cutoff?
          if ( bestSoFar <= alpha )
          {
            TransTable.StoreBoard( theBoard, bestSoFar, jcMove.EVALTYPE_UPPERBOUND, depth, MoveCounter );
            HistoryTable.AddCount( theBoard.GetCurrentPlayer(), mov );
            NumRegularCutoffs++;
            return bestSoFar;
          }
        }
      }
      // Test for checkmate or stalemate
      if ( bestSoFar >= ALPHABETA_MAXVAL )
      {
        // Can MAX capture MIN's king?
        newBoard.Clone( theBoard );
        if( newBoard.GetCurrentPlayer() != FromWhosePerspective )
          newBoard.SwitchSides();
        if ( !movegen.ComputeLegalMoves( newBoard ) )
          return bestSoFar + depth;
        else
          return 0;
      }
    }

    // If we haven't returned yet, we have found an accurate minimax score
    // for a position which is neither a checkmate nor a stalemate
    TransTable.StoreBoard( theBoard, bestSoFar, jcMove.EVALTYPE_ACCURATE, depth, MoveCounter );
    return bestSoFar;
  }

  // int QuiescenceSearch
  // A slight variant of alphabeta which only considers captures and null moves
  // This is necesary because the evaluation function can only be applied to
  // "quiet" positions where the tactical situation (i.e., material balance) is
  // unlikely to change in the near future.
  // Note that, in this version of the code, the quiescence search is not limited
  // by depth; we continue digging for as long as we can find captures.  Some other
  // programs impose a depth limit for time-management purposes.
  public int QuiescenceSearch( boolean nodeType, jcBoard theBoard, int alpha, int beta )
  {
    jcMove mov = new jcMove();
    NumQuiescenceNodes++;

    // 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 ) )
    {
      if ( nodeType == MAXNODE )
      {
        if ( ( mov.MoveEvaluationType == jcMove.EVALTYPE_ACCURATE ) ||
             ( mov.MoveEvaluationType == jcMove.EVALTYPE_LOWERBOUND ) )
        {
          if ( mov.MoveEvaluation >= beta )
          {
            NumQuiescenceTTHits++;
            return mov.MoveEvaluation;
          }
        }
      }
      else
      {
        if ( ( mov.MoveEvaluationType == jcMove.EVALTYPE_ACCURATE ) ||
             ( mov.MoveEvaluationType == jcMove.EVALTYPE_UPPERBOUND ) )
        {
          if ( mov.MoveEvaluation <= alpha )
          {
            NumQuiescenceTTHits++;
            return mov.MoveEvaluation;
          }
        }
      }
    }

    int bestSoFar = ALPHABETA_MINVAL;

    // Start with evaluation of the null-move, just to see whether it is more
    // effective than any capture, in which case we must stop looking at
    // captures and damaging our position
    // NOTE: If the quick evaluation is enough to cause a cutoff, we don't store
    // the value in the transposition table.  EvaluateQuickie is so fast that we
    // wouldn't gain anything, and storing the value might force us to erase a
    // more valuable entry in the table.
    bestSoFar = Evaluator.EvaluateQuickie( theBoard, FromWhosePerspective );
    if ( ( bestSoFar > ( beta + EVAL_THRESHOLD ) ) || ( bestSoFar < ( alpha - EVAL_THRESHOLD ) ) )
      return bestSoFar;
    else
      bestSoFar = Evaluator.EvaluateComplete( theBoard, FromWhosePerspective );

    // Now, look at captures
    jcMoveListGenerator movegen = new jcMoveListGenerator();
    if ( !movegen.ComputeQuiescenceMoves( theBoard ) )
    {
      return bestSoFar;
    }

    jcBoard newBoard = new jcBoard();

    // Case #1: We are searching a Max Node
    if ( nodeType == jcAISearchAgent.MAXNODE )
    {
      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 = QuiescenceSearch( !nodeType, newBoard, 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 )
          {
            TransTable.StoreBoard( theBoard, bestSoFar, jcMove.EVALTYPE_UPPERBOUND, 0, MoveCounter );
            // Add this move's efficiency in the HistoryTable
            HistoryTable.AddCount( theBoard.GetCurrentPlayer(), mov );
            NumQuiescenceCutoffs++;
            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;
        else
          return 0;
      }
    }
    else
    // Case #2: Min Node
    {
      int currentBeta = beta;
      while( ( mov = movegen.Next() ) != null )
      {
        newBoard.Clone( theBoard );
        newBoard.ApplyMove( mov );

        int movScore = QuiescenceSearch( !nodeType, newBoard, alpha, currentBeta );
        if ( movScore == ALPHABETA_ILLEGAL )
          continue;
        currentBeta = Math.min( currentBeta, movScore );
        if ( movScore < bestSoFar )
        {
          bestSoFar = movScore;
          // Cutoff?
          if ( bestSoFar <= alpha )
          {
            TransTable.StoreBoard( theBoard, bestSoFar, jcMove.EVALTYPE_UPPERBOUND, 0, MoveCounter );
            HistoryTable.AddCount( theBoard.GetCurrentPlayer(), mov );
            NumQuiescenceCutoffs++;
            return bestSoFar;
          }
        }
      }
      // Test for checkmate or stalemate
      if ( bestSoFar >= ALPHABETA_MAXVAL )
      {
        // Can MAX capture MIN's king?
        newBoard.Clone( theBoard );
        if( newBoard.GetCurrentPlayer() != FromWhosePerspective )
          newBoard.SwitchSides();
        if ( !movegen.ComputeLegalMoves( newBoard ) )
          return bestSoFar;
        else
          return 0;
      }
    }

    // If we haven't returned yet, we have found an accurate minimax score
    // for a position which is neither a checkmate nor a stalemate
    TransTable.StoreBoard( theBoard, bestSoFar, jcMove.EVALTYPE_ACCURATE, 0, MoveCounter );
    return bestSoFar;
  }


  // jcAISearchAgent MakeNewAgent
  // Standard "subclass factory" design pattern
  public static jcAISearchAgent MakeNewAgent( int type, jcOpeningBook ref )
  {
    switch( type )
    {
      case AISEARCH_ALPHABETA:
        return( new jcAISearchAgentAlphabeta() );
      case AISEARCH_MTDF:
        return( new jcAISearchAgentMTDF( ref ) );
      default:
        return null;
    }
  }

  // jcMove PickBestMove( jcBoard theBoard )
  // Each agent class needs some way of picking a move!
  public abstract jcMove PickBestMove( jcBoard theBoard );
}