Божий алгоритм

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

Объем

Определение

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

Решение

Алгоритм можно считать решающим такую головоломку, если он принимает на вход произвольную начальную конфигурацию и выдает на выходе последовательность ходов, приводящую к окончательной конфигурации ( если головоломка разрешима из этой начальной конфигурации, в противном случае он сигнализирует о невозможности решения такой головоломки). решение). Решение оптимально, если последовательность ходов как можно короче. Наивысшее значение этого числа среди всех начальных конфигураций известно как число Бога . ^{[ 3 ]} или, более формально, минимаксное значение. ^{[ 4 ]} Таким образом, Божий алгоритм для данной головоломки — это алгоритм, который решает головоломку и дает только оптимальные решения.

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

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

Примеры

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

Механические головоломки

n - Пазлы

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

Башни Ханоя

Для головоломки «Ханойские башни» известен алгоритм Бога для любого заданного количества дисков. Количество ходов увеличивается экспоненциально с увеличением количества дисков ( $2^{n}-1$ ) . ^{[ 9 ]}

Кубик Рубика

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

Нерешённые игры

В некоторых хорошо известных играх с очень ограниченным набором простых и четко определенных правил и ходов никогда не был определен Божий алгоритм выигрышной стратегии. Примерами являются настольные игры шахматы и го . ^{[ 12 ]} В обеих этих играх количество позиций быстро увеличивается с каждым ходом. Общее количество всех возможных позиций, примерно 5×10 ⁴⁴^{[ 13 ]} для шахмат и 10 ¹⁸⁰ (на доске 19х19) для го, ^{[ 14 ]} слишком велик, чтобы его можно было решить методом грубой силы с помощью современных вычислительных технологий (сравните теперь решенный с большим трудом кубик Рубика размером всего лишь около 4,3 × 10) . ¹⁹ позиции ^{[ 15 ]}). Следовательно, грубое определение алгоритма Бога для этих игр невозможно. Хотя созданы шахматные компьютеры, способные обыграть даже лучших игроков, они не просчитывают игру до конца. Deep Blue , например, искал только на 11 ходов вперед (считая ход каждого игрока за два хода), сокращая пространство поиска всего до 10. ¹⁷. ^{[ 16 ]} После этого он оценивал каждую позицию на предмет преимущества в соответствии с правилами, основанными на человеческой игре и опыте.

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

С другой стороны, шашки (шашки) уже давно подозреваются в том, что они «разыгрываются» ее специалистами-практиками. ^{[ 19 ]} В 2007 году Шеффер и др. доказал это, рассчитав базу данных всех позиций с десятью или менее фигурами, предоставив Божий алгоритм для всех окончаний шашек, который использовался, чтобы доказать, что все идеально сыгранные игры в шашки заканчиваются вничью. ^{[ 20 ]} Однако шашки всего с 5 × 10 ²⁰ позиции ^{[ 21 ]} и того меньше, 3,9 × 10 ¹³, в базе данных, ^{[ 22 ]} решить гораздо более простую задачу — того же порядка, что и кубик Рубика.

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

См. также

Примечания

^ Пол Энтони Джонс, Джедбург Джастис и Кентиш Файр: Истоки английского языка в десяти фразах и выражениях , Hachette UK, 2014 ISBN 1472116224 .
^ См., например , «Кубический компендиум Рубика» Эрно Рубика, Тамаша Варги, Гержсона Кери, Дьёрдя Маркса и Тамаша Векерди (1987, Oxford University Press, ISBN 0-19-853202-4 ), с. 207: «...Пираминкса намного проще, чем Волшебный Куб... Николас Хаммонд показал, что Алгоритм Бога состоит не более чем из 21 хода (включая четыре тривиальных хода вершины). [Недавно три человека нашли Алгоритм Бога. Максимальное количество ходов — 15 (включая четыре хода вершин).]"
^ Джонатан Филдс (11 августа 2010 г.). «Поиски быстрого решения кубика Рубика подходят к концу» . Новости Би-би-си .
^ Jump up to: ^а ^б Сингмастер, с. 311, 1980 г.
^ Джойнер, страница 149.
^ А. Брюнгер, А. Марцетта, К. Фукуда и Дж. Нивергельт, Стенд параллельного поиска ZRAM и его приложения , Annals of Operations Research 90 (1999), стр. 45–63.
^ Норског, Брюс; Дэвидсон, Морли (8 декабря 2010 г.). «Загадку пятнадцати можно решить за 43 хода » . Домен форума Cube . Проверено 15 марта 2022 г.
^ Дэниел Ратнер, Манфред К. Вармут (1986). «Найти кратчайшее решение для расширения N × N головоломки из 15 сложно» . в материалах АААИ-86 . Национальная конференция по искусственному интеллекту, 1986. стр. 168–172.
^ Руэда, Чарльз (август 2000 г.). «Оптимальное решение головоломки Ханойских башен» . Universidad Autónoma de Manizales [Автономный университет Манисалеса] . Манисалес , Колумбия . Архивировано из оригинала 5 июня 2004 г. Проверено 15 марта 2022 г.
^ Ричард Э. Корф, « Поиск оптимальных решений кубика Рубика с использованием баз данных шаблонов », Proc. Натл. Конф. об искусственном интеллекте (AAAI-97), Провиденс, Род-Айленд, июль 1997 г., стр. 700–705.
^ Рокицки, Томас; Коцемба, Герберт; Дэвидсон, Морли; Детридж, Джон (2010). «Число Бога — 20» . Cube20.org . Проверено 15 марта 2022 г.
^ Ротенберг, с. 11
^ Джон Тромп. «Рейтинг шахматных позиций» . Гитхаб .
^ Дерево, с. 199
^ Сингмастер, 1981.
^ Дерево, с. 188
^
- Дерево, с. 197
- Мохаммадиан, с. 11
^ Дерево, стр.197.
^ Фрейзер и Ханна, с. 197
^ Мур и Мертенс, глава 1.3, «Игра в шахматы с Богом»
^ Шеффер и др. , с. 1518
^ Мур и Мертенс, «Примечания» к главе 1.
^ Колесо

Ссылки

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

[1] Пол Энтони Джонс, Джедбург Джастис и Кентиш Файр: Истоки английского языка в десяти фразах и выражениях , Hachette UK, 2014 ISBN 1472116224 .

[2] См., например , «Кубический компендиум Рубика» Эрно Рубика, Тамаша Варги, Гержсона Кери, Дьёрдя Маркса и Тамаша Векерди (1987, Oxford University Press, ISBN 0-19-853202-4 ), с. 207: «...Пираминкса намного проще, чем Волшебный Куб... Николас Хаммонд показал, что Алгоритм Бога состоит не более чем из 21 хода (включая четыре тривиальных хода вершины). [Недавно три человека нашли Алгоритм Бога. Максимальное количество ходов — 15 (включая четыре хода вершин).]"

[3] Джонатан Филдс (11 августа 2010 г.). «Поиски быстрого решения кубика Рубика подходят к концу» . Новости Би-би-си .

[Sing311-4] Jump up to: ^а ^б Сингмастер, с. 311, 1980 г.

[5] Джойнер, страница 149.

[6] А. Брюнгер, А. Марцетта, К. Фукуда и Дж. Нивергельт, Стенд параллельного поиска ZRAM и его приложения , Annals of Operations Research 90 (1999), стр. 45–63.

[7] Норског, Брюс; Дэвидсон, Морли (8 декабря 2010 г.). «Загадку пятнадцати можно решить за 43 хода » . Домен форума Cube . Проверено 15 марта 2022 г.

[8] Дэниел Ратнер, Манфред К. Вармут (1986). «Найти кратчайшее решение для расширения N × N головоломки из 15 сложно» . в материалах АААИ-86 . Национальная конференция по искусственному интеллекту, 1986. стр. 168–172.

[9] Руэда, Чарльз (август 2000 г.). «Оптимальное решение головоломки Ханойских башен» . Universidad Autónoma de Manizales [Автономный университет Манисалеса] . Манисалес , Колумбия . Архивировано из оригинала 5 июня 2004 г. Проверено 15 марта 2022 г.

[10] Ричард Э. Корф, « Поиск оптимальных решений кубика Рубика с использованием баз данных шаблонов », Proc. Натл. Конф. об искусственном интеллекте (AAAI-97), Провиденс, Род-Айленд, июль 1997 г., стр. 700–705.

[GN20-11] Рокицки, Томас; Коцемба, Герберт; Дэвидсон, Морли; Детридж, Джон (2010). «Число Бога — 20» . Cube20.org . Проверено 15 марта 2022 г.

[12] Ротенберг, с. 11

[13] Джон Тромп. «Рейтинг шахматных позиций» . Гитхаб .

[14] Дерево, с. 199

[15] Сингмастер, 1981.

[16] Дерево, с. 188

[17] 
Дерево, с. 197
Мохаммадиан, с. 11

[18] Дерево, с. 197

[19] Мохаммадиан, с. 11

[18] Дерево, стр.197.

[19] Фрейзер и Ханна, с. 197

[20] Мур и Мертенс, глава 1.3, «Игра в шахматы с Богом»

[21] Шеффер и др. , с. 1518

[22] Мур и Мертенс, «Примечания» к главе 1.

[23] Колесо

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]