Алгоритм Бога - это понятие, появившееся в ходе обсуждения способов решения головоломки « Кубик Рубика» [1], но оно также может быть применено к другим комбинаторным головоломкам и математическим играм . [2] Это относится к любому алгоритму, который производит решение с наименьшим возможным количеством ходов, идея состоит в том, что только всеведущее существо может знать оптимальный шаг из любой данной конфигурации.
Сфера
Определение
Это понятие применяется к головоломкам, которые могут предполагать конечное количество «конфигураций» с относительно небольшим, четко определенным арсеналом «ходов», которые могут быть применимы к конфигурациям и затем привести к новой конфигурации. Решение головоломки означает достижение обозначенной «окончательной конфигурации», особой конфигурации или одной из набора конфигураций. Для решения головоломки применяется последовательность ходов, начиная с некоторой произвольной начальной конфигурации.
Решение
Алгоритм может быть рассмотрен для решения такой головоломки, если он принимает на входе произвольную начальную конфигурацию и производит на выходе последовательность ходов, ведущих к окончательной конфигурации ( если головоломка разрешима из этой начальной конфигурации, в противном случае она сигнализирует о невозможности решения задачи). решение). Решение будет оптимальным, если последовательность ходов будет как можно короче. Этот счет известен как число Бога , [3] или, более формально, минимаксное значение. [4] Алгоритм Бога для данной головоломки - это алгоритм, который решает головоломку и производит только оптимальные решения.
Некоторые авторы, такие как Дэвид Джойнер, считают, что для того, чтобы алгоритм мог быть правильно назван «алгоритмом Бога», он также должен быть практичным , что означает, что алгоритм не требует чрезмерного количества памяти или времени. Например, использование гигантской таблицы поиска, проиндексированной начальными конфигурациями, позволило бы очень быстро находить решения, но потребовало бы огромного количества памяти. [5]
Вместо того, чтобы запрашивать полное решение, можно эквивалентно попросить один ход от начальной, но не окончательной конфигурации, где этот ход является первым из некоторого оптимального решения. Алгоритм для одноходовой версии задачи можно превратить в алгоритм для исходной задачи, вызывая его многократно, применяя каждый ход, о котором сообщается в текущей конфигурации, до тех пор, пока не будет достигнут окончательный вариант. И наоборот, любой алгоритм для исходной задачи можно превратить в алгоритм для одноходовой версии, усекая его выходные данные до первого хода.
Примеры
Хорошо известные головоломки, подходящие под это описание, - это механические головоломки, такие как кубик Рубика , Ханойские башни и головоломка 15 . Также описана игра в пасьянс с колышками для одного человека , а также множество логических головоломок , таких как проблема миссионеров и каннибалов . Их объединяет то, что они могут быть смоделированы математически как ориентированный граф , в котором конфигурации являются вершинами, а перемещает дуги.
Механические пазлы
n- головоломки
Головоломка « Пятнадцать» может быть решена за 80 ходов из одной плитки [6] или за 43 хода из нескольких плиток [7] в худшем случае. Для обобщения n- головоломки задача нахождения оптимального решения NP-сложна . [8] Таким образом, остается неизвестным, существует ли практический алгоритм Бога для решения этой проблемы, но это кажется маловероятным.
Башни Ханоя
Для загадки Ханойских башен алгоритм Бога известен для любого заданного количества дисков. Количество ходов экспоненциально от количества дисков () . [9]
кубик Рубика
Алгоритм определения минимального количества ходов для сборки кубика Рубика был опубликован в 1997 году Ричардом Корфом. [10] Хотя с 1995 года было известно, что 20 - это нижняя граница количества ходов для решения в худшем случае, в 2010 году с помощью обширных компьютерных вычислений было доказано, что никакая конфигурация не требует более 20 ходов. [11] Таким образом, 20 - точная верхняя граница длины оптимальных решений. Математик Дэвид Сингмастер «опрометчиво предположил», что это число равно 20 в 1980 году [4].
Неразгаданные игры
В некоторых хорошо известных играх с очень ограниченным набором простых, четко определенных правил и ходов, тем не менее, никогда не определялся их алгоритм Бога для выигрышной стратегии. Примерами являются настольные игры в шахматы и го . [12] В обеих играх количество позиций с каждым ходом быстро увеличивается. Общее количество всех возможных позиций, приблизительно 10 154 для шахмат [13] и 10 180 (на доске 19 × 19) для Го, [14] слишком велико, чтобы разрешить решение методом грубой силы с современной компьютерной технологией (сравните теперь решен, с большим трудом, Кубик Рубика всего около4,3 × 10 19 позиций [15] ). Следовательно, определение алгоритма Бога методом грубой силы для этих игр невозможно. Хотя были созданы шахматные компьютеры, способные обыграть даже лучших игроков-людей, они не просчитывают игру до конца. Deep Blue , например, искал только 11 ходов вперед (считая ход каждого игрока как два хода), уменьшая пространство поиска до 10 17 . [16] После этого он оценил преимущество каждой позиции в соответствии с правилами, основанными на игре и опыте людей.
Даже эта стратегия невозможна с Go. Помимо того, что нужно оценивать гораздо больше позиций, до сих пор никто не разработал набор простых правил для оценки силы позиции го, как это было сделано в шахматах. [17] [18] Алгоритмы оценки подвержены элементарным ошибкам [17], поэтому даже при ограниченном взгляде в будущее с целью, ограничивающейся поиском наиболее сильной промежуточной позиции, алгоритм Бога для Go был невозможен.
С другой стороны, шашки (шашки), внешне похожие на шахматы, давно подозреваются в том, что они «разыгрываются» опытными практиками. [19] В 2007 году Schaeffer et al. Доказал это, рассчитав базу данных всех позиций с десятью или менее фигурами. Таким образом, у Шеффера есть алгоритм Бога для всех финальных партий шашек и он использовал его, чтобы доказать, что все идеально сыгранные шашки закончатся ничьей. [20] Однако шашки только с5 × 10 20 позиций [21] и даже меньше,3.9 × 10 13 , в базе данных Шеффера, [22] - это гораздо более легкая задача, и она того же порядка, что и кубик Рубика.
Величина набора позиций головоломки не полностью определяет, возможен ли алгоритм Бога. Уже решенная головоломка Ханойская башня может состоять из произвольного количества частей, и количество позиций увеличивается экспоненциально по мере того, как. Тем не менее, алгоритм решения применим к проблеме любого размера, а поскольку время работы алгоритма равнопроблема NP-сложная. [23]
Смотрите также
- Машина Oracle
- Божественный ход
- Доказательства из КНИГИ
Заметки
- ^ Пол Энтони Джонс, Джедбург Справедливость и Kentish Огонь: Происхождение английского языка в десять фраз и выражений , Hachette UK, 2014 ISBN 1472116224 .
- ↑ См., Например, «Сборник кубиков Рубика» Эрно Рубика, Тамаша Варги, Герзсона Кери, Дьёрдь Маркса и Тамаша Векерди (1987, Oxford University Press, ISBN 0-19-853202-4 ), стр. 207: «... Пираминкс намного проще, чем Волшебный куб ... Николас Хаммонд показал, что Алгоритм Бога состоит не более чем из 21 хода (включая четыре тривиальных хода вершины). [Совсем недавно Алгоритм Бога нашли три человека. Максимальное количество ходов - 15 (включая четыре хода вершины).] "
- ^ Джонатан Филдс (11 августа 2010 г.). «Поиски быстрого решения в кубике Рубика подошли к концу» . BBC News .
- ^ a b Singmaster 1980 , стр. 311.
- Перейти ↑ Joyner 2002 , p. 149.
- ^ А. Брюнггер, А. Марцетта, К. Фукуда и Дж. Нивергельт, Стенд параллельного поиска ZRAM и его приложения , Annals of Operations Research 90 (1999), стр. 45–63.
- ^ «Пятнадцать головоломок можно решить за 43 хода » . Домен куба Форум
- ^ Даниэль Ратнер, Манфред К. Вармут (1986). «Найти кратчайшее решение для расширения N × N головоломки из 15 непросто» . в Трудах AAAI-86 . Национальная конференция по искусственному интеллекту, 1986. С. 168–172.
- ↑ Карлос Руэда, «Оптимальное решение загадки Ханойских башен» .
- ^ Ричард Э. Корф, « Поиск оптимальных решений для кубика Рубика с использованием баз данных шаблонов », Proc. Natl. Конф. по искусственному интеллекту (AAAI-97), Провиденс, Род-Айленд, июль 1997 г., стр. 700–705.
- ^ «Число Бога - 20» . Cube20.org
- ^ Ротенберг 2009 , стр. 11.
- Перейти ↑ Baum 2004 , p. 187.
- Перейти ↑ Baum 2004 , p. 199.
- ^ Singmaster 1981 .
- Перейти ↑ Baum 2004 , p. 188.
- ^ а б Баум 2004 , стр. 197.
- ^ Дэвис, Чалаби и Бербанк-Грин 2000 , стр. 11.
- Перейти ↑ Fraser & Hannah 1885 , p. 197.
- ^ Мур и Мертенс 2011 , глава 1.3, «Игра в шахматы с Богом».
- ^ Schaeffer et al. 2007 , стр. 1518.
- ^ Мур и Мертенс 2011 , «Примечания» к главе 1.
- ^ Руэда
Рекомендации
- Баум, Эрик Б. (2004). Что такое мысль? . MIT Press. ISBN 0262025485.
- Дэвис, Дэррил Н; Чалаби, Т; Бербанк-Грин, B (2000), «Искусственная жизнь, агенты и вперед», Новые рубежи в вычислительном интеллекте и его приложениях , IOS Press: 125–139, ISBN 9051994761
- Фрейзер, Роберт; Ханна, W, ред. (1885). «Еженедельный журнал призывных игроков». Vol. 2. Глазго: Дж. Х. Берри. Журнал Cite требует
|magazine=
( помощь ) - Джойнер, Дэвид (2002). Приключения в теории групп . Издательство Университета Джона Хопкинса. ISBN 0-8018-6947-1.
- Мур, Кристофер; Мертенс, Стефан (2011). Природа вычислений . Издательство Оксфордского университета. ISBN 0191620807.
- Ротенберг, Гади (2009). Катализ, Алгоритм Бога и Зеленый демон . Издательство Амстердамского университета. ISBN 9056295896.
- Шеффер, Джонатан; Берч, Нил; Бьёрнссон, Ингви; Кишимото, Акихиро; Мюллер, Мартин; Лейк, Роберт; Лу, Пол; Сатфен, Стив (14 сентября 2007 г.). «Шашки решены» . Наука . 317 (58444): 1518–1522.
- Singmaster, Дэвид (1981). Заметки о Волшебном кубе Рубика . Пингвин. ISBN 0-907395-00-7.
- Singmaster, Дэвид (1983). «Образовательная ценность венгерского« Волшебного куба » ». Материалы Четвертого Международного конгресса по математическому образованию . Состоялось в Беркли, Калифорния, 10–16 августа 1980 года: Birkhauser Boston Inc: 307–312. ISBN 978-0-8176-3082-9.CS1 maint: location ( ссылка )