VPF::Применение альфа-бета отсечения в шахматах

ButchelorOfHumanities

Дата 31.12.2010, 09:50 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 31.12.2010

Репутация: нет
Всего: нет

Дело обстоит так: я (школьник, а не прожженный программист) пишу шахматную программу под спор. Основной алгоритм - минимакс с альфа-бета отсечением. Вот псевдокод:

Код


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

Так что игроки получают маленький штраф за более длинный путь к победе.

Оба моих решения этой проблемы мне лично кажутся какими-то корявыми. Возможно есть более простое и эстетичное решение которое мне (дилетанту) не пришло в голову?

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »