чемпиона (каждый человек имеет право ошибиться; конечно, это относится и к чемпиону. Он был очень усталым). Ни одна важная теорема машиной не обнаружена, Что же касается диссертаций по психологии, то, может быть, даже хорошо, что предсказание Симона не оправдалось… Очень больно видеть, до какой степени информатика является благоприятным местом для ложных предсказаний. Сколько их нам обещали, этих чудес, которых мы так никогда и не увидели! Два года тому назад, во время Сикоба, журналист первой программы Французского телевидения показывал чудесную машину. Она была удивительно похожа на фотокопировальную. Он приподнял крышку, нашел там букву, нажал кнопку «и теперь буква зарегистрирована и мы ее легко узнаем, когда это потребуется». Фантастика! Покончим с этими мучительными сеансами поисков буквы этим господином, который два месяца назад подписал по этому делу контракт, номер которого я забыл… Но это был не господин, это была дама, и это было не два месяца назад, это был прошлый февраль. Больше никто не говорил об этой волшебной машине. Как же может случиться, что молодые люди не имеют никакого здравого смысла в информатике, так что можно без опаски предсказывать самые фантастические и самые неправдоподобные вещи, не вызывая ни смеха, ни краски стыда. «Мы подготовим 100000 преподавателей за пять лет…» Но это — совсем другая история, как говорил Киплинг.
Вернемся-ка к шахматам. Речи нет о лом, чтобы вы ими занялись; это выше понимания любителя, даже самого талантливого. Но я хочу предложить вам нечто, что все же имеет какое-то отношение к шахматам и одновременно может позволить упражняться в постановке пьесы.
Я представляю шахматную доску на рис. 15 как на экране своего микрокомпьютера в виде квадратной таблицы с 64 полями, которые представлены точками. На шахматной доске в левом верхнем углу расположена черная ладья (помеченная крестом), а в нижнем правом углу — белая ладья (помеченная звездочкой). Тринадцать шашек, помеченных маленькими кружочками, случайным образом расположены на игровом поле. Компьютер перемещает черную ладью ?, а вы — белую ладью *. Каждый игрок на своем ходе передвигает ладью, как при игре в шахматы; только на поля на той же строке или в том же столбце. Можно взять шашку и встать на место, которое она занимала; тогда эта шашка выходит из игры. Можно, взять противоположную ладью, если оказывается возможным попасть на занимаемое ею место. Тогда игра останавливается, и тот, кто взял чужую ладью, и есть победитель. В противном случае игра останавливается, когда больше шашек нет. Тот, кто взял больше шашек, и есть победитель.
Вам необходимо указывать компьютеру, какой именно ход вы хотите сделать. Вы можете, например, отметить строки цифрами, а столбцы — буквами, как на рисунке. Ваш первый ход будет, без сомнения, на H2 или B1…
Стратегия совершенно не очевидна. У вас много возможностей. Не так много, конечно, как в шахматной игре, но достаточно для того, чтобы вам пришлось заняться всерьез, что бы написать программу, которую было бы трудно побить.
Если вы при этом достигли совершенства, почему бы не попробовать ее вариант, который не должен вызывать намного больше затруднений (???): та же задача, но ладьи заменены конями.
*** Игра 26. Могущественная четверка.
Эта игра продается на рынке в другой форме. Она происходит в прямоугольном пространстве с 5 строками и 7 столбцами. Игра ориентирована, у нее есть низ и верх. Игровые позиции суть наинизшие свободные места в каждом столбце. Каждый игрок на своем ходе помещает свой отличительный знак на одно из игровых полей: например, один ставит крестики (+), другой — нолики (0). Первый, кто поставит на одной линии четыре принадлежащих ему знака — либо горизонтально, либо вертикально, либо по диагонали — выигрывает. На рис. 16 будем считать, что нолики при игре ставит тот игрок, чей ход именно сейчас. Если он не сыграет немедленно в пятом столбце, то его противник выиграет следующим ходом. По диагонали, начинающейся у основания четвертого столбца и идущей влево и вверх, есть три нолика, но единственное игровое поле в первом столбце обозначено точкой, и немедленно реализовать продолжение линии поэтому нельзя. Очевидно, что его противник не имеет никакого желания служить ему подставкой при пополнении первого столбца вместо того, чтобы заниматься разыгрыванием мест, допускающих продолжение линии…
Эту игру, производную от вошек, программировать намного проще, потому что всего полей только 35, и только 7 из них являются игровыми полями на каждом ходе. Это существенно ограничивает работу. В реализованной мною версии ответ микрокомпьютера практически мгновенный (порядка секунды). Я не думаю, что я располагаю программой-чемпионом, я не очень хорошо знаком с атим родом игр…
5. Стратегия без игры (выигрывающие стратегии)
Я объединил в этой главе несколько игр, которые можно найти на рынке и для которых существует стратегия решения. Как только она становится известной, игра теряет всякий интерес. Единственное связанное с такими играми удовольствие — обнаружить, как с ними покончить. Поэтому напишите программу — это наилучший способ сформулировать выигрышную стратегию, а затем забудьте игру, она вам больше ничего не принесет. И тем хуже, если продавцы этих игр не согласятся со мной… Некоторые из этих игр являются классическими среди информатиков. Я попытался их немного подновить. Многие стратегии могут быть элегантно запрограммированы с помощью рекурсивных процедур, но на языке Бейсик это невозможно. Всегда наступает день, когда фанатики этого языка, такого удобного для первых шагов, начинают понимать его ограниченность… Рекурсивность допустима в языках LSE и Паскаль.
? Игра 27. Бездельник.
Эта игра на рынке есть. Она имеет вид дощечки, в которую продето
Через кольца проходит челнок, длинный замкнутый контур, представленный на рисунке. Дело в том, чтобы его вынуть и, таким образом, освободить от колец (рис. 17).
Первое, что нужно сделать — это научиться, как пропускать одно кольцо через челнок, или как его оттуда вынуть. Несколько манипуляций — и вы быстро убеждаетесь, что в какой стадии ни была бы игра, всегда можно надеть или снять первое кольцо, которое свободно (не проходит вокруг какого-либо гвоздя). Можно также освободить кольцо, которое следует за первым занятым кольцом (если оно проходит вокруг челнока), или одеть его на челнок, если оно не одето. Таким образом, игру «бездельник» можно заменить равносильной игрой, которую легче представить на компьютере.
Эта игра ведется на таблице, разделенной на несколько полей (8 полей на рисунке). В начальном состоянии каждое поле покрыто шашкой. Поля размечены цифрами. Играть на данном поле — значит, поставить туда шашку, если поле пусто, и удалить шашку, стоящую на этом поле — в противоположном случае. Правила игры следующие:
— можно всегда играть на первом поле,
— можно играть на поле, которое следует за первым занятым полем.
Есть две возможных игры:
НАДЕВАТЬ: игровое поле вначале пусто. Заполнить все поля.
СНИМАТЬ: игровое поле вначале наполнено шашками на каждой клетке. Нужно все убрать,
Эта задача имеет очень элегантное рекурсивное решение. Но если вы немного подумаете, то вы сможете также найти очень простое итеративное решение, причем игра НАДЕВАТЬ оказывается более
