0

私は基本的にゲームボードを持っており、プレイヤーは同じ場所に複数回移動することはできません。そうしないと負けます。プレイヤーは -1、+1、-16、または +16 だけ移動できます。ミニマックスを使用してこの問題を解決し、ミニマックスが使用する入力を受け取って、それがどのように行われたかを確認したいと考えています。

これが私が現在やっている方法です

#pragma optimize("", off)

#include <stdio.h>
#include <Windows.h>

#define hitcount 4

#define POINT 1
#define MINE 2
#define END 3

//4 targets: hit all 1's
//player/mine is 2
//game ender is 3
int Board[] = {
    0, 0, 0, 0, 0, 0, 0,
    1, 0, 0, 0, 0, 1, 0,
    2, 0, 0, 1, 0, 0, 1,
    0, 0, 0, 0, 0, 0, 0,
    3, 0, 0, 0, 0, 0, 0
};

static const int choices[] = {
    -1, 1, -16, 16
};

struct mb {
    int end;
    int score;
    int* moveset;
};

mb solve(int Position, int *Board, int BoardSize, int *MoveSet = NULL, int Offset = 0, int Choice = 0, int Score = 0, bool tree = true) {
    if( tree ) { //tree
        int *BoardCopy = new int[BoardSize];        

        for( int i = 0; i < sizeof(choices); i++ ) {
            MoveSet = new int[256];
            for( int i = 0; i < 256; i++ )
                MoveSet[i] = 0xFF;

            memcpy(BoardCopy, Board, BoardSize);
            mb m = solve(Position, BoardCopy, BoardSize, MoveSet, Offset, i, Score, false);

            if( m.moveset != NULL ) {               
                if( m.end == 1 && m.score == hitcount ) {
                    delete[] BoardCopy;
                    return m;
                }               

            }

            delete[] MoveSet; //this is apparently causing problems??
        }

        delete[] BoardCopy;

    }
    else { //branch
        mb m = {0, 0, MoveSet};

        Position += choices[Choice];
        m.moveset[Offset] = choices[Choice];
        if( Position < 0 || Position >= BoardSize || Board[Position] == MINE || (Board[Position] == END && Score != hitcount) ) {
            m.moveset = NULL;
            return m;
        }
        else if( Board[Position] == POINT ) {
            m.score++;
        }
        else if( Board[Position] == END ) {
            m.end = 1;
            return m;
        }

        Board[Position] = MINE; 

        return solve(Position, Board, BoardSize, m.moveset, Offset + 1, Choice + 1, m.score);

    }

    mb m = {0, 0, NULL};
    return m;
}


int main() {

    int Position = 0;
    for( int i = 0; i < sizeof(Board); i++ ) {
        if( Board[i] == MINE ) Position = i;
    }

    mb m = solve(Position, Board, sizeof(Board));
    if( m.end == 1 && m.moveset != NULL && m.score == hitcount ) {
        printf("SUCCESS!\n");
    }

    getchar();
    return 0;
}

しかし、うまくいきません。理由がわかりません。アルゴリズムは機能しているように見えますが、問題はメモリのクリーンアップに関連しているようです。solve を数回呼び出した後の _CrtIsValidHeapPtr での私の VC++ スタジオ ブレークポイント

4

1 に答える 1

0

アルゴリズムの正しさを証明することはできません。ただし、対処する必要がある未定義の動作につながるコーディング エラーがあります。

主な問題は、配列のサイズと配列内の要素の数を混同していることです。では、の配列要素の数を決定するためにmain()を使用する必要があります。そうしないと、 の配列境界の外側を読み取ることになります。次に、 toとして渡しますが、これは範囲内にあるかどうかを確認するときに使用する適切な値ではありません。外側のループでも、配列要素の数が正しく計算されません。sizeof(Board)/sizeof(*Board)BoardBoardsizeof(Board)BoardSizesolvePositionforchoices

i二次的な問題として、ループ変数名をiの内側のforループで名前を付けた別の変数で覆い隠していますsolve()。混乱を避けるために、おそらく名前を変更する必要があります。

したがって、これらを念頭に置いて、次のように変更しmain()ます。

    for( int i = 0; i < sizeof(Board)/sizeof(*Board); i++ ) {
        if( Board[i] == MINE ) Position = i;
    }

    mb m = solve(Position, Board, sizeof(Board)/sizeof(*Board));

次に、次のように変更しsolve()ます。

        for( int i = 0; i < sizeof(choices)/sizeof(*choices); i++ ) {
            MoveSet = new int[256];
            for( int j = 0; j < 256; j++ )
                MoveSet[j] = 0xFF;

            memcpy(BoardCopy, Board, BoardSize*sizeof(int));

また、forとnew/deleteを使用すると、コード内のビジネスをかなり簡単に回避できます。例えば：std::vector<int>BoardCopyMoveSet

        std::vector<int> BoardCopy(BoardSize);

        //...
            std::copy(Board, Board+BoardSize, BoardCopy.begin());

int *コードにあるようにパラメーターを渡すには、 を渡しますが&BoardCopy[0]、コードを変更してstd::vector<int> &. これを行うと、 へのすべての呼び出しを削除できますdelete BoardCopy。

于 2013-09-28T03:04:52.683 に答える