/*  PlyGenerator - A class to generate chess moves from a game position.  Copyright (C) 2003 The Java-Chess team <info@java-chess.de>  This program is free software; you can redistribute it and/or  modify it under the terms of the GNU General Public License  as published by the Free Software Foundation; either version 2  of the License, or (at your option) any later version.  This program is distributed in the hope that it will be useful,  but WITHOUT ANY WARRANTY; without even the implied warranty of  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the  GNU General Public License for more details.  You should have received a copy of the GNU General Public License  along with this program; if not, write to the Free Software  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.*/ package de.java_chess.javaChess.engine;import de.java_chess.javaChess.*;import de.java_chess.javaChess.bitboard.*;import de.java_chess.javaChess.engine.hashtable.*;import de.java_chess.javaChess.game.*;import de.java_chess.javaChess.piece.*;import de.java_chess.javaChess.ply.*;import de.java_chess.javaChess.position.*;/** * This class generates all possible plies for a  * given game position. */public class PlyGenerator {    // Static variables    // The scores for presorted plies.    private short HASHTABLE_PLY         = 101;    private short QUEEN_TRANSFORMATION  = 100;    private short ROOK_TRANSFORMATION   = 98;    private short BISHOP_TRANSFORMATION = 96;    private short KNIGHT_TRANSFORMATION = 94;    private short MATERIAL_WIN          = 50;    private short REGULAR_PLY           = 20;    // The moves of a knight, of there are no limitations due to position on the board's edge, opponent's pieces  etc.    private static int [] [] _knightPlyOffset = { { -2, -1}, { -2, 1}, { -1, -2}, { -1, 2}, { 1, -2}, { 1, 2}, { 2, -1}, { 2, 1}};    // The moves of a king. Also with no limitations due to board size etc.    private static int [] [] _kingPlyOffset = { { -1, 0}, { -1, 1}, { 0, 1}, { 1, 1}, { 1, 0}, { 1, -1}, { 0, -1}, { -1, -1}};        // Instance variables    /**     * The current game.     */    Game _game;    /**     * A hashtable with already computed plies.     */    PlyHashtable _hashtable;    /**     * The current board.     */    BitBoard _board;    /**     * A analyzer to check for chess (needed for castling)     */    BitBoardAnalyzer _analyzer;    /**     * An array for the current plies to avoid the overhead of dynamic data structures.     */    AnalyzedPly [] _currentPlies = new AnalyzedPlyImpl[150];    /**     * A counter for the currently computed plies.     */    private int _plyCounter = 0;    /**     * Caches for some important bitmasks.     */    long _emptySquares;  // The empty squares.    long _attackablePieces;  // All the pieces of the opponent minus the king.    /**     * The possible knight plies for each square.     */    private long [] _knightMask = new long[64];    /**     * The possible king plies for each square.     */    private long [] _kingMask = new long[64];    /**     * A flag to indicate, if we compute the moves for the player with the white pieces.     */    private boolean _white;    // Constructors    /**     * Create a new instance of a ply generator.     *     * @param game The current game.     * @param hashtable A hashtable to store the best plies so far.     */    public PlyGenerator( Game game, PlyHashtable hashtable) {	setGame( game);	setHashtable( hashtable);	precomputeKnightPlies();	precomputeKingPlies();    }    /**     * Create a new instance of a ply generator      * from a given board.     *     * @param game The current game.     * @param board The board to operate on.     * @param hashtable A hashtable to store the best plies so far.     */    public PlyGenerator( Game game, BitBoard board, PlyHashtable hashtable) {	this( game, hashtable);	setBoard( board);    }    // Methods    /**     * Get the current game.     *     * @return The current game.     */    public final Game getGame() {	return _game;    }    /**     * Set the current game.     *     * @param The current game.     */    public final void setGame( Game game) {	_game = game;    }    /**     * Get the current hashtable for this ply generator.     *     * @return The current hashtable for this ply generator.     */    public final PlyHashtable getHashtable() {	return _hashtable;    }    /**     * Set a new hashtable for this ply generator.     *     * @param hashtable The new hashtable for this ply generator.     */    public final void setHashtable( PlyHashtable hashtable) {	_hashtable = hashtable;    }    /**     * Get the plies for a given board and color.     * Passing the last ply is suboptimal, since it's slower than     * accessing the game history.     *     * @param lastPly The ply, that lead to the given board.     * @param board The board with the game position.     * @param white true, if white has the next move.     */    public final Ply [] getPliesForColor( BitBoard board, boolean white) {	setBoard( board);	return getPliesForColor( white);    }    /**     * Get the plies for a given game position and color.     *     * @param white true, if white has the next move.     */    public final Ply [] getPliesForColor( boolean white) {	resetPlies();	_white = white;  // Store the color of the current player.	// Compute some bitmasks, so we don't have to compute them again for each piece type.	_emptySquares = getBoard().getEmptySquares(); // Get the positions of the empty squares.	_attackablePieces = getBoard().getAllPiecesForColor( ! _white) & ~getBoard().getPositionOfPieces( Piece.KING << 1 | ( _white ? 0 : 1));	// Add the possible plies for all piece types.	// I tried to sort this list according to the probality for a check, so	// the analyzer has a better chance to find it early.	addPliesForKnights();	addPliesForBishops();	addPliesForRooks();	addPliesForQueens();	addPliesForPawns();	addPliesForKing();	// Check, if there's a good ply for this board in the hash table.	Ply hashtablePly = getHashtable().getPly( getBoard(), _white);	if( hashtablePly != null) {  // If so, increase the score of this ply.	    for( int index = 0; index < _plyCounter; index++) {		if( _currentPlies[index].getPly().equals( hashtablePly)) {		    _currentPlies[index].setScore( HASHTABLE_PLY);		    break;		}	    }	}	// Presort the plies	presortPlies();	// Convert the plies to a array of the correct size	Ply [] plies = new Ply[ _plyCounter];	int destIndex = 0;	for( int sourceIndex = (_plyCounter - 1); sourceIndex >= 0; ) {	    plies[ destIndex++] = _currentPlies[ sourceIndex--].getPly();	}	return plies;    }    /**     * Add all the plies for pawns of the current color.     */    private final void addPliesForPawns() {	if( _white) {	    // Get the positions of all pawns	    long pawnPos = getBoard().getPositionOfPieces( Piece.PAWN << 1 | 1);	    // Add all the diagonal attacks	    addRelativePliesUpward( ( ( pawnPos & BitBoard._NOT_LINE_H) << 9) & _attackablePieces, 17, 63, -9);	    addRelativePliesUpward( ( ( pawnPos & BitBoard._NOT_LINE_A) << 7) & _attackablePieces, 16, 62, -7);	    // Check for a en-passent attack	    if( getLastPly() != null) {		Position destination = getLastPly().getDestination();		Piece piece = getBoard().getPiece( destination);		// The check for the color is sorta redundant, but during analysis the		// order of moves might be incorrect.		if( piece != null && piece.getType() == Piece.PAWN && piece.getColor() == Piece.BLACK) {		    int sourceIndex = getLastPly().getSource().getSquareIndex();		    int destinationIndex = getLastPly().getDestination().getSquareIndex();		    // If the pawn moved 2 squares		    if( ( sourceIndex - destinationIndex) == 16) {			int attackableIndex = sourceIndex - 8;			// Compute the bitmask for the pawn.			long attackablePawnBitmask = ( 1L << attackableIndex);			// Add the en passant attacks.			if( ( ( ( pawnPos & BitBoard._NOT_LINE_H) << 9) & attackablePawnBitmask) != 0L) {			    addPly( new EnPassantPlyImpl( new PositionImpl( attackableIndex - 9)			                 	          , new PositionImpl( attackableIndex)				                          , new PositionImpl( destinationIndex))				    , MATERIAL_WIN);			}			// Add the en passant attacks.			if( ( ( ( pawnPos & BitBoard._NOT_LINE_H) << 7) & attackablePawnBitmask) != 0L) {			    addPly( new EnPassantPlyImpl( new PositionImpl( attackableIndex - 7)			                 	          , new PositionImpl( attackableIndex)				                          , new PositionImpl( destinationIndex))				    , MATERIAL_WIN);			}		    }		}	    }	    // Add all the 2 square plies. Since the square in front of the pawn has to be free, I have to	    // add the bit and with the shifted empty squares.	    addRelativePliesUpward( ( (pawnPos & BitBoard._ROW_2 & ( _emptySquares >>> 8) ) << 16) & _emptySquares, 24, 31, -16);	    // Add all the 1 square plies.	    long movedPawns = (pawnPos << 8) & _emptySquares;	    addRelativePliesUpward( movedPawns & BitBoard._NOT_ROW_8, 16, 55, -8);	    	    // Now take care of the last row.	    movedPawns &= BitBoard._ROW_8;	    while( movedPawns != 0L) {		int destinationSquare = BitUtils.getHighestBit( movedPawns);		int sourceSquare = destinationSquare - 8;		// Add all transformation types as plies.		boolean capture = ( ( ( 1L << destinationSquare) & _attackablePieces) != 0L);		addTransformationPly( sourceSquare, destinationSquare, Piece.QUEEN, capture, QUEEN_TRANSFORMATION);		addTransformationPly( sourceSquare, destinationSquare, Piece.KNIGHT, capture, KNIGHT_TRANSFORMATION);		addTransformationPly( sourceSquare, destinationSquare, Piece.ROOK, capture, ROOK_TRANSFORMATION);		addTransformationPly( sourceSquare, destinationSquare, Piece.BISHOP, capture, BISHOP_TRANSFORMATION);		movedPawns &= ~( 1L << destinationSquare);	    }	} else {	    // Get the positions of all pawns	    long pawnPos = getBoard().getPositionOfPieces( Piece.PAWN << 1);	    // Add all the diagonal attacks	    addRelativePliesDownward( ( ( pawnPos & BitBoard._NOT_LINE_A) >>> 9) & _attackablePieces, 46, 0, 9);	    addRelativePliesDownward( ( ( pawnPos & BitBoard._NOT_LINE_H) >>> 7) & _attackablePieces, 47, 0, 7);	    // Check for a en-passent attack	    if( getLastPly() != null) {		Position destination = getLastPly().getDestination();		Piece piece = getBoard().getPiece( destination);		// The check for the color is sorta redundant, but during analysis the		// order of moves might be incorrect.		if( piece != null && piece.getType() == Piece.PAWN && piece.getColor() == Piece.BLACK) {		    int sourceIndex = getLastPly().getSource().getSquareIndex();		    int destinationIndex = getLastPly().getDestination().getSquareIndex();		    // If the pawn moved 2 squares		    if( ( destinationIndex - sourceIndex) == 16) {			int attackableIndex = sourceIndex + 8;			// Compute the bitmask for the pawn.			long attackablePawnBitmask = ( 1L << attackableIndex);			// Add the en passant attacks.			if( ( ( ( pawnPos & BitBoard._NOT_LINE_H) >>> 9) & attackablePawnBitmask) != 0L) {			    addPly( new EnPassantPlyImpl( new PositionImpl( attackableIndex + 9)			                 	          , new PositionImpl( attackableIndex)				                          , new PositionImpl( destinationIndex))				    , MATERIAL_WIN);