negaalphabetasearcher.java

一个黑白棋的源代码(尚未完成

package org.yangcq.logic.search;

import org.yangcq.logic.chessboard.ChessboardImpl;
import org.yangcq.logic.chessboard.IChessboard;
import org.yangcq.logic.step.Step;

public final class NegaAlphaBetaSearcher extends BasicSearcher
{

    private Step bestStep = null;

    public Step getBestStep()
    {
        IChessboard context = ChessboardImpl.getChessboard();
        Step[][] steps = context.getBoardCopy();
        boolean side = context.getCurrentPlayer().isChessmanBlack();
        this.search(steps, side, this.getSearchDepth(), Long.MIN_VALUE, Long.MAX_VALUE, false);
        return this.bestStep;
    }

    private long search(Step[][] steps, boolean side, int depth, long alpha, long beta, boolean prePass)//alpha,beta剪枝算法

    {
        long val;
        boolean opSide = !side;
        if (depth <= 0)
        {
            return this.getValuer().getValue(steps, side); //估值
        }
        Step[] validStep = this.getStepGenerater().getValidSteps(steps, side); //走法生成
        if (validStep != null)
        {
            for (int i = 0; i < validStep.length; i++)
            {

                long count = this.getStepGenerater().chess(steps, validStep[i].getX(), validStep[i].getY(), validStep[i].getColor().booleanValue()); //走一步
                val = -search(steps, opSide, depth - 1, -beta, -alpha, false); //让对手估值
                this.getStepGenerater().unChess(steps, validStep[i].getX(), validStep[i].getY(), count); //撤销一步
                if (val >= alpha)
                {
                    alpha = val;
                    if (depth == this.getSearchDepth())
                    {
                        this.bestStep = validStep[i].clone();
                    }
                    if (alpha >= beta)
                    {
                        return beta; //剪枝
                    }
                }
            }
        } else
        {
            if (prePass)
            {
                val = 0;
                for (int x = 0; x < steps.length; x++)
                {
                    for (int y = 0; y < steps.length; y++)
                    {
                        if (steps[x][y] != null && steps[x][y].getColor().booleanValue() == side)
                        {
                            val++;
                        } else if (steps[x][y] != null && steps[x][y].getColor().booleanValue() == opSide)
                        {
                            val--;
                        }
                    }
                }
                if (val >= alpha)//似乎不太可能！

                {
                    alpha = val;
                }
            } else
            {
                val = -search(steps, opSide, depth, -beta, -alpha, true);
                if (depth == this.getSearchDepth())
                {
                    this.bestStep = null; //以前可能已经对最好着法赋值，但是那是对手赋的值，所以要擦除
                }
                if (val >= alpha)//似乎也不太可能！

                {
                    alpha = val;
                }
            }
        }

        return alpha;
    }
}