jsingh6413 / conwaycnn

Conway's Game of Life grid prediction using CNN

ConwayCNN

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

Предисловие

Клеточный автомат Конвэя или же "Conway's Game of Life" - автомат, подчиняющийся простым правилам: клетки могут быть либо "живыми", либо "мёртвыми". Каждую эпоху клетки умирают или рождаются по следующим правилам: если у пустой клетки было три живых соседа, в ней зарождается жизнь; если у живой было больше двух живых соседей, она выживает, а иначе - умирает.

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

Также у автомата есть множество усложнений и модификаций. Мы будем рассматривать только замкнутое игровое поле: его первая "строчка" связана с последней, а правый "столбец" - с левым.

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

Почему именно эта задача?

Задача была предложена на Kaggle в 2020 году как альтернативное вступительное испытание в Ozon Masters. Я смог принять участие в этом турнире буквально в последние дни его проведения, так что решил сосредоточиться на быстром и легковесном решении, не требующем глубокого анализа начальных условий генерации состояний.

В обучающих данных содержится само поле на итерации $n$, его состояние в момент $n-k$ и само значение $k$. В тренировочных - только состояние $n$ и число итераций $k$. Требуется определить состояние автомата в момент $n-k$.

Архитектура, проблемы и идеи

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

Учитывая, что поле замкнуто, а максимальная удалённость по итерациям - шесть эпох, базовая архитектура приняла следующий вид:

1. Массив, содержащий значение поля, расширяется на семь клеток в каждую сторону (расширение типа wrap).
2. Расширенный массив подаётся на вход компактной свёрточной сети, которая делает предсказание ровно на одну эпоху.
3. Создаются ещё пять моделей, идентичных базовой за исключением размерности входных данных: вместо двумерного массива с состоянием поля сети принимают два таких массива, содержащих состояние в момент $n$ и в момент $(n-k+1)$.
4. Новые модели обучаются последовательно: для каждой $i$-ой модели сначала делается предсказание при помощи $(i-1)$-ой модели, затем это предсказание объединяется с оригинальными данными и подаётся на вход сети.

Таким образом, любая $i$-ая модель, кроме первой, опирается на результат предыдущей. Конечно, здесь стоило бы подавать на вход каждой последующей модели предсказания всех её предшественниц, а также увеличивать объём сети, но ограничения на время обучения и выполнения на CPU сделали такой вариант невозможным.

Из-за отсутствия времени также не было тюнинга гиперпараметров модели: не настраивался даже порог бинаризации, хотя при настройке этого параметра можно было бы устанавливать уровень "доверия" к каждой следующей эпохе. Также следовало бы использовать регуляризацию при построении сетью состояний, из которых нельзя было бы перейти к текущему.

Стоит упомянуть, что при аккуратном использовании рекуррентных слоёв можно было бы попытаться добиться лучшего результата и уменьшить и размерность, и число итоговых моделей. Однако при использовании рекуррентного замыкания качество оставляло желать лучшего, из чего и был сделан вывод о необходимости нескольких моделей.

Что дальше?

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

Данные для обучения и предсказания доступны на Kaggle.