Игры с Чипом

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

— Это нечестно. Ты же знаешь, что в те сказочные времена не было ни радио, ни телефонов и даже портновский сантиметр был редкостью. Нет, единственный выход - мерить туфельку на ногу.

— Да ведь это та же самая задача! — воскликнул Сережа, немного подумав.

— Я бы...

— Тсс! Пусть лучше ребята пришлют нам программу поиска Золушки. Я думаю, что без нашей помощи принц ее просто не найдет, и сказка кончится плохо!

— Ну, хорошо, а как же построить девушек по размеру туфельки?

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

— Конечно, нужно только изменить программу. Но ведь придворных дам много. Нельзя ли эту задачу как-нибудь распараллелить?

— Молодец! Не думал я, что ты догадаешься. Но пусть ребята поломают над этой задачей головы сами, а я дам только легкий намек. Предположим, что мы разделили девушек на 2 группы и каждую из них построили. Если ты, используя предыдущие задачи, придумаешь, как соединить эти два строя, ты найдешь самый быстрый метод сортировки, который называется метод «вставок-слияний». А тогда ты не только поможешь королевской женитьбе, но и быстро справишься с генеральной уборкой.

ОТ РЕДАКЦИИ.

Ребята, поможем Сереже решить задачу Чипа? Пришлите нам свои программы, а на конверте напишите: "Где Золушка?» Лучшие программы мы напечатаем.

Бурная жизнь Фатландии 

— Чип, давай во что-нибудь поиграем. — предложил Сережа своему другу, — только на этот раз давай играть по-честному)

— А я всегда играю честно! — возмутился Чип. — Жульничать умеет только очень большой компьютер, да и то с помощью программы искусственного интеллекта. А нам, маленьким машинкам, это просто не по силам.

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

— Понимаю, ты хочешь, чтобы я показал тебе игру без выигрышной стратегии?

— Да. что-нибудь вроде шахмат, шашек или крестиков-ноликов на бесконечном поле, только новенькое.

— Ну, для крестиков-ноликов выигрышная стратегия есть, при правильной игре всегда побеждает крестик. Только алгоритм не такой простой, как в игре со спичками или в игре «орел-решка». Он придуман в Японии, занимает три увесистых тома и состоит в переборе большого числа позиций. Это больше похоже на математическое доказательство, а не на руководство к действию.

— А что за выигрышный алгоритм в игре «орел-решка»?

— Очень простой: не играть вообще.

— Чип, а есть машины, которые умеют играть в крестики-нолики по выигрышному алгоритму?

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

— Ну вот, Чип, опять ты сказки рассказываешь! Разве может машина придумать что-нибудь сама? Она знает только то, что есть в программе.

— Не совсем так. Например, для шашек уже существует программа, думающая, «как человек». Ее идея в том, чтобы компьютер все время учился: после каждого хода сравнивал результаты своих прошлых прогнозов с тем, что на самом деле происходит, и в следующий раз делал более точные прогнозы. Такие прогнозы заменяют ему перебор ходов: он посмотрит несколько ходов вперед, а дальнейшие варианты предугадывает. После каждого хода он прогнозирует все лучше и лучше. Ему ничего не стоит хранить в памяти все сыгранные партии и извлекать из них уроки.

— А как он это делает? Ведь алгоритм прогноза надо было написать заранее?

— Что-то, конечно, надо было написать заранее, в этом и состоит искусство программиста, но можно сделать так, чтобы программа сама себя исправляла.

— Ладно, хватит, Чип, я устал от разговоров. Давай все-таки поиграем.

— Хорошо, давай сыграем в машинную игру под названием «Жизнь». Условия игры такие. Колония бактерий живет на бескрайних просторах Фатландии. Предположим, что эта страна разбита на клетки, как листок из тетради. В каждой клетке только одна бактерия. Соседями одной клетки считаются все клетки, расположенные рядом по горизонтали, вертикали и диагонали. Мерой времени у нас служит смена поколений бактерий, и колония будет жить по таким законам:

1. Если у клетки меньше двух соседей, то бактерия в ней гибнет от скуки.

2. Если у клетки больше трех соседей, то бактерия в ней гибнет от тесноты.

3. Если у пустой клетки ровно три соседа, то в ней рождается новая жизнь.

Только не применяй эти правила поочередно к каждой клетке, бактерии рождаются и гибнут по общему сигналу.

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

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

— Чип, постой. Я не понимаю. Ведь та клетка, которая была сбоку, умерла, значит, у верхней средней клетки нет трех соседей.

— Я же сказал, они умирают и рождаются только по общему сигналу, в Фатландии жесткий порядок. Ты сначала найди все возможные изменения в своей колонии, а потом уж разом меняй.

— Понял, понял. Тогда в следующем поколении наша колония станет такой: 

а потом опять

и так далее.

— Молодец! А колония

вообще никогда не меняется, но в Фатландии случаются и более невероятные приключения. Поиграй, например, с обыкновенным крестиком

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

— Чип! А давай напишем программу для «жизни»!

— Давай, только пусть это будет не простой подсчет соседей, а программа, которая ищет игровые ситуации. Например, если колония зациклится (повторит прошлое состояние), то пусть программа на это отреагирует.

Сережа подумал и написал программу. И машина выдала по этой программе вот такую серию картинок.

ОТ РЕДАКЦИИ:

Ребята! А вам такое задание: на листе бумаги в клеточку ноликами нарисуйте первую букву своего имени (такую форму будет иметь ваша колония бактерий) и продолжите историю развития этой колонии. Самую интересную историю мы напечатаем. На конверте поставьте девиз: «Жизнь».

Чип и Сережа читают ваши письма 

— Чип! Посмотри, как много у нас новых друзей! — обрадовался Сережа, глядя на стол, заваленный письмами. Он взял наугад несколько конвертов: Мурманск, Одесса, Хабаровск, Ленинград, Киев... — Вот бы съездить ко всем этим ребятам в гости!