Спасибо за статью! Вы сделали полезную работу. Тем, кто ищет, ваша публикация поможет сократить время поиска. Время — самое ценное, что у нас есть. Продолжайте, если у вас есть такая возможность.
Уважаю членов Хабро-Сообщества, которые пишут качественные, умные комментарии. Такие комментарии полезны во всех смыслах и касаются сути публикации. Без таких людей было бы скучно и неинтересно.
Тяжело воспринимаю комментарии, которые не имеют отношения ни к сути публикации, не к смыслу другого комментария. Критические комментарии важны для «здоровья» нашего сообщества, однако они должны носить смысл, связанный с контекстом публикации.
В целом, радует, что администрация Хабра старается учитывать мнение большинства членов нашего сообщества. Надеюсь, что эволюция нашего сообщества, как большого живого организма, пойдет в правильном направлении…
Когда я выложил на Хабр публикацию: «One Billion Queens Problem Solution или, «Исследование закономерностей в списке решений задачи распределения n-Ферзей», я не думал, что дискуссия перекинется на проект, который еще не опубликован. Как я уже писал, результаты исследования «разработка алгоритма решения n-Queens Completion Problem», подготовлены к публикации. После выхода статьи, я приведу достаточно подробное описание алгоритма для Хабра. Давайте подождем немного.
По поводу вопросов:
1.«Оказался ли он доказано правильным?»
-Да, алгоритма решения n-Queens Completion Problem» является линейным. Так как это принципиально, расчеты проводились несколько десятков миллионов раз. Результаты это подтверждают.
2.«Вы же знаете, да, что для этой задачи есть хорошо описанное решение за линейное время? Не требующее решения задачи n-queens completion?»
-Как я уже писал в комментарии, a) разработка алгоритма решения n-Queens Completion Problem», и b) поиск хотя бы одного решения для заданного значения n, это разные задачи.
Первая задача — n-Queens Completion Problem, относится к множеству NP-Complete, и является достаточно сложной. Я не нашел публикацию, где приводилось бы решение данной проблемы.
По поводу второй задачи «поиск хотя бы одного решения…» — имеется большое количество различных публикаций, которые прямо или косвенно касаются этой задаче. Посмотрите (W. Kosters and dll, n-Queens — 339 references, (September 11, 2017), www.liacs.leidenuniv.nl/~kosterswa/nqueens, возможно, что-то интересное найдете для себя. Есть различные алгоритмы «поиска хотя бы одного решения…». Одни работают быстро, другие медленно.
Я тоже разрабатывал алгоритм «поиска хотя бы одного решения…» для целей исследования, но об этом, в своей публикации на Хабре я ничего не писал. Хотя, алгоритм получился интересный и работает достаточно быстро. Среднее время поиска одного решения для доски размером миллион на миллион составляет около 9 секунд. Спасибо!
В связи с выше изложенным, я прошу дискуссию по поводу проекта «разработка алгоритма решения n-Queens Completion Problem» приостановить, до выхода соответствующей публикации на Хабре.
1. В задаче идет речь о «произвольных» k ферзях «произвольно» расположенных на шахматной доске размера n x n. В ходе исследования я рассматривал значения n от 7 до 50 миллионов.
2. К моему удивлению, алгоритм оказался линейным.
3. Вы правы, речь идет о «найти одно любое решение задачи n-queen placement, где n = миллиард». Это решение в виде 1-мерного массива (файла) доступно для скачивания. Об этом написано в публикации
Я с вами согласен.
Уход фигур с доски освобождает одну клетку и тем самым увеличивает возможное пространство выбора. С другой стороны, каждая фигура на доске имеет свое «поле влияния» и требует дополнительных «переборных» расчетов для формирования оптимального хода
Давайте порассуждаем вместе, как влияет потеря каждой фигуры на размер пространства состояния.
1. Мы имеем недетерминированную задачу.
2. В алгоритме «мы выступаем от имени» одного из игроков
3. Мы должны найти такую последовательность шагов (ходов), которая, как можно скорее поставит короля противника «в неловкое положение»
4. Любой наш шаг, начиная с первого – это выбор одного оптимального шага в огромном пространстве состояния. Любой такой шаг изменяет пространство состояния и меняет возможности дальнейшего нашего выбора.
5. Любой шаг противника – это «агрессивное» изменение «нашего» пространства состояния. Шаг противника изменяет наше пространство состояния так как «он может», мы меняем его пространство состояния так как «мы хотим».
6. Каждая фигура, как вы правильно сказали, «дает ветвление не только своими ходами, но и тем, что мешает остальным». Т.е. каждая фигура на доске является источником увеличения размера пространства состояния. Каждая фигура «приумножает» возможности ходов в «пространстве состояния». Когда фигура покидает доску, то автоматически «уничтожаются» все возможные ходы в пространстве состояния, которые были порождены этой фигурой. Поэтому, когда в ходе игры, сокращается количество фигур на шахматной доске, то соответственно уменьшается размер пространства состояния. (Достаточно представить себе размер пространства состояния, который «порождается», когда на доске по одной фигуре с каждой стороны, по две фигуры и т.д.
Речь идет об алгоритме решения n-Queens Completion Problem. Данная задача относится к классу NP-Complete. Об этом была публикация на Хабре. Суть ее состоит в следующем. На шахматной доске размера n x n не противоречиво расставлены k ферзей. Требуется разработать алгоритм, который «достроит» данную композицию до полного решения, либо доказать, что данная композиция не может быть комплектована до полного решения. Именно о линейном алгоритме решения данной задачи я писал в своем комментарии. Я нереально долго сидел над решением этой задачи. Настолько долго, что как-то стыдно было «соскочить» не получив положительного результата. Результаты исследования по данному проекту подготовлены к публикации. После выхода статьи, я обязательно выложу на Хабре подробное описание. Там очень много интересного.
Так вот, данный алгоритм я использовал для того, чтобы найти одно решение задачи о «распределении одного миллиарда ферзей на шахматной доске размером миллиард на миллиард». Это было в декабре и мне хотелось преподнести всем членам Хабра-Сообщества небольшой новогодний подарок в виде такого «интеллектуального изделия».
Сама задача нахождения одного решения является интересной алгоритмической задачей, но к классу NP-Complete не относится.
Задача нахождения всех решений для заданного n формулируется немного иначе. Никто не требует найти «подряд» все решения для заданного значения n. Требуется только определить количество всех решений для каждого значения n. Это достаточно сложная задача и относится к классу NP-Complete. Методом прямого вычисления всех полных решений, в предыдущие годы был найден размер списка всех решений вплоть до значения n=27. После этого подобные расчеты не проводились, так как это требует значительных вычислительных ресурсов и временных затрат. Кстати, нет необходимости в том, чтобы найти последовательный список всех полных решений. Достаточно найти только первую половину этого списка. Вторая половина списка полных решений симметрична и комплементарна к первой половине списка. Поэтому, все найденные значения размера списка полных решений являются четными числами.(Sloane N.J.A. (2016). The on-line encyclopedia of integer sequences. oeis.org/search?q=A000170&language=english&go=Search). Я об этом писал в публикации.
Хотя уважаемый мною коллега hippohood высказался о моем комментарии «по форме», а не «по сути», я решил найти время и ответить, так как это важно. Я, в самом деле считаю, что у нас на Хабре очень много талантливых и выдающихся программистов и коллега hippohood один из них. Нет сложных задач программирования, которые мы не можете решить. Сложности есть только внутри нас. Мы не должны принимать «близко к сердцу» мнение «толпы», что это «очень сложная задача». Для них сложная, для нас – нет. Каждый член Хабро-Сообщества не такой «как все». Нам нужно быть напористым и терпеливым, и тогда пройдет время, и мы добьемся своих целей.
Вы когда-нибудь сидели 60 дней подряд над одной и той же «сложной задачей» программирования. С утра до вечера (а реально до глубокой ночи). Почти без выходных и почти без праздников. А чтобы 120 дней работать в таком режиме вам приходилось? Так, чтобы не потерять веру в то, что вы делаете. Именно в таком режиме я работал всю первую половину 2018 года. Я был «глубоко занят» разработкой алгоритма решения n-Queens Completion Problem. Мне друзья советовали бросить это дело или показаться психологу. Прошло много месяцев прежде чем мне удалось получить первое очертание работающего алгоритма. Я не буду повторяться, об этом когда-то кратко написал в комментарии.
Считаю, что каждому из нас следует расширить границы своих возможностей и целенаправленно идти к решению той «сложной задачи», которая вам нравится.
В заключение, я хотел бы привести анекдот, который имеет отношение к теме:
-Четыре грузинских мальчика спорят о том, у кого дедушка самый высокий.
-Один говорит: «Мой дедушка такой высокий, как эта грузовая машина»
-Второй: «Мой дедушка такой высокий, как это дерево»
-Третий: «Мой дедушка такой высокий, что упирается головой в звезды»
-Четвертый спрашивает у третьего: «А звезды такие круглые и теплые?»
-Тот отвечает: «Да!»
-Четвертый: «Так это яйца моего дедушки»
— — — — Так вот, я считаю, что программисты Хабра-Сообщества «самые высокие», остальные им до пояса.
Публикации SLY_G на Хабре всегда представляют интерес для читателей. Удивительно продуктивный человек, что заслуживает уважения. Его публикация на этот раз оказалась пафосной. Но человек сделал это «от души».
Я согласен с мнениями наших коллег old_bear, vics001, высказанных ранее. Давайте без эйфории посмотрим на постановку самой задачи и, предположительно на то, что (возможно) делает AlphaZero, как программа, разработанная замечательным коллективом Deep Mind.
1.Речь идет о не детерминированной задаче формирования ветви поиска решения в пространстве состояния очень большого размера. Каждый шаг сделанный игроком и каждый шаг сделанный противником изменяют возможности выбора во всех последующих шагах. Одновременно, потеря каждой фигуры «понемногу» сокращает размер пространства состояния.
2.Можно ли утверждать, что разработан алгоритм на основе искусственных нейронных сетей, который обучается формированию оптимальной стратегии совершения каждого хода для победы над противником? Думаю, что вряд ли. Пространство состояния имеет огромные размеры и вряд ли кто-либо реально способен охватить хотя бы 1% этого пространства состояния, чтобы «крепко обучиться»
3.Реально используются эвристические правила, которые были обнаружены каждой из команд, в результате изучения того, как формируется ветвь поиска решения в этой не детерминированной задаче. Думаю, что этих правил много, они параметрические и, большая часть этих правил у обеих команд скорее всего совпадает.
4.Уверен, что нейронная сеть построена и используется для оптимизации параметров этих правил. То, что команда Deep Mind добилась успеха в решении данной конкретной задачи- то ребята молодцы. Я высоко ценю их труд.
5.Перенести «кавалерийским наскоком» разработанный алгоритм для решения других актуальных задач, так просто не получится. Там нужно искать свои эвристические правила и, как минимум, оптимизировать неизвестные параметры этих правил. Возможно, подтверждением этому может служить участие Deep Mind в конкурсе по прогнозу свойств белков. Хотя Deep Mind оказался впереди, но ошибка прогноза оказалась настолько большой, что результаты пока никакого практического интереса не представляют.
6.Тональность данной публикации не должен «расшатывать психику» программистов. Будет правильно, если мы хорошо осознаем то, что делают коллеги из Deep Mind и разработаем что-нибудь еще лучше. А так, давайте порадуемся за достижения наших коллег и пожелаем им дальнейших успехов.
7.Я уверен в том, что в нашем Хабра-сообществе есть выдающиеся команды, которым вполне под силу решить подобную задачу или задачу более сложную. Дайте им хотя бы десятую часть той суммы, которая была выделена на этот проект, и вы очень скоро увидите результаты.
Думаю, что небольшие косяки в переводе не нарушили цельность восприятия. Спасибо за перевод!
Я с большой симпатией отношусь к Демису Хассабису и высоко оцениваю достижения компании DeepMind. Мне кажется, образ Демиса Хассабиса может служить хорошим примером подражания для школьников. Замечательный человек, одержимый хорошей идеей и целеустремленно движущийся к ней.
1.Думаю, каждый из нас «понемногу» занимался «искусственным интеллектом» и, наверное, продолжает заниматься и теперь. Я редко использую журналистский термин «искусственный интеллект», а вместо этого использую «Constructed Intelligence». Для меня «искусственный интелект» как понятие бесконечности в математике.
2.Можно перечислить длинный список изделий, созданных человеком, в которых в той или иной степени используется Constructed Intelligence. То, чем занимается команда DeepMind – это задачи «верхнего эшелон» в разработке очередного изделия Constructed Intelligence. Их успех позволит открыть новые горизонты для всех, кто вовлечен в подобные исследования и, возможно, позволит отодвинуть стену непонимания принципиальных вопросов.
3.Один из принципиальных вопросов (как я думаю) – это разработка алгоритма обучения. Звучит настолько тривиально и понятно, что кажется, что это вообще не проблема. На самом деле это не так. Как случайную переменную Y, равномерно распределенную на некотором отрезке, научить тому, «как себя ведет» случайная переменная X, равномерно распределенную на некотором другом отрезке, так, чтобы переменная Y могла «многое рассказать о поведении переменной X? Это простой «предельный пример», требующий разработки принципиально нового алгоритма обучения. И такой алгоритм может быть построен, хотя звучит абсурдно в реалиях существующих знаний, «как может одна случайная переменная предсказывать другую случайную переменную, если связь между ними равна нулю?».
4.То, что реализовано в алгоритме Alfa Go – это хорошая эвристика для формирования ветви поиска решения в пространстве состояния, в условиях заданного списка ограничений. Поведение противника и его действия, это тоже ограничения, при формировании выбора для очередного шага. Это хорошая не детерминированная задача. По уровню сложности она близка ко многим задачам из класса NP-Complete. Однако, я там не вижу обучения. Невозможно обучиться «всем возможностям» в пространстве состояния, когда в этой задаче оно настолько огромное, что «… молекул не хватит». Скорее всего, речь идет о нескольких правилах, изменяющихся а процессе формирования ветви поиска решения. Эти правила должны быть неотъемлемым свойством данной задачи. И молодцы, если они это нашли. (Кстати, интересно было бы узнать, сколько вариантов перебора делает алгоритм Alfa Go для выполнения очередного шага, и как это количество вариантов перебора меняется в процессе игры от начала к концу. Это своего рода критерий качества используемой эвристики).
Хорошая работа. Славно потрудились.
Думаю, что в этом направлении исследования скоро появятся новые интересные достижения. Единственное, хочу сказать, что за миллионы лет жизни на земле в цепочке «жизнь – смерть», что-то разрушается, и на останках разрушенного рождается что-то новое. Поэтому, очень хотелось бы, чтобы на этом направлении кто-то серъезно думал об этом, и синтезирую новые объекты, не нарушал БАЛАНС. В качестве тяжелого примера-напоминания можно привести полиэтиленовые пакеты, которые в виде мусора образовали в океане целые скопления-острова, размером с маленькую европейскую страну. Это пример для предостережения и к ДНК отношение не имеет.
Быстро посмотрел публикацию и у меня пропало «чувство удовлетворения». Жалко, хорошее название. К уважаемому мною «Нетологии» и переводчице это отношение не имеет. Не совсем серъезно подошел к теме товарищ из Кембриджа. Мне это напоминает старое высказывание сантехника, что он «плоскогубцами всем грыжу вылечит». Это достаточно сложная и интересная тема (Прогнозирование вперед значений динамических рядов) и неправильно так легкомысленно к этому подходить. Искусственные нейронные сети – это лишь один из инструментов, который используется для таких целей. У него есть свои достоинства, и (как и у любого метода) есть свои недостатки. Для биржевых цен акций тех или иных компаний, можно сказать, что «год на год» не приходится и «месяц на месяц» не приходится. То, что вы обучались в прошлом, совсем не означает, что вы можете прогнозировать в настоящем. Ситуация поменялась на рынке, «в мире», и динамическая кривая совсем другая. Поменялась «точка опоры».Поэтому нужен алгоритм, который обучается и накапливает знания в потоке, постоянно «впитывая новые знания». И не обязательно, что это будут нейронные сети.
p.s. У музыкантов плохая музыка «режет слух», график «предсказания», приведенный в статье, мне «режет зрение». Две «ломанные кривые» пляшут синхронно как трамвайные пути после землетрясения. Так не должно быть, там явное систематическое смещение.
Хабр родился в России и очень много молодых людей, членов нашего сообщества, учатся на публикациях Хабра. Для них, это «школа жизни», представленная в форме «сделай как я». Для всех этих молодых людей и тех, кто присоединяется к нам каждый день, русский язык является родным. Поэтому и текст публикации на русском и комментарии, воспринимаются ими быстро и адекватно, как по смыслу, так и по форме. Для публикаций на английском — этого не будет.
Учитывая ту огромную миссию, которую выполняет Хабро-сообщество для этих людей, для России, то считаю важны:
1. Обязательную публикацию любой статьи на русском языке.
2. Чтобы опубликовать статью на английском (или другом языке), достаточно перевести искомый русский текст на английский и разместить в «англоязычной части Хабра».
3. Если какая-то статья изначально написана и опубликована на английском, то эту статью обязательно стоит перевести на русский язык и опубликовать в русскоязычной части Хабра, если эта статья представляет интерес для Хабро-Сообщества.
Три простых правила, но они позволяют учесть:
— интересы абсолютного большинства членов Хабро-Сообщества, которые хотели бы писать, читать и рассуждать на родном русском языке;
— интересы собственников Хабра, которые хотели бы расширить свой бизнес;
— и интересы тех авторов, которые хотели бы презентовать себя в англоязычном мире.
В начале скажу, что «Задачу о N ферзях признали NP-полной задачей» не является верным высказыванием и один из уважаемых членов Хабра-Сообщества достаточно подробно об этом писал. С другой стороны задача «n-Queens Completion Problem» относится к множеству NP-Complete.
По поводу линейного алгоритма решения этой задачи — вы правы, если бы год назад мне об этом сказал бы кто-то другой, я бы тоже не поверил. Видимо, это тот редкий случай, когда много месяцев живешь внутри задачи, и наступает момент, когда становится прозрачным то, что раньше «не было видно». Могу «подтвердить», что Будда был прав, когда сидел в уединении и долго оставался в состоянии медитации. Да, алгоритм линейный. За все время исследования я несколько десятков миллионов раз проводил расчеты для различных значений n, и алгоритм оставался линейным. Диапазон значений n в исследовании менялся от 7 до пятидесяти миллионов.
По поводу возможности разработки полиномиального (а еще лучше — линейного) алгоритма для решения других сложных задач из множества NP-Complete, могу сказать следующее:
a) задача, которую я решал, связана с разработкой оптимального алгоритма формирования ветви поиска решения, в условиях меняющихся, с каждым шагом, ограничений.
b) решение удалось получить только после того, когда в результате многочисленных экспериментов (Computational Simulation) были установлены важные правила, которые являются неотъемлемым свойством данной задачи.
c) ряд задач, из множества NP-Complete можно попытаться решить, используя установленные правила, или иные правила «в том же русле». Есть большая вероятность того, что некоторые задачи будут успешно решены «по аналогии». Но лучше решить, а потом об этом сказать. А пока, это только уверенное предположение. Тут уместна поговорка:«Не скажи гоп, пока не перепрыгнешь». Поэтому следует подождать.
По поводу всяких призов. Признаюсь честно — я об этом не думал. Удовольствие, которое получаешь, решая сложные задачи «достаточно дорого стоят». Но тут важно другое. Дело в том, что одним наиболее важных, принципиальных выводов, которые были получены в результате исследования, состоит в том, что «данную задачу и задачи, ей подобные, невозможно решить на основе привычных методов математики: на основе определений, формулировки лемм и доказательства теорем. Эту и подобные ей задачи можно решить только на основе „алгоритмической математики“. Думаю, что нашим уважаемым коллегам математикам „это может не понравиться“. Однако это не ограничивает возможности математики, а наоборот — расширяет эти возможности через направление „алгоритмической математики“.
Вряд ли „вектор моих мыслей“ будет направлен в сторону каких либо премий. Это было бы не рационально и мешало бы работать. В настоящий момент, я больше нуждаюсь в том, чтобы устроиться на работу у кого нибудь на пол-ставки в качестве разработчика сложных и ответственных алгоритмов, или других сложных задач, где я могу принести реальную пользу. Уже 4 года нахожусь в Марселе, и, к сожалению, так и не удалось устроиться на работу. На простые задачи не хотел терять время, а сложные задачи они не хотели ставить. (Интересный факт: после долгого перерыва у меня вышла публикация, в которой, в позиции, где указывается место работы я честно написал „безработный“. Ответственный сотрудник редакции написал, что „безработные у нас не публикуются“ и что „безработный не может делать такие публикации“. Пришлось согласиться на фразу „независимый исследователь“. Так, что я теперь в статусе: безработный — независимый исследователь.
Я рад, что вы «забрали подарок домой». Мне нравится наше Хабро-Сообщество, и мне хотелось сделать что нибудь приятное для членов сообщества. И вообще, показать, что в Хабро-Сообществе такие «подарки» могут преподнести, а в других сообществах — вряд ли.
Чтобы эти 3.7 Gb не простаивали зря на вашем диске, предлагаю простую задачу для творчества и отдыха. Все числа в этом массиве, это числа от 1 до одного миллиарда, перечисленные в особой последовательности в соответствии с ограничениями, согласно условиям задачи. Возьмем последовательно любой миллион чисел из этого списка и разнесем их в обнуленный 1-мерный массив размером миллиард, т.е. в соответствующую ячейку запишем номер ячейки. Теперь, если «сжать» этот массив, т.е. убрать нули, то получим 1 миллион чисел, которые, как было сказано, меняются от 1 до одного миллиарда. Теперь, на основе «проекции» сведем изменение чисел от 1 до миллиарда к изменению — от 1 до миллиона. Таким образом мы получим все числа от 1 до миллиона, но имеющих особый порядок перечисления. Поставим каждому из этих миллионов чисел, некий «цвет» из последовательной гаммы цветов и выведем это на экран в виде изображения 1000 х 1000 пикселей. Учитывая, что в решении есть определенная гармония, то просматривая сотню произвольных таких изображений, вы найдете хотя бы одну, которая вам понравится. Это будет некоторой, своеобразной визуализацией определенной части общего решения. Я этого не делал, но думаю, что это будет весело. Успехов!
Я искренне считаю, что если вы в свое время построили алгоритм и получали решение для 30 х 30, пусть даже за час, то вы относитесь к особой категории программистов, которые не боятся сложных задач, и, скорее всего, используют девиз «Вижу цель — не вижу преграду». Будем объективны, это, все таки, достаточно сложная задача. И если программист-исследователь ее решил, то можно считать, что он сдал «Очередную норму ГТО» в области программирования. Я выше уже писал, что в течение почти всего 2018 года занимался исследованием и разработкой алгоритма для решения «n-Queens Completion Problem». Я так долго и «нагло» с одной и той же задачей не сидел. В итоге, спустя много-много месяцев мне удалось разработать алгоритм который решает эту проблему за линейное время. (Среднее время получения решения одного решения для доски размером миллион на миллион составляет меньше 9 секунд). После этого я решил получить решение для больших значений n. Для n=(100, 300, 500 — миллионов) проблем не возникало. Когда начал рассматривать n=одному миллиарду, возникли проблемы. Оперативной памяти 32 Gb не хватило. (Я большие массивы в алгоритме не использую. Но наличие контрольных векторов размером с миллиард, перекрыло кислород). Пришлось остановиться, переосмыслить. После этого разделил алгоритм на три части, с сохранением промежуточных результатов. И в итоге, если не учесть время загрузки и выгрузки промежуточных фалов, то решение было получено, примерно за 3.5-4 часа. Хочу сказать, что я осознанно и целенаправленно искал это решение как подарок для членов Хабро-Сообщества к новому году. Статья была подготовлена в стандарте HTML-5 еще в конце декабря 2018, но Хабро-Приемник не пропустил. Я не знал, что там немного иные «стандарты». В итоге, пришлось, как сказал бы Лукашенко, «перетрахивать» набранный текст, и уже подавать после нового года. Спасибо Хабро-Sis-Админам, успели подать материал к «старому новому году»
Спасибо за грамотный вопрос! Ее можно сформулировать в виде следующей задачи:«На доске размера (n+1) x (n+1) правильно расставлены ферзи в n последовательных строках таким образом, что остались свободными первая (последняя) строка и первый (последний) столбец. Можно ли расположить еще один (последний) ферзь таким образом, чтобы получить правильное решение? Это один из частных вариантов формулировки общей задачи о „Комплектации произвольной композиции из k ферзей до полного решения“. В таком виде задача была сформулирована F. Nauck в 1850 году. В сентябре 2017 года I.P. Gent, C. Jefferson, P. Nightingale доказали, что данная проблема относится к классу NP-Complete. Ссылки на эти статьи есть в публикации. Повторюсь, речь идет конкретно о задаче „Комплектации ...“. Ценю, вы человек проницательный, спокойно сформулировали вопрос, который относится к одному частному случаю решения NP-Complete задачи. Дополнительно могу сказать следующее. Большую часть 2018 года я был занят разработкой алгоритма решения этой NP-Complete задачи. Я был на творческой диете и почти каждый день был занят только этой задачей. Спустя 4 месяца я получил удовлетворительный результат. Еще через 4 месяца я добился того, что алгоритм выполняет решение данной задачи за линейное время, для произвольного значения n и произвольных k ферзей не противоречиво расположенных на доске n x n. После этого я, в течение следующих трех месяцев вел исследования, чтобы добиться правильного решения в этом „лабиринте“ не с 5-го или 30-го раза, а чтобы решение преимущественно было получено с первого раза. Удивительно, но и в этом вопросе удалось получить положительных результатов. Ваш вопрос интересный и „задел за живое“. Поэтому все и рассказал. Я подготовил большую статью для отправки в Journal of Artificial Intelligence Research. Однозначно, после выхода публикации я приведу подробное описание полученных результатов. Там много чего интересного.
Тяжело воспринимаю комментарии, которые не имеют отношения ни к сути публикации, не к смыслу другого комментария. Критические комментарии важны для «здоровья» нашего сообщества, однако они должны носить смысл, связанный с контекстом публикации.
В целом, радует, что администрация Хабра старается учитывать мнение большинства членов нашего сообщества. Надеюсь, что эволюция нашего сообщества, как большого живого организма, пойдет в правильном направлении…
По поводу вопросов:
1.«Оказался ли он доказано правильным?»
-Да, алгоритма решения n-Queens Completion Problem» является линейным. Так как это принципиально, расчеты проводились несколько десятков миллионов раз. Результаты это подтверждают.
2.«Вы же знаете, да, что для этой задачи есть хорошо описанное решение за линейное время? Не требующее решения задачи n-queens completion?»
-Как я уже писал в комментарии, a) разработка алгоритма решения n-Queens Completion Problem», и b) поиск хотя бы одного решения для заданного значения n, это разные задачи.
Первая задача — n-Queens Completion Problem, относится к множеству NP-Complete, и является достаточно сложной. Я не нашел публикацию, где приводилось бы решение данной проблемы.
По поводу второй задачи «поиск хотя бы одного решения…» — имеется большое количество различных публикаций, которые прямо или косвенно касаются этой задаче. Посмотрите (W. Kosters and dll, n-Queens — 339 references, (September 11, 2017),
www.liacs.leidenuniv.nl/~kosterswa/nqueens, возможно, что-то интересное найдете для себя. Есть различные алгоритмы «поиска хотя бы одного решения…». Одни работают быстро, другие медленно.
Я тоже разрабатывал алгоритм «поиска хотя бы одного решения…» для целей исследования, но об этом, в своей публикации на Хабре я ничего не писал. Хотя, алгоритм получился интересный и работает достаточно быстро. Среднее время поиска одного решения для доски размером миллион на миллион составляет около 9 секунд. Спасибо!
В связи с выше изложенным, я прошу дискуссию по поводу проекта «разработка алгоритма решения n-Queens Completion Problem» приостановить, до выхода соответствующей публикации на Хабре.
2. К моему удивлению, алгоритм оказался линейным.
3. Вы правы, речь идет о «найти одно любое решение задачи n-queen placement, где n = миллиард». Это решение в виде 1-мерного массива (файла) доступно для скачивания. Об этом написано в публикации
Уход фигур с доски освобождает одну клетку и тем самым увеличивает возможное пространство выбора. С другой стороны, каждая фигура на доске имеет свое «поле влияния» и требует дополнительных «переборных» расчетов для формирования оптимального хода
1. Мы имеем недетерминированную задачу.
2. В алгоритме «мы выступаем от имени» одного из игроков
3. Мы должны найти такую последовательность шагов (ходов), которая, как можно скорее поставит короля противника «в неловкое положение»
4. Любой наш шаг, начиная с первого – это выбор одного оптимального шага в огромном пространстве состояния. Любой такой шаг изменяет пространство состояния и меняет возможности дальнейшего нашего выбора.
5. Любой шаг противника – это «агрессивное» изменение «нашего» пространства состояния. Шаг противника изменяет наше пространство состояния так как «он может», мы меняем его пространство состояния так как «мы хотим».
6. Каждая фигура, как вы правильно сказали, «дает ветвление не только своими ходами, но и тем, что мешает остальным». Т.е. каждая фигура на доске является источником увеличения размера пространства состояния. Каждая фигура «приумножает» возможности ходов в «пространстве состояния». Когда фигура покидает доску, то автоматически «уничтожаются» все возможные ходы в пространстве состояния, которые были порождены этой фигурой. Поэтому, когда в ходе игры, сокращается количество фигур на шахматной доске, то соответственно уменьшается размер пространства состояния. (Достаточно представить себе размер пространства состояния, который «порождается», когда на доске по одной фигуре с каждой стороны, по две фигуры и т.д.
Так вот, данный алгоритм я использовал для того, чтобы найти одно решение задачи о «распределении одного миллиарда ферзей на шахматной доске размером миллиард на миллиард». Это было в декабре и мне хотелось преподнести всем членам Хабра-Сообщества небольшой новогодний подарок в виде такого «интеллектуального изделия».
Сама задача нахождения одного решения является интересной алгоритмической задачей, но к классу NP-Complete не относится.
Задача нахождения всех решений для заданного n формулируется немного иначе. Никто не требует найти «подряд» все решения для заданного значения n. Требуется только определить количество всех решений для каждого значения n. Это достаточно сложная задача и относится к классу NP-Complete. Методом прямого вычисления всех полных решений, в предыдущие годы был найден размер списка всех решений вплоть до значения n=27. После этого подобные расчеты не проводились, так как это требует значительных вычислительных ресурсов и временных затрат. Кстати, нет необходимости в том, чтобы найти последовательный список всех полных решений. Достаточно найти только первую половину этого списка. Вторая половина списка полных решений симметрична и комплементарна к первой половине списка. Поэтому, все найденные значения размера списка полных решений являются четными числами.(Sloane N.J.A. (2016). The on-line encyclopedia of integer sequences. oeis.org/search?q=A000170&language=english&go=Search). Я об этом писал в публикации.
Вы когда-нибудь сидели 60 дней подряд над одной и той же «сложной задачей» программирования. С утра до вечера (а реально до глубокой ночи). Почти без выходных и почти без праздников. А чтобы 120 дней работать в таком режиме вам приходилось? Так, чтобы не потерять веру в то, что вы делаете. Именно в таком режиме я работал всю первую половину 2018 года. Я был «глубоко занят» разработкой алгоритма решения n-Queens Completion Problem. Мне друзья советовали бросить это дело или показаться психологу. Прошло много месяцев прежде чем мне удалось получить первое очертание работающего алгоритма. Я не буду повторяться, об этом когда-то кратко написал в комментарии.
Считаю, что каждому из нас следует расширить границы своих возможностей и целенаправленно идти к решению той «сложной задачи», которая вам нравится.
В заключение, я хотел бы привести анекдот, который имеет отношение к теме:
-Четыре грузинских мальчика спорят о том, у кого дедушка самый высокий.
-Один говорит: «Мой дедушка такой высокий, как эта грузовая машина»
-Второй: «Мой дедушка такой высокий, как это дерево»
-Третий: «Мой дедушка такой высокий, что упирается головой в звезды»
-Четвертый спрашивает у третьего: «А звезды такие круглые и теплые?»
-Тот отвечает: «Да!»
-Четвертый: «Так это яйца моего дедушки»
— — — — Так вот, я считаю, что программисты Хабра-Сообщества «самые высокие», остальные им до пояса.
Я согласен с мнениями наших коллег old_bear, vics001, высказанных ранее. Давайте без эйфории посмотрим на постановку самой задачи и, предположительно на то, что (возможно) делает AlphaZero, как программа, разработанная замечательным коллективом Deep Mind.
1.Речь идет о не детерминированной задаче формирования ветви поиска решения в пространстве состояния очень большого размера. Каждый шаг сделанный игроком и каждый шаг сделанный противником изменяют возможности выбора во всех последующих шагах. Одновременно, потеря каждой фигуры «понемногу» сокращает размер пространства состояния.
2.Можно ли утверждать, что разработан алгоритм на основе искусственных нейронных сетей, который обучается формированию оптимальной стратегии совершения каждого хода для победы над противником? Думаю, что вряд ли. Пространство состояния имеет огромные размеры и вряд ли кто-либо реально способен охватить хотя бы 1% этого пространства состояния, чтобы «крепко обучиться»
3.Реально используются эвристические правила, которые были обнаружены каждой из команд, в результате изучения того, как формируется ветвь поиска решения в этой не детерминированной задаче. Думаю, что этих правил много, они параметрические и, большая часть этих правил у обеих команд скорее всего совпадает.
4.Уверен, что нейронная сеть построена и используется для оптимизации параметров этих правил. То, что команда Deep Mind добилась успеха в решении данной конкретной задачи- то ребята молодцы. Я высоко ценю их труд.
5.Перенести «кавалерийским наскоком» разработанный алгоритм для решения других актуальных задач, так просто не получится. Там нужно искать свои эвристические правила и, как минимум, оптимизировать неизвестные параметры этих правил. Возможно, подтверждением этому может служить участие Deep Mind в конкурсе по прогнозу свойств белков. Хотя Deep Mind оказался впереди, но ошибка прогноза оказалась настолько большой, что результаты пока никакого практического интереса не представляют.
6.Тональность данной публикации не должен «расшатывать психику» программистов. Будет правильно, если мы хорошо осознаем то, что делают коллеги из Deep Mind и разработаем что-нибудь еще лучше. А так, давайте порадуемся за достижения наших коллег и пожелаем им дальнейших успехов.
7.Я уверен в том, что в нашем Хабра-сообществе есть выдающиеся команды, которым вполне под силу решить подобную задачу или задачу более сложную. Дайте им хотя бы десятую часть той суммы, которая была выделена на этот проект, и вы очень скоро увидите результаты.
Я с большой симпатией отношусь к Демису Хассабису и высоко оцениваю достижения компании DeepMind. Мне кажется, образ Демиса Хассабиса может служить хорошим примером подражания для школьников. Замечательный человек, одержимый хорошей идеей и целеустремленно движущийся к ней.
1.Думаю, каждый из нас «понемногу» занимался «искусственным интеллектом» и, наверное, продолжает заниматься и теперь. Я редко использую журналистский термин «искусственный интеллект», а вместо этого использую «Constructed Intelligence». Для меня «искусственный интелект» как понятие бесконечности в математике.
2.Можно перечислить длинный список изделий, созданных человеком, в которых в той или иной степени используется Constructed Intelligence. То, чем занимается команда DeepMind – это задачи «верхнего эшелон» в разработке очередного изделия Constructed Intelligence. Их успех позволит открыть новые горизонты для всех, кто вовлечен в подобные исследования и, возможно, позволит отодвинуть стену непонимания принципиальных вопросов.
3.Один из принципиальных вопросов (как я думаю) – это разработка алгоритма обучения. Звучит настолько тривиально и понятно, что кажется, что это вообще не проблема. На самом деле это не так. Как случайную переменную Y, равномерно распределенную на некотором отрезке, научить тому, «как себя ведет» случайная переменная X, равномерно распределенную на некотором другом отрезке, так, чтобы переменная Y могла «многое рассказать о поведении переменной X? Это простой «предельный пример», требующий разработки принципиально нового алгоритма обучения. И такой алгоритм может быть построен, хотя звучит абсурдно в реалиях существующих знаний, «как может одна случайная переменная предсказывать другую случайную переменную, если связь между ними равна нулю?».
4.То, что реализовано в алгоритме Alfa Go – это хорошая эвристика для формирования ветви поиска решения в пространстве состояния, в условиях заданного списка ограничений. Поведение противника и его действия, это тоже ограничения, при формировании выбора для очередного шага. Это хорошая не детерминированная задача. По уровню сложности она близка ко многим задачам из класса NP-Complete. Однако, я там не вижу обучения. Невозможно обучиться «всем возможностям» в пространстве состояния, когда в этой задаче оно настолько огромное, что «… молекул не хватит». Скорее всего, речь идет о нескольких правилах, изменяющихся а процессе формирования ветви поиска решения. Эти правила должны быть неотъемлемым свойством данной задачи. И молодцы, если они это нашли. (Кстати, интересно было бы узнать, сколько вариантов перебора делает алгоритм Alfa Go для выполнения очередного шага, и как это количество вариантов перебора меняется в процессе игры от начала к концу. Это своего рода критерий качества используемой эвристики).
Думаю, что в этом направлении исследования скоро появятся новые интересные достижения. Единственное, хочу сказать, что за миллионы лет жизни на земле в цепочке «жизнь – смерть», что-то разрушается, и на останках разрушенного рождается что-то новое. Поэтому, очень хотелось бы, чтобы на этом направлении кто-то серъезно думал об этом, и синтезирую новые объекты, не нарушал БАЛАНС. В качестве тяжелого примера-напоминания можно привести полиэтиленовые пакеты, которые в виде мусора образовали в океане целые скопления-острова, размером с маленькую европейскую страну. Это пример для предостережения и к ДНК отношение не имеет.
p.s. У музыкантов плохая музыка «режет слух», график «предсказания», приведенный в статье, мне «режет зрение». Две «ломанные кривые» пляшут синхронно как трамвайные пути после землетрясения. Так не должно быть, там явное систематическое смещение.
Учитывая ту огромную миссию, которую выполняет Хабро-сообщество для этих людей, для России, то считаю важны:
1. Обязательную публикацию любой статьи на русском языке.
2. Чтобы опубликовать статью на английском (или другом языке), достаточно перевести искомый русский текст на английский и разместить в «англоязычной части Хабра».
3. Если какая-то статья изначально написана и опубликована на английском, то эту статью обязательно стоит перевести на русский язык и опубликовать в русскоязычной части Хабра, если эта статья представляет интерес для Хабро-Сообщества.
Три простых правила, но они позволяют учесть:
— интересы абсолютного большинства членов Хабро-Сообщества, которые хотели бы писать, читать и рассуждать на родном русском языке;
— интересы собственников Хабра, которые хотели бы расширить свой бизнес;
— и интересы тех авторов, которые хотели бы презентовать себя в англоязычном мире.
По поводу линейного алгоритма решения этой задачи — вы правы, если бы год назад мне об этом сказал бы кто-то другой, я бы тоже не поверил. Видимо, это тот редкий случай, когда много месяцев живешь внутри задачи, и наступает момент, когда становится прозрачным то, что раньше «не было видно». Могу «подтвердить», что Будда был прав, когда сидел в уединении и долго оставался в состоянии медитации. Да, алгоритм линейный. За все время исследования я несколько десятков миллионов раз проводил расчеты для различных значений n, и алгоритм оставался линейным. Диапазон значений n в исследовании менялся от 7 до пятидесяти миллионов.
По поводу возможности разработки полиномиального (а еще лучше — линейного) алгоритма для решения других сложных задач из множества NP-Complete, могу сказать следующее:
a) задача, которую я решал, связана с разработкой оптимального алгоритма формирования ветви поиска решения, в условиях меняющихся, с каждым шагом, ограничений.
b) решение удалось получить только после того, когда в результате многочисленных экспериментов (Computational Simulation) были установлены важные правила, которые являются неотъемлемым свойством данной задачи.
c) ряд задач, из множества NP-Complete можно попытаться решить, используя установленные правила, или иные правила «в том же русле». Есть большая вероятность того, что некоторые задачи будут успешно решены «по аналогии». Но лучше решить, а потом об этом сказать. А пока, это только уверенное предположение. Тут уместна поговорка:«Не скажи гоп, пока не перепрыгнешь». Поэтому следует подождать.
По поводу всяких призов. Признаюсь честно — я об этом не думал. Удовольствие, которое получаешь, решая сложные задачи «достаточно дорого стоят». Но тут важно другое. Дело в том, что одним наиболее важных, принципиальных выводов, которые были получены в результате исследования, состоит в том, что «данную задачу и задачи, ей подобные, невозможно решить на основе привычных методов математики: на основе определений, формулировки лемм и доказательства теорем. Эту и подобные ей задачи можно решить только на основе „алгоритмической математики“. Думаю, что нашим уважаемым коллегам математикам „это может не понравиться“. Однако это не ограничивает возможности математики, а наоборот — расширяет эти возможности через направление „алгоритмической математики“.
Вряд ли „вектор моих мыслей“ будет направлен в сторону каких либо премий. Это было бы не рационально и мешало бы работать. В настоящий момент, я больше нуждаюсь в том, чтобы устроиться на работу у кого нибудь на пол-ставки в качестве разработчика сложных и ответственных алгоритмов, или других сложных задач, где я могу принести реальную пользу. Уже 4 года нахожусь в Марселе, и, к сожалению, так и не удалось устроиться на работу. На простые задачи не хотел терять время, а сложные задачи они не хотели ставить. (Интересный факт: после долгого перерыва у меня вышла публикация, в которой, в позиции, где указывается место работы я честно написал „безработный“. Ответственный сотрудник редакции написал, что „безработные у нас не публикуются“ и что „безработный не может делать такие публикации“. Пришлось согласиться на фразу „независимый исследователь“. Так, что я теперь в статусе: безработный — независимый исследователь.
Чтобы эти 3.7 Gb не простаивали зря на вашем диске, предлагаю простую задачу для творчества и отдыха. Все числа в этом массиве, это числа от 1 до одного миллиарда, перечисленные в особой последовательности в соответствии с ограничениями, согласно условиям задачи. Возьмем последовательно любой миллион чисел из этого списка и разнесем их в обнуленный 1-мерный массив размером миллиард, т.е. в соответствующую ячейку запишем номер ячейки. Теперь, если «сжать» этот массив, т.е. убрать нули, то получим 1 миллион чисел, которые, как было сказано, меняются от 1 до одного миллиарда. Теперь, на основе «проекции» сведем изменение чисел от 1 до миллиарда к изменению — от 1 до миллиона. Таким образом мы получим все числа от 1 до миллиона, но имеющих особый порядок перечисления. Поставим каждому из этих миллионов чисел, некий «цвет» из последовательной гаммы цветов и выведем это на экран в виде изображения 1000 х 1000 пикселей. Учитывая, что в решении есть определенная гармония, то просматривая сотню произвольных таких изображений, вы найдете хотя бы одну, которая вам понравится. Это будет некоторой, своеобразной визуализацией определенной части общего решения. Я этого не делал, но думаю, что это будет весело. Успехов!