Улучшение производительности этого MiniMax с AlphaBeta Pruning

Question

Улучшение производительности этого MiniMax с AlphaBeta Pruning

У меня есть следующая реализация минимакс альфа бета для игры отелло (реверси). Я исправил некоторые проблемы этот нить. На этот раз я хотел бы улучшить производительность этой функции. MAX_DEPTH = 8 занимает очень много времени. Что можно сделать, чтобы повысить производительность, сохранив при этом искусственный интеллект?

mm_out minimax(Grid& G, int alpha, int beta, Action& A, uint pn, uint depth, bool stage) {
if (G.check_terminal_state() || depth == MAX_DEPTH) {
return mm_out(A, G.get_utility(pn));
}

// add end game score total here

set<Action> succ_temp = G.get_successors(pn);
for (Action a : succ_temp) {
Grid gt(G);
a.evaluate(gt);
}
set<Action, action_greater> successors(succ_temp.begin(), succ_temp.end());

// if no successor, that player passes
if (successors.size()) {
for (auto a = successors.begin(); a != successors.end(); ++a) {
Grid gt(G);
gt.do_move(pn, a->get_x(), a->get_y(), !PRINT_ERR);
Action at = *a;
mm_out mt = minimax(gt, alpha, beta, at, pn ^ 1, depth + 1, !stage);
int temp = mt.val;
//          A = mt.best_move;

if (stage == MINIMAX_MAX) {
if (alpha < temp) {
alpha = temp;
A = *a;
}
if (alpha >= beta) {
return mm_out(A, beta);
}
}
else {
if (beta > temp) {
beta = temp;
A = *a;
}
if (alpha >= beta) {
return mm_out(A, alpha);
}}
}
return mm_out(A, (stage == MINIMAX_MAX) ? alpha : beta);
}
else {
return mm_out(A, (stage == MINIMAX_MAX) ? (std::numeric_limits<int>::max() - 1) : (std::numeric_limits<int>::min() + 1));
}

}

Вспомогательная функция:

int Grid::get_utility(uint pnum) const {
if (pnum)
return wcount - bcount;
return bcount - wcount;
}

0

alpha-beta-pruning artificial-intelligence c++minimax

Решение

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

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

Источник

Accepted Answer

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

Первая техника, которую вы можете реализовать — это таблица транспозиции. Таблицы транспонирования хранят в хеш-таблице все ранее посещенные узлы в дереве поиска игр. Большинство игровых состояний, особенно при глубоком поиске, могут быть достигнуты с помощью различных транспозиций или порядков ходов, которые восстанавливаются в одном и том же конечном состоянии. Сохраняя ранее найденные игровые состояния, если вы обнаружите, что состояние уже найдено, вы можете использовать данные, хранящиеся в таблицах, и прекратить углублять поиск в этом узле. Стандартная техника хранения игровых состояний в хеш-таблице называется Zobrist Hashing. Подробная информация о реализации таблиц транспозиции доступна в Интернете.
Второе, что должна включать ваша программа, — это упорядочение ходов. По сути, это означает, что нужно проверять ходы не в том порядке, в котором вы их сгенерировали, а в том порядке, который, скорее всего, приведет к отсечке альфа-бета (т.е. сначала удачные ходы). Очевидно, вы не можете знать, какие ходы лучше, но большинство ходов можно заказать, используя наивную технику. Например, в Отелло ход, который находится в углу или краю, должен быть исследован первым. Упорядочивание ходов должно привести к увеличению отсечений и увеличению скорости поиска. Это создает нулевую потерю точности.
Вы также можете добавить начальные книги. Обычно начальные ходы занимают больше всего времени, так как на доске полно больше возможностей. Открывающая книга — это база данных, в которой хранятся все возможные ходы, которые могут быть сделаны в первые несколько ходов, и лучший ответ на них. В Отелло с низким коэффициентом ветвления, это будет особенно полезно в начальной игре
Probcut. Я не буду вдаваться в подробности, так как это более продвинутая техника. Однако он дал хорошие результаты с Отелло, поэтому я решил опубликовать эту ссылку.https://chessprogramming.wikispaces.com/ProbCut

1