Как стать автором
Обновить

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

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

Но об этом после, а для начала я расскажу, как уделал собственную программу в решении простой, на вид, головоломки из игры 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, если она уйдет в бесконечные вычисления. Доказано, что такую машину Тьюринга создать невозможно. Однако, на практике, если дать нетривиальную, но не очень длинную машину Тьюринга и последовательность бит математику, то в большинстве случаев он определит, остановится вычисление или нет. То же самое касается и других алгоритмически неразрешимых проблем. Их частные случаи разрешимы при помощи карандаша и бумаги, но в каждом случае решение получается разным, и все они несводимы к одному универсальному методу. Все дело в необходимости первичной гипотезы.

Любая наука, какой бы точной она ни была, продвигается вперед гипотезами. Чтобы объяснить закон природы или доказать теорему, ученый первым делом выдвигает гипотезу, для чего обращается к интуиции. Далее, используя математический формализм, ученый доказывает или опровергает ее, и если гипотеза опровергнута, он выдвигает новую. В сущности, ученые пользуются тем же методом, что и любой человек при решении головоломки. Ученые точных наук в равной степени хорошо владеют формальными методами доказательства, но выдающиеся ученые отличаются от обычных тем, что гипотезы, порожденные их интуицией, оказываются вернее. На данный момент ни психологи, ни нейрофизиологи, ни тем более математики не могут дать ответа на вопрос: как возникает гипотеза, но лишь ответив на этот вопрос можно будет говорить о возможности (или невозможности) создания искусственного действительно интеллекта.
Теги:
Хабы:
+27
Комментарии 54
Комментарии Комментарии 54

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн