 | Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) ( Узнайте, как и когда удалить этот шаблон сообщения )
|
Maven является искусственный интеллект Эрудит игрок, созданный Brian Sheppard. Он использовался в официальных лицензионных играх Hasbro Scrabble.
Алгоритмы [ править ]
Фазы игры [ править ]
Игра Maven подразделяется на три фазы: фаза «середины игры», фаза «перед эндшпилем» и фаза «финал».
Фаза «середины игры» длится с начала игры до тех пор, пока в сумке не останется девять или меньше плиток. Программа использует быстрый алгоритм для поиска всех возможных розыгрышей на заданной стойке, а затем часть программы, называемая «кибитцер», использует простые эвристики, чтобы отсортировать их в приблизительном порядке качества. Затем наиболее многообещающие ходы оцениваются с помощью «моделирования», при котором программа имитирует случайный розыгрыш плиток, воспроизводит заданное количество ходов и сравнивает разброс очков в результатах ходов. Моделируя тысячи случайных розыгрышей, программа может дать очень точную количественную оценку различных пьес. (При поиске по методу Монте-Карло Maven не использует поиск по дереву Монте-Карло.потому что он оценивает деревья игры только в два уровня, а не до конца игры, и не перераспределяет развертывания на более перспективные ветви для более глубокого изучения; в терминологии обучения с подкреплением стратегию поиска Maven можно рассматривать как «усеченную симуляцию Монте-Карло». Настоящая стратегия MCTS не нужна, потому что эндшпиль может быть решен. Поверхностный поиск объясняется тем, что автор Maven утверждает [1], что из-за быстрой смены букв в сумке, как правило, нецелесообразно смотреть глубже, чем в 2 слоя, потому что если вместо этого смотреть глубже, например, 4-слойный , дисперсиявознаграждений будет больше, а моделирование займёт в несколько раз больше времени, помогая лишь в нескольких экзотических ситуациях: «Мы утверждаем, что если требуется экстремальная ситуация, такая как CACIQUE, чтобы увидеть ценность четырехслойной симуляции, тогда они не стоят делает." Поскольку стоимость доски в Scrabble может быть оценена с очень высокой точностью, в отличие от таких игр, как Go , более глубокое моделирование вряд ли изменит первоначальную оценку.)
Фаза «перед эндшпилем» работает почти так же, как фаза «середины игры», за исключением того, что она предназначена для того, чтобы попытаться создать хорошую ситуацию в конце игры.
Фаза «эндшпиля» вступает в силу, как только в мешке не остается тайлов. В играх для двух игроков это означает, что игроки теперь могут определить по начальному распределению букв точные тайлы на стойках друг друга. Maven использует алгоритм поиска B-звезд для анализа дерева игр на этапе финала.
Переместить поколение [ править ]
Maven использовал несколько алгоритмов для генерации ходов , но застрял алгоритм DAWG . GADDAG алгоритм быстрее, но DAWG для североамериканского английского языка всего 0,5 МБ, по сравнению с примерно 2,5 МБ для GADDAG. Это имеет большое значение для загружаемых игр, тогда как преимущество в скорости не имеет значения. (Обратите внимание, что «неважно» не означает, что разница небольшая, просто пользователи не могут заметить разницу. GADDAG, возможно, в два раза быстрее, но оба алгоритма достаточно быстры.)
Оценка стойки [ править ]
Первая (1986 г.) версия Maven использовала набор из около 100 шаблонов для оценки стоек. Каждая плитка имела значение (27 шаблонов). Каждый дубликат имел значение (22 шаблона). Были образцы для трех экземпляров и четырехугольников для букв, которые имеют достаточное представление в сумке. Наконец, комбинация QU была шаблоном.
Вскоре после выхода первой версии Maven приобрела термины оценки стойки для баланса гласных / согласных и распределения Q / U. Баланс гласных / согласных - это поиск по таблице, основанный на подсчете гласных и согласных, оставшихся в стойке. Распределение Q / U варьировало значения Q и U с помощью поиска в таблице, индексированного по тому, сколько из них осталось в сумке.
Вскоре после этого Maven приобрела оценщик дублирования тайлов. Идея заключалась в том, чтобы изменить стойку в зависимости от возможности рисования дубликатов. Например, A обычно лучше, чем I в качестве плитки, но если в сумке осталось 7 A и только 2 I, то, возможно, нам стоит оставить I.
Подбор параметров был выполнен путем настройки значений для прогнозирования общей суммы будущих баллов. В настоящее время это называется обучением временной разнице .
Эта оценочная конструкция стойки была оригинальной для Maven. Он был очень успешным в соревновании с человеческими чемпионами того времени.
Позднее конструкция была расширена другими исследователями. Марк Уоткинс отстаивал то, что он называл «паттернами синергии плитки». Это такие комбинации, как ADES, которые составляют основу многих высоко оцененных слов. Это естественное продолжение дизайна, которое значительно улучшает игру. Набор паттернов Maven постепенно расширялся от базового набора, равного 100, до более чем 400.
С тех пор Maven перешел на совершенно другую архитектуру, предложенную Джоном О'Лафлином и реализованную в Quackle . Это «исчерпывающая» архитектура, в которой программа имеет разные параметры оценки стойки для каждой из 3 миллионов возможных комбинаций от 0 до 7 ячеек. С развитием компьютерных мощностей за последнее десятилетие стало возможным настраивать такие большие наборы параметров.
Обратной стороной исчерпывающего подхода является то, что Maven потеряла возможность варьировать оценки в зависимости от плиток, оставшихся в сумке. Дело в том, что у исчерпывающего оценщика стоек нет терминов, которые связывают стоимость стойки с возможными доходами из сумки.
Версия Maven для исчерпывающей оценки стоек добавила эту возможность. В Maven каждая стойка имеет свой собственный оценщик лайнера, где значение этой стойки варьируется в зависимости от вероятности рисования дубликата, вероятности рисования гласной и вероятности рисования Q и U. Эта система имеет 5 параметров. на стойку, всего около 15 миллионов параметров.
Моделирование [ править ]
Великий чемпион среди людей Рон Тикерт изучал Scrabble, десятки раз разыгрывая отдельные позиции и сводя результаты в таблицу. Он предположил, что со скоростью Maven можно будет автоматизировать этот процесс в ночное время. Брайан Шеппард назвал этот процесс «симуляцией», хотя в нардах он называется «развертывание», а в Go - «воспроизведение».
Процесс заключался в выборе N ходов-кандидатов с использованием эвристики «оценка + стойка». Затем разыграйте эти ходы сотни или тысячи раз, чтобы увидеть, какой из кандидатов работает лучше всего. Вы можете изменять глубину воспроизведения в соответствии с вашими целями; играйте на два или четыре хода вперед, чтобы получить хорошее представление о разнице очков, или играйте до конца игры, чтобы измерить шансы на победу.
К середине 1990-х компьютеры стали достаточно быстрыми, и Maven использовала моделирование для выбора ходов в соревновательных играх с контролем времени турнира. Для этой цели при масштабировании моделирования были важны алгоритмические улучшения. Самым важным нововведением было изменение количества испытаний, предоставляемых кандидатам, чтобы более успешные кандидаты получали больше усилий. Также было полезно контролировать стойки, чтобы все ходы кандидатов сравнивались с одним и тем же беспристрастным распределением.
Анализ игр, в которые играет движок моделирования Maven, показывает, что Maven превзошла уровень навыков человеческих чемпионов.
Финал [ править ]
Сильная игра в эндшпиле Scrabble намного сложнее, чем кажется. Теоретически эндшпиль - это игра с идеальной информацией, поэтому алгоритм отсечения альфа-бета должен работать. Но на практике Alpha Beta плохо работает на Scrabble.
Проблема с альфа-бета-версией заключается в том, что в некоторых эндшпилях Scrabble требуется 14 ходов для игры, и невозможно так глубоко исследовать. Это не просто теоретическая возможность. Когда один игрок «застрял» с плиткой, то разыграть все оставшиеся плитки невозможно. В этой ситуации оптимальная стратегия для обеих сторон обычно состоит в том, чтобы играть по одной плитке за каждый ход.
Maven использует другой подход. В * Алгоритм поиска представляет собой селективный глубины, прогрессивный увеличивающийся алгоритм , который гарантирует , чтобы найти оптимальные решения для двух игроков игр , когда можно вычислить верхние и нижние границы значений каждой позиции.
Оказывается, можно оценить верхнюю и нижнюю границы эндшпильных позиций. Эти границы верны (то есть истинное значение лежит в пределах интервала) для подавляющего большинства позиций. Поскольку B * является достаточно устойчивым при наличии небольшого процента ошибок в границах, Maven может решить эндшпиль, который другие подходы не могут.
Дальнейшее уточнение делает финальные решения Maven асимптотически оптимальными даже при наличии ошибок. Когда поиск B * завершается доказательством того, что один ход является лучшим, а время еще остается, Maven расширяет свои оценки на 1 пункт и выполняет поиск снова. Эти повторные поиски обычно очень быстрые, потому что дерево из предыдущего поиска все еще в значительной степени актуально. Повторное использование этой политики будет постепенно выявлять ошибки, начиная с самых мелких (и предположительно наиболее вероятных) ошибок.
Исчерпывающий пред-эндшпиль [ править ]
Когда в сумке остаются только 1 или 2 плитки («PEG-1» или «PEG-2»), можно выполнить исчерпывающий поиск в пространстве состояний.
Случай с PEG-1 важен, потому что почти половина всех игр проходит через это состояние. Maven может полностью воспроизвести такие состояния практически во всех случаях. То есть для всех разрешенных ходов Maven может разыграть итоговые эндшпили (до 8 на каждый разрешенный ход) и вычислить, какая сторона выиграет игру в каждом случае. Поскольку есть некоторые ситуации (например, два пробела, застревание с Q), требующие дополнительных усилий, расчет выполняется постепенно. То есть Maven сначала расширяет свой анализ там, где решение является близким и актуальным.
В PEG-2 обычно невозможно исчерпывающе изучить все последовательности ходов, поэтому Maven делает все возможное за отведенное время.
Одной из особенностей таких ситуаций с малым количеством тайлов является то, что очень сложно безопасно сократить список допустимых ходов. Например, оптимальная игра отстает от более чем 50 других ходов по эвристике «счет + стойка» более чем в 1% случаев.
Эта политика не дает теоретически идеальной игры, потому что невозможно знать, каким должно быть истинное начальное распределение невидимых плиток. Предполагая, что равномерное распределение работает хорошо, и можно вычислить выводы о невидимых плитках, которые незначительно улучшают это предположение.
Еще одно ограничение заключается в том, что Maven не обращается к аспекту «скрытой информации» в таких ситуациях. То есть теоретически существуют ситуации, когда игроки максимизируют ожидание, случайным образом выбирая ходы в соответствии с распределением вероятностей. Maven выбирает чистые стратегии на каждом узле.
Ссылки [ править ]
- ^ pg14, Шеппард 2002
- Шеппард, Брайан (2002). "Эрудит мирового уровня" (PDF) . Искусственный интеллект . 134 (1–2): 241–275. DOI : 10.1016 / S0004-3702 (01) 00166-7 .
Внешние ссылки [ править ]
- Hasbro
- Функитрон
