Реализация сюрреалистических чисел для игр

11

У Конвея очень приятная конструкция из сюрреалистических чисел. Это «числа», которые содержат как действительные числа, так и порядковые числа, полностью упорядочены и имеют все свойства поля (за исключением того, что они образуют не множество, а класс).

Смотрите, например, этот PDF или Википедию для ознакомления.

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

У меня вопрос: знаете ли вы, кто-нибудь реализовал этот подход в ИИ (то есть в компьютерном плеере), чтобы улучшить свой уровень в игре? Я особенно заинтересован в случае с Go, но и с другими. Если нет, есть ли препятствие или причина, почему это не будет хорошей идеей?

reference-request gt.game-theory implementation board-games combinatorial-game-theory Денис
источник
1
Согласно книге «Математическое движение», кажется, что Рэймонд Чен использовал компаньон-программу для решения проблем с эндшпилем в книге, но я не знаю, где ее можно найти. У меня также есть смутное воспоминание о том, что Берлекамп ссылается на «Go explorer», о котором можно упомянуть в статье «Интеллектуальная игровая доска и Go explorer: исследование в области разработки программного обеспечения и знаний». Однако я не думаю, что теория комбинаторных игр в настоящее время действительно используется в лучших игровых программах Go.
Марк С.
3
Если я правильно помню (может быть, не так, как это было давным-давно), по словам Дэвида Вулфа (соавтора «Математического го»), можно придумать позиции для финальной игры «Го», где лучшие профессиональные игроки склонны играть неоптимально как точка зрения, в то время как подход теории игр Конвея / Берлекампа / Вольфа позволяет сравнительно легко вычислить оптимальное значение. Однако такие позиции надуманы. Это явление редко встречается в играх, возникающих в реальной игре.
Нил Янг

Ответы:

8

У меня нет ответа на ваш вопрос о том, использовалась ли теория игр Конвея для создания игровых программ, но, тем не менее, вас может заинтересовать « Combinatorial Game Suite» , «программа с открытым исходным кодом, помогающая исследованию комбинаторных игр ». теория игр »(о которой я впервые узнал здесь ). Он включает в себя реализацию различных стандартных операций над играми Conway в канонической форме, а также язык сценариев для описания новых игр.

Ноам Цайлбергер
источник
3

в некоторых поисках, похоже, не так много опубликованных общих реализаций сюрреалистических чисел. вот реализация сюрреалистических чисел в coq .

  • Сюрреалистические цифры в coq / Mamane, TYPES'04 Материалы международной конференции 2004 года по типам доказательств и программ

    Сюрреалистические числа образуют полностью упорядоченное (коммутативное) поле, содержащее копии действительных и (всех) порядковых чисел. Я закодировал большую часть структуры Кольца сюрреалистических чисел в Coq. Эта кодировка основана на кодировке Aczel теории множеств в теории типов.

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

есть некоторые частичные реализации сюрреалистической арифметики для игры под названием hackenbush (Davis), популяризированной Конвеем, Берлекампом и Гаем, на которые есть несколько ссылок.

Го действительно является одной из передовых областей исследования игрового ИИ (считается гораздо сложнее, чем шахматы, которые занимали ИИ на протяжении десятилетий), но, похоже, мало исследований, посвященных конкретно использованию сюрреалистических чисел для его моделирования / игры. Go считается границей для алгоритмов машинного обучения / ИИ, потому что он также имеет относительно уникальный статус / различие в том, что лучшие программные алгоритмы («все еще / в настоящее время») не превосходят чемпионов-игроков.

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

ВЗН
источник