Интеллектуальные системы. Алгоритм поиска оптимального хода в игре Крестики-нолики

вторник, 13 ноября 2012 г.
Уверен, многие успели насладиться великолепным квестом  Machinarium. Вы наверняка помните того робота, которого надо было обыграть в баре, чтобы получить необходимые болтики. Так вот, игра, в которую его надо было обыграть, очень похожа на  крестики-нолики, но имеет поле 10 на 10 и продолжается, пока один из игроков не выстроит ряд из пяти фигурок.

Продолжая тему интеллектуальных систем, предлагаю написать алгоритм для игры в крестики-нолики по правилам, предложенным в Machinarium.

Сыграть!

Игры с нулевой суммой

Прежде всего, следует отметить, что крестики-нолики - это игра с нулевой суммой. То есть игра, в которой выигрыш одного  игрока означает проигрыш другого.
Формально антагонистическая игра может быть представлена тройкой <X, Y, F>, где X и Y — множества стратегий первого и второго игроков, соответственно; F — функция выигрыша первого игрока, ставящая в соответствие каждой паре стратегий (ситуации) (x,y), x \in X, y \in Y действительное число, соответствующее полезности первого игрока при реализации данной ситуации. Так как интересы игроков противоположны, функция F одновременно представляет и проигрыш второго игрока.

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

Дерево игры (решений)

Начнем с малого, с классических крестиков-ноликов на поле 3 на 3. Процесс игры можно представить в виде графа, узлы которого представляют собой состояния игрового поля после хода одного из игроков:
Пример дерева игры в крестики-нолики
В простейшем случае, можно строить полный граф игры и выбирать ход, ведущий к победе (или к ничьей). Но такое решение крайне ресурсоемко. В дереве игры, в классические крестики-нолики, придется раскрыть 255168 возможных ходов! Думаю, излишне говорить, что дерево игры по обозначенным в начале статьи правилам, будет гораздо больше.

Минимаксная процедура

Чтобы сократить дерево игры, можно поступать по аналогии с человеческим решением: человек тоже не способен продумать все варианты развития игры в соответствии со своим ходом, но он может  продумать возможные варианты на несколько ходов вперед и выбрать наилучший из них. Количество шагов, на которое способен продумать игру человек, ограничено его интеллектуальными способностями. В случае с компьютерным решением, таким ограничением может стать память или время работы алгоритма. В простейшем случаем можно ограничиться глубиной раскрытия дерева.

В таком случае, мы, конечно, рискуем выбрать ход, который будет привлекательным при выбранной глубине раскрытия дерева решений, но окажется проигрышным в более долгосрочной перспективе... Но не будем пессимистами!

Самый интересный аспект такого подхода, это способ оценки выгоды от того или иного хода. В самом простейшем случае, можно выделить некоторые состояния игрового поля (ничья, победа и поражение) и присвоить каждому из них некоторый числовой коэффициент(оценку).
Пример оценок игрового поля
(none = 0; draw = 2; win = 5; lose = -5)
Такая оценка строится не для каждого узла дерева игры, а только для его листьев. Оценка же каждого узла получается из следующих соображений: на каждом этапе раскрытия дерева решений, начиная с последнего (на котором получаются листы с оценками), выбирается ход, наиболее предпочтительный для игрока, чей ход приводит к порождению узлов. При этом, для игрока, за которого ведется игра, оценка должна стремиться к максимуму, а для противника к минимуму.

Так, играя (к примеру) за  нолики, каждый нечетный ход представляет их интересы и выбирается ход с наибольшей оценкой (игрок MAX), а каждый четный - интересы крестиков, выбирается ход с наименьшей оценкой (игрок MIN). Такой подход называется минимаксной процедурой.

Пример дерева игры, раскрытого на глубину в три хода

Алгоритм

Для лучшего понимания алгоритма, привожу пример его реализации на вымышленном языке программирования:
// Оценка максимального выигрыша игрока.
// field состояние поля в результате хода игрока MIN.         
// player идентификатор игрока MAX.  
function MAX(field, player, deph) : int
    if isTerminal(field) then
        return heuristic(field, player)
    end
    score  = -INFINITY
    for child from children(field, player) do
        s = MIN(child, -player, deph+1)
        if s > score  then score  = s        
    end
    return score
end

// Оценка минимальных потерь противника.
// field состояние поля в результате хода игрока MAX.         
// player идентификатор игрока MIN.    
function MIN(field, player, deph) : int
    if isTerminal(field) then
        return -heuristic(field, player)
    end
    score  = INFINITY
    for child from children(field, player) do
        s = MAX(child, -player, deph+1)
        if s < score  then score  = s
    end
    return score
