Жак Арсак - Программирование игр и головоломок

Не предпринимайте здесь слишком глубокого изучения выигрывающей стратегии. Мы к ней еще вернемся ниже. Устройте только, чтобы ваш компьютер выигрывал при приведенных выше условиях, если старт для него благоприятен…

Вы легко сообразите, как представить эту игру на экране,

??** Игра 24.Гениальный отгадчик.

Вы уже сделали гениального ответчика; эта игра сложнее. Составьте программу для отыскания комбинаций, задуманных гениальному отгадчику. Вы можете идти двумя путями:

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

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

Вы скажете, что это неинтересно. Но это не так. Во-первых, стратегия поиска является вызовом для способности мышления. Мне пришлось немного подумать, чтобы получить в свое время разумный ответ с 6 позициями и 8 цветами. Попробуйте сами и убедитесь! С другой стороны, для гениального отгадчика существует проблема эффективного начала, В программе, составленной мною, я сам выбираю первые испытательные комбинации. Я смотрел, сколько было систематических попыток и каковы они были. Это позволило понять, насколько важен начальный выбор и может ли он сильно влиять на результаты. Это — хорошее орудие экспериментирования. И это очень легко устроить. Компьютер запрашивает вас, сколько опытов априори вы хотите осуществить. Затем он запрашивает у вас начальные комбинации, число которых он только что прочел. После этого компьютер предпринимает систематическое исследование, какая из предложенных комбинаций должна быть оставлена.

Чтобы преуспеть, вам нужен хороший метод, и программировать нужно очень тщательно.

?** Игра 25.Погоня за сокровищем.

Любой начинающий в информатике мечтает сделать программу — чемпиона мира по шахматам… Я и сам видел несознательных, бросавшихся на эту задачу. Чтобы утешить их, нужно сказать, что это — одно из больных мест истории информатики. Компьютеры были еще электронными монстрами, напичканными радиолампами, которые приходилось охлаждать кубическими метрами воды, когда Герберт Симон (недавний Нобелевский лауреат по экономике) уже сделал примечательные предсказания:

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

— через 10 лет компьютер обнаружит и докажет новую важную математическую теорему;

— через 10 лет большая часть диссертаций, выпускаемых по психологии, будет облечена в форму программ для компьютеров или качественных комментариев к примечательным особенностям компьютерных программ (Герберт А. Симон, Аллан Кьюзлл: Эвристическое решение задач: следующее продвижение в исследовании операций. «Operations research», т. 6, январь-февраль 1958, с. 6),

И через 25 лет с момента предсказания у нас не возникло проблемы запрещать доступ компьютеров к шахматным чемпионатам, они не представляют серьезной угрозы. Да, одна из программ выиграла партию у чемпиона (каждый человек имеет право ошибиться; конечно, это относится и к чемпиону. Он был очень усталым). Ни одна важная теорема машиной не обнаружена, Что же касается диссертаций по психологии, то, может быть, даже хорошо, что предсказание Симона не оправдалось… Очень больно видеть, до какой степени информатика является благоприятным местом для ложных предсказаний. Сколько их нам обещали, этих чудес, которых мы так никогда и не увидели! Два года тому назад, во время Сикоба, журналист первой программы Французского телевидения показывал чудесную машину. Она была удивительно похожа на фотокопировальную. Он приподнял крышку, нашел там букву, нажал кнопку «и теперь буква зарегистрирована и мы ее легко узнаем, когда это потребуется». Фантастика! Покончим с этими мучительными сеансами поисков буквы этим господином, который два месяца назад подписал по этому делу контракт, номер которого я забыл… Но это был не господин, это была дама, и это было не два месяца назад, это был прошлый февраль. Больше никто не говорил об этой волшебной машине. Как же может случиться, что молодые люди не имеют никакого здравого смысла в информатике, так что можно без опаски предсказывать самые фантастические и самые неправдоподобные вещи, не вызывая ни смеха, ни краски стыда. «Мы подготовим 100000 преподавателей за пять лет…» Но это — совсем другая история, как говорил Киплинг.

Вернемся-ка к шахматам. Речи нет о лом, чтобы вы ими занялись; это выше понимания любителя, даже самого талантливого. Но я хочу предложить вам нечто, что все же имеет какое-то отношение к шахматам и одновременно может позволить упражняться в постановке пьесы.

Я представляю шахматную доску на рис. 15 как на экране своего микрокомпьютера в виде квадратной таблицы с 64 полями, которые представлены точками. На шахматной доске в левом верхнем углу расположена черная ладья (помеченная крестом), а в нижнем правом углу — белая ладья (помеченная звездочкой). Тринадцать шашек, помеченных маленькими кружочками, случайным образом расположены на игровом поле. Компьютер перемещает черную ладью ×, а вы — белую ладью *. Каждый игрок на своем ходе передвигает ладью, как при игре в шахматы; только на поля на той же строке или в том же столбце. Можно взять шашку и встать на место, которое она занимала; тогда эта шашка выходит из игры. Можно, взять противоположную ладью, если оказывается возможным попасть на занимаемое ею место. Тогда игра останавливается, и тот, кто взял чужую ладью, и есть победитель. В противном случае игра останавливается, когда больше шашек нет. Тот, кто взял больше шашек, и есть победитель.

Вам необходимо указывать компьютеру, какой именно ход вы хотите сделать. Вы можете, например, отметить строки цифрами, а столбцы — буквами, как на рисунке. Ваш первый ход будет, без сомнения, на H2 или B1…

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

Если вы при этом достигли совершенства, почему бы не попробовать ее вариант, который не должен вызывать намного больше затруднений (???): та же задача, но ладьи заменены конями.