plygenerator.java

elcome to the Java-Chess project! As you might know, we aim at creating a fully functional chess

/*
  PlyGenerator - A class to generate chess moves from a game position.

  Copyright (C) 2003 The Java-Chess team <[e-mail]>

  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];
	for( int index = 0; index < _plyCounter; index++) {
	    plies[index] = _currentPlies[index].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) & 0x00FFFFFFFFFFFFFFL) ) << 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.
		addTransformationPly( sourceSquare, destinationSquare, Piece.QUEEN, QUEEN_TRANSFORMATION);
		addTransformationPly( sourceSquare, destinationSquare, Piece.KNIGHT, KNIGHT_TRANSFORMATION);
		addTransformationPly( sourceSquare, destinationSquare, Piece.ROOK, ROOK_TRANSFORMATION);
		addTransformationPly( sourceSquare, destinationSquare, Piece.BISHOP, 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) & 0x007FFFFFFFFFFFFFL & _attackablePieces, 46, 0, 9);
	    addRelativePliesDownward( ( ( pawnPos & BitBoard._NOT_LINE_H) >> 7) & 0x01FFFFFFFFFFFFFFL & _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) & 0x007FFFFFFFFFFFFFL & attackablePawnBitmask) != 0L) {