end 

Здесь следует пояснить ряд используемых функций.
  • Функция isTerminal проверяет, не достигнуто ли терминальное состояние на игровом поле. Терминальное состояние, это состояние при котором наступил выигрыш одного из игроков, или исчерпаны все возможные ходы, или выполнено условие прекращения раскрытия дерева игры (достигнута максимальная глубина / закончилась память). 
  • Функция heuristic дает эвристическую оценку состояния игрового поля.
  • Функция children, при каждом обращении к ней, возвращает следующего потомка  текущей оцениваемой позиции в дереве игры. Т.е. раскрывает дерево игры на следующую глубину.

Представленное решение достаточно грубое и содержит много практически идентичного кода. Если внимательно посмотреть на код, можно заметить, что вызов функции MAX эквивалентно вызову -MIN (справедливо и обратное утверждение).

Исходя из этого наблюдения, можно сократить код до одной функции:

// Оценивает состояние игрового поля после хода MIN.
// field состояние поля в результате хода игрока MIN.         
// player идентификатор игрока MAX.  
function MAXIMIN(field, player, deph) : int
    if isTerminal(field) then
        return heuristic(field, player)
    end
    score  = -INFINITY
    for child from children(field, player) do
        s = MAXIMIN(child, -player, deph+1)
        if s > score  then score  = s        
    end
    return score
end

Или:
// Оценивает состояние игрового поля после хода MAX.
// field состояние поля в результате хода игрока MAX.         
// player идентификатор игрока MIN.    
function MINIMAX(field, player, deph) : int
    if isTerminal(field) then
        return -heuristic(field, player)
    end
    score  = INFINITY
    for child from children(field, player) do
        s = MINIMAX(child, -player, deph+1)
        if s < score  then score  = s
    end
    return score
end 
При выборе одного из вариантов(MAXIMIN или MINIMAX) будьте внимательны, очень важно не напутать с аргументами при первом вызове этих функций. Если вершина раскрыта за игрока MAX (последний ход был игрока MAX), то следует вызывать функцию MINIMAX или -MAXIMIN.

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

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

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

 Альфа-бета отсечения. Общие идеи

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

Предположим, что мы раскрыли крайнюю левую вершину за кружки на глубине 3, получили оценку 7 и перешли к раскрытию следующей вершины на этой глубине. Обратите внимание, что следующая вершина последняя в этой ветке и после ее раскрытия мы перейдем на глубину выше, где выбор будут делать ромбики. Ромбики же, получив оценку первой вершины 7, очевидно, не станут делать выбор вершины с большей оценкой и вторая, раскрытая нами вершина с оценкой 9, выбрана не будет. И стоило ее раскрывать?

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

Вот как это работает: раскрытие корневой вершины начинается с эмпирически подобранными параметрами альфа и бета. В простейшем случае им присваиваются максимально и минимально допустимые оценки. Далее, дерево раскрывается на максимальную глубину, которая может определяться фиксированным значением глубины, временем или памятью. Производится эвристическая оценка полученных листов. Оценки сравниваются на предмет попадания в диапазон альфа-бета. Если раскрытие происходит за игрока MAX и оценка оказывается больше беты, или раскрытие происходит за игрока MIN и оценка оказывается меньше альфа, то дальнейшее рассмотрение вершин становится не целесообразным.
Пример бета отсечения

На приведенном выше рисунке представлен случай с бета отсечением. После раскрытия всех листьев в левой ветке и получив оценку 7 для первой вершины на глубине два, мы переходим к раскрытию второй вершины. Получая оценку для каждой дочерней ее вершины, сравниваем ее с полученной ранее оценкой 7. Если оценка вновь раскрытой вершины окажется больше, то нет смысла раскрывать остальные вершины, тк очевидно что выбор будет сделан в ползу вершины с оценкой 7. Аналогичные рассуждения применимы для параметра альфа.

Алгоритм

// Оценка максимального выигрыша игрока player в позиции position.
function MAX(position, alpha, beta, deph, player) : int
    if isTerminal(position) then
        return heuristic(position, player)
    end
    score  = alpha
    for child from children(position, player) do
        s = MIN(child, score, beta, deph+1, -player)
        if s > score  then score  = s 
        if score >= beta then return score
    end
    return score
end

// Оценка минимальных потерь игрока player в позиции position.
function MIN(position, alpha, beta, deph, player) : int
    if isTerminal(position) then
        return -heuristic(position, player)
    end
    score  = beta
        for child from children(position, player) do
             s = MAX(child, alpha, score, deph+1, -player)
        if s < score  then score  = s
        if score <= alpha then return score
    end
    return score
end 

или в одну функцию:

function AlphaBeta(position, alpha, beta, deph, player) : int
    if isTerminal(position) then
        return -heuristic(position)
    end
    score  = beta;
    for child from child(position, player) do
        s = -AlphaBeta(child, -score, -alpha, deph+1, -player)
        if s < score  then score  = s
        if score <= alpha then return score
    end;
    return score
end 

Подобное решение может показаться не очевидным. Для более подробного рассмотрения того, как к нему придти,  читайте перевод статьи Д.Е.Кнута и Р.У.Мура например здесь.


Интуитивный подход


Описанная в данной статье эвристика слишком проста, чтобы позволить достаточно сократить дерево игры и не потерять ощущения интеллектуальности компьютерного оппонента на заявленном в самом начале поле 10 на 10 клеток. Не станем останавливаться на достигнутом и попробуем зайти с другого края.

Отвлечемся от общепринятого подхода к решению игр с нулевой суммой и попытаемся проанализировать собственное мышление при игре в крестики нолики. Тут пора бы признаться, что мы редко смотрим на много шагов вперед, а просто стремимся действовать по следующим правилам: чем длиннее собирается комбинация в результате нашего хода, тем лучше, и чем большую комбинацию мы подпортим противнику, тем опять же нам лучше. Попытаемся обучить такой стратегии компьютер.

Введем функцию оценки каждого хода следующего вида:

,

где m - оцениваемый ход, G(m) - оценка пользы от хода для игрока, Q(m) - оценка степени вредительства противнику.

Мерой, для хода, может послужить длина собираемой комбинации k и длина нарушаемой комбинации противника k'  в каждом из возможных четырех направлений (по вертикали, по горизонтали и в двух диагоналях):

Пример потенциальных областей для сбора выигрышной комбинации длинной 4
Для наглядности рассмотрим пример на поле 7 на 7  игры за крестики до 4.



В этом примере значения k и k' будут следующими:
  • для горизонтальной линии k = 1, k' = 1; 
  • для вертикальной линии k = 4, k' = 0; 
  • для первой диагонали (\) k = 0, k' = 4; 
  • для второй диагонали (/) k = 2, k' = 0.

Основываясь на введенных обозначениях, можно описать оценочную функцию для каждого хода следующим образом:


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

Как выбрать функции G и Q

Меня два раза спрашивали: «Скажите на милось, мистер Бэббидж, что случится, если вы введете в машину неверные цифры? Cможем ли мы получить правильный ответ?»
Я не могу себе даже представить какая путаница в голове может привести к подобному вопросу.

— Charles Babbage

При выборе функций G и Q трудно найти универсальную формулу, но можно опереться на ключевые ситуации в игре, и сделать выбор исходя из собственных предпочтений в них.

Прежде всего, чтобы алгоритм не упускал возможность завершить игру в свою пользу, необходимо выполнение следующего условия:
    (1)
где W - длина выигрышной комбинации.

Так же, глупо отдавать предпочтение своему ходу, когда противник в шаге от победы:
Игра за крестики до 5

Отсюда следующее условие:
  (2)
Коэффициент 4 обусловлен тем, что возможна(хотя и крайне мало вероятна) ситуация, когда оцениваемый ход будет получать значения k близкие к k' сразу в четырех направлениях.

И еще один пример, который иллюстрирует ситуацию, когда может быть сделан нежелательный, на мой взгляд, выбор:


Я исхожу из того, что важнее собрать более длинную последовательность, чем без конца плодить развилки:
   (3)
Исходя из этих соображения, в качестве G и Q были выбраны следующие функции:

Выбранные функции удовлетворяют условиям (2) и (3) уже при значении k и k' равным 3, и на практике дают вполне приемлемые результаты.

Что еще можно сделать

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

Игнорировать ходы, которые в принципе не могут привести к победе

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

Объединить интуитивные рассуждения с минимаксной процедурой.

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

Упростить определение терминального состояния.

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

Идея заключается в том, что состояние игры изменяется в результате хода, который влияет не на все поле целиком, а только на окрестность ячейки, в которую был выполнен ход, в радиусе выигрышной длины. Достаточно проверять, не привел ли ход к завершению игры и в соответствии с этим менять состояние игрового поля.

Для ничьи, ничего умнее полного перебора предложить не могу. Были мысли по кешированию свободных клеток, но это скорее только навредит.

Сократить количество потенциальных ходов

Обычно, в качестве возможных ходов, выбираются пустые клетки поля. Но если поле имеет относительно большой размер, вариантов ходов может оказаться очень много. Есть подозрения, что достаточно рассматривать не все пустые клетки поля, а только пустые клетки в окрестности уже занятых:


Такой подход дает большой выигрыш на больших полях, практически нивелируя влияние размера поля на время действия алгоритма.

Добавить критерии оценки хода

Помимо длины, собираемой в результате хода последовательности, в роли критерия качества хода можно брать полное количество своих (или чужих) клеток в ряду:

Игра за крестики до 5.
Ход "б" приводит крестиков к победе

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

Реализация на Java

Здесь должен быть java-applet с пример моей реализации всего изложенного в статье. Если вы видите этот текст, вероятно у вас отключен Java-plugin. Что делать?
Чтобы не быть голословным, все выше описанное было реализовано мной на java и выложено в открытом репозитории на bitbucket. А так же, в виде архива с документацией, исходниками и самим приложением.
Приложение имеет несколько ключей запуска для регулирования размера поля, глубины раскрытия дерева и прочее. Подробнее, о ключах, вы можете почитать в справке, которая вызывается следующим образом:
java -jar tictactoe.jar -h

14 комментариев :

  1. Отлично все расписано, отличная реализация. Побаловался маленько с параметрами, очень понравилось, логика заметно меняется с увеличение глубины просчета шагов. Спасибо вам большое за хорошую работу!



    В игру поиграл, дошел до шахты и забросил, графика интересная, но я не любитель игр))

    ОтветитьУдалить
    Ответы
    1. Спасибо за отзыв. А за игру жаль. Я тоже не сказать чтобы геймер, но от подобных неординарных проектов в восторге =)

      Удалить
  2. Победил таки этот устаревший ява плагин :)

    ОтветитьУдалить
  3. Анонимный1 июня 2013 г., 9:08

    оболдеть как все сложно, буду пробовать спасибо!

    ОтветитьУдалить
  4. Не понравилось, я 3 из 4 раз обыграл компьютер

    ОтветитьУдалить
    Ответы
    1. Вы молодец! Попробуйте повысить глубину раскрытия дерева игры: java -jar tictactoe-3.3.5.jar -d 4

      Удалить
  5. Побеждаю каждый раз.

    > Так же, глупо отдавать предпочтение своему ходу, когда противник в шаге от победы.
    Это бесспорное определение ты распространяешь на все размеры цепочек и делаешь неправильный вывод:
    > Я исхожу из того, что важнее собрать более длинную последовательность, чем без конца плодить развилки

    В этом просчет твоего алгоритма.

    ОтветитьУдалить
    Ответы
    1. Скорее слабое место :) Но ты молодец! Углядел)

      Удалить
  6. Очень жаль, что нельзя попробовать размер поля <10...

    ОтветитьУдалить
    Ответы
    1. отчего же? можно (пример для поля 3х3):
      java -jar tictactoe-3.3.5.jar -w 3 -s 3

      Удалить
  7. Спасибо большое за статью !
    Все доступно и подробно изложено, мне очень помогла разобраться в такой непростой для меня теме.
    Хотел добавить, что в процессе анализа работы алгоритма с альфа-бета отсечением обнаружилось, что алгоритм показывает лучший результат ( сокращается количество раскрываемых вершин ), если на каждом уровне переменной score мы продолжаем присваивать значение -INFINITY, а не альфа или бета. Тестировал на поле 3х3 с глубиной 8 и для поля 10х10 с глубиной 3. Можете это прокомментировать , это у меня какая-то ошибка ? или это естественное поведение ?

    ОтветитьУдалить
    Ответы
    1. К сожалению сейчас я не могу ответить с полной уверенностью, тк для этого нужно снова погружаться в детали алгоритма. Но на сколько я помню его идею, альфа и бета значения - сужающие границы пространства поиска, они призваны сократить варианты раскрытия дерева. Странно что их игнорирование дает лучший вариант. Возможно Вам не повезло с контрольными примерами?

      Удалить
    2. Да. Мне тоже это показалось странным. Но количество "альфа-бета отсечений" увеличилось , а количество раскрываемых вершин стало меньше. Возможно это просто стечение определенных обстоятельств)

      Удалить

Ваше мнение мне искренне интересно. Смелее!

Технологии Blogger.