Программирование игр и головоломок

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

В этом разделе вам предстоит встретиться с двумя трудностями:

— найти стратегию для компьютера;

— запрограммировать ее.

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

Игра 16. Чтобы войти в курс дела,

Это — крайне простая игра, которую Роуз-Бол [BAL] относит к средневековым играм, поскольку ей действительно более 500 лет.

Вы выкладываете на стол 50 спичек. Каждый игрок по очереди вынимает спички из кучи, по меньшей мера 1 и не более 6. Кто берет последнюю спичку, выигрывает.

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

Вы можете изменить игру, взяв в качестве допускающих изменение данных — начальное число спичек и максимальное число спичек₍ которое можно вытащить на каждом ходе.

? Игра 17. Игра дат.

Эта игра предложена Берлокеном [BER]. Номер года в ней не очень существен, но предполагается, что год не високосный: в феврале 28 дней. Первый игрок сообщает какую-нибудь дату января. Каждый игрок на своем ходе называет более позднюю дату, увеличивая либо календарную дату в месяце, либо месяц, но не то и другое сразу. Если, например, начальной датой было 8 января, то можно перейти к 8 марта или к 12 января. Можно увеличить меньше: 9 января или 8 февраля; можно перейти сразу к 8 декабря или 31 января. Внимание: если вы переходите к 31 января, то ваш противник сможет в дальнейшем менять только месяцы, и притом лишь месяцы с 31 днем.

Первый, кто доберется до 31 декабря, выигрывает.

У вас не должно возникнуть никаких затруднений ни в определении стратегии, ни в программировании этой игры. Подумайте о проверке осмысленности предлагаемых дат… Кроме того, вставьте цикл ожидания, чтобы дать игроку время для ответных действий. Компьютер должен быть вежлив и должен спросить, кто будет начинать, по крайней мере, бросить «орла» или «решку», чтобы узнать, кому начинать…

?** Игра 18. Игра с 24 картами.

Расположим на столе 24 раскрытые карты: все карты с номерами от 1 до 6 обычной колоды, где туз считается за 1. Масти карт несущественны: двойка бубен имеет то же значение, что и двойка треф.

Каждый игрок при своем ходе берет со стола карту и складывает ее значение с суммой тех, которые были взяты ранее [14]. Первый, кто берет в точности 50 очков, выигрывает. Внимание: если при вашем ходе вы, взяв карту, не можете не превысить 50 очков, то вы проиграли. Если, например, ваш партнер увеличил сумму до 49 очков, а все тузы уже взяты, то вы проиграли: карту нужно брать, а ее значение больше единицы.

Это — вариант средневековой игры. Стратегия гораздо сложнее, потому что карт каждого сорта только 4. К этой игре нужно привыкнуть. Сперва компьютер выигрывает все партии подряд (любопытна реакция программиста: я счастлив, что моя программа меня обыгрывает). Но по прошествии нескольких партий уже я выигрываю. Тогда программу нужно улучшить.

?** Игра 19. Игра города Нима.

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

Ну, нет. Поскольку решения, предложенные в вышеупомянутых книгах (и, поскольку перечитывать их бесполезно, то я их имена и не указываю), очень плохо запрограммированы и совершенно не объяснены. Вам придется сделать лучше. Если вы знаете выигрывающую стратегию, то вам придется ее испытать, чтобы её проверить. Если вы ее не знаете, вы должны попробовать ее изобрести. Во всех случаях нужно программировать очень тщательно, чтобы не делать ненужных вычислений.

Напомним даже саму игру на тот очень мало правдоподобный случай, если вы ее еще не знаете. Это игра для двоих, и компьютер будет вашим партнером. На столе — кучи спичек в некотором количестве, и в каждой куче — некоторое количество спичек. Например, есть 5 кучек с 8, 13, 7, 5, 9 спичками.

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

Исходное положение: 8, 13, 7, 5, 9

Вы проиграли. Если вы возьмете две спички из одной кучки, то компьютер возьмет две из другой, так что и последнюю и потому выиграет. Если же вы возьмете одну спичку из одной кучки, то он возьмет одну из другой, и вы проигрываете на следующем ходе.

Мариенбадская игра является простым вариантом этой: проигрывает тот, кто берет последнюю спичку…

Этот род игр можно решительно осудить. Это — совершенно несправедливая игра. Выигрывающая стратегия существует. Если ваш противник ее не знает (как было в приведенном выше примере), то он обязательно проигрывает. Если же он ее знает, то он первый воспользуется усвоенной им выигрывающей стратегией, и вы ничего не сможете сделать. С другой стороны, даже если вы знаете выигрывающую стратегию, вы рискуете проиграть компьютеру, потому что вы не так хорошо считаете…

?** Игра 20. Игра Норткотта.

Вот менее известная игра, которую, однако, гораздо труднее программировать. Эта игра разыгрывается двумя участниками на прямоугольной площадке, разделенной на поля, как показано на рис. 12.

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

Размер игры значит очень мало. Я предпочитаю игру с тремя строками, но 4 и 5 — тоже очень хорошие числа. Длина строк несущественна. Выберите ее так, чтобы игра хорошо смотрелась.

На экране вы можете воспользоваться техникой, которая нам так часто служила. Пусть свободные клетки будут представлены точками, шашки одного из игроков — звездочками, а другого — 0. На рис. 13 воспроизведено начальное положение (4 строки, 9 полей на строке). Ход компьютера состоит просто в перемещении одной из его шашек (внимание: если ответ будет слишком быстрым, его, может статься, будет трудно воспринимать. Подумайте, как использовать цикл ожидания). Ход игрока может быть дан компьютеру в вг-де указания, на какой строке нужно переставить шашку и число полей при перемещении; положительное число указывает на приближение к противнику, отрицательное число означает отход к краю игрового поля. Все это очень просто,