Читать книгу "Вычислительное мышление. Метод решения сложных задач - Питер Макоуэн"

Паноптикум жизни

Конвей обнаружил, что некоторые комбинации являются статичными. Они остаются в одном и том же месте игрового поля без изменений, поэтому он назвал их натюрмортами — как, например, змею на рис. 57. Какие еще простые начальные комбинации, относящиеся к натюрмортам, вам удастся найти?

Некоторые шаблоны меняют форму, проходя через фиксированный набор вторичных шаблонов, в конце концов возвращаются к исходному варианту — и снова начинают бесконечный повторяющийся цикл. Их назвали осцилляторами. Например, очень простой осциллятор, так называемая мигалка, показан на рис. 58. Если начать с набора мигалок, которые находятся на достаточном расстоянии, чтобы не мешать друг другу, вы создадите замечательные мерцающие узоры. Такие комбинации из группы осцилляторов называются пульсарами — по имени необычных звезд, на которых с определенной периодичностью происходят всплески энергии.

Коллега Конвея Ричард Гай натолкнулся на удивительные фигуры, которые сохраняют форму, но передвигаются по сетке. Их назвали планерами (рис. 59). В целом движущиеся конфигурации называют космическими кораблями.

В игре «Жизнь» даже можно имитировать логические вентили. Как мы говорили выше, это базовые составляющие компьютера. Их делают из транзисторов, нейронов и… из клеток игры «Жизнь». Это значит, что, располагая достаточно большой сеткой, можно создать на ней работающий компьютер — исключительно из клеток, следующих этим простым правилам.

Моделируем новые миры

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

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

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

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

Игры, в которые играют люди

Любите играть в слова?

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

БУСЫ, ХЛЕБ, БАНЯ, ПЛУГ, СНЕГ, ГАТЬ, УРОН, ОРЕХ, МАРС.

Вот правила:

1. Первый игрок выбирает слово из списка, вычеркивает его из списка и записывает.

2. Второй игрок делает то же самое с еще не вычеркнутым словом.

3. Игроки продолжают ходить до тех пор, пока кто-нибудь не выиграет. Победителем становится тот, кто первый сможет собрать три слова с одной и той же буквой.

Например, игра может пойти так:

игрок 1 берет БУСЫ,

игрок 2 берет ХЛЕБ,

игрок 1 берет БАНЯ,

игрок 2 берет ГАТЬ,

игрок 1 берет ПЛУГ,

игрок 2 берет ОРЕХ,

игрок 1 берет УРОН...

…и выигрывает, собрав БУСЫ, ПЛУГ и УРОН. Это три слова, в которых есть буква У.

Сыграйте несколько партий, чтобы понять принцип. А потом читайте дальше — и найдете хитрый способ выигрывать… а может, догадаетесь сами? Мы вернемся к этому чуть позже.

ПОДСКАЗКА. Подумайте, как расположить слова в квадрате, чтобы было легче заметить выигрышный набор слов. Вы уже знаете очень похожую игру!

Как обыграть человека

Мы знаем, что компьютеры творят чудеса, и одно из таких чудес — умение выигрывать у людей в игры. Компьютер может победить чемпиона мира по шахматам, но как? А может ли обычный листок бумаги действовать столь разумно, что будет играть так же хорошо, как человек? Да. Если правила будут верными. И сейчас у вас есть шанс сыграть против такого листка и посмотреть, что получится.

Крестики-нолики — популярная игра на основе сетки, позволяющая быстро развлечься и посоревноваться. Давайте сыграем — и заодно рассмотрим базовые принципы, благодаря которым компьютеры могут участвовать в играх. В игре «Крестики-нолики» участники по очереди делают ход на поле 3×3. Один ставит нолики, другой — крестики. Сделать ход — значит написать X или 0 в пустой клетке на доске. Первый, кто поставит три символа в одну линию по горизонтали, вертикали или диагонали, выигрывает. Если никому не удастся это сделать, получается ничья.