jcmovelistgenerator.java

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

/******************************************************************************
 * jcMoveListGenerator.java - Find all pseudo-legal moves given a board state
 * by F.D. Laram閑
 *
 * Purpose: Identify a list of possible moves
 *
 * History:
 * 27.07.00 Creation
 *****************************************************************************/

package javachess;
import javachess.jcBoard;
import javachess.jcMove;
import java.util.*;

public class jcMoveListGenerator
{

  /**************************************************************************
   * INSTANCE VARIABLES
   *************************************************************************/

  // The list of moves, implemented as a java collection class, namely the
  // ArrayList (dynamic array)
  ArrayList Moves;
  Iterator MovesIt;

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

  // Construction
  public jcMoveListGenerator()
  {
    Moves = new ArrayList( 10 );
    MovesIt = null;
    ResetIterator();
  }


  // public void ResetIterator
  // Prepare an iterator for scanning through the list of moves
  public void ResetIterator()
  {
    // Mark the old iterator, if any, for garbage collection
    if ( MovesIt != null )
      MovesIt = null;

    // Make a new iterator ready for scanning
    MovesIt = Moves.iterator();
  }

  // Accessors
  public ArrayList GetMoveList() { return Moves; }
  public int Size() { return Moves.size(); }

  // public boolean Find( jcMove mov )
  // Look for a specific move in the list; if it is there, return true
  // This is used by the jcPlayerHuman object, to verify whether a move entered
  // by the player is actually valid
  public boolean Find( jcMove mov )
  {
    ResetIterator();
    jcMove testMove;
    while( ( testMove = Next() ) != null )
    {
      if ( mov.Equals( testMove ) )
        return true;
    }
    return false;
  }

  // public jcMove FindMoveForSquares( int source, int dest )
  // look for a move from "source" to "dest" in the list
  public jcMove FindMoveForSquares( int source, int dest )
  {
    ResetIterator();
    jcMove testMove;
    while( ( testMove = Next() ) != null )
    {
      if ( ( testMove.SourceSquare == source ) && ( testMove.DestinationSquare == dest ) )
        return testMove;
    }
    return null;
  }

  // public jcMove Next()
  // Find the next move in the list, if any
  public jcMove Next()
  {
    if ( MovesIt.hasNext() )
      return (jcMove) MovesIt.next();
    else
      return null;
  }

  // public boolean ComputeLegalMoves
  // Look at the board received as a parameter, and build a list of legal
  // moves which can be derived from it.  If there are no legal moves, or if
  // one of the moves is a king capture (which means that the opponent's
  // previous move left the king in check, which is illegal), return false.
  public boolean ComputeLegalMoves( jcBoard theBoard )
  {
    // First, clean up the old list of moves, if any
    Moves.clear();

    // Now, compute the moves, one piece type at a time
    if ( theBoard.GetCurrentPlayer() == jcPlayer.SIDE_WHITE )
    {
      // Clean up the data structures indicating that the last white move
      // was a castling, if any
      if ( theBoard.GetExtraKings( jcPlayer.SIDE_WHITE ) != 0 )
      {
        theBoard.ClearExtraKings( jcPlayer.SIDE_WHITE );
      }
      // Check for white moves, one piece type at a time
      // if any one type can capture the king, stop the work immediately
      // because the board position is illegal
      if ( !ComputeWhiteQueenMoves( theBoard ) ) return false;
      if ( !ComputeWhiteKingMoves( theBoard ) ) return false;
      if ( !ComputeWhiteRookMoves( theBoard, jcBoard.WHITE_ROOK ) ) return false;
      if ( !ComputeWhiteBishopMoves( theBoard, jcBoard.WHITE_BISHOP ) ) return false;
      if ( !ComputeWhiteKnightMoves( theBoard ) ) return false;
      if ( !ComputeWhitePawnMoves( theBoard ) ) return false;
    }
    else  // Compute Black's moves
    {
      if ( theBoard.GetExtraKings( jcPlayer.SIDE_BLACK ) != 0 )
      {
        theBoard.ClearExtraKings( jcPlayer.SIDE_BLACK );
      }
      if ( !ComputeBlackQueenMoves( theBoard ) ) return false;
      if ( !ComputeBlackKingMoves( theBoard ) ) return false;
      if ( !ComputeBlackRookMoves( theBoard, jcBoard.BLACK_ROOK ) ) return false;
      if ( !ComputeBlackBishopMoves( theBoard, jcBoard.BLACK_BISHOP ) ) return false;
      if ( !ComputeBlackKnightMoves( theBoard ) ) return false;
      if ( !ComputeBlackPawnMoves( theBoard ) ) return false;
    }

    // And finally, if there are no pseudo-legal moves at all, we have an
    // obvious error (there are no pieces on the board!); flag the condition
    if ( Moves.size() == 0 )
      return false;
    else
    {
      ResetIterator();
      return true;
    }
  }


