ДРУГОЙ ВЗГЛЯД НА АЛГОРИТМ ОТСЕЧЕНИЯ ИГРОВОГО ДЕРЕВА «ЛУЧШИЙ

ДРУГОЙ ВЗГЛЯД НА АЛГОРИТМ ОТСЕЧЕНИЯ ИГРОВОГО ДЕРЕВА «ЛУЧШИЙ –ПЕРВЫЙ»

Шмелев Григорий Сергеевич

Студент 2-го курса

институт прикладной математики и компьютерных наук

ФГБОУ ВО «Тульский государственный университет»

Россия, г. Тула

Аннотация. Алгоритмы альфа-бета-отсечения были популярны в поиске по дереву игр с момента их обнаружения. Многочисленные улучшения предложены в литературе, и часто неясно, какие из них будут наилучшими для реализации. С одной стороны, некоторые улучшения могут занять слишком много времени, чтобы точно настроить их гиперпараметры или решить, не изменятся ли они из-за ограничений памяти. С другой стороны «лучший – первый» методы отсечения, в основном аналоги печально известного алгоритма SSS*, алгоритма, который оказался инновационным к моменту своего открытия, но постепенно стал неиспользуемым, так как требовал слишком много памяти и времени на выполнение. Более поздние исследования не показывают, что «лучший – первый» подходы полностью отличаются от основанных на поиске в глубину улучшений, но оба подхода кажутся переходными в том смысле, что «лучший – первый» подход можно рассматривать как подход с поиском в глубину с определенным набором улучшений и с учетом растущей мощности компьютеров. При этом, похоже, SSS* теперь не сильно затрачивает память. Тем не менее, кажется, что довольно трудно понять природу алгоритма SSS*, почему он делает то, что он делает, и почему его называют слишком сложным, чтобы его можно было визуализировать и понять на интеллектуальном уровне. Эта статья пытается восполнить этот пробел и предоставить некоторые экспериментальные результаты, сравнивая вышеперечисленные два улучшения с наиболее многообещающими улучшениями.

Ключевые слова: альфа-бета-отсечение, SSS* алгоритм, деревья игр.

Введение

Существование, изобретение и повторное изобретение методов альфа-бета-отсечения можно отследить до 1956 года. В 20-м веке было множество вариаций и большое разнообразие улучшений, исследований и критериев, сформулированные для этих методов отсечения. Другой алгоритм SSS*, предложенный Стокманом в 1979 году [5], оказался инновационным. Имея совершенно иной подход к проблеме деревьев игр, будучи алгоритмом поиска в пространстве состояний вместо обхода дерева в глубину, имея экспериментальные результаты и теоретическое доказательство того, что SSS* никогда не исследует узел, который игнорирует альфа-бета, алгоритм, тем не менее, предъявлял высокие требования к памяти, что привело к его быстро растущей популярности и к скоротечному падению, когда алгоритм был объявлен мертвым на 8-й конференции Advance in Computer Chess в 1996 году [6].

Тем не менее, до настоящего времени алгоритм SSS* продолжает волновать население, являясь важной частью учебников и учебных программ, и даже несмотря на то, что многие называют его слишком сложным для понимания, неинтуитивным, сложным [2] и более медленным в отношении новых достижений в области методов альфа-бета-отсечения, трудно оставить незамеченным основы, на котором они стали основаны. В то время как каждый совершенствовал метод глубины, SSS* рассматривал проблему наилучшим образом, более того, он искал в пространстве решений «стратегии», которые эта статья исследует очень подробно, так как этот аспект игнорировался в предыдущей литературе. SSS* было названо трудным для понимания, поскольку он шокирующе отличалось от исследований, проводимых в то время в данной области, но было бы неправильно говорить, что он был неинтуитивным.

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

Алгоритм SSS*

