Алгоритм богов - Википедия - Gods algorithm

Алгоритм Бога это понятие возникло в результате обсуждения способов решения Кубик Рубика головоломка,[1] но это также может быть применено к другим комбинаторный загадки и математические игры.[2] Это относится к любому алгоритму, который производит решение с наименьшим возможным количеством ходов, идея состоит в том, что только всеведущий будет знать оптимальный шаг из любой данной конфигурации.

Объем

Определение

Это понятие применяется к загадки что может предполагать конечный количество «конфигураций» с относительно небольшим, четко определенным арсеналом «ходов», которые могут быть применимы к конфигурациям и затем привести к новой конфигурации. Решение головоломки означает достижение обозначенной «окончательной конфигурации», единственной конфигурации или одной из набора конфигураций. Для решения головоломки применяется последовательность ходов, начиная с некоторой произвольной начальной конфигурации.

Решение

Можно рассматривать алгоритм для решения такой головоломки, если он принимает на входе произвольную начальную конфигурацию и производит на выходе последовательность ходов, ведущих к окончательной конфигурации (если головоломка разрешима из этой начальной конфигурации, иначе она сигнализирует о невозможности решения). Решение будет оптимальным, если последовательность ходов будет как можно короче. Это количество известно как Число бога,[3] или, более формально, минимакс ценить.[4] Следовательно, алгоритм Бога для данной головоломки - это алгоритм, который решает головоломку и производит только оптимальные решения.

Некоторые авторы, такие как Дэвид Джойнер, считают, что для того, чтобы алгоритм назывался «алгоритм Бога», он также должен быть практичный, что означает, что алгоритм не требует чрезмерного количества памяти или времени. Например, используя гигантский Справочная таблица индексирование начальными конфигурациями позволит очень быстро находить решения, но потребует огромного количества памяти.[5]

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

Примеры

Хорошо известные головоломки, подходящие под это описание: механические головоломки подобно Кубик Рубика, Башни Ханоя, а 15 головоломка. Игра одного человека колышек пасьянс также покрывается, как и многие логические головоломки, такой как проблема миссионеров и каннибалов. Их объединяет то, что они могут быть смоделирован математически как ориентированный граф, в котором конфигурации являются вершинами, а перемещает дуги.

Механические пазлы

п-пазлы

В Пятнадцать пазлов можно решить за 80 ходов по одной плитке[6] или 43 хода с несколькими плитками[7] в худшем случае. Для его обобщения п-задача, проблема поиска оптимального решения NP-жесткий.[8] Поэтому остается неизвестным, существует ли практический алгоритм Бога для решения этой проблемы, но это кажется маловероятным.

Башни Ханоя

Для Башни Ханоя пазл, алгоритм Бога известен для любого заданного количества дисков. Количество ходов экспоненциально зависит от количества дисков. ().[9]

Кубик Рубика

Основная статья: Оптимальные решения для кубика Рубика

Алгоритм определения минимального количества ходов для сборки кубика Рубика был опубликован в 1997 году Ричардом Корфом.[10] Хотя с 1995 года было известно, что 20 - это нижняя граница количества ходов для решения в худшем случае, в 2010 году с помощью обширных компьютерных вычислений было доказано, что для конфигурации не требуется более 20 ходов.[11] Таким образом, 20 - это острый верхняя граница от длины оптимальных решений. Математик Дэвид Сингмастер "опрометчиво предположил", что это число равнялось 20 в 1980 году.[4]

Неразгаданные игры

В некоторых хорошо известных играх с очень ограниченным набором простых и четко определенных правил и ходов, тем не менее, никогда не определялся их алгоритм Бога для выигрышной стратегии. Примеры настольные игры шахматы и Идти.[12] В обеих этих играх количество позиций с каждым ходом быстро увеличивается. Общее количество всех возможных позиций, примерно 10154 для шахмат[13] и 10180 (на доске 19 × 19) для го,[14] слишком велик, чтобы можно было использовать грубую силу с современными вычислительными технологиями (сравните теперь решенный, с большим трудом, кубик Рубика с размером всего около 4,3 × 1019 позиции[15]). Следовательно, определение алгоритма Бога методом грубой силы для этих игр невозможно. Хотя были созданы шахматные компьютеры, способные обыграть даже лучших игроков-людей, они не просчитывают игру до конца. Темно-синий, например, выполнялся поиск только на 11 ходов вперед (считая ход каждого игрока как два хода), уменьшая пространство поиска до 1017.[16] После этого он оценил преимущество каждой позиции в соответствии с правилами, основанными на игре и опыте людей.

Даже эта стратегия невозможна с Go. Помимо того, что нужно оценивать гораздо больше позиций, до сих пор никто не разработал набор простых правил для оценки силы позиции го, как это было сделано для шахмат.[17] Алгоритмы оценки склонны делать элементарные ошибки[18] так что даже при ограниченном взгляде в будущее с целью, ограничивающейся поиском наиболее сильной промежуточной позиции, алгоритм Бога для Go оказался невозможным.

