java - 効率的なアルファベータ剪定ゲーム検索ツリーを実装する方法は?

Question

人工知能とそれをプログラムに実装する方法について学ぼうとしています。最も簡単に開始できるのは、単純なゲーム (この場合は Tic-Tac-Toe) とゲーム検索ツリー (再帰呼び出しであり、実際のデータ構造ではありません) です。このトピックに関する講義で、この非常に役立つビデオを見つけました。

私が抱えている問題は、アルゴリズムへの最初の呼び出しの実行に非常に長い時間 (約 15 秒) がかかっていることです。コード全体にデバッグ ログ出力を配置しましたが、アルゴリズムの一部を過度に呼び出しているようです。

コンピューターに最適な動きを選択する方法は次のとおりです。

    public Best chooseMove(boolean side, int prevScore, int alpha, int beta){
    Best myBest = new Best(); 
    Best reply;

    if (prevScore == COMPUTER_WIN || prevScore == HUMAN_WIN || prevScore == DRAW){
        myBest.score = prevScore;
        return myBest;
    }

    if (side == COMPUTER){
        myBest.score = alpha;
    }else{
        myBest.score = beta;
    }
    Log.d(TAG, "Alpha: " + alpha + " Beta: " + beta + " prevScore: " + prevScore);
    Move[] moveList = myBest.move.getAllLegalMoves(board);
    for (Move m : moveList){
        String choice;
        if (side == HUMAN){
            choice = playerChoice;
        }else if (side == COMPUTER && playerChoice.equals("X")){
            choice = "O";
        }else{
            choice = "X";
        }
        Log.d(TAG, "Current Move: column- " + m.getColumn() + " row- " + m.getRow());
        int p = makeMove(m, choice, side);
        reply = chooseMove(!side, p, alpha, beta);
        undoMove(m);
        if ((side == COMPUTER) && (reply.score > myBest.score)){
            myBest.move = m;
            myBest.score = reply.score;
            alpha = reply.score;
        }else if((side == HUMAN) && (reply.score < myBest.score)){
            myBest.move = m;
            myBest.score = reply.score;
            beta = reply.score;
        }//end of if-else statement
        if (alpha >= beta) return myBest;
    }//end of for loop
    return myBest;
}

スポットが空の場合にmakeMoveメソッドが移動し、値を返す場所 (-1 - 人間の勝利、0 - 引き分け、1 - コンピュータの勝利、-2 または 2 - それ以外)。エラーはgetAllLegalMovesメソッドにある可能性があると思いますが：

    public Move[] getAllLegalMoves(String[][] grid){
    //I'm unsure whether this method really belongs in this class or in the grid class, though, either way it shouldn't matter.
    items = 0;
    moveList = null;
    Move move = new Move();

    for (int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            Log.d(TAG, "At Column: " + i + " At Row: " + j);
            if(grid[i][j] == null || grid[i][j].equals("")){
                Log.d(TAG, "Is Empty");
                items++;
                if(moveList == null || moveList.length < items){
                    resize();
                }//end of second if statement
                move.setRow(j);
                move.setColumn(i);
                moveList[items - 1] = move;
            }//end of first if statement
        }//end of second loop
    }//end of first loop
    for (int k = 0; k < moveList.length; k++){
        Log.d(TAG, "Count: " + k + " Column: " + moveList[k].getColumn() + " Row: " + moveList[k].getRow());
    }
    return moveList;
}

private void resize(){
    Move[] b = new Move[items];
    for (int i = 0; i < items - 1; i++){
        b[i] = moveList[i];
    }
    moveList = b;
}

すべてを要約すると:最適な動きを選択するのに時間がかかる原因は何ですか? 私は何が欠けていますか？このアルゴリズムを実装する簡単な方法はありますか? どんな助けや提案も大歓迎です、ありがとう!

Answer 1

アルファ ベータ プルーニングを使用したミニマックス ツリーは、ツリーとして視覚化する必要があります。ツリーの各ノードは、将来に向けて多くの方向転換を行う可能性のある動きであり、その子は、そこから実行できるすべての動きです。

可能な限り高速で、先を見据えている動きの数に比例したスペースのみが必要になることを保証するには、深さ優先検索を実行し、一方から他方へと「スイープ」します。たとえば、ツリー全体が構築されていると想像すると、プログラムは実際には、リードからルートまでのストランドを一度に 1 つずつ構築し、その一部を破棄します。

この時点で、ウィキペディアの疑似コードをコピーします。これは、非常に簡潔で明確だからです。

