Я хочу изменить непревзойденный тик, чтобы он работал для блока 5 на 5, вводя глубину, чтобы ограничить уровни поиска. Какие-либо предложения?

Вот фрагмент кода для минимаксного алгоритма. Для матрицы 5 на 5 это занимает много времени. Я хочу представить переменную, которая отслеживает глубину рекурсии и ограничивает ее. Вот ссылка на весь код: http://ideone.com/e.js/pyFHRu

int MiniMax(char _board[25], player _player) {
int best_val = -INFINITY, index = 0;
std::list<int> move_list;
char best_moves[25] = {0};
generate_moves(_board, move_list);
while(!move_list.empty()) {
_board[move_list.front()] = _player.symbol;
cSymbol = _player.symbol;
int val = MinMove(_board, _player);
if(val > best_val) {
best_val = val;
index = 0;
best_moves[index] = move_list.front() + 1;
} else if(val == best_val) {
best_moves[++index] = move_list.front() + 1;
}
_board[move_list.front()] = 0;
move_list.pop_front();
}
if(index > 0) {
index = rand() % index;
}
return best_moves[index];
}

// finds best move for 'min player'
int MinMove(char _board[25], player _player) {
int pos_value = evaluate_position(_board, _player);
if(pos_value != -1) {
return pos_value;
}
int best_val = +INFINITY;
std::list<int> move_list;
generate_moves(_board, move_list);
while(!move_list.empty()) {
_player.symbol == 'X' ? cSymbol = 'O' : cSymbol = 'X';
_board[move_list.front()] = cSymbol;
int val = MaxMove(_board, _player);
if(val < best_val) {
best_val = val;
}
_board[move_list.front()] = 0;
move_list.pop_front();
}
return best_val;
}

// finds best move for 'max player'
int MaxMove(char _board[25], player _player) {
int pos_value = evaluate_position(_board, _player);
if(pos_value != -1) {
return pos_value;
}
int best_val = -INFINITY;
std::list<int> move_list;
generate_moves(_board, move_list);
while(!move_list.empty()) {
_player.symbol == 'X' ? cSymbol = 'X' : cSymbol = 'O';
_board[move_list.front()] = cSymbol;
int val = MinMove(_board, _player);
if(val > best_val) {
best_val = val;
}
_board[move_list.front()] = 0;
move_list.pop_front();
}
return best_val;
}

0

Решение

Если вы уже работаете с меньшей глубиной, то вам нужно рассчитать эвристику. Эвристика — это значение от -1 до 1, показывающее оценку положения. Если у вас глубина 10 (вы рассчитываете 10 слоев), то вам нужно вычислить эвристику, когда вы достигнете конечной позиции вашей оценки (глубина равна 0 или кто-то выиграл).

Таким образом, мы можем достичь алгоритма MiniMax с ограниченной максимальной глубиной, где вы вычисляете оценку полученной позиции с помощью эвристической функции, если игра не выиграна. Если вы хотите устранить, казалось бы, бесполезные ветви вашего дерева оценки, используя эвристику для дальнейшей оптимизации времени оценки, тогда вы можете использовать альфа-бета-отсечение, подробнее Вот а также Вот.

0

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


По вопросам рекламы [email protected]