chessengineimpl.java

一个用java编写的国际象棋小游戏

	    AnalyzedPly searchDepthResult = startMinimaxAlphaBeta( isWhite());
	    if( searchDepthResult != null) {
		_bestPly = searchDepthResult;
		sOutput = "Best ply for search depth " + _searchDepth + " is " + _bestPly.getPly().toString() + " with score " + _bestPly.getScore();
		if ( this.enginePanel != null ) {
		    this.enginePanel.modifyText( sOutput );
		}
	    }
	    // If search depth 1 was completed and no valid ply was found,
	    // it seems that the computer is checkmate and the search can be aborted.
	} while( ! _stopSearch && ( _bestPly != null));
    }

    /**
     * Start a complete Minimax-Alpha-Beta search. This is the search level 1, where we have to store the
     * analyzed ply, so it gets a special method.
     *
     * @param white Flag to indicate, if white is about to move.
     */
    private final AnalyzedPly startMinimaxAlphaBeta( boolean white) {
	short curAlpha = AnalyzedPly.MIN_SCORE;
	short curBeta = AnalyzedPly.MAX_SCORE;
	int bestPlyIndex = -1;

	Ply [] plies = _plyGenerator.getPliesForColor( (BitBoard)getBoard(), white);
	if( white) {
	    for( int i = 0; i < plies.length; i++) {
		if( _stopSearch && ( _searchDepth > 1)) {  // If the search time is over and at least depth 1 was completed
		    return null;                           // abort the search at search depth 1.
		}                                          // (Deeper levels are still searched).
		getGame().doPly( plies[i]);
		short val = minimaxAlphaBeta( plies[i], getBoard().getBoardAfterPly( plies[i]), false, 1, curAlpha, curBeta);
		if( val > curAlpha) {
		    curAlpha = val;
		    bestPlyIndex = i;
		}
		if( curAlpha >= curBeta) {
		    getGame().undoLastPly();  // Take the last ply back, before the loop is aborted.
		    break;
		}
		getGame().undoLastPly();
	    }

	    // Since this is the best ply so far, we store it in the hashtable. This makes sense,
	    // since the minimax algorithm is started several times, before a move is selected.
	    // So this move is not necessarily applied immediately!
	    getHashtable().pushEntry( new PlyHashtableEntryImpl( getBoard(), plies[bestPlyIndex]));

	    return ( bestPlyIndex != -1) ? new AnalyzedPlyImpl( plies[bestPlyIndex], curAlpha) : null;
	} else {
	    for( int i = 0; i < plies.length; i++) {
		if( _stopSearch && ( _searchDepth > 1)) {  // If the search time is over and at least depth 1 was completed
		    return null;                           // abort the search at search depth 1.
		}                                          // (Deeper levels are still searched).
		getGame().doPly( plies[i]);
		short val = minimaxAlphaBeta( plies[i], getBoard().getBoardAfterPly( plies[i]), true, 1, curAlpha, curBeta);
		if( val < curBeta) {
		    curBeta = val;
		    bestPlyIndex = i;
		}
		if( curBeta <= curAlpha) {
		    getGame().undoLastPly();  // Take the last ply back, before the loop is aborted.
		    break;
		}
		getGame().undoLastPly();
	    }

	    // Since this is the best ply so far, we store it in the hashtable. This makes sense,
	    // since the minimax algorithm is started several times, before a move is selected.
	    // So this move is not necessarily applied immediately!
	    getHashtable().pushEntry( new PlyHashtableEntryImpl( getBoard(), plies[bestPlyIndex]));

	    return ( bestPlyIndex != -1) ? new AnalyzedPlyImpl( plies[bestPlyIndex], curBeta) : null;
	}
    }

    /**
     * Perform a alpha-beta minimax search on the board.
     *
     * @param lastPly The ply, that created this board.
     * @param board The board to analyze.
     * @param white true, if white has the next move.
     * @param byte searchLevel The level to search for.
     * @param alpha The current maximum.
     * @param beta The current minimum.
     */
    private final short minimaxAlphaBeta( Ply lastPly, Board board, boolean white, int searchLevel, short alpha, short beta) {
	if( searchLevel >= _searchDepth) {
	    _analyzedBoards++;
	    return analyzeBoard( board);
	} else {
	    short curAlpha = alpha;
	    short curBeta = beta;
	    int bestPlyIndex = -1;

	    Ply [] plies = _plyGenerator.getPliesForColor( (BitBoard)board, white);
	    if( white) {
		for( int i = 0; i < plies.length; i++) {
		    getGame().doPly( plies[i]);
		    short val = minimaxAlphaBeta( plies[i], board.getBoardAfterPly( plies[i]), false, searchLevel + 1, curAlpha, curBeta);
		    if( val > curAlpha) {
			curAlpha = val;
			bestPlyIndex = i;  // Store the index of this ply, so we can access it later.
		    }
		    if( curAlpha >= curBeta) {
			getGame().undoLastPly();  // Take the last ply back, before the loop is aborted.
			break;
		    }
		    getGame().undoLastPly();
		}

		if( bestPlyIndex != -1) {
		    // Since this is the best ply for this search level, we store it in the hashtable
		    getHashtable().pushEntry( new PlyHashtableEntryImpl( board, plies[ bestPlyIndex]));
		}

		return curAlpha;
	    } else {
		for( int i = 0; i < plies.length; i++) {
		    getGame().doPly( plies[i]);
		    short val = minimaxAlphaBeta( plies[i], board.getBoardAfterPly( plies[i]), true, searchLevel + 1, curAlpha, curBeta);
		    if( val < curBeta) {
			curBeta = val;
			bestPlyIndex = i;  // Store the index of this ply, so we can access it later.
		    }
		    if( curBeta <= curAlpha) {
			getGame().undoLastPly();  // Take the last ply back, before the loop is aborted.
			break;
		    }
		    getGame().undoLastPly();
		}

		if( bestPlyIndex != -1) {
		    // Since this is the best ply for this search level, we store it in the hashtable
		    getHashtable().pushEntry( new PlyHashtableEntryImpl( board, plies[ bestPlyIndex]));
		}

		return curBeta;
	    }
	}
    }

    /**
     * Compute a score for a game position.
     *
     * @return A score for the current game position.
     */
    public final short analyzeBoard( Board board) {
	return _analyzer.analyze( (BitBoard)board, isWhite());
    }

    /**
     * Check if a ply made by the user is valid.
     *
     * @param ply The user ply.
     *
     * @return true, if the ply is valid. false otherwise.
     */
    public final boolean validateUserPly( Ply ply) {

	// The following code is really inefficient, since
	// the ply computation should be done during the permanent brain
	// computations.

	// Compute all the plies a user can perform (also really not
	// very effient).
	Ply [] plies = _plyGenerator.getPliesForColor( (BitBoard)getBoard(), ! isWhite());

	for( int p = 0; p < plies.length; p++) {  // For each ply
	    if( plies[p].equals( ply)) {          // if the user ply equals this computed
		return true;                      // ply, it seems to be valid.
	    }
	}

	// The computer could not compute the ply, the user has made,
	// so we assume, that it is not valid.
	System.out.println( "Invalid move " + ply.toString());
	System.out.println( "Piecetype on source square " + ( getBoard().getPiece( ply.getSource()) == null ? "null" : "" + getBoard().getPiece( ply.getSource()).getType()));
	System.out.println( "Valid moves are:");
	for( int p = 0; p < plies.length; p++) {  // For each ply
	    System.out.print( plies[p].toString() + " ");
	}
	System.out.println();
	return false;
    }

    /**
     * Return a menu from the chess engine, where the user
     * can change the settings.
     *
     * @return A menu for the engine settings.
     */
    public final JMenu getMenu() {

	// Create a new menu.
	JMenu engineMenu = new JMenu( "Engine");

	// Add a menu for the maximum search time
	JMenu searchTimeMenu = new JMenu( "Search time");

	// Add various options for the search time
	// (maybe a user defined search time should be added, too).
	_searchTimeMenuItem = new JMenuItem[ _searchTime.length];
	for( int st = 0; st < _searchTime.length; st++) {
	    _searchTimeMenuItem[st] = new JMenuItem( "" + _searchTime[st] + " seconds");
	    _searchTimeMenuItem[st].addActionListener( this);

	    // Add the current search time menu item to it's menu.
	    searchTimeMenu.add( _searchTimeMenuItem[st]);
	}

	// Add the search time menu to the main engine menu.
	engineMenu.add( searchTimeMenu);

	// Add a menu for the hashtable size.
	JMenu hashtableSizeMenu = new JMenu( "Hashtable size");

	// Add various options for the hashtable size.
	_hashtableSizeMenuItem = new JMenuItem[ _hashtableSize.length];
	for( int hts = 0; hts < _hashtableSize.length; hts++) {
	    _hashtableSizeMenuItem[hts] = new JMenuItem( "" + _hashtableSize[hts] + " entries");
	    _hashtableSizeMenuItem[hts].addActionListener( this);

	    // Add the current search time menu item to it's menu.
	    hashtableSizeMenu.add( _hashtableSizeMenuItem[hts]);
	}

	// Add the search time menu to the main engine menu.
	engineMenu.add( hashtableSizeMenu);

	// Return the engine menu.
	return engineMenu;
    }

    /**
     * Perform a action (could be a menu related action).
     *
     * @param actionEvent The event.
     */
    public final void actionPerformed(ActionEvent actionEvent) {

	// Check if the user has requested a new search time
	for( int st = 0; st < _searchTime.length; st++) {
	    if( actionEvent.getSource().equals( _searchTimeMenuItem[ st])) {
		setMaximumSearchTime( _searchTime[ st] * 1000);
		break;
	    }
	}

	// Check, if the user has requested a different hashtable size.
	for( int hts = 0; hts < _hashtableSize.length; hts++) {
	    if( actionEvent.getSource().equals( _hashtableSizeMenuItem[ hts])) {
		getHashtable().setMaximumSize( _hashtableSize[ hts]);
		break;
	    }
	}
    }

    /**
     * Sets the EnginePanel to be able to output in the panel and not only with
     * System.out.println(...)
     *
     * @param panel The EnginePanel to set
     */
    public void setEnginePanel(EnginePanel panel) {
	this.enginePanel = panel;
    }

    /**
     * Get the current game state.
     *
     * @param white True, if the state of the white player is requested.
     *
     * @return The current game state.
     */
    public final byte getCurrentGameState( boolean white) {
	
	// Test if the given player is in check.
	boolean inCheck = _analyzer.isInCheck( (BitBoard)getBoard(), white);

	// Test if the player has valid plies available.
	// The following computation of the available plies is not really efficient,
	// since they are done anyway (either to compute the next computer ply or to
	// check if a user ply is valid). So maybe the plygenerator or the engine should
	// cache the computed plies.
	boolean validPliesAvailable = ( _plyGenerator.getPliesForColor( (BitBoard)getBoard(), white).length > 0);

	if( inCheck) {
	    return validPliesAvailable ? GameState.CHECK : GameState.CHECKMATE;
	} else {
	    return validPliesAvailable ? GameState.ONGOING : GameState.DRAW;
	}
    }
}