В 1987 году вышла дебютная научно-популярная книга Джеймса Глика «Хаос. Создание новой науки», впервые опубликованная на русском языке в переводе издательства «Амфора» и выложенная здесь. Эта книга оживила интерес к теории самоорганизующихся систем, сформулированной в середине XX века в работах Германа Хакена (1927-2024) из Штутгартского университета, посвящённых синергетике. Смежные исследования по физике неравновесных систем принадлежат Илье Романовичу Пригожину (1917 - 2003),  франко-американскому физику российского происхождения. В основе этих работ лежит идея о том, что существуют такие системы, нарастающая энтропия в которых постепенно выравнивается, и общая структура системы остаётся относительно неизменной, несмотря на то, что в отдельных частях системы энтропия продолжает нарастать. В том же 1987 году появилось удивительное исследование Пера Бака, Чао Танга и Курта Визенфельда, в котором они описали модель песчаной кучи.    

Феномен связан с изучением и моделированием самоорганизующихся систем и их устойчивости, а также смыкается с исследованием фракталов, степенных рядов и клеточных автоматов. В контексте фракталов эту тему рассматривал на Хабре уважаемый Андрей Заболотский @Browning в статье «Фракталы в песках или больше трёх не собираться». Если желаете вместо моего текста почитать строгое, но вполне популярное и увлекательное изложение данной темы — отсылаю вас к статье уважаемого Никиты Калинина «Песочная модель», размещённой на сайте МФТИ. Под катом я расскажу, как эта модель работает и какие неожиданные вопросы подбрасывает.

Данная модель описывается как совокупность совершенно одинаковых песчинок, которые распределены таким образом, как будто скапливаются в вершинах квадратной сетки (графа). Предельное количество песчинок в вершине кучи называется степенью кучи. Когда количество песчинок в вершине графа достигает величины степени, вершина переходит в неустойчивое состояние, а когда превышает – обваливается. Куча занимает больше места, чем до обвала, количество песчинок в вершинах, окружающих точку обвала, на какое-то время снова устанавливается ниже критического.

После многократного накопления и осыпания такого рода структуры совершенно разного рода приобретают фрактальные очертания.

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

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

Можно представить себе игру, в которой поле расчерчено на клетки, в которые случайным образом вбрасываются песчинки. Ёмкость одной клетки – восемь песчинок. Как только в клетку попадает любое количество песчинок сверх десяти, лишние песчинки вытесняются в соседние клетки. Если в соседних клетках из-за этого также накапливается избыточное количество песчинок, то перераспределение распространяется на соседние клетки и так далее, пока в каждой клетке вновь не останется 8 или менее песчинок.

В результате куча будет уплотняться в центральной части и расширяться на периферии, заполняя ранее пустовавшие области.

Интерес к самоорганизующейся критичности и соответствующие исследования проистекают из статистической физики. Открытие Бака, Танга и Визенфельда заключается в том, что сложные системы могут развиваться в направлении самоорганизующейся критичности без внешней настройки или какого-либо направляющего фактора. В таких системах локальные закономерности, описывающие, например, формирование отдельных барханов или дюн, прослеживаются как во всё более крупном, так и во всё более мелком масштабе (масштабная инвариантность) и подчиняются степенному закону.

Степенной закон — это математическая формулировка, характеризующая частоту определённых событий в зависимости от масштаба. Если частота некоторых событий или явлений сохраняется в любом рассматриваемом масштабе, то есть не зависит от степени увеличения, то мы имеем дело с фракталом. Одним из первых известных геометрических фракталов является «снежинка Коха», названная так в честь шведского математика Хельге фон Коха, исследовавшего её в 1904 году.

Фракталы повсеместно присутствуют в природе. Выше я упоминал о фрактальной природе береговых линий. Также фрактальная форма характерна для ветвящихся молний, горных гребней, кровеносных сосудов, нейронов и синапсов, а фрактальная форма капусты романеско уже стала мемом. Масштабная инвариантность развития песчаной кучи также указывала, что эта структура должна быть подобна фракталу, и подтверждение этой гипотезы нашла в 1996 году коллаборация из Белградского и Бостонского университетов под руководством Гарри Юджина Стенли. Оказалось, что модель песчаной кучи, нарастая и обрушиваясь, развивается по модели треугольника Серпинского — другого давно известного фрактала.

Главным фактором сброса критичности в модели песчаной кучи являются осыпи или обвалы (toppling). Каскадный обвал приводит к образованию лавины (avalanche). При этом обвал является сбросом не только избыточной массы, но и избыточной энтропии. После обвала энтропия старой кучи не увеличивается или даже снижается, энтропия (хаос) в окрестностях кучи возрастает.

При обрушении одной из вершин соседние вершины могут стать нестабильными. Если систему можно описать конечным связным графом, и количество песчинок в системе конечно, то после конечного количества обвалов все вершины станут стабильными. Модель песчаной кучи также именуется «абелевой», так как развитие системы и движение её к состоянию самоорганизующейся критичности не зависит от порядка насыпания песчинок и от конкретной последовательности обвалов (лавин).

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

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

Песок и сложность

Ранее на Хабре уважаемый @dionisdimetor попытался исследовать вопрос о том, что такое сложность в статье «Меры сложности: колмогоровская, вычислительная и эффективная сложность, логическая и термодинамическая глубина», где он находит интересные взаимосвязи между разными аспектами сложности, а в одном из разделов сравнивает сложность и упорядоченность. Ещё ближе к нашей теме перевод статьи Кевина Симлера «Сложные системы. Выход на критический уровень», размещённый на Хабре уважаемым @m1rko. Автор второй статьи схватывает характерную «инфекционную» или «заразную» характеристику сложности, указывая, что постепенно сложность распространяется в системе, в результате чего может достичь критического уровня — и система развалится. Равномерное распределение сложности в системе автор этой статьи сравнивает с иммунитетом и прослеживает важное отношение между нарастанием сложности и нарастанием энтропии. Пытаясь охарактеризовать сложность, следует отметить, что сложные системы обычно принимают вид иерархической «сети», «пирамиды» или «матрёшки», где интерфейсы между частями системы просты, надёжны и, как правило, единообразны, а отдельные части или уровни системы могут сильно отличаться. Модель песчаной кучи выделяется на фоне других сложных систем самоподобием от уровня к уровню, а также усложнением не через образование надстроек, а через образование фракталов. Если сложность можно сравнить с «масштабированием», то для большинства усложняющихся систем этот процесс будет «вертикальным» или «слоистым», а для песчаной кучи – «горизонтальным». Рост и обрушения песчаной кучи описываются в аппарате статистической физики, однако, как я подробнее расскажу в конце этой статьи, поведение реальных песчинок не полностью соответствует поведению абстрактных частиц в такой модели.

Песчаная куча не может самоорганизоваться в сложную устойчивую структуру, например, в микрочип, но в качестве математической абстракции очень удачно объясняет возникновение самоорганизации, а также эмулирует сложность. Модель песчаной кучи – это разновидность клеточного автомата; другой известный клеточный автомат — игра «Жизнь».

Правила кучи

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

• Среднюю и максимальную продолжительность каскада,

• «Радиус разлёта» типичного каскада,

• Спрогнозировать, где и когда возникнет большой каскад

Модель подчиняется двум основным правилам:

1.       Правило критичности: если кучка песчинок в любой из клеток вырастает выше  N (= 4, 5, подробнее об этом ниже), то неизбежно следует обвал. Допустим, если это значение равно 4, то в любой момент, когда мы остановим симуляцию, ни в одной из клеток не может быть более 4 песчинок.

2.      Правило обвала (осыпи): поскольку в систему постоянно досыпаются песчинки, в какой-то момент в некоторых клетках может оказаться не только 4, но и 5, и кратно больше песчинок. Чем сильнее такое мгновенное нарушение правила критичности, тем сильнее будет обвал. В математической модели обвал идёт «по сторонам света», но в реальности он идёт в любых направлениях, в том числе, по диагонали. Поскольку выше мы сочли все песчинки идентичными, они в одинаковом темпе и примерно в равном количестве осыпаются со всех сторон столешницы на пол.

Пара интересных реализаций