function alphabeta(node, depth, α, β, Player)         
    if  depth = 0 or node is a terminal node
        return score
    if  Player = MaxPlayer
        for each child of node
            α := max(α, alphabeta(child, depth-1, α, β, not(Player) ))     
            if β ≤ α
                break                             (* Beta cut-off *)
        return α
    else
        for each child of node
            β := min(β, alphabeta(child, depth-1, α, β, not(Player) ))     
            if β ≤ α
                break                             (* Alpha cut-off *)
        return β

ノート：

-'for each child of node' - 現在のボードの状態を編集するのではなく、移動を適用した結果である完全に新しいボードを作成します。不変オブジェクトを使用することで、コードにバグが発生しにくくなり、一般的に推論が速くなります。

-このメソッドを使用するには、現在の状態から実行できるすべての可能な移動に対して呼び出し、深さ -1、アルファの場合は -Infinity、ベータの場合は +Infinity を指定します。これらの呼び出しのうち、最も高い値を返す呼び出しが最適です。

概念的には非常に単純です。正しくコーディングすれば、一度に複数の (深さ) ボードをインスタンス化することはなく、無意味な分岐などを考慮することもありません。

Answer 2

私はあなたのためにあなたのコードをプロファイリングするつもりはありませんが、これはとても素晴らしいコーディングの形なので、三目並べの小さなaiを書きました:

import java.math.BigDecimal;

public class Board {

    /**
     * -1: opponent
     * 0: empty
     * 1: player
     */
    int[][] cells = new int[3][3];

    /**
     * the best move calculated by eval(), or -1 if no more moves are possible
     */
    int bestX, bestY;

    int winner() {
        // row
        for (int y = 0; y < 3; y++) {
            if (cells[0][y] == cells[1][y] && cells[1][y] == cells[2][y]) {
                if (cells[0][y] != 0) {
                    return cells[0][y];
                }
            }
        }

        // column
        for (int x = 0; x < 3; x++) {
            if (cells[x][0] == cells[x][1] && cells[x][1] == cells[x][2]) {
                if (cells[x][0] != 0) {
                    return cells[x][0];
                }
            }
        }

        // 1st diagonal
        if (cells[0][0] == cells[1][1] && cells[1][1] == cells[2][2]) {
            if (cells[0][0] != 0) {
                return cells[0][0];
            }
        }

        // 2nd diagonal
        if (cells[2][0] == cells[1][1] && cells[1][1] == cells[0][2]) {
            if (cells[2][0] != 0) {
                return cells[2][0];
            }
        }

        return 0; // nobody has won
    }

    /**
     * @return 1 if side wins, 0 for a draw, -1 if opponent wins
     */
    int eval(int side) {
        int winner = winner();
        if (winner != 0) {
            return side * winner;
        } else {
            int bestX = -1;
            int bestY = -1;
            int bestValue = Integer.MIN_VALUE;
        loop:
            for (int y = 0; y < 3; y++) {
                for (int x = 0; x < 3; x++) {
                    if (cells[x][y] == 0) {
                        cells[x][y] = side;
                        int value = -eval(-side);
                        cells[x][y] = 0;

                        if (value > bestValue) {
                            bestValue = value;
                            bestX = x;
                            bestY = y;
                            if (bestValue == 1) {
                                // it won't get any better, we might as well stop thinking
                                break loop;
                            }
                        }
                    }
                }
            }
            this.bestX = bestX;
            this.bestY = bestY;
            if (bestValue == Integer.MIN_VALUE) {
                // there were no moves left, it must be a draw!
                return 0;
            } else {
                return bestValue;
            }
        }
    }

    void move(int side) {
        eval(side);
        if (bestX == -1) {
            return;
        }
        cells[bestX][bestY] = side;
        System.out.println(this);

        int w = winner();
        if (w != 0) {
            System.out.println("Game over!");
        } else {
            move(-side);
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        char[] c = {'O', ' ', 'X'};
        for (int y = 0; y < 3; y++) {
            for (int x = 0; x < 3; x++) {
                sb.append(c[cells[x][y] + 1]);
            }
            sb.append('\n');
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        long start = System.nanoTime();
        Board b = new Board();
        b.move(1);
        long end = System.nanoTime();
        System.out.println(new BigDecimal(end - start).movePointLeft(9));
    }
}

賢明な読者は、私がアルファ/ベータ カットオフを使用していないことに気付くでしょう。それでも、やや古いノートブックでは、これは 0.015 秒でゲームをプレイします...

あなたのコードをプロファイリングしていないので、何が問題なのかはっきりとは言えません。ただし、検索ツリーのすべてのノードで考えられるすべての動きをログに記録すると、何か関係がある可能性があります。