САЙТ НИКОЛАЯ РУСИНА -

- ЖИВОПИСЬ, СКУЛЬПТУРА, ПРОЗА И ЕЩЕ КОЕ ЧТО


ГЛАВНАЯ


ОСТАВЬТЕ ВАШИ КОММЕНТАРИИ
НА СТРАНИЦЕ НАШЕГО ФОРУМА
ЗАНИМАТЕЛЬНЫЕ ЗАДАЧИ

ИГРА "ЖИЗНЬ"
Дж.Конуэя



ИГРА











Игра "Жизнь", придуманная американским математиком Дж. Конуэем, уже несколько десятков лет привлекает к себе пристальное внимание. Созданы десятки программ, реализующих эту игру чуть ли не на всех типах компьютеров, написаны тысячи статей, десятки сайтов в интернете посвящены этой игре. Мы предлагаем Вам несколько страниц из книги Мазтина Гарднера "Крестики-нолики" (перевод с английского И. Е. Зино). .....Настоящая же глава посвящена самому знаменитому детищу Конуэя-игре, которую сам Конуэй назвал "Жизнь". Для игры "Жизнь" вам не понадобится партнер - в нее можно играть и одному. Возникающие в процессе игры ситуации очень похожи на реальные процессы, происходящие при зарождении, развитии и гибели колоний живых организмов. По этой причине "Жизнь" можно отнести к быстро развивающейся категории так называемых "моделирующих игр" - игр, которые в той или иной степени имитируют процессы, происходящие в реальной жизни. Для игры "Жизнь", если не пользоваться ЭВМ, вам понадобится довольно большая доска, разграфленная на клетки, и много плоских фишек двух цветов (например, просто несколько наборов обычных шашек небольшого диаметра или одинаковых пуговиц двух цветов). Можно также воспользоваться доской для игры в го, но тогда вам придется раздобыть маленькие плоские шашки, которые свободно умещаются в ячейках этой доски. (Обычные камни для игры в го не годятся потому, что они не плоские.) Можно также рисовать ходы на бумаге, но значительно проще, особенно для начинающих, играть, переставляя фишки или шашки на доске. Основная идея игры состоит в том, чтобы, начав с какого-нибудь простого расположения фишек (организмов), расставленных по различным клеткам доски, проследить за эволюцией исходной позиции под действием "генетических законов" Конуэя, которые управляют рождением, гибелью и выживанием фишек. Конуэй тщательно подбирал свои правила и долго проверял их "на практике", добиваясь, чтобы они по возможности удовлетворяли трем условиям: не должно быть ни одной исходной конфигурации, для которой существовало бы простое доказательство возможности неограниченного роста популяции; в то же время должны существовать такие начальные конфигурации, которые заведомо обладают способностью беспредельно развиваться; должны существовать простые начальные конфигурации, которые в течение значительного промежутка времени растут, претерпевают разнообразные изменения и заканчивают свою эволюцию одним из следующих трех способов: полностью исчезают (либо из-за перенаселенности, т. е. слишком большой плотности фишек, либо, наоборот, из-за разреженности фишек, образующих конфигурацию); переходят в устойчивую конфигурацию и перестают изменяться вообще или же, наконец, выходят на колебательный режим, при котором они совершают некий бесконечный цикл превращений с определенным периодом. Короче говоря, правила игры должны быть такими, чтобы поведение популяции было достаточно интересным, а главное, непредсказуемым. Генетические законы Конуэя удивительно просты. Прежде чем мы их сформулируем, обратим внимание на то, что каждую клетку доски (которая, вообще говоря, считается бесконечной) окружают восемь соседних клеток: четыре имеют с ней общие стороны, а четыре другие - общие вершины. Правила игры (генетические законы) сводятся к следующему:

выживание

. Каждая фишка, у которой имеются две или три соседние фишки, выживает и переходит в следующее поколение;

гибель

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

рождение

