3

私は現在、オセロ用の優れた AI を作ろうとしており、Minimax アルゴリズムを使用してそれを実現しました。しかし、α-β プルーニングを使用してさらに深く検索しようとすると、アルゴリズムがひどく機能しているように見えました。Wiki や Berkely.edu などの他のソースで確認しましたが、正しく実装されていると思いますが、まだ問題が見つかりません。

def alphabeta(board, player, a, b, lev):
        h = heur(board, player)
        if lev == 0:
                return h, None
        poss = get_legal_moves(board, player)
        if len(poss) == 0:
                return h, None
        move = 0
        for x in poss:
                cpboard = board[:]
                cpboard[x] = player
                bracket(cpboard, player, x)
                a1, q = alphabeta(cpboard, opponent_color(player), a, b, lev-1)
                if player is me:
                        if a1 > a:
                                a, move = a1, x
                else:
                        if a1 < b:
                                b, move = a1, x
                if b <= a:
                        break
        if player is me:
                return a, move
        else:
                return b, move
4

2 に答える 2

2

あなたのアルファベータコードはおそらく間違っています。プレイヤーが「ターンをパスする」(つまり、利用可能な手がない) 場合に何が起こるかに注意してください。これにより、コードにトリッキーなバグがありました。

アルファ値とベータ値を入れ替えて再帰を呼び出しましたか? 私は次のように動作します(Javaコード):

private float minimax(OthelloBoard board, OthelloMove best, float alpha, float beta, int depth)
{
    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 INFINITY;        
    if ((state == OthelloBoard.STATE_WHITE_WINS) && (currentPlayer == OthelloBoard.WHITE))
        return INFINITY;
    if ((state == OthelloBoard.STATE_BLACK_WINS) && (currentPlayer == OthelloBoard.WHITE))
        return -INFINITY;
    if ((state == OthelloBoard.STATE_WHITE_WINS) && (currentPlayer == OthelloBoard.BLACK))
        return -INFINITY;

    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;
}

呼び出しは次のようになります。

 OthelloMove bestFound = new OthelloMove();
 int maxDepth = 8;
 minimax(board, bestFound, -Float.MAX_VALUE, Float.MAX_VALUE, maxDepth);
//Wait for Thread to finish
 board.makeMove(bestFound);

編集: プレーヤーに利用可能な手がない場合、getAllMoves() は「ダミーの手」を返します。これはボードをまったく変更せず、ターンを渡すだけです。

それが役に立てば幸い！

于 2012-02-28T20:25:21.770 に答える
1

あなたのアルファベットの実装は私には健全に見えます。minimax と alphabeta は正しく実装すると同じ結果を生成するため、少なくとも適度な検索深度では、古い minimax コードを alphabeta に対するチェックとして使用できるはずです。同じゲーム ツリーを検索したときに結果が異なる場合は、何か間違ったことをしたことがわかります。

しかし、ほとんどの場合、悪いプレイは "heur" 評価関数の何かの結果です。

于 2012-01-16T08:05:41.983 に答える