Алгоритмы компьютерного го применяются в других играх?

Совсем недавно программы Computer Go смогли конкурировать с людьми, используя деревья поиска Монте-Карло:

Программа Монте-Карло (MC) играет в случайные игры и легко оценивает конечную позицию (выигрыш или проигрыш). Программа MC ищет ходы с высоким коэффициентом выигрыша, рассчитанным на основе не менее нескольких сотен случайных игр.

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

Я чувствую, что с помощью этого метода можно было бы «решить» гораздо больше игр, включая, возможно, подавляющее большинство настольных игр…

Два вопроса:

  • Применялся ли уже метод Монте-Карло к другим играм? (Есть ли конкретные реализации?)

  • В каких играх, среди тех, которые имеют четко сформулированные правила и не полагаются на сложное общение между игроками, можно ожидать, что этот метод не сработает?

Ответы (3)

Применялся ли уже метод Монте-Карло к другим играм? (Есть ли конкретные реализации?

Да. Эта дипломная работа может быть вам интересна. Он охватывает нарды, бридж, го, скрэббл и клоббер.

В каких играх, среди тех, которые имеют четко сформулированные правила и не полагаются на сложное общение между игроками, можно ожидать, что этот метод не сработает?

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

  • MAVEN использует алгоритмы поиска B * в эндшпиле (больше не нужно рисовать плитку).
  • MoGo использует шаблоны 3x3, чтобы помочь идентифицировать «интересные» ходы, а Верхнюю достоверность, применяемую к деревьям (UCT), чтобы помочь исключить из рассмотрения менее оптимальные случайные ходы и ускорить поиск.

Хотя методы Монте-Карло являются полезным инструментом в настольных играх, они не являются идеальным решением. Компьютерные программы Go, использующие MCTS, по-прежнему не могут обыграть лучших игроков на досках 19x19 без значительных гандикапов. Программы Computer Bridge не подходят для опытных игроков. Методы Монте-Карло подходят только к идеальной игре с бесконечным временем/пространством.

+1 с дополнительным реквизитом для различных игр. Я впечатлен тем, что поиск по методу Монте-Карло хорошо сработал для TD-Gammon.
Честно говоря, я не знаю, достаточно ли хорошо определен метод Монте-Карло, чтобы можно было отличить алгоритм MCTS, алгоритм развертывания, нейронную сеть и т. д. Я думаю, что список игр мог бы быть даже намного длиннее, но ОП только хотел знать, существуют ли они.
Откуда вы взяли, что MoGo использует базы эндшпилей? В Go такого нет. Вы имеете в виду базы данных для открытия ходов (которые действительно были добавлены в некоторых других MC AI)?
google.com/… К сожалению, вы правы. MoGo использует шаблоны 3x3, чтобы делать более интересные ходы в целом, вместо случайного подхода MC, это не специально для эндшпилей. Моя общая точка зрения остается в силе: методы MC не годятся для эндгеймов.

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

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

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

В шахматах среднее количество возможных ходов в типичный момент игры составляет около 30 различных ходов. Типичная игра длится около 40 ходов. В го есть около 250 вариантов на ход, а игра длится около 150 ходов.

Это означает, что оценка возможных ходов в го намного, гораздо дальше в будущее, чем в шахматах.

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

Традиционный шахматный ИИ использует то, что называется функцией оценки, которая использует ярлыки (например, присваивает больше очков ферзям, чем пешкам), чтобы оценить доску и сказать, что состояние игры лучше или хуже для одного игрока, чем для другого. В Го очень сложно придумать функцию оценки, так как части одинаковы, а территория не высечена почти до конца игры. Вот почему традиционный подход шахматного ИИ к го потерпел неудачу, большие пространства решений и состояний невозможно сократить, поэтому поиск неэффективен.

Теперь давайте перевернем проблему и посмотрим, почему использование Монте-Карло в шахматах может быть плохой идеей. Поскольку случайная игра не различает «хорошие ходы» и «плохие ходы», подавляющее большинство случайных игр будет исследовать явно плохие игровые деревья. Например, пожертвовать своим ферзем без каких-либо преимуществ или сделать его уязвимым, чтобы противник не использовал его. Мало информации получается путем усреднения результатов отдельных неудачных ходов. Этот тип ИИ будет работать, но потребует гораздо больше вычислений, чем обычный оценочный подход.

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

Итак, почему Монте-Карло работает на го (т.е. может побеждать людей)? Это работает, потому что и люди, и компьютеры очень плохо играют в го (по сравнению с теоретической идеальной игрой). Выборка случайной игры Монте-Карло работает, потому что не требуется более высокого уровня понимания паттернов, чем может быть получено эффективным с точки зрения вычислений способом.

Итак, как сравнить другие настольные игры? Давайте зададим себе эти вопросы:

  1. Можно ли легко оценить ситуацию на доске?
  2. Сколько решений/ходов возможно каждый ход?
  3. Сколько решений нужно принять в типичной игре?
  4. Насколько предсказуемы результаты каждого хода?

Большинство настольных игр обладают характеристиками, которые делают их гораздо ближе к шахматам, чем го, по первым 3 вопросам. Это наводит на мысль, что ИИ в шахматном стиле будет проще, быстрее и эффективнее.

Поскольку № 4 отличается как для шахмат, так и для го, давайте посмотрим, как он влияет на два алгоритма.

Если бы у нас был фактор случайности, скажем, вытягивание карты из стопки из 60 карт, то каждое решение взять карту будет разветвлять игру на 60 возможных исходов. В зависимости от того, что рисуют другие игроки, их выбор будет меняться, что снова ставит нас в положение выборки, когда многие состояния крайне маловероятны или невозможны (аргумент против Монте-Карло). Между тем, можно легко написать функцию оценки, которая будет присваивать значения каждой карте (в сочетании с состоянием доски).

Я не видел, чтобы метод Монте-Карло применялся к другим ИИ для настольных игр, и выше приведены некоторые из причин, почему. Это также причины, по которым ожидается, что он потерпит неудачу. Когда он терпит неудачу, он может эффектно потерпеть неудачу в том, что он делает тупоумные, очевидные плохие ходы, потому что «случайные» результаты из выборок просто оказались иррациональными далеко за пределы будущих случайных выборов.

Если вы хотите узнать больше, я предлагаю эти сайты:

http://aaai.org/AITopics/

http://beej.us/blog/data/monte-carlo-method-game-ai/

http://www.aihorizon.com/essays/chessai/intro.htm

Я думаю, что исходный вопрос предполагает, что вы используете какую-то статическую функцию оценки для обрезки (неполного) дерева поиска, используемого методом Монте-Карло, точно так же, как вы делаете с более обычным поиском (согласно пункту об «интересных» ветвях ). Таким образом, основной вопрос для такой игры, как шахматы, звучит так: «Насколько ухудшается игра ИИ, когда вы берете образец Монте-Карло вместо того, чтобы исследовать все ветви детерминированным образом?»
Извините, я не согласен с большинством ваших утверждений, и ваша вторая ссылка (единственная, которая кажется относящейся к этому вопросу) не учитывает деревья поиска Монте-Карло (см. Последний абзац).
Кстати, это ваш вывод, что деревья поиска MC не подходят для шахмат и большинства настольных игр?
@StéphaneGimenez «Я не согласен с большинством того, что вы утверждаете», на мой взгляд, довольно бесполезно расплывчато.
@NealTibrewala Ваш пример рисования карт не имеет для меня смысла. Вы можете учитывать вероятностные события при поиске по дереву. (Хотя, насколько мне известно из моих немного устаревших студенческих знаний, самый успешный ИИ для игр, включающих элемент случайности, по-прежнему основан на машинном обучении .)
@ Алекс, я знаю, я хотел бы вскоре добавить явные комментарии и попытаться найти несколько ссылок для их резервного копирования, но это займет некоторое место.
Я сделал некоторые правки (в основном опечатки и форматирование). Ваше замечание об оценке доски приятно и имеет смысл, но я не вижу, как проблема изучения деревьев «тупоголовых очевидных плохих ходов» лучше решается в го, чем в шахматах. Пропорционально, я бы поставил на то, что в любой момент в игре го больше плохих ходов, чем в шахматах. Хотя, может быть, в шахматах последствия одного неудачного хода могут быть более непосредственными и необратимыми, чем в го.
Все, отличные комментарии. @shujaa, например, как только вы потеряете определенное количество штук, потеря почти неизбежна. Однако случайная игра этого не покажет, так как другая сторона, скорее всего, проиграет две «случайно». Этих определенностей достаточно, чтобы шахматы «решались» из-за почти достоверности некоторых оценок. " games.slashdot.org/story/12/04/02/2043240/… "
@StéphaneGimenez Извините, что вы не согласны. Я утверждаю, что MC Search необходим только в Go из-за сложности создания полезной функции оценки. В большинстве других настольных игр нет такой сложности, как в го, и в них легко написать оценочные функции. Следовательно, нет необходимости создавать ИИ на основе MC, и это было бы излишне долго и дорого (хотя их было бы легче «написать»).
...почему в этом ответе так много говорится о шахматах? Кто сказал что-нибудь о шахматах?
@Нил. С помощью MC вы можете улучшить любую хорошую или частично точную функцию оценки. В Go бывает, что вам вообще не нужна никакая функция оценки (достаточно просто финишировать случайным образом). Но ничто не мешает использовать оценочную функцию после некоторого углубления в дереве поиска МК (пример: ферзь + ладья против ничего - это выигрыш). Тогда алгоритм может сходиться быстрее, но ничто не гарантирует, что он сойдётся к идеальной игре.
@NealTibrewala Это имеет смысл, возможно, вы могли бы отредактировать свой ответ, чтобы проблемы с оценкой Go стали основным моментом. Как есть, вы не упоминаете об этом до 6-го абзаца.
@BlueRaja-DannyPflughoeft: Вопрос действительно заключается в следующем: (1) выполнялась ли MC с другими играми и (2) где это может привести к сбою. Так что в этом ответе можно рассмотреть шахматы.

Хорошо, я провел небольшое исследование. Цитирую эту бумагу :

За последние несколько лет в области компьютерных игр появилось несколько методов, основанных на методе Монте-Карло. Они уже успешно применялись во многих играх, включая POKER (Billings et al., 2002) и SCRABBLE (Sheppard, 2002). Поиск по дереву Монте-Карло (MCTS), метод, основанный на методе Монте-Карло, который был впервые применен в 2006 году, реализован в программах GO с самым высоким рейтингом. Эти программы впервые обыграли профессиональных игроков в ГО на доске 9 × 9. Однако эта техника не является специфической для ГО или классических настольных игр, ее можно легко обобщить на современные настольные или видеоигры. Кроме того, его реализация довольно проста. В предлагаемой демонстрации мы покажем, что MCTS можно эффективно применять к

  1. классические настольные игры (например, GO)
  2. современные настольные игры (например, SETTLERS OF CATAN) и
  3. видеоигры (например, игра SPRING RTS).

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

Я бы назвал 9 x 9 очень ограниченным успехом. Вы значительно снижаете фактор ветвления, связанный с каждым ходом, по сравнению с полной доской 19 x 19.
Я присутствовал в комнате на первой официальной победе 9x9 против профи от MoGo, и это было 3 или 4 года назад. Теперь они всего в 4-5 камнях от лучших профессионалов в формате 19х19 . В свою очередь, один профессионал однажды заявил, что находится примерно в трех камнях от идеальной игры (и с точки зрения игрока в го это правдоподобно).
Отчасти это сводится к определению «неудачи». ИИ MC Catan будет играть «хорошо» и может победить других ИИ, но они утверждают, что это всего лишь «сложный противник», подразумевая, что люди все еще могут победить. В общем, любой поиск MC требует, чтобы хорошие ходы и плохие ходы находились в довольно разумном соотношении. Иными словами, существует верхняя граница того, насколько хорошим может быть ИИ на основе MC, который может превзойти классический сокращающий ИИ (в невырожденных случаях).
@Neal: Конечно, люди все еще могут выиграть Катан. Даже если бы компьютер мог играть абсолютно идеально , люди, даже новички, могли бы обыграть его в приличном проценте случаев. Это связано с большим количеством случайностей, присущих Катану. То же самое касается покера, бриджа, криббиджа и т. д. Этого нельзя сказать об играх с полной информацией, таких как шахматы или го; компьютер, играющий идеально, всегда сможет гарантировать победу/ничью, играя за выгодную сторону.
Алгоритмы компьютерного го применяются в других играх?
СпросиСетьПолитика конфиденциальности1y, 0v