Учитывая, что динамика описанных процессов очень нелинейная, песчаную кучу сложно описать простыми циклическими алгоритмами с постепенным нарастанием сложности. Сложность нарастает и спадает непредсказуемо. Здесь я размещу 500-шаговую симуляцию заполнения кучи с максимальным N =4, построенную исследователем-робототехником Лео Медрано.  

Поведение этой модели удалось описать через обучение с подкреплением. Чаще всего обучение с подкреплением применяется для совершенствования навыков агентов (ботов) в играх или в смежных областях, где приходится учитывать поведение множества конкурирующих акторов, например, в высокочастотной торговле. Автор алгоритма запрограммировал агента так, чтобы он смог вбросить на поле максимальное количество песчинок, контролируя частоту обвалов и расстояние, на которое они распространяются. Причём обвал мог случайным образом последовать «вверх», «вниз», вправо или влево. Вот что у него получилось:

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

Автор взял за основу нейронную сеть REINFORCE/policy gradients. Она принимает на вход актуальное состояние кучи, а на выход выдаёт вероятностное распределение пяти возможных исходов (действий). На каждом шаге агент выбирает действие в соответствии с вышеописанной политикой, прогнозирует траектории движения песчинок и пытается предвосхищать новые состояния. Данный опыт заинтересовал меня тем, что автор совместил модель песчаной кучи с игрой на выживание. Агенту требуется не только наращивать количество песчинок в клетке, но и конкурировать с другими агентами, а также следить за тем, чтобы его не вынесло из игры. Внимательно проследив приведённую выше gif-картинку примерно на 200 шагов, можно заметить, что на поле долго остаются практически пустые области, в то время как в других областях наблюдается концентрация максимального числа песчинок (по 4) сразу в нескольких смежных клетках. Можно сказать, что при участии агентов песчаная модель сближается с клеточным автоматом и, вероятно, поддаётся описанию не только через обучение с подкреплением, но и через эволюционные алгоритмы. Полная реализация алгоритма, предложенная Медрано, выложена здесь.

Также обращу ваше внимание на альтернативную реализацию, предложенную Крисом Уэллонсом в 2020 году, написанную на Python. Весь код приведён в посте, однако она отличается от рассмотренных выше тем, что в данном случае куча насыпается от краёв поля к центру.

Этот вариант интересен тем, что в нём «агентская» составляющая отсутствует, и накопление кучи происходит спонтанно. Именно в таком исполнении куча начинает проявлять фрактальные свойства, а переход от одной стабильной конфигурации к другой является рекуррентным. После схода больших лавин и сброса избыточных песчинок куча возвращается к состоянию, похожему на предыдущее стабильное состояние.

Вопросов больше чем ответов

Как полагает знаменитый современный математик Джордан Элленберг, всё может быть ещё сложнее, и сходство песчаной кучи с клеточным автоматом является лишь поверхностным. Игру «Жизнь» можно подталкивать к сложному поведению, подбирая комплект глайдеров и корректируя исходные условия, тогда как модель песчаной кучи стремится к сложности (и неизменно — к фрактальному рисунку) сама по себе, без какого-либо внешнего воздействия на неё. Кроме того, как Элленберг указывает здесь, ни о каких N = 4 речь, по-видимому не идёт: куча начинает скатываться к хаосу после накопления в среднем 2,125 песчинок в клетке. Закономерности песчаной кучи роднят её не столько с движением дюн, сколько с кристаллизацией при снижении температуры. Нарастание плотности кучи – величина, обратная падению температуры при превращении жидкости в твёрдое тело. Возможно, именно этим и объясняется фрактальная форма снежинок. Однако температура в жидкости обычно равномерно снижается во всём объёме, то есть в жидкости не наблюдается аналога «температурных лавин». При этом в модели песчаной кучи лавины происходят регулярно и сближаются по активности и частоте с сейсмическими событиями. Чем выше магнитуда землетрясения, тем реже такое событие происходит, однако землетрясения схожей силы происходят регулярно относительно «своей весовой категории». Модель песчаной кучи описывает явления прямо на границе устойчивости и хрупкости и требует более подробного изучения в как можно более разнообразных средах.