Первоначальная разработка алгоритма альфа-бета заключалась в том, что он был слепым алгоритмом и искал дерево слева направо [1]. Было очевидно, что алгоритм может быть улучшен при условии, что лучшие узлы будут посещены первыми или будут находиться в левой части дерева. Были предприняты усилия для улучшения переупорядочения этого хода с использованием итеративных таблиц углубления и транспонирования в сочетании с различными другими улучшениями, такими как эвристика истории, минимальное окно, поиск стремления, переменная глубина поиска, эвристика убийцы и т. Д. [4]. SSS * использовал метод грубой силы, чтобы упорядочить эти ходы, позже мы увидим, что между глубиной первой альфа-беты и лучшей первой SSS * нет большой разницы. Существует плавный переход между двумя вариантами, достигнутыми за счет различных улучшений альфа-беты, из-за чего в конечном итоге SSS* может быть сформулирован как особый случай повторных вызовов с нулевым окном с алфавитными таблицами [3].

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

A. Стратегия

Мы начнем с определения понятия стратегии. Стратегию можно представить как набор ходов, которые игрок MAX думал сыграть за каждый возможный ход MIN после поиска K-PLY глубоко в дереве игры из текущей конфигурации / состояния. И именно так обычно начинают играть новые игроки в пошаговые стратегии (turn-based game). Они не знают об узнаваемых конфигурациях доски, которые стараются вспоминать более опытные игроки, которые могут привести к более быстрой / легкой победе или проигрышу; скорее они начинают с размышлений о возможных сценариях, которые могут возникнуть при каждом ходе MIN, и имеют ответную реакцию на каждый из ходов, как делают бы агенты, не обладающие специфическими знаниями в предметной области. Каким бы ни был ход MIN, у MAX есть готовый ответ. Такое поддерево называется стратегией.

SSS* ищет в пространстве состояний стратегий.

B. Значение для стратегии

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

Рассмотрим поддерево на рисунке 1 с заданными значениями eval. Узлы MAX представлены квадратами, а узлы MIN представлены кружками. Дерево достаточно симметрично для понимания целей и имеет постоянный коэффициент ветвления 2. Мы ищем глубину 4-PLY и применяем функцию eval() на листьях. Серые узлы — это те, которые не исследованы ванильным альфа-бета-отсечением. Оценочные значения таковы, что лучшие узлы распределены больше по направлению к правой стороне дерева.

Рисунок 1 – пример игрового дерева.

C. Скопления

Конечный узел может быть частью более чем одной стратегии. В этом конкретном примере каждый лист принадлежит 2 стратегиям, которые можно визуализировать путем формирования поддеревьев стратегий с учетом всех вариантов выбора для MIN и одного варианта для MAX. SSS* является исчерпывающим в том смысле, что никогда не пропускает лучшую стратегию. Это больше похоже на грубую силу, но это не то, как на самом деле работает SSS*.

Соотношение между значением листового узла L и значением стратегии S можно определить так, что любое значение L будет верхней границей значения стратегии S. Таким образом, мы можем сказать, что листовой узел представляет собой частичную стратегию, которая не решена полностью. Листовые узлы представляют более чем одну стратегию, к которой мы будем обращаться по кластеру стратегий. Каким бы ни было значение конечного узла L, оно будет верхней границей для всех стратегий, принадлежащих этому кластеру.

Мы поддерживаем приоритетную очередь кластеров, и кластеры представлены не явно, а, существенным образом, их репрезентативным конечным узлом. Каждый элемент в очереди представлен кортежем, состоящим из имени узла, понятия о том, является ли он ЖИВЫМ (live) или РЕШЕННЫМ (solved), и верхней границы значения eval: <name, live/solved, bound>. Самое высокое значение всегда будет в начале очереди, поэтому приоритетная очередь — это максимальная очередь с учетом значения eval, распространяемого вверх, как решение поддерева ниже этого узла.

Чтобы охватить все стратегии, то есть получить подмножество листьев, охватывающих все стратегии, составляем первую часть алгоритма SSS*, рассматриваемого как его прямая фаза. Мы можем видеть, что это может быть достигнуто интуитивно, покрывая все ветви для выбора MAX и выбирая любой из вариантов для MIN. После это приведет к выбору листовых узлов, которые охватывают все стратегии. Стратегия была получена путем выбора одного варианта для MAX с учетом всех вариантов выбора для MIN. Кластеры, которые охватывают все стратегии, могут быть получены «наоборот», то есть путем выбора всех вариантов для MAX, но одного варианта для MIN.

Теперь, когда мы убедились, что не упускаем ни одной стратегии, алгоритм более высокого уровня для SSS* можно определить как:

1) Найти лучшую частичную стратегию

2) Уточнять, пока не будет найдено лучшее решение, так как это «лучший -первый» алгоритм.

SSS* поддерживает приоритетную очередь репрезентативных узлов. Каждый элемент в очереди является либо живым, либо решенным. Поэтому, когда мы изначально начинаем, то делаем это с корневого узла и помечаем его как LIVE. Кажется, что проблема сравнима с проблемой знаменитого алгоритма AO* в том смысле, что мы рассматриваем только один выбор для MIN, который можно сравнить с узлом OR, а узел AND можно сравнить с MAX. В алгоритме AO* есть узлы, которые решены или не решены. В этом случае мы явно указываем их как LIVE. Алгоритм SSS* продолжает работать до тех пор, пока не будет решен корневой узел, что является еще одним сходством с алгоритмом AO*. Оба являются алгоритмами «лучший – первый».

Мы начинаем с корневого узла, помечаем его как LIVE, ставим границу +large и вставляем этот кортеж в очередь с приоритетами.

Подобно алгоритму AO*, SSS* также имеет две отдельные фазы: прямую и фазу резервного копирования. При прямой фазе мы в основном ищем кластеры, охватывающие все стратегии. На рисунке 2, 4 узла, выделенные розовым цветом, представляют 4 кластера. Каждый кластер представляет 2 стратегии. На рисунке показано, как мы рассмотрели все варианты выбора для MAX и произвольно оставили большинство в этом случае, единственный выбор для MIN. Эти 4 конечных узла представляют 2 стратегии каждый. После того, как конечные узлы были достигнуты и решены, SSS* переходит к этапу резервного копирования. Эти 4 терминальных узла будут отсортированы в очереди приоритетов в соответствии с их оценочным значением.

Рисунок 2 – пример игрового дерева с указанием узлов, которые охватывают все стратегии.

Не предоставляя псевдокод для алгоритма SSS*, который находится в свободном доступе, мы поговорим о различных случаях/условиях и действиях, выполняемых при прямой фазе и при фазе резервного копирования, которые помогают лучше понять алгоритм и, как правило, почему SSS* делает то, что он делает.

Прямая фаза:

· MAX, live, не конечный –> добавить всех детей в очередь

· MIN, live, не конечный –> добавить одного ребенка

Фаза резервного копирования:

· Конечный –> пометить как решенное и поместите значение узла в качестве значений eval

· MAX, solved –> заменить братом младшего значения ИЛИ заменить родителем и отметить его как решенное

· MIN, solved –> заменить на родительский и пометить как решенный

В примере на рисунке 2 узел MAX со значением 70 будет находиться в начале очереди, а его брат будет проверен. В данном случае у него нет родного брата с более низким значением eval, следовательно мы заменяем его родительским элементом и помечаем его как SOLVED. Это связано с тем, что MIN будет определять результаты стратегии и всегда будет стремиться минимизировать ценность игрового дерева.

Как только мы переходим к его родительскому узлу, который является узлом MIN, нет никакой причины проверять его братьев или братьев любого узла MIN, так как более ранний узел MAX, который мы выбрали на (текущая глубина + 1) был из начала очереди. Это означает, что другая стратегия от брата текущего узла MIN имеет верхнюю границу значения, которое существенно ниже 70, и, следовательно, MAX никогда не выберет этот узел. Таким образом, мы можем пометить узел MIN как решенный и перейти к его родителю. Это несколько похоже на отсечение альфы. В этот момент дерево выглядит как на рисунке 3. Узлы, посещенные алгоритмом SSS*, выделены розовым цветом, и на данный момент верхняя граница узла MAX на глубине 2 равна 70. Алгоритм теперь решает для своего брата с верхней границей 70. Метки на рисунке вне узлов представляют соответствующие верхние границы.

Рисунок 3 – Пример игрового дерева, показывающий первую отсечение для одноуровневого узла MIN.

Обратите внимание, что это снова запускает прямую фазу SSS* на некоторое время, пока конечные узлы не будут снова достигнуты. Поскольку верхняя граница остается равной 70, дальнейшие узлы в поддереве, которые должны быть исследованы в рамках этого одноуровневого элемента, определяются либо для минимума/максимума значения узла, либо для границы, в зависимости от того, что ниже. Следующие 2 важных шага для выполнения алгоритма SSS* показаны на рисунках 4 и 5.

Рисунок 4 – Пример игрового дерева, показывающего заметный шаг при выполнении алгоритма SSS*.

Рисунок 5 – Пример игры, показывающей дерево решенных решений и узлы, исследуемые алгоритмом SSS*.

Следует отметить, что алгоритм SSS* в целом сфокусирован на правой стороне дерева, где больше шансов получить решение, и этот пример подтверждает утверждение Стокмана [5] о том, что SSS* никогда не исследует узел, который альфа-бета может игнорировать, и в конечном итоге посещает меньше узлов, чем наша ванильная альфа-бета.

Сопутствующие работы

Различные комбинации достижений в альфа-бета-отсечении уже были опробованы в прошлом [4]. Было обнаружено, что комбинация таблиц транспонирования и эвристики истории с итеративным углублением составляет почти 99% сокращения размера игрового дерева [4]. С помощью таблиц транспонирования можно генерировать деревья, которые меньше минимального дерева. Хотя определение минимального дерева является нечетким и для неравномерных факторов ветвления оно принимается как лучший случай альфа-бета. Некоторые результаты, полученные Шеффером, показывают, что по мере увеличения вычислительной мощности и удешевления компьютерной памяти, к 1995 году алгоритм SSS* был на самом деле не столь неэффективен и его можно было реализовать для таких программ, как Phoenix, на современных машинах того времени [2]. Однако неясно, было ли это принято во внимание после того, как алгоритм был объявлен мертвым.

Эксперимент

A. Экспериментальная установка

Мы реализуем классическую игру «Отелло-реверси» и сравниваем лучшую комбинацию улучшений, примененных к альфа-бета (доказано экспериментально) [4], с SSS* с итеративным углублением, динамическим упорядочением перемещений и таблицами транспонирования, применяемыми к обоим. Мы сопоставляем их с точки зрения количества общих узлов, исследованных на конечном уровне. Хотя были противоречивые точки зрения, касательно того, отражает ли число исследованных конечных узлов фактический характер сложности и время выполнения алгоритма, общее мнение остается таковым, что оба они довольно тесно связаны друг с другом [4]. Нет сомнений в том, что он не зависит от системы, в которой работает алгоритм, и в некоторой степени связан с размером игрового дерева, которое необходимо изучить, и с фактическим временем, затраченным на алгоритм для расчета значения текущего состояния. В среднем мы насчитываем более 50 популярных позиций, выбранных по личным предпочтениям, и которые казались довольно распространенными, поскольку исторические контрольные позиции считаются устаревшими, поскольку в последние годы не было создано новых контрольных показателей для реверси [2].

B. Результаты

На рисунке 6 показано количество листовых узлов, исследуемых алгоритмом SSS* по сравнению с альфа-бета (оба с соответствующими усовершенствованиями, как описано выше). Поскольку некоторые литературные источники уже не согласны с более ранней точкой зрения о том, что O (wd / 2) является слишком большим требованием к памяти для практических целей [2], мы видим, что SSS* работает довольно близко к альфа-бета и на самом деле не так уж много разницы между количеством листовых узлов исследуют эти два. Чередующийся характер для глубин в случае количества исследованных листовых узлов также неоднократно указывался в прошлом, что можно довольно кратко описать тем фактом, что дополнительные затраты на выращивание дерева с дополнительной PLY до нечетной глубины составляют больше, чем для четной глубины [4].

ВЫВОДЫ

Эта статья была попыткой преодолеть разрыв между несколькими алгоритмами исследования дерева игр и попыткой объяснить логистику алгоритма SSS*. Точка зрения алгоритма SSS* во время его разработки была наиболее нетрадиционной, и в этой статье предпринята попытка объяснить недостающие сюжеты, которые делают его стоящим в арсенале любого программиста. Помимо этого, были предприняты попытки разрешить путаницу, стоящую за SSS*, и не оставить ее незамеченным остроумие, которое было задействовано в разработке такой идеи на тот момент. Поскольку теперь мы знаем, что эти два алгоритма очень похожи по своей природе и что можно предложить другой, начиная с одного и изменяя гиперпараметры используемых улучшений, в литературе было показано, что нативный SSS* эквивалентен альфа-бета при использовании таблиц транспонирования с повторным поиском нулевого окна [3]. Мы окончательно устанавливаем тот факт, что оба могут использоваться взаимозаменяемо в зависимости от варианта использования, и бесполезно тратить время на выбор между двумя, так как оба выдают сравнимые результаты, когда используются, заботясь о различных улучшениях, которые были сделаны с момента их открытия

Рисунок 6 – Количество листовых узлов (улучшенных) как альфа-беты, так и SSS*.

Список использованной литературы:

1. Alpha-beta [Электронный ресурс] // chessprogramming wiki – Режим доступа: https://www.chessprogramming.org/Alpha-Beta (дата обращения: 15.11.2019).

2. Plaat, A. A Minimax Algorithm Better Than Alpha-beta?: No and Yes / A. Plaat, J. Schaeffer, W. Pijls, A. de Bruin – Alberta, 2017 – 45 c.

3. Plaat, A. SSS* = Alpha-Beta + TT / A. Plaat, J. Schaeffer, W. Pijls, A. de Bruin – Alberta, 2014 – 36 c.

4. Schaeffer, J. The history heuristic and alpha-beta search enhancements in practice / J. Schaeffer // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 1989. – №11. – С. 1203–1212.

5. Stockman, G. A minimax algorithm better than alpha-beta? / G. Stockman // Artificial Intelligence. – 1979. – №2. – С. 179–196.

6. SSS* and Dual* [Электронный ресурс] // chessprogramming wiki – Режим доступа: https://www.chessprogramming.org/SSS*_and_Dual* (дата обращения: 15.11.2019).

Сведения об авторе:

Шмелев Григорий Сергеевич – студент 2-го курса института прикладной математики и компьютерных наук ФГБОУ ВО «Тульский государственный университет».

ANOTHER LOOK AT THE BEST - FIRST GAME TREE PRUNNING ALGORITHM

Shmelev G. S.

Abstract. The alpha-beta pruning algorithms have been mainstream in game tree searching as far back as they were found. Various enhancements are suggested in writing and it is regularly overpowering regarding which would be the best for usage. A specific improvement can take very long to fine tune its hyperparameters or to choose whether it will not make a big deal about a distinction because of the memory confinements. Then again are the best first pruning techniques, for the most part the partners of the notorious SSS* algorithm, the algorithm which demonstrated out to be problematic at the hour of its disclosure however bit by bit became outsider as being excessively memory serious and making some higher memories intricacy. Later research doesn't see the best first approaches to deal with be totally not quite the same as the depth ﬁrst based enhancements however both appear to be transitionary as in a best first approach could be looked as a depth ﬁrst approach with a specific arrangement of improvements and with the developing intensity of the PCs, SSS* didn't appear to be as burdening on the memory either. All things being equal, there is by all accounts very difficulty in understanding the idea of the SSS* calculation, why it does what it does and it being named as being too perplexing to even consider fathoming, picture and comprehend on a scholarly level. This article attempts to connect this hole and give some test results contrasting the two and the most encouraging advances.

Keywords: alpha-beta pruning, SSS * algorithm, game trees.

References:

1. Alpha-beta [Electronic resourse] // chessprogramming wiki – Access mode: https://www.chessprogramming.org/Alpha-Beta (access date: 15.11.2019).

2. Plaat, A. A Minimax Algorithm Better Than Alpha-beta?: No and Yes / A. Plaat, J. Schaeffer, W. Pijls, A. de Bruin. – Alberta, 2017. – 45 p.

3. Plaat, A. SSS* = Alpha-Beta + TT / A. Plaat, J. Schaeffer, W. Pijls, A. de Bruin. – Alberta, 2014.– 36 p.

5. Stockman, G. A minimax algorithm better than alpha-beta? / G. Stockman // Artificial Intelligence. – 1979. – №2. – P. 179–196.

6. SSS* and Dual* [Electronic resourse] // chessprogramming wiki – Access mode: https://www.chessprogramming.org/SSS*_and_Dual* (access date: 15.11.2019).