Минимаксная реализация не работает с рекурсией и переполнением стека

Question

Минимаксная реализация не работает с рекурсией и переполнением стека

У меня в основном есть игровое поле, и игрок не может перейти в одно и то же место более одного раза, иначе вы проиграете. Игрок может двигаться только на -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;
}

Тем не менее, это не работает. Я не могу понять, почему. Алгоритм выглядит так, как будто он должен работать, и я считаю, что проблема связана с очисткой памяти. Мои точки останова VC ++ studio в _CrtIsValidHeapPtr после вызова решают несколько раз

0

c++minimax

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Я не могу засвидетельствовать правильность алгоритма. Но есть ошибки кодирования, которые приведут к неопределенному поведению, на которое вам следует обратить внимание.

Основная проблема заключается в том, что вы путаете размер массива с количеством элементов в массиве. В вашем main(), вы должны использовать sizeof(Board)/sizeof(*Board) определить количество элементов массива для Boardиначе вы будете читать вне границы массива Board, Затем вы проходите sizeof(Board) как BoardSize в solveно, опять же, это не то значение, которое следует использовать, когда вы проверяете, Position в пределах границ. Ваш внешний for цикл также вычисляет количество элементов массива для choices неправильно.

В качестве вторичной проблемы, вы затмеваете 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));

Кроме того, вы можете избежать new/delete бизнес в вашем коде довольно легко с помощью std::vector<int> за BoardCopy а также MoveSet, Например:

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

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

Пройти в int * параметр, как у вас в коде, вы бы передать &BoardCopy[0], но вы должны рассмотреть возможность изменения кода, чтобы std::vector<int> &, Когда вы сделаете это, вы можете удалить все звонки на delete BoardCopy,

0