2

アルファ ベータ プルーニングでミニマックスを使用してオセロ エンジンを作成しています。正常に動作していますが、次の問題が見つかりました。

アルゴリズムが位置が失われたことを検出すると、予想どおり -INFINITY を返しますが、この場合、「最良の」動きを追跡できません...位置はすでに失われていますが、とにかく有効な動きを返す必要があります（優れたチェスエンジンのように、より長く生き残る動きが望ましいです）。

コードは次のとおりです。

private float minimax(OthelloBoard board, OthelloMove best, float alpha, float beta, int depth)
{             
    OthelloMove garbage = new OthelloMove();             
    int currentPlayer = board.getCurrentPlayer();

    if (board.checkEnd())
    {                        
        int bd = board.countDiscs(OthelloBoard.BLACK);
        int wd = board.countDiscs(OthelloBoard.WHITE);

        if ((bd > wd) && currentPlayer == OthelloBoard.BLACK)                
            return INFINITY;
        else if ((bd < wd) && currentPlayer == OthelloBoard.BLACK)                           
            return -INFINITY;            
        else if ((bd > wd) && currentPlayer == OthelloBoard.WHITE)                            
            return -INFINITY;            
        else if ((bd < wd) && currentPlayer == OthelloBoard.WHITE)                            
            return INFINITY;            
        else                             
            return 0.0f;            
    }
    //search until the end? (true during end game phase)
    if (!solveTillEnd )
    {
        if (depth == maxDepth)
            return OthelloHeuristics.eval(currentPlayer, board);
    }

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

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

        if(score > alpha)
        {  
            //Set Best move here
            alpha = score;                
            best.setFlipSquares(mv.getFlipSquares());
            best.setIdx(mv.getIdx());        
            best.setPlayer(mv.getPlayer());                              
        }

        if (alpha >= beta)
            break;                

    }                
    return alpha;
}

私はそれを使用して呼び出します：

AI ai = new AI(board, maxDepth, solveTillEnd);

//create empty (invalid) move to hold best move
OthelloMove bestMove = new OthelloMove();
ai.bestFound = bestMove;
ai.minimax(board, bestMove, -INFINITY, INFINITY, 0);

//dipatch a Thread
 new Thread(ai).start();
//wait for thread to finish

OthelloMove best = ai.bestFound();

失われた位置 (たとえば、10 移動後に失われたと想像してください) が検索されると、上記の最良の変数は、引数として渡された空の無効な移動に等しくなります...なぜ??

助けてくれてありがとう！

4

3 に答える 3

3

あなたの問題は、勝敗スコアとして -INFINITY と +INFINITY を使用していることです。勝敗のスコアは、他のどの位置評価スコアよりも高い/低いが、無限値と等しくない必要があります。これにより、どうしようもなく負けたポジションでも、確実にムーブが選択されます。

于 2012-03-01T07:40:15.943 に答える
2

ミニマックスを実装してから長い時間が経っているので間違っているかもしれませんが、あなたのコードは、勝ちまたは負けの動きに遭遇した場合、最良の変数を更新しないようです (これは (board.checkEnd() で発生します) ) メソッドの先頭にあるステートメント)。

また、アルゴリズムをできるだけ多く勝たせたい場合、または勝てない場合はできるだけ少なく負けないようにしたい場合は、eval 関数を更新することをお勧めします。勝利の状況では、大きな値 (非勝利の状況よりも大きい) を返す必要があります。負けの状況では、大きな負の値 (負けのない状況よりも小さい) を返す必要があり、負けるほど値が小さくなります。

eval 関数をそのように更新し、チェック if (board.checkEnd()) を完全にスキップすると、(他に問題がない限り) アルゴリズムは正常に動作するはずです。幸運を！

于 2012-03-01T07:23:39.290 に答える
0

ポジションが本当に勝ったか負けたかを検出できる場合、それはエンドゲームを解決していることを意味します。この場合、ゲームの途中で評価する見積もりとは異なり、これは正確に計算できるため、評価関数はゲームの最終スコアを返す必要があります (例: 完全勝利の場合は 64、わずかな敗北の場合は 31)。

于 2012-03-01T08:55:28.897 に答える