Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Применение альфа-бета отсечения в шахматах

Автор: ButchelorOfHumanities 31.12.2010, 09:50

Дело обстоит так: я (школьник, а не прожженный программист) пишу шахматную программу под спор. Основной алгоритм - минимакс с альфа-бета отсечением. Вот псевдокод: Код function maximize(node, depth, alpha, beta)       //ход белых       if  depth = 0 or node is a terminal node         return evaluate(node)    else         for each child of node             alpha:= max(α, mininize(child, depth-1, alpha, beta))                  if beta≤alpha                 break      return alpha function minimize(node, depth, alpha, beta)         //ход черных     if  depth = 0 or node is a terminal node         return evaluate(node)    else         for each child of node             beta:= min(α, maximize(child, depth-1, alpha, beta))                  if beta≤alpha                 break      return beta function evaluate(node) - оценочная функция Где node - некоторая позиция на доске, depth - глубина расчета в полуходах, child - некоторый ход одного из игроков, alpha и beta - минимальный и максимальный коэффициенты сожаления соответствующие интересам обоих играков. Если компьютер играет белыми, то функция вызывается так: maximize(текущаяПозиция, числоПолуходов, -бесконечность, +бесконечновть) Проблема заключается в следующем: Если на доске есть возможность поставить мат в два хода (четыре полухода) и вызывается функция maximize(текущаяПозиция, 4, -бесконечность, +бесконечновть), то комп ставит мат в два хода, однако если вызвать функцию maximize(текущаяПозиция, 6, -бесконечность, +бесконечновть) при той же позиции на доске, то вместо быстрого мата в два хода комп ставит более долгий мат в три. Иными словами - выше приведенный алгоритм не учитывает приоритетность быстрого выигрыша. Пока что я придумал два возможных решения: 1) Последовательный вызов maximize(текущаяПозиция, 2, -бесконечность, +бесконечновть), maximize(текущаяПозиция, 4, -бесконечность, +бесконечновть), maximize(текущаяПозиция, 6, -бесконечность, +бесконечновть) - то есть поиск мата в один, два и три хода последовательно. 2) Изманение алгоритма на: Код function maximize(node, depth, alpha, beta)       //ход белых       if  depth = 0 or node is a terminal node         return evaluate(node)-depth            //CHANGED!    else         for each child of node             alpha:= max(α, mininize(child, depth-1, alpha, beta))                  if beta≤alpha                 break      return alpha function minimize(node, depth, alpha, beta)         //ход черных     if  depth = 0 or node is a terminal node         return evaluate(node)+depth          //CHANGED!    else         for each child of node             beta:= min(α, maximize(child, depth-1, alpha, beta))                  if beta≤alpha                 break      return beta Так что игроки получают маленький штраф за более длинный путь к победе. Оба моих решения этой проблемы мне лично кажутся какими-то корявыми. Возможно есть более простое и эстетичное решение которое мне (дилетанту) не пришло в голову?

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)