. Если число фишек, с которыми граничит какая-нибудь пустая клетка, в точности равно трем (не больше и не меньше), то на этой клетке происходит рождение нового "организма", т. е. следующим ходом на нее ставится одна фишка. Важно понять, что гибель и рождение всех "организмов" происходят одновременно. Вместе взятые, они образуют одно поколение или, как мы будем говорить, один "ход" в эволюции начальной конфигурации. Ходы Конуэй рекомендует делать следующим образом: начать с конфигурации, целиком состоящей из черных фишек; определить, какие фишки должны погибнуть, и положить на каждую из обреченных фишек по одной черной фишке; найти все свободные клетки, на которых должны произойти акты рождения, и на каждую из них поставить по одной фишке белого цвета; выполнив все эти указания, еще раз внимательно проверить, не сделано ли каких-либо ошибок, затем снять с доски все погибшие фишки "(т. е. столбики из двух фишек), а всех новорожденных (белые фишки) заменить черными фишками. Проделав все операции, вы получите первое поколение в эволюции первоначальной конфигурации. Аналогичным образом получаются и все последующие поколения. Теперь уже ясно, для чего нам нужны фишки двух цветов: поскольку рождение и гибель "организмов" происходят одновременно, новорожденные фишки никак не влияют на гибель и рождение остальных фишек, и поэтому, проверяя новую конфигурацию, необходимо уметь отличать их от "живых" фишек, перешедших из предыдущего поколения. Допустить ошибку, в особенности, если вы играете впервые, очень легко. Со временем вы будете делать все меньше и меньше ошибок, однако даже опытные игроки должны очень внимательно проверять каждое новое поколение перед тем, как снимать с доски погибшие фишки и заменять черными фишками новорожденные белые. Начав игру, вы сразу заметите, что популяция непрестанно претерпевает необычные, нередко очень красивые и всегда неожиданные изменения. Иногда первоначальная колония организмов постепенно вымирает, т. е. все фишки исчезают, однако произойти это может не сразу, а лишь после того, как сменится очень много поколений. В большинстве своем исходные конфигурации либо переходят в устойчивые (последние Конуэй называет "любителями спокойной жизни") и перестают изменяться, либо навсегда переходят в колебательный режим. При этом конфигурации, не обладавшие в начале игры симметрией, обнаруживают тенденцию к переходу в симметричные формы. Обретенные свойства симметрии в процессе дальнейшей эволюции не утрачиваются, а симметрия конфигурации может лишь обогащаться. Конуэй высказал гипотезу, согласно которой не существует ни одной начальной конфигурации, способной беспредельно расти. Иначе говоря, любая конфигурация, состоящая из конечного числа фишек, не может перейти в конфигурацию, у которой число фишек превосходило бы некий конечный верхний предел. Это, наверное, наиболее глубокая и самая сложная задача, возникающая в игре "Жизнь". В свое время Конуэй предлагал премию в 50 долларов тому, кто до конца 1970 г. первым докажет или опровергнет его гипотезу. Опровергнуть предположение Конуэя можно было бы, например, построив конфигурацию, к которой, следуя правилам игры, все время приходилось бы добавлять новые фишки. К ним можно отнести, в частности, "ружье" (конфигурацию, которая через определенное число ходов "выстреливает" движущиеся фигуры вроде "глайдера", о котором мы еще будем говорить) или "паровоз, пускающий дым из трубы" (движущаяся конфигурация, оставляющая за собой "клубы дыма"). Результаты соперничества за объявленный Конуэем приз обсуждаются в следующей главе. Рассмотрим теперь, что же происходит с некоторыми простыми конфигурациями. Одиночная фишка, а также любая пара фишек, где бы они ни стояли, очевидно, погибают после первого же хода. Исходная конфигурация из трех фишек (мы будем называть ее триплетом), как правило, погибает. Выживает триплет лишь в том случае, если, по крайней мере, одна фишка граничит с двумя занятыми клетками. Пять триплетов, не исчезающих на первом же ходу, изображены на рис. 1. (При этом ориентация триплетов, т. е. как они расположены на плоскости - прямо, "вверх ногами" или косо, не играет никакой роли.) Первые три конфигурации (а, б, в) на втором ходу погибают. Относительно конфигурации в заметим, что любой диагональный ряд фишек, каким бы длинным он ни оказался, с каждым ходом теряет стоящие на его концах фишки и, в конце концов, совсем исчезает. Скорость, с которой шахматный король перемещается по доске в любом направлении, Конуэй называет "скоростью света". (Причины этого станут понятны в дальнейшем.) Пользуясь этой терминологией, можно сказать, что любой диагональный ряд фишек распадается с концов со скоростью света. Предлагаем программу, написанную на языке Visual Basic 4.0 и реализующую игру Жизнь: ----------------------------------- Option Explicit Dim X, Y, Z, M, N, Sum As Integer Dim X1, Y1, M1, N1 As Integer Dim Pole(100, 100) As Integer Dim Pole1(100, 100) As Integer Dim Pole3(100, 100) As Integer Dim XM, YM, XP, YP As Integer Dim a1, a2, a3, a4, a5, a6, a7, a8, a9 As Integer Private Sub cmdPusk_Click() ScaleMode = 3 ' Set scale to pixels. Pole(3, 7) = 1 Pole(4, 5) = 1 Pole(4, 7) = 1 Pole(5, 6) = 1 Pole(5, 7) = 1 For M = 0 To 100 Step 1 Line (0, 10 * M)-(Width, 10 * M), RGB(0, 255, 0) Next M For N = 0 To 100 Step 1 Line (10 * N, 0)-(10 * N, Height), RGB(0, 255, 0) Next N For X = 1 To 99 Step 1 For Y = 1 To 99 Step 1 If Pole(X, Y) = 1 Then FillStyle = 0 FillColor = QBColor(4) Circle (5 + 10 * (X - 1), 5 + 10 * (Y - 1)), 5 Else End If Next Y Next X For Z = 1 To 100 Step 1 For X = 1 To 30 Step 1 For Y = 1 To 30 Step 1 XM = X - 1 XP = X + 1 YM = Y - 1 YP = Y + 1 a1 = Pole(XM, YM) a2 = Pole(X, YM) a3 = Pole(XP, YM) a4 = Pole(XM, Y) a6 = Pole(XP, Y) a7 = Pole(XM, YP) a8 = Pole(X, YP) a9 = Pole(XP, YP) Sum = a1 + a2 + a3 + a4 + a6 + a7 + a8 + a9 If Pole(X, Y) = 1 Then GoTo Line1 Else GoTo Line2 Line1: If Sum = 2 Or Sum = 3 Then Pole1(X, Y) = 1 Else Pole1(X, Y) = 0 End If GoTo Line3 Line2: If Sum = 3 Then Pole1(X, Y) = 1 Else Pole1(X, Y) = 0 End If Line3: Next Y Next X For X1 = 1 To 30 Step 1 For Y1 = 1 To 30 Step 1 Pole(X1, Y1) = Pole1(X1, Y1) Next Y1 Next X1 For X1 = 1 To 99 Step 1 For Y1 = 1 To 99 Step 1 If Pole1(X1, Y1) = 1 Then GoTo Line4 Else GoTo Line5 Line4: FillStyle = 0 FillColor = QBColor(4) Circle (5 + 10 * (X1 - 1), 5 + 10 * (Y1 - 1)), 5 GoTo Line6 Line5: FillStyle = 0 FillColor = QBColor(7) Circle (5 + 10 * (X1 - 1), 5 + 10 * (Y1 - 1)), 5 Line6: Next Y1 Next X1 Next Z End Sub ---------------------------------------
©2010-2017 Сайт Николая Русина.