Max Home IndustryЭто забавный проект, который вполне может предложить интересные продолжения. И вам не обязательно быть экспертом в игре в жизнь, чтобы присоединиться к ней.
Клеточные автоматы очаровательны, потому что они вызывают такое сложное поведение из таких простых правил. «Игра жизни GoL» Джона Конвея, пожалуй, самая известная, и она удивительно сложна, учитывая, насколько просты ее правила. Что еще более удивительно, так это время и усилия, которые люди вкладывают в поиск конфигураций клеток, которые достигают определенного поведения.
Если вы возьмете изображение и оцифруете его в двоичном формате, вы можете рассматривать это как отправную точку для конфигурации GoL. Возьмем, к примеру, Мону Лизу. Оцифровка дает:
Затем вы можете запустить моделирование и посмотреть, что произойдет. Поскольку блоки живых клеток рядом друг с другом умирают на следующем этапе, вы почти сразу получаете контур, а затем конфигурации, которые медленно распадаются и выглядят все менее и менее похожими на оригинал.
А как насчет проблемы поиска конфигурации, которая превращается в хорошо известный образ? Это проблема, которую Кевин Галлиган решает в своем личном блоге. Если вы думаете, что это легко, то вы, вероятно, не заметили, что GoL не является обратимым клеточным автоматом. Вы не можете легко вернуться во времени от конфигурации, которую вы хотите, к более ранней конфигурации, которая эволюционирует в нее. Однако вы можете написать логическое уравнение, которое дает состояние сетки в терминах того, каким она должна быть для генерации текущего состояния. Например, если ячейка жива, то, если она была жива в более раннем состоянии, у нее должно быть 2 или 3 живых соседа, но если она мертва, то 3 из ее соседей должны быть живы. Вы можете записать это в виде логического уравнения, включающего состояния ячеек.
Большая проблема в том, что это уравнение большое и сложное, поэтому его нужно решить. Вы должны найти значения всех переменных, которые делают уравнение истинным. Если у вас есть поверхностное знакомство с теорией информатики, вы узнаете, что это проблема SAT, и есть автоматические решатели SAT, которые мы можем использовать. Однако SAT — это проблема NP Complete, и это делает ее одной из тех проблем, которые очень быстро становятся слишком серьезными для решения. Тем не менее, вы можете работать с 400 ячейками примерно за 250 секунд.
Таким образом, вы можете взять состояние и записать логическое уравнение для состояния, которое перерастет в него за один временной шаг. Затем вы можете взять это состояние, записать его логическое уравнение и решить для состояния, которое было до него, и так далее. Задача решена!
Не совсем. На каждом этапе может быть несколько решений, а решения быть не может вообще. Некоторые конфигурации называются «Садами Эдема», потому что вы можете доказать (что нелегко), что нет конфигурации, которая эволюционирует в них. Кажется, что они встречаются чаще, чем вы можете себе представить, и, следовательно, их трудно избежать. Все опробованные образы, кроме одного, привели к созданию Эдемского сада на самом первом шаге назад.
Возвращаясь к оцифрованной Моне Лизе, как вы думаете, как выглядит конфигурация, которая превращается в нее всего за один шаг?
Не так много следов оригинала!
Взгляните на блог Кевина, чтобы увидеть больше примеров.
Почему так много Эдемских садов?
Даже если вам это не нравится, по крайней мере, вы теперь знаете, для чего можно использовать решатель SAT.
Майк Джеймс — автор «Руководства по теории для программиста», которое, как следует из подзаголовка «Объяснение великих идей», ставит своей целью представить фундаментальные идеи информатики, включая SAT, в неформальной и в то же время информативной форме.