2

アルファ ベータ カットのミニマックスを使用して、オセロをプレイする単純なエンジンを作成しています。うまくプレイしていますが、奇妙なインデックス範囲外の例外が発生することがあります（常にエンドゲームの近くで）。

これが私のアルゴリズムです

private float minimax(OthelloBoard board, OthelloMove best, float alpha, float beta, int depth)
{
    calls++;

    float bestResult = -Float.MAX_VALUE;
    OthelloMove garbage = new OthelloMove();

    int state = board.getState();
    int currentPlayer = board.getCurrentPlayer();

    if (state == OthelloBoard.STATE_DRAW)
        return 0.0f;
    if ((state == OthelloBoard.STATE_BLACK_WINS) && (currentPlayer == OthelloBoard.BLACK))
        return Float.MAX_VALUE;
    if ((state == OthelloBoard.STATE_WHITE_WINS) && (currentPlayer == OthelloBoard.WHITE))
        return Float.MAX_VALUE;
    if ((state == OthelloBoard.STATE_BLACK_WINS) && (currentPlayer == OthelloBoard.WHITE))
        return -Float.MAX_VALUE;
    if ((state == OthelloBoard.STATE_WHITE_WINS) && (currentPlayer == OthelloBoard.BLACK))
        return -Float.MAX_VALUE;

    if (depth == maxDepth)
        return OthelloHeuristics.eval(currentPlayer, board);

    ArrayList<OthelloMove> moves = board.getAllMoves(currentPlayer);

    for (OthelloMove mv : moves)
    {            
        board.makeMove(mv);
        alpha = - minimax(board, garbage, -beta, -alpha, depth + 1);
        board.undoMove(mv);

        if (beta <= alpha)
            return alpha;
        if (alpha > bestResult)
        {                
            best.setFlipSquares(mv.getFlipSquares());
            best.setIdx(mv.getIdx());        
            best.setPlayer(mv.getPlayer());
            bestResult = alpha;
        }
    }     
     return bestResult;
}

makeMove と undoMove 内で、ゲームの状態 (黒の勝利、白の勝利、引き分け) を更新します。また、これらのメソッド内でプレーヤーを切り替えます。プレーヤーが手札を持っていない場合、ボードを変更せずにダミーの動きを行い、プレーヤーを切り替えます。

コードはもっとたくさんありますが、問題はアルゴリズムがゲーム オーバーの位置に達したときに発生すると思います。この問題は、エンジンがランダムな動きをするように設定した場合には発生しないため、問題はアルファ ベータ アルゴリズムにあるはずです。

ここに getAllMoves があり、この呼び出し getFlips:

   public ArrayList<OthelloMove> getAllMoves(int player)
   {
    ArrayList<OthelloMove> moves = new ArrayList<OthelloMove>();

    for (int i = 10; i < 90; i++) 
    {
        int col = i % 10;

        if (col != 0 && col != 9)            
        {
            if (cells[i] == EMPTY)
            {
                ArrayList<Integer> flips = getFlips(i, player);                    
                if (flips.size() > 0)
                {
                    OthelloMove mv = new OthelloMove();
                    mv.setFlipSquares(flips);
                    mv.setIdx(i);                        
                    mv.setPlayer(player);
                    moves.add(mv);
                }
            }
        }

    }                                     

    return moves;
}

これが getFlips です。

    public ArrayList<Integer> getFlips(int idx, int player)
    {        
    int opponent = getOpponent(player);
    ArrayList<Integer> flips = new ArrayList<Integer>();

    if (cells[idx] != EMPTY)
        return flips;

    for (Integer dir : DIRECTIONS)
    {
        int distance = 1;
        int tempIdx = idx;

        while (cells[tempIdx += dir] == opponent)
            distance++;

        if ((cells[tempIdx] == player) && (distance > 1)) 
        {

            while (distance-- > 1)
            {                    
                tempIdx -= dir;
                flips.add(tempIdx);
            }                            
        }            
    }
    return flips;
}

updateState は次のとおりです。

    public void updateState()
    {                   
    int opponent = getOpponent(currentPlayer);
    int playerMoves = getAllMoves(currentPlayer).size();
    int opponentMoves = getAllMoves(opponent).size();

    if ( ((playerMoves == 0) && (opponentMoves == 0)) ||  (emptyCells == 0))
    {                        
        int blackDiscs = countDiscs(BLACK);
        int whiteDiscs = countDiscs(WHITE);

        if (blackDiscs > whiteDiscs)
            state = STATE_BLACK_WINS;
        else if (blackDiscs < whiteDiscs)
            state = STATE_WHITE_WINS;
        else 
            state = STATE_DRAW;

    }                       

}

ありがとう！

4

2 に答える 2

2

私は特にゲームに精通していませんが、それはラインのファクトハットと関係があると思います：

while (cells[tempIdx += dir] == opponent)

また、範囲外ではないことを確認する必要があります。そうしないと、ボードの端にまだ対戦相​​手がいる場合は、増加し続けます。dir

この行を次のように変更してみてください。

while (tempIdx + dir >= 0 && tempIdx + dir < cells.length && cells[tempIdx += dir] == opponent)

経験則として、通常、配列アクセス、特にループでは、長さを明示的にチェックして範囲外になるのを防ぐことをお勧めします。

于 2012-02-27T08:10:56.227 に答える
0

問題が見つかりました、とにかくありがとう。

このバグは、プレイヤーが移動できず、ターンをパスしなければならない状況でした。注意が必要なのは、「ゴースト ムーブ」(ボードを変更しないムーブ) をプレイし、プレーヤーのターンを切り替えて、ミニマックスがこの状況に気付かないようにすることです。

私はこれをやっていましたが、間違った場所で！コードは次のようになります。

   public void makeMove (OthelloMove move)
   {                    
    int player = move.getPlayer();        
    ArrayList<Integer> flips = move.getFlipSquares();

    if (flips != null)
    {                                   
        int idx = move.getIdx();                    
        cells[idx] = player;
        for (Integer flip : flips)
            cells[flip] = player;        

        emptyCells--;    
        this.updatePhase();           
    }
    this.toogleCurrentPlayer();                    
}

public void undoMove (OthelloMove move)
{                    
    int player = move.getPlayer();        
    ArrayList<Integer> flips = move.getFlipSquares();
    int opponent = getOpponent(player);

    if (flips != null)
    {
        int idx = move.getIdx();

        cells[idx] = EMPTY;
        for (Integer flip : flips)
            cells[flip] = opponent;

        emptyCells++;                                         
        this.updatePhase();
    }
    this.toogleCurrentPlayer();         
 }
于 2012-02-27T20:27:20.847 に答える