Интуиция, головоломки и вычислимость

    В этой статье я хочу рассказать об одном парадоксе, который был подмечен давно, но который до сих пор является таинственной загадкой — одной из тех, о которых рассказывают преподаватели, чтобы заинтересовать студентов своим предметом. Этот парадокс непосредственно связан с проблемой искусственного интеллекта, поэтому данная статься опубликована в соответствующем блоге.

    Но об этом после, а для начала я расскажу, как уделал собственную программу в решении простой, на вид, головоломки из игры Still Life.



    Головоломка представляет собой пять барабанов с карточными мастями, таким образом каждый барабан может принимать четыре положения.



    При клике на один из барабанов поворачивается он сам и некоторые другие, то есть каждый барабан имеет свой паттерн. Причем сам поворачиваемый барабан вращается всегда по часовой стрелке, остальные же могут вращаться как угодно либо не вращаться вообще.

    Паттерны таковы:

         1  2  3  4  5
        --------------
    1:  +1 -1 +1  0  0
    2:  +1 +1  0  0 -1
    3:   0 -1 +1 -1  0
    4:  -1  0  0 +1 +1
    5:   0  0 -1 +1 +1
    


    Здесь +1 — это вращение по часовой стрелке, -1 — вращение против часовой стрелки, 0 — отсутствие вращения.

    Если обозначить состояния барабана числами 0 1 2 3, то начальное состояние системы будет: 0 2 0 3 1.

    Задача: найти последовательность поворотов барабанов, приводящую систему в состояние 0 0 2 0 0.

    Дело было вечером. Мне было лень ковыряться с головоломкой, и я решил написать программу, которая решала бы ее за меня. Но писать какую-то сложную программу мне тоже было лень, поэтому я решил использовать грубую силу. Очевидно, что решение задачи можно представить пятеричным числом некоторой неизвестной длины. Каждая цифра этого числа будет представлять выбор одного из барабанов на шаге, соответствующем разряду цифры. Тогда brute force сводится к перебору всех пятеричных чисел до тех пор, пока решение не будет найдено. Для каждой длины числа, количество итераций будет 5n, где n — длина числа. В худшем случае алгоритм отработает 5min(N), где min(N) — это минимальное количество шагов n, за которое можно решить задачу. Я предположил, что для данной задачи это значение невелико и запустил brute force. Я сходил на кухню, приготовил чай, выпил его (кружка чая у меня — это мера времени равная приблизительно 20-ти минутам), — brute force висел где-то на n = 10. Поняв, что это надолго, я решил все-таки поковырять головоломку сам. К своему удивлению, я подобрал комбинацию минут за десять, — brute force еще висел где-то на n = 10.

    По-началу я подумал, что решение можно найти быстрее, используя A*, но оказалось, что из-за заковырестости пространства поиска найти допустимую априорную оценку не так-то просто. Скажем, если брать за априорную оценку количество несовпадений текущего и конечного паттерна, такая оценка будет давать 3 всегда, когда до решения остался один шаг. Я уверен, что придумать допустимую априорную оценку можно, но доказательство того, что она допустима скорее всего нетривиально. Я так и не придумал апприорной оценки (пусть это будет задачкой для хабрасообщества), но, по правде говоря, не сильно этим занимался, потому что, при помощи коллег, нашел другое — более простое решение.

    Законектившись к офисной сети, я запустил brute force на рабочей станции и лег спать. На следующее утро в офисе я обнаружил, что мой Core i5 таки нашел решение на глубине 14 за какое-то немыслимое количество итераций. Заниматься сей фигней на работе не было времени, и я решил подключить коллективный разум, разослав задачу команде. Команда ответила вопросом: а можно ли поворачивать барабаны назад? По условию задачи как бы нельзя, но нетрудно доказать, что для каждого барабана три поворота вперед эквивалентны одному повороту назад. Таким образом, решение можно представить десятичным числом, заменив последовательности из трех одинаковых цифр одной. Меняя основание степени, мы уменьшаем показатель степени, а значит сокращаем количество итераций значительно. Модифицированный алгоритм находил решение за 300 с копейками итераций, на Core i5, за доли секунды.

    Да, задача в конечном итоге была решена алгоритмически, компьютером быстрее, чем способен любой человек, но вот в чем парадокс: я решил задачу, но при этом я не смог сформулировать алгоритм, которым я ее решал. Не то чтобы я его забыл — я точно знаю, что ни до, ни во время решения я не изобретал и не использовал какой-то четкой стратегии, то есть я решал задачу иррационально — методом тыка.

    Общую схему решения, однако, можно сформулировать как алгоритм:

    TARGET_STATE = [0, 0, 2, 0, 0] # Конечное состояние.
    
    intuition = Intuition.new # Безсознательное.
    solution = [] # Решение.
    current_state = [0, 2, 0, 3, 1] # Начальное состояние.
    
    while current_state != TARGET_STATE
      # Если комбинация выглядит плохо, возвращаемся к предыдущей.
      if !solution.empty? && intuition.bad_state?(current_state)
        current_state = do_step_back(current_state, solution.pop)
      else
        # Выбираем следующий шаг на основании ощущения его правильности.
        step = intuition.get_step(current_state)
        solution.push(step)
    
        # Делаем шаг, получая новое состояние.
        current_state = do_step(current_state, step)
      end
    end
    


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

    Это мой личный опыт, но существует другой, более яркий, пример данного парадокса.

    В математике существует такая классическая проблема — проблема алгоритмической разрешимости. Поскольку любой вычислительный процесс может быть реализован машиной Тьюринга, проблему можно сформулировать так: для некой задачи, можно ли создать машину Тьюринга, решающую ее. Существует множество проблем, для которых доказана невозможность их алгоритмического решения, и одна из таких проблем — это проблема остановки собственно машины Тьюринга. Говоря строго, дана последовательность бит, которая представляет собой конкатенацию некой произвольной машины Тьюринга и неких произвольных данных для подачи ей на вход (предполагается, что между машиной и данными есть непротиворечиво распознаваемый разделитель). Нужно построить такую машину Тьюринга, которая бы возвращала 1 если данная машина на данном вводе остановится и 0, если она уйдет в бесконечные вычисления. Доказано, что такую машину Тьюринга создать невозможно. Однако, на практике, если дать нетривиальную, но не очень длинную машину Тьюринга и последовательность бит математику, то в большинстве случаев он определит, остановится вычисление или нет. То же самое касается и других алгоритмически неразрешимых проблем. Их частные случаи разрешимы при помощи карандаша и бумаги, но в каждом случае решение получается разным, и все они несводимы к одному универсальному методу. Все дело в необходимости первичной гипотезы.

    Любая наука, какой бы точной она ни была, продвигается вперед гипотезами. Чтобы объяснить закон природы или доказать теорему, ученый первым делом выдвигает гипотезу, для чего обращается к интуиции. Далее, используя математический формализм, ученый доказывает или опровергает ее, и если гипотеза опровергнута, он выдвигает новую. В сущности, ученые пользуются тем же методом, что и любой человек при решении головоломки. Ученые точных наук в равной степени хорошо владеют формальными методами доказательства, но выдающиеся ученые отличаются от обычных тем, что гипотезы, порожденные их интуицией, оказываются вернее. На данный момент ни психологи, ни нейрофизиологи, ни тем более математики не могут дать ответа на вопрос: как возникает гипотеза, но лишь ответив на этот вопрос можно будет говорить о возможности (или невозможности) создания искусственного действительно интеллекта.
    Метки:
    Поделиться публикацией
    Комментарии 54
    • +5
      То ли я чего-то не понял, то ли операция «нажать на барабан» коммутативна, и всего вариантов 3^5 (да и их перебирать не надо).
      • +1
        Второй, четвёртый и пятый барабаны тыкнуть дважды, третий один раз. Если я правильно понял запись паттернов (а не транспонированно).
        • +3
          ой, трижды, а не дважды
        • +5
          Всего 5 секций и 4 масти. Теорема о числе комбинаций: 4^5.
          Почему вы взяли 3?
          • +8
            В военное время пи равно четырём, а воскресным вечером и тройка за четвёрку сойдёт.
            m^k :)
        • +21
          Ну, конкретно для этой задачи можно составить систему линейных уравнений, которая примитивно решается за N^3 ( можно и быстрей ), в то время как ваш способ имеет экспоненциальную сложность.
          А вообще не понял, о чем статья. О том, что интуиция рулит? Ну, так вы написали программу которая делает тупые действия, а не ищет решение данной проблемы, поэтому неудивительно, что она действовала так тупо.
          Разумеется, что программа написанная за 5 минут на коленке не может сравниться в изощренности с человеческим мозгом.
          • +5
            Согласен, линейные уравнения — первое что приходит в голову.

            from sympy import *
            
            A = Matrix([[1, -1,  1,  0,  0],
                        [1,  1,  0,  0, -1],
                        [0, -1,  1, -1,  0],
                        [-1, 0,  0,  1,  1],
                        [0,  0, -1,  1,  1]]).T
            
            b = Matrix([0,0,0,-3,-1])
            sol = A.LUsolve(b)
            
            print map(lambda a: a % 4, sol)
            
            [2, 1, 3, 3, 1]
            • –4
              Причем здесь линейные уравнения? Это поисковая задача.

              Решение:
              1 1 1 2 3 3 3 4 4 4

              Я немного ошибся с статье (давно дело было, детали забыл). Кратчайшее решение имеет длину не 14, а 10, но это сути не меняет.
              • +8
                При том, что решение может быть представлено как решение системы линейных уравнений.

                Как верно заметили выше — операции поворота барабанов коммутативны, то есть не имеет значения, в каком порядке крутить выбирать барабаны — важно только то, сколько раз каждый будет повернут. Если количество поворотов каждого из барабанов обозначить переменными xi — как раз СЛАУ из пяти уравнений и получится.
                • +3
                  Ну вы же сами изобразили повороты как +1 и -1, и получилась матрица. К тому же, через уравнения сразу находится кратчайшее решение.
                  PS накосячил с данными, там не [0,0,0,-3,-1] а [0, -2, 2, -3, -1]. И получается как раз [0, 3, 1, 3, 3]
                  • 0
                    ОК, я понял ваше решение (без объяснения оно выглядит странно). Еще я вспомнил, один наш бизнес-аналитик решил задачу в Excel-е. Он скорее всего использовал ваш метод.

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

                    Решая задачу методом тыка, человек (в данном случае я) перебирает комбинации, не задумываясь о коммутативности и тем более не решая систем уравнений. Я помню, что перебирал варианты, возвращаясь к предыдущим, и я точно не перебирал сотни комбинаций (это заняло бы больше времени). Барабанов в этой задаче не просто так пять, именно это число образов человек может одновременно держать в памяти, поэтому предсказать ходы более чем на один шаг здесь очень сложно. Парадокс заключается в том, что я делал ходы без всяких рассчетов, на основании внутреннего ощущения, и это дало результат. Объяснить это удачей сложно, потому что уж слишком малая здесь вероятность попасть пальцем в небо.

                    В конце концов, ваше решение тоже как-то пришло к вам в голову или вы его вспомнили, но тогда оно как-то пришло в голову кому-то другому. Не известно формального способа решить любую задачу, но задачи как-то решаются, и в этом заключается загадка.
                  • +2
                    Ваше «поисковое» решение нашло неоптимальный вариант. Кратчайшее решение имеет длину 10 (см. товарища hellman ниже) и находится как решение СЛУ [0;2;2;1;3]=K*M, где M — Ваша транспонированная матрица паттернов. Проблема не в отсутствии алгоритмов, а в Вашем неумении их использовать.
                    Любая задача математики может быть сформулирована как поисковая. «найти верное решение». Можно даже пространство поиска соорудить, а потом обвинять компьютер, что он дурак и ничего не может решить.
              • +8
                А в чем парадокс то?
                • НЛО прилетело и опубликовало эту надпись здесь
                • +1
                  У машины нет фантазии для гипотезы
                  • +1
                    Зато у машины есть псевдослучайные генераторы случайных чисел.
                    И, в зависимости от характера случайной примеси, их можно считать более или менее случайными.
                    А сказать, насколько делека фантазия от случайных чисел, пока нельзя — не хватает знаний в данной области )
                  • –2
                    Поиск в ширину без априорной оценки и есть brute force. Подбор числа можно реализовать оптимальней и распаралелить.
                    • –2
                      Это не будет брутфорсом, если не заходить повторно в уже посещенные состояния — это уже будет динамическое программирование, с асимптотическим временем работы O(M^N) = O(1024).
                      • –2
                        Прямой последовательный перебор тоже не заходит в пройденные состояния.
                        • +3
                          это называется распаралеленный обход в ширину :) и не спорьте, я прав
                          • 0
                            Согласен, это одно и тоже.
                          • –2
                            Если бы ваш перебор не заходил в пройденные состояния, он бы и одной секунды не проработал.

                            Потому что вообще всего состояний тысяча — ему просто негде было бы еще ходить :)
                            • 0
                              Он просто искал в другом пространстве состояний, не учитывая коммутативность операций.
                          • –1
                            в общих чертах да, но динамическое программирование в данной ситуации неприменимо — граф состояниий цикличен
                            • 0
                              А чем нам помешает его цикличность? Нам же незачем по циклам ходить.
                      • +2
                        Как несложно заметить, у нас всего 4^5 = 1024 вершины. Любой разумный алгоритм поиска решит задачу мгновенно.
                        Так что пример неудачный. Если Вы не смогли придумать эффективный алгоритм — это не значит, что его нет.

                        Общая же мысль довольно очевидна. Существование алгоритмически неразрешимых задач — один из краеугольных камней фундаментальной математики (с его помощью например доказываются теоремы Геделя о неполноте).
                        На практике, если «не очень длинная» машина Тьюринга — это машина Тьюринга длиной <= 100500 бит, то вполне есть алгоритм, который по каждой такой МТ скажет, останавливается она или нет)
                        • +1
                          Тоже не понял, в чем собственно парадокс. Приведенная задача с машиной Тьюринга не решается алгоритмически в общем случае, для частных случаев решение находится. С человеком так же, некоторые задачи веками ждут решения и не доказана их неразрешимость. Приведите хоть одну задачу, которая неразрешима алгоритмически, но решена человеком в общем виде.
                          Касательно математики — да, многие задачи изначально решались с привлечением интуиции, но любое доказательство принимается только тогда, когда имеет строго формальную форму. А за пределами математики полной достоверности нет вообще.
                          • 0
                            > Приведите хоть одну задачу, которая неразрешима алгоритмически, но решена человеком в общем виде.

                            Тест Тьюринга.
                            • 0
                              Не доказана алгоритмическая неразрешимость
                              • 0
                                Что такое тест Тьюринга? Только не надо давать ссылку на статью в википедии, дайте формальное определение.
                              • –1
                                Все алгоритмы придуманы людьми, но не придумано алгоритма, построения других алгоритмов, потому что невозможно создать алгоритм строящий сам себя.
                                • 0
                                  Простите, что Вы понимаете под «построить алгоритм»? Только формально, пожалуйста.
                                  • –1
                                    Построить алгоритм, значит построить вычислительный процесс, то есть машину Тьюринга.
                                    • 0
                                      Отлично, Вы описали формат выхода. А какой должен быть вход, и каким свойствам должен удовлетворять выход?
                                  • +1
                                    бездоказательное утверждение.
                                    а алгоритмы, строящие другие алгоритмы, существуют. пример — генетическое программирование
                                    • –1
                                      Моделирование эволюции — это совсем другая материя. Эволюционные процессы фундаментально недетерминированы, поэтому не могут считаться классическими вычислительными процессами.
                                      • 0
                                        Что за бред, простите? С каких пор вероятностные алгоритмы перестали быть алгоритмами, и уж тем более вычислительными процессами (которые, кстати, и есть «другая материя»)? Вы не хотите ли перечитать определение алгоритма и вычислительного процесса, прежде чем писать такую чушь?
                                        • 0
                                          «Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)

                                          «Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)

                                          «Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков)

                                          «Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)

                                          «Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)
                                          • 0
                                            Детерминированный порядок выполнения и детерминированность алгоритма — не одно и то же. Если Вы помните, у Кнута второй том посвящен вероятностным алгоритмам. Ни в одном из приведенных определений нет ни слова об эквивалентности алгоритма вычислительным процессам и отрицания возможности использования случайных величин.
                                            • 0
                                              Хорошо, тогда как получить криптографическое случайное число, не имея источника энтропии?
                                              • 0
                                                Начнем с того, что Вы понимаете под источником энтропии. Про генераторы псевдослучайных чисел слышали?
                                                • 0
                                                  С псевдослучайными числами есть одна проблема — рано или поздно они начинают повторяться и в долгосрочной перспективе процесс все равно становится детерминорованным.

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

                                                  Если нам нужны случайные данные для вычисления со сколь угодно большим количеством обращений к генератору случайных чисел, нам нужен генератор действительно случайных чисел, то есть криптографический генератор.
                                                  • +1
                                                    Последовательность случайных чисел, взятых извне, может считаться исходными данными алгоритма. Это никак не противоречит определению алгоритма. При этом сам алгоритм не изменится. Это и есть «детерминированный порядок выполнения» — структура алгоритма не изменяется в зависимости от входных данных. Это могут быть даже не случайные числа. Представьте машину Тьюринга, которая читает ленту нулей и единиц и останавливается тогда, когда встретит первую единицу на ленте. Длина и содержание ленты при этом никак не влияет на структуру самой машины Тьюринга. Любые взятые извне данные в принципе могут считаться случайными
                                            • 0
                                              выделяемое Вами слово определённость говорит только о конечности множества операций, составляющих носитель алгоритма
                                              • 0
                                                Не совсем

                                                "Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного".
                                                • 0
                                                  И в чем противоречие? если считать начальное значение генератора псевдослучайных чисел или само случайное число входными данными, вероятностный алгоритм выродится в обычный детерминированный
                                                  • 0
                                                    Кстати, от куда это определение? Оно не совсем верно в части В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. Это не так, если нет оговорки, что различные реализации используют одно мультимножество операций и на множестве операций определено транзитивное отношение.
                                                • +2
                                                  А давайте теперь вспомним строгое, принятое в математике определение алгоритма (точнее вычислимой функции) (там их несколько, но все они в смысле вычислимости эквивалентны).
                                                  Итак. Функция называется вычислимой, если существует вычисляющая ее машина Тьюринга. В понятии МТ случайности нет, да она там и не нужна.
                                                  Хотя есть и вариант со случайностью. Как правило, он реализуется путем дополнительного входа, содержащего «результаты бросания монетки».

                                                  Обычное требование к вероятностному алгоритму — он дает правильный ответ чаще, чем неправильный. В этом случае наличие случайности на вычислимость никак не влияет. Ибо никто не мешает нам перебрать все возможные варианты выпадения монетки.
                                      • +2
                                        Ксати, приведенный «универсальный алгоритм, которым любой обычный человек решает любую головоломку» по-сути есть эвристический поиск в пространстве состояний. Вы просто не определили эвристики «хорошая комбинация» и «оценка состояния».
                                        • +6
                                          Складывая числа от 1 до 100 большинство людей тупо сделают цикл 1+2+3+...+100, хотя маленький Гаусс доказательно советовал решение в две операции (1+100)*50. Ничего не напоминает? Тупой перебор vs СЛАУ+метод все того же Гаусса.

                                          P.S. Теги к заметке — это такая тонкая ирония?

                                          • +3
                                            Описанную ситуацию можно назвать парадоксом, если считать компьютер волшебной палочкой, а не высокотехнологичным молотком. :)
                                            • НЛО прилетело и опубликовало эту надпись здесь

                                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.