Шахматный AI с альфа-бета алгоритмом
Я реализовал альфа-бета-алгоритм для своей шахматной игры, однако, чтобы сделать довольно глупый ход, требуется много времени (минут для 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;
}
функция альфа-бета:
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;
}
}
РЕДАКТИРОВАТЬ: я должен отметить, что на методе valuBoard оценивается только подвижность фигур (количество возможных ходов, ходы захвата получают более высокий балл в зависимости от захваченного фрагмента)
Спасибо.
Решение
Я вижу, что вы пытаетесь реализовать алгоритм мини-макс. Однако в коде есть что-то, что вызывает у меня подозрения. Мы сравним код с шахматным движком Stockfish с открытым исходным кодом. Пожалуйста, обратитесь к алгоритму поиска на https://github.com/mcostalba/Stockfish/blob/master/src/search.cpp
1. Прохождение доски б по значению
У вас есть это в вашем коде:
alphaBeta (Board b, int alpha, int beta, char char, bool nodeType)
Я не знаю, что такое «доска». Но это не выглядит правильным для меня. Давайте посмотрим на Stockfish:
Поиск значения (Позиция& pos, Stack * ss, значение альфа, значение бета, глубина
глубина, bool cutNode)
Положение объекта передано по ссылке в Стокфиш. Если «Board» является классом, программе необходимо будет делать новую копию каждый раз, когда вызывается функция альфа-бета. В шахматах, когда нам приходится оценивать множество узлов, это явно недопустимо.
2. Нет хеширования
Хэширование делается в Stockfish как:
ttValue = ttHit? value_from_tt (tte-> value (), ss-> ply): VALUE_NONE;
Без хеширования вам нужно будет снова и снова оценивать одну и ту же позицию, снова и снова. Вы никуда не уйдете без хеширования.
3. Проверка на мат
Вероятно, не самое значительное замедление, но мы никогда не должны проверять наличие матов в каждом отдельном узле. В Stockfish:
// All legal moves have been searched. A special case: If we're in check
// and no legal moves were found, it is checkmate.
if (InCheck && bestValue == -VALUE_INFINITE)
return mated_in(ss->ply); // Plies to mate from the root
Готово ПОСЛЕ все возможные ходы обыскиваются. Мы делаем это потому, что обычно у нас гораздо больше не-матовых узлов, чем у мат-матов.
4. Board bTemp (false);
Это выглядит как серьезное замедление. Давайте возьмем на Stockfish:
// Step 14. Make the move pos.do_move(move, st, ci, givesCheck);
Вы не должны создавать временный объект в каждом узле (создание объекта bTemp). Машина должна была бы выделить некоторое пространство стека, чтобы сохранить bTemp. Это может быть серьезным ухудшением производительности, в частности, если bTemp не является основной переменной (т. Е. Вряд ли будет кэшироваться процессором). Stockfish просто изменяет внутреннюю структуру данных, не создавая новую.
5. bTemp.cloneBoard (b);
Аналогично 4, еще хуже, это делается для каждого движения в узле.
6. std :: cout << «максимальная отсечка» << станд :: епсИ;
Может быть, в это трудно поверить, печать на терминал намного медленнее, чем обработка. Здесь вы создаете потенциальное замедление, что строка должна быть сохранена в буфер ввода-вывода. Функция может (я не уверен на 100%) даже блокировать вашу программу, пока на терминале не появится текст. Stockfish делает это только для статистической сводки, определенно не каждый раз, когда у вас сбой-максимум или сбой-минимум.
7. Не сортировать ход PV
Вероятно, не то, что вы хотите сделать, прежде чем решать другие вопросы. У Stockfish у них есть:
std :: stable_sort (RootMoves.begin () + PVIdx, RootMoves.end ());
Это делается для каждой итерации в итерационно-углубляющейся структуре.
Другие решения
Я собираюсь рассмотреть только проблему стоимости времени выполнения вашего алгоритма, потому что я не знаю деталей реализации функции оценки вашей платы.
Чтобы все было как можно проще, я буду предполагать наихудший случай для алгоритма.
Функция getMove выполняет вызовы len1 для функции alphaBeta, которая, в свою очередь, выполняет вызовы len2 к себе, которые, в свою очередь, делают вызовы len3 к себе и т. Д., Пока глубина не достигнет 0 и рекурсия не прекратится.
Из предположения наихудшего случая, скажем, n = max (len1, len2, …), так что вы
n * n * n * … * n вызывает alphaBeta с числом умножений в зависимости от глубины d, что приводит к n ^ d вызовам alphaBeta, что означает, что у вас экспоненциальное поведение во время выполнения. Это очень медленно и побеждено только факториальным поведением во время выполнения.
Я думаю, что вы должны взглянуть на нотацию Big O для этой цели и попытаться оптимизировать свой алгоритм соответствующим образом, чтобы получить гораздо более быстрые результаты.
С наилучшими пожеланиями,
OPM