3

私は自分のチェス ゲームにアルファ ベータ アルゴリズムを実装しましたが、最終的にかなりばかげた動きをするのに多くの時間 (4 プライの場合は数分) がかかります。

私は2日間間違いを見つけようとしてきました（間違いを犯したと思います）。私のコードに外部からの入力をいただければ幸いです。

getMove 関数: ルート ノードに対して呼び出され、すべての子ノード (可能な移動) に対して alphaBeta 関数を呼び出し、最高スコアの移動を選択します。

Move AIPlayer::getMove(Board b, MoveGenerator& gen)
{
    // defined constants: ALPHA=-20000 and BETA= 20000
    int alpha = ALPHA; 
    Board bTemp(false); // test Board
    Move BestMov;
    int i = -1; int temp;
    int len = gen.moves.getLength();  // moves is a linked list holding all legal moves
    BoardCounter++; // private attribute of AIPlayer object, counts analyzed boards
    Move mTemp;     // mTemp is used to apply the nextmove in the list to the temporary test Board
    gen.mouvements.Begin();   // sets the list counter to the first element in the list
    while (++i < len && alpha < BETA){
        mTemp = gen.moves.nextElement();
        bTemp.cloneBoard(b);
        bTemp.applyMove(mTemp);
        temp = MAX(alpha, alphaBeta(bTemp, alpha, BETA, depth, MIN_NODE));
        if (temp > alpha){
            alpha = temp;
            BestMov = mTemp;
        }
    }
    return BestMov;
}

alphaBeta 関数:

int AIPlayer::alphaBeta(Board b, int alpha, int beta, char depth, bool nodeType)
{
    Move m;
    b.changeSide();
    compteurBoards++;
    MoveGenerator genMoves(b); // when the constructor is given a board, it automatically generates possible moves
    // the Board object has a player attribute that holds the current player
    if (genMoves.checkMate(b, b.getSide(), moves)){ // if the current player is in checkmate
        return 100000;
    }
    else if (genMoves.checkMate(b, ((b.getSide() == BLACK) ? BLACK : WHITE), moves)){ // if the other player is in checkmate
        return -100000;
    }
    else if (!depth){
        return b.evaluateBoard(nodeType);

    }
    else{
        int scoreMove = alpha;
        int best;
        genMoves.moves.Begin();
        short i = -1, len = genMoves.moves.getLength();
        Board bTemp(false);

        if (nodeType == MAX_NODE){
            best = ALPHA;
            while (++i < len){
                bTemp.cloneBoard(b);
                if (bTemp.applyMove(genMoves.moves.nextElement())){ 
                    scoreMove = alphaBeta(bTemp, alpha, beta, depth - 1, !nodeType);
                    best = MAX(best, scoreMove);
                    alpha = MAX(alpha, best);

                    if (beta <= alpha){ 
                        std::cout << "max cutoff" << std::endl;
                        break;
                    }
                }
            }
            return scoreMove;
        //return alpha;
        }
        else{
            best = BETA;
            while (++i < len){
                bTemp.cloneBoard(b);
                if (bTemp.applyMove(genMoves.moves.nextElement())){ 
                    scoreMove = alphaBeta(bTemp, alpha, beta, depth - 1, !nodeType);
                    best = MIN(best, scoreMove);
                    beta = MIN(beta, best);
                    if (beta <= alpha){ 
                        std::cout << "min cutoff" << std::endl;
                        break;
                    }
                }
            }
            return scoreMove;
            //return beta;
        }
        return meilleur;
    }
}

編集：evaluateBoardはピースの可動性のみを評価することに注意してください（可能な移動の数、キャプチャされたピースに応じてキャプチャの移動はより高いスコアを取得します）

ありがとうございました。

4

2 に答える 2

0

ボード評価関数の実装の詳細がわからないため、アルゴリズムのランタイム コストの問題のみを扱います。

できるだけ単純にするために、アルゴリズムの最悪のケースを想定します。

getMove 関数は、alphaBeta 関数に対して len1 呼び出しを行い、次にそれ自体に対して len2 呼び出しを行い、さらにそれ自体に対して len3 呼び出しを行い、深さが 0 に達して再帰が停止するまで繰り返します。最悪の場合の仮定のために、n = max(len1, len2, ...) としましょう。

n * n * n * ... * n は、深さ d に応じた乗算回数で alphaBeta を呼び出します。これは、alphaBeta への n^d 呼び出しにつながります。これは、指数関数的なランタイム動作があることを意味します。これは非常に遅く、階乗実行時の動作によってのみ打ち負かされます。

そのために Big O 表記法を調べ、それに応じてアルゴリズムを最適化して、はるかに高速な結果を得る必要があると思います。

よろしく、OPM

于 2015-06-01T06:39:50.290 に答える