Этот пост является частью ChurrPurr.ai, задачи по разработке онлайн-стратегии и искусственного интеллекта для ее освоения. Играйте в последнюю версию игры здесь.
Теперь, когда я решил заняться проблемой создания ИИ для Churr-Purr, стратегической игры, которую я недавно изучил, у меня возник вопрос: насколько сложна эта задача, в которую я попадаю?
Одним из способов, которым компьютерные ученые пытаются количественно оценить сложность программирования ИИ для различных игр, является идея «сложности».
В общих чертах это спрашивает, сколько различных вариаций может иметь игра - потому что чем больше возможных вариаций, тем больше возможностей ИИ должен теоретически оценить, чтобы выбрать лучший образ действий. (Это не совсем так, в зависимости от целей вашего ИИ и методов оценки, но для наших целей этого достаточно.)
Например, в шахматах у первого игрока (белых) есть 20 возможных начальных ходов - чтобы переместить каждую свою пешку на одно или два поля, или переместить коня вперед-влево или вперед-вправо. У второго игрока (черных) также есть 20 возможных ходов, так что только для первого хода существует 400 различных вариантов.
Это много, но ведь компьютеры ведь довольно быстрые? К сожалению, проблема со временем усугубляется - и к концу 5-го полного хода появляется ~ 5 миллионов различных позиций. Не идеально.
Игра Го - недавний очаг исследований искусственного интеллекта, учитывая успех DeepMind в победе над чемпионами мира с помощью программы AlphaGo, - даже более сложна, чем шахматы. В профессиональном го используется сетка 19 x 19, по сравнению с сеткой шахмат 8 x 8, и игры между экспертами обычно длятся намного больше ходов в го, чем в шахматах.
Соответственно, в то время как для оценки полного дерева игр в шахматы требуется всего 10 ^ 123 различных ветвей, для Go требуются ветки порядка 10 ^ 360. Каждое из этих чисел значительно больше, чем предполагаемое количество атомов во Вселенной.
(Учитывая масштаб этих чисел, у вас было бы вполне разумно задаться вопросом, как компьютерные ученые понимают эти огромные деревья игр - и мы получим это в следующих статьях.)
Как Churr-Purr соотносится с этими цифрами? Давайте начнем с оценки только первого этапа игры, на котором игроки по очереди кладут жетон на незанятые поля доски, оставляя возможность убрать жетоны, что усложняет игру.
Первый игрок играет на одном из 24 открытых квадратов, а второй игрок размещается на одном из 23 оставшихся. Игроки продолжают игру по очереди, пока у них не закончатся жетоны, всего 18 ходов. Таким образом, при таком подходе сложность упрощенного этапа может быть рассчитана как 24 * 23 * 22 * 21… * 7, что примерно равно 10 ^ 21.
После учета удалений и второго этапа игры это число может стать немного хуже, но, по крайней мере, мы не пытаемся взломать новую версию шахмат с нуля. Серебряные накладки. (Примечание: я написал этот пост до того, как обнаружил, что Churr-Purr на самом деле может быть решенной игрой и как минимум похож на известную игру Nine Men's Morris - 10 ^ 50 согласно Википедии, но с дополнительной третью stage против Churr-Purr. Я возьму.)
Чтобы решить и / или уменьшить сложность Чурра-Пурра, в нашем распоряжении есть два коротких пути: это симметрия и решенные позиции.
В подходе, описанном выше, я отметил, что игрок 1 должен выбрать одно из 24 мест для своей первой игры. Это правда, но среди этих 24 мест на самом деле есть только 4 уникальных игры: игра в углу среднего кольца; игра в середине среднего кольца; игра в углу не среднего кольца; и игра в средней точке не-среднего кольца.
В свете 4 возможных первых ходов вы можете задаться вопросом, действительно ли у игрока 2 есть 23 уникальных ответа для игры - и ответ отрицательный. Для одного из первых 4 ходов, которые я наметил, я рассчитал ~ 14 уникальных ответов, поэтому давайте сделаем предположение, которое примерно одинаково для всех 4.
Если предположить отсутствие дальнейшей симметрии после хода 2 (вероятно, сомнительное предположение), наша математика тогда будет 4 * 14 * 22 * 21 * 20…. * 7, что составляет ~ 6 * 10 ^ 19. Одно только это изменение означает, что нам нужно будет вычислить примерно в 10 раз меньше ветвей, чтобы полностью оценить первый этап. Опять же, я возьму это.
Таким образом, другие игры также выигрывают от симметрии. Например, в «Крестики-нолики» на первый взгляд кажется, что у него 9 первых ходов, но есть только 3 уникальных: игра в середине; игра в углу; или играть на неугловом краю. У оппонента действительно нет 8 уникальных ответов и т. Д.
Тем не менее, хотя 10 ^ 19 меньше, чем 10 ^ 21, оно остается огромным числом - и, вероятно, это низкая оценка сложности Churr-Purr, учитывая сложности удаления частей и второго этапа, каждый из которых может добавить несколько порядков величины. филиалов.
Итак, если мы хотим провести исчерпывающую оценку этих ветвей, какие еще инструменты мы имеем в своем распоряжении? (В дополнение к эвристике / более сложным методам искусственного интеллекта, которые помогут нам обойти эту исчерпывающую оценку.)
Второй инструмент - это решаемые позиции. Под решенной позицией я подразумеваю такую, в которой игрок может добиться победы с помощью последовательности ходов, независимо от того, что делает его противник. Обратите внимание, что решенная игра может быть очень далека от завершения или очень близка к нему.
Например, если в позиции игрок 1 находится на расстоянии одного хода от выигрыша, и сейчас ход игрока 1, это решенная позиция. Это довольно интуитивно понятно.
Что немного менее интуитивно, так это то, что позиция может быть решена задолго до этого прямого выигрыша, если игрок 1 может форсировать прибытие в эту позицию. (Кстати, некоторые игры полностью решены, а это означает, что с самого начала игрок может добиться победы (или иногда используется как синоним, принудить к ничьей) с идеальной игрой [Churr-Purr может даже быть одной из них!] . Например, шашки технически решены, и лучшие компьютеры в мире будут играть до бесконечного количества ничьих. На практике, однако, люди совершают ошибки, поэтому иногда решенные игры или позиции все же могут заканчиваться результатами, противоречащими « решение'.)
Мы можем использовать решенные позиции, если определим, что определенные позиции влекут за собой победу, задолго до фактического завершения игры. Например, следующая позиция в начале этапа 2 «решена» для победы игрока 1:
В то время как исчерпывающая оценка продолжала бы проходить через шаги после этой точки, мы можем сократить наш поиск до тех пор, пока мы сможем распознать эти позиции; вывод предрешен, поэтому нет необходимости разбирать дальнейшие ветки.
Я подозреваю, что обнаружение элементов решенной позиции в Churr-Purr станет важным открытием, которое приведет мой ИИ к успеху. Как только ИИ получит хорошее представление о том, какие позиции являются выигрышными и проигрышными, он может начать планирование действий, которые лучше всего сходятся на этих выигранных позициях.
Это будет интересная подзадача, потому что, хотя у меня есть неплохая интуиция для решения определенных позиций (например, у P1 есть неизбежная тройка в ряд, чтобы начать второй этап, а у P2 нет тройки в ряду) ряды и отсутствие возможности блокировать 3-в-ряду P1), я также подозреваю, что в игре возникает много решенных позиций, но я еще не распознал их с моими ограниченными вычислительными и проницательными способностями.
Надеюсь, я смогу научить компьютер преуспевать в тех аспектах, в которых я иногда ошибаюсь, и затем эффективно направить свой путь к этим позициям. На данный момент я считаю, что это ближе к сути того, что я помогу оценить ИИ, но этот контент сам по себе является кормом для другого поста.
Прочтите предыдущий пост. Прочтите следующий пост.