С другой стороны, Черновики (шашки), имеющие внешнее сходство с шахматами, уже давно подозреваются в том, что их опытные практики «разыгрывают».[19] В 2007 году Шеффер и другие. доказал, что это так, рассчитав базу данных всех позиций с десятью или менее фигурами. Таким образом, у Шеффера есть алгоритм Бога для всех финальных партий шашек и он использовал его, чтобы доказать, что все идеально сыгранные шашки заканчиваются вничью.[20] Однако шашки только с 5 × 1020 позиции[21] и даже меньше, 3,9 × 1013, в базе данных Schaeffer,[22] Решить задачу гораздо проще, она того же порядка, что и кубик Рубика.

Величина набора позиций головоломки не полностью определяет, возможен ли алгоритм Бога. Уже решенная головоломка Ханойская башня может состоять из произвольного количества частей, а количество позиций увеличивается экспоненциально по мере того, как . Тем не менее, алгоритм решения применим к проблеме любого размера, а поскольку время работы алгоритма равно проблема NP-сложная.[23]

Смотрите также

Примечания

  1. ^ Пол Энтони Джонс, Джедбург Джастис и Кентиш Файр: истоки английского языка в десяти фразах и выражениях, Hachette UK, 2014 г. ISBN  1472116224.
  2. ^ См. Например Кубический компендиум Рубика Эрне Рубик, Тамаш Варга, Герзсон Кери, Дьёрдь Маркс и Тамаш Векерди (1987, Oxford University Press, ISBN  0-19-853202-4), п. 207: «... Пираминкс намного проще, чем Волшебный куб ... Николас Хаммонд показал, что Алгоритм Бога состоит не более чем из 21 хода (включая четыре тривиальных хода вершины). [Недавно три человека нашли Алгоритм Бога. Максимальное количество ходов - 15 (включая четыре хода вершины).] "
  3. ^ Джонатан Филдс (11 августа 2010 г.). «Поиски быстрого решения в кубике Рубика подошли к концу». Новости BBC.
  4. ^ а б Singmaster, стр. 311, 1980 г.
  5. ^ Джойнер, стр.149
  6. ^ А. Брюнггер, А. Марцетта, К. Фукуда и Й. Нивергельт, Стенд параллельного поиска ZRAM и его приложения, Анналы исследований операций 90 (1999), стр. 45–63.
  7. ^ «Головоломку пятнадцати можно решить за 43 года. движется". Домен куба Форум
  8. ^ Даниэль Ратнер, Манфред К. Вармут (1986). «Найти кратчайшее решение для расширения N × N головоломки из 15 непросто». в Труды AAAI-86. Национальная конференция по искусственному интеллекту, 1986. С. 168–172.
  9. ^ Карлос Руэда, «Оптимальное решение загадки Ханойские башни».
  10. ^ Ричард Э. Корф "Поиск оптимальных решений для кубика Рубика с использованием баз данных шаблонов ", Proc. Natl. Конф. по искусственному интеллекту (AAAI-97), Провиденс, Род-Айленд, июль 1997 г., стр. 700–705.
  11. ^ «Число Бога - 20». Cube20.org
  12. ^ Ротенберг, стр. 11
  13. ^ Баум, стр. 187
  14. ^ Баум, стр. 199
  15. ^ Певец, 1981
  16. ^ Баум, стр. 188
  17. ^ Баум, стр. 197
    • Мохаммадян, стр. 11
  18. ^ Баум, стр.197
  19. ^ Фрейзер и Ханна, стр. 197
  20. ^ Мур и Мертенс, глава 1.3, «Игра в шахматы с Богом»
  21. ^ Шеффер и другие., п. 1518
  22. ^ Мур и Мертенс, «Примечания» к главе 1
  23. ^ Руэда

Рекомендации

  • Баум, Эрик Б., Что такое мысль?, MIT Press, 2004 г. ISBN  0262025485.
  • Дэвис, Дэррил Н .; Chalabi, T .; Бербанк-Грин, Б., «Искусственная жизнь, агенты и вперед», в Мохаммадьяне, Масуд, Новые рубежи в области вычислительного интеллекта и его приложений, стр. 125–139, IOS Press, 2000 ISBN  9051994761.
  • Фрейзер, Робер (редактор); Ханна, В. (ред.), Еженедельный журнал The Draft Players ', т. 2, Глазго: Дж. Г. Берри, 1885.
  • Дэвид Джойнер (2002). Приключения в теории групп. Издательство Университета Джона Хопкинса. ISBN  0-8018-6947-1.
  • Мур, Кристофер; Мертенс, Стефан, Природа вычислений, Oxford University Press, 2011 г. ISBN  0191620807.
  • Ротенберг, Гади, Катализ, Алгоритм Бога и Зеленый демон, Издательство Амстердамского университета, 2009 г. ISBN  9056295896.
  • Джонатан Шеффер, Нил Берч, Ингви Бьёрнссон, Акихиро Кишимото, Мартин Мюллер, Роберт Лейк, Пол Лу, Стив Сатфен, «Шашки решены», Наука, т. 317, нет. 58444, pp. 1518–1522, 14 сентября 2007 г.
  • Певец, Дэвид, Заметки о волшебном кубе Рубика, Пингвин, 1981 ISBN  0-907395-00-7.
  • Сингмастер, Дэвид, «Образовательная ценность венгерского« Волшебного куба »», Материалы Четвертого Международного конгресса по математическому образованию, проходившем в Беркли, Калифорния, 10–16 августа 1980 г., стр. 307–312, Birkhauser Boston Inc, 1983 г. ISBN  978-0-8176-3082-9.