  // public boolean ComputeQuiescenceMoves
  // Find only the moves which are relevant to quiescence search; i.e., captures
  public boolean ComputeQuiescenceMoves( jcBoard theBoard )
  {
    ComputeLegalMoves( theBoard );
    for( int i = Moves.size() - 1; i >= 0; i-- )
    {
      jcMove mov = (jcMove) Moves.get( i );
      if ( ( mov.MoveType != jcMove.MOVE_CAPTURE_ORDINARY ) &&
           ( mov.MoveType != jcMove.MOVE_CAPTURE_EN_PASSANT ) )
        Moves.remove( i );
    }
    ResetIterator();
    return( Moves.size() > 0 );
  }

  // public void Print()
  // Dump the move list to standard output, for debugging purposes
  public void Print()
  {
    // Do not use the iterator, to avoid messing up a regular operation!
    for( int it = 0; it < Moves.size(); it++ )
    {
      jcMove mov = (jcMove) Moves.get( it );
      mov.Print();
    }
  }


  /*************************************************************************
   * PRIVATE METHODS
   * For move generation
   *************************************************************************/

   private boolean ComputeWhiteQueenMoves( jcBoard theBoard )
   {
     if ( !ComputeWhiteBishopMoves( theBoard, jcBoard.WHITE_QUEEN ) ) return false;
     if ( !ComputeWhiteRookMoves( theBoard, jcBoard.WHITE_QUEEN ) ) return false;
     return true;
   }

   private boolean ComputeWhiteKingMoves( jcBoard theBoard )
   {
     // Fetch the bitboard containing position of the king
     long pieces = theBoard.GetBitBoard( jcBoard.WHITE_KING );

     // Find it!  There is only one king, so look for it and stop
     int square;
     for( square = 0; square < 64; square++ )
     {
       if ( ( jcBoard.SquareBits[ square ] & pieces ) != 0 )
         break;
     }

     // Find its moves
     for( int i = 0; i < KingMoves[ square ].length; i++ )
     {
       // Get the destination square
       int dest = KingMoves[ square ][ i ];

       // Is it occupied by a friendly piece?  If so, can't move there
       if ( ( theBoard.GetBitBoard( jcBoard.ALL_WHITE_PIECES ) &
             jcBoard.SquareBits[ dest ] ) != 0 )
          continue;

       // Otherwise, the move is legal, so we must prepare to add it
       jcMove mov = new jcMove();
       mov.SourceSquare = square;
       mov.DestinationSquare = dest;
       mov.MovingPiece = jcBoard.WHITE_KING;

       // Is the destination occupied by an enemy?  If so, we have a capture
       if ( ( theBoard.GetBitBoard( jcBoard.ALL_BLACK_PIECES ) &
            jcBoard.SquareBits[ dest ] ) != 0 )
       {
         mov.MoveType = jcMove.MOVE_CAPTURE_ORDINARY;
         mov.CapturedPiece = theBoard.FindBlackPiece( dest );

         // If the piece we find is a king, abort because the board
         // position is illegal!
         if ( mov.CapturedPiece == jcBoard.BLACK_KING )
         {
            return false;
         }
       }

       // otherwise, it is a simple move
       else
       {
         mov.MoveType = jcMove.MOVE_NORMAL;
         mov.CapturedPiece = jcBoard.EMPTY_SQUARE;
       }

       // And we add the move to the list
       Moves.add( mov );
     }

     // Now, let's consider castling...
     // Kingside first
     if ( theBoard.GetCastlingStatus( jcBoard.CASTLE_KINGSIDE + jcPlayer.SIDE_WHITE ) )
     {
       // First, check whether there are empty squares between king and rook
       if ( ( ( theBoard.GetBitBoard( jcBoard.ALL_WHITE_PIECES ) & jcBoard.EMPTYSQUARES_WHITE_KINGSIDE ) == 0 ) &&
            ( ( theBoard.GetBitBoard( jcBoard.ALL_BLACK_PIECES ) & jcBoard.EMPTYSQUARES_WHITE_KINGSIDE ) == 0 ) )
       {
         jcMove mov = new jcMove();
         mov.MovingPiece = jcBoard.WHITE_KING;
         mov.SourceSquare = 60;
         mov.DestinationSquare = 62;
         mov.MoveType = jcMove.MOVE_CASTLING_KINGSIDE;
         mov.CapturedPiece = jcBoard.EMPTY_SQUARE;
         Moves.add( mov );
       }
     }
     if ( theBoard.GetCastlingStatus( jcBoard.CASTLE_QUEENSIDE + jcPlayer.SIDE_WHITE ) )
     {
       if ( ( ( theBoard.GetBitBoard( jcBoard.ALL_WHITE_PIECES ) & jcBoard.EMPTYSQUARES_WHITE_QUEENSIDE ) == 0 ) &&
            ( ( theBoard.GetBitBoard( jcBoard.ALL_BLACK_PIECES ) & jcBoard.EMPTYSQUARES_WHITE_QUEENSIDE ) == 0 ) )
       {
         jcMove mov = new jcMove();
         mov.MovingPiece = jcBoard.WHITE_KING;
         mov.SourceSquare = 60;
         mov.DestinationSquare = 58;
         mov.MoveType = jcMove.MOVE_CASTLING_QUEENSIDE;
         mov.CapturedPiece = jcBoard.EMPTY_SQUARE;
         Moves.add( mov );
       }
     }
     return true;
   }

   // private boolean ComputeWhiteRookMoves
   // Receives an extra "pieceType" parameter, because the queen AND the rook
   // need to use this function
   private boolean ComputeWhiteRookMoves( jcBoard theBoard, int pieceType )
   {
     // Fetch the bitboard containing positions of these pieces
     long pieces = theBoard.GetBitBoard( pieceType );

     // If there are no pieces of this type, no need to work very hard!
     if ( pieces == 0 )
     {
       return true;
     }

     // This is a white piece, so let's start looking at the bottom
     // of the board
     for( int square = 63; square >= 0; square-- )
     {
       if ( ( pieces & jcBoard.SquareBits[ square ] ) != 0 )
       {
         // There is a piece here; find its moves
         for( int ray = 0; ray < RookMoves[ square ].length; ray++ )
         {
           for( int i = 0; i < RookMoves[ square ][ ray ].length; i++ )
           {
             // Get the destination square
             int dest = RookMoves[ square ][ ray ][ i ];

             // Is it occupied by a friendly piece?  If so, can't move there
             // AND we must discontinue the current ray
             if ( ( theBoard.GetBitBoard( jcBoard.ALL_WHITE_PIECES ) &
                  jcBoard.SquareBits[ dest ] ) != 0 )
               break;

             // Otherwise, the move is legal, so we must prepare to add it
             jcMove mov = new jcMove();
             mov.SourceSquare = square;
             mov.DestinationSquare = dest;
             mov.MovingPiece = pieceType;

             // Is the destination occupied by an enemy?  If so, we have a capture
             if ( ( theBoard.GetBitBoard( jcBoard.ALL_BLACK_PIECES ) &
                  jcBoard.SquareBits[ dest ] ) != 0 )
             {
               mov.MoveType = jcMove.MOVE_CAPTURE_ORDINARY;
               mov.CapturedPiece = theBoard.FindBlackPiece( dest );

               // If the piece we find is a king, abort because the board
               // position is illegal!
               if ( mov.CapturedPiece == jcBoard.BLACK_KING )
               {
                 return false;
               }

               Moves.add( mov );
               break;
             }
             // otherwise, it is a simple move
             else
             {
               mov.MoveType = jcMove.MOVE_NORMAL;
               mov.CapturedPiece = jcBoard.EMPTY_SQUARE;
               Moves.add( mov );
             }
           }
         }
         // Turn off the bit in the temporary bitboard; this way, we can
         // detect whether we have found the last of this type of piece
         // and short-circuit the loop
         pieces ^= jcBoard.SquareBits[ square ];
         if ( pieces == 0 )
           return true;
       }
     }

     // We should never get here, but the return statement is added to prevent
     // obnoxious compiler warnings
      return true;
   }