Программирование игр и головоломок - [19]

Шашки: 4 4 7 8 9 100

Число, которое нужно получить: 380

В течение 45 с, которые я выделил своему компьютеру, я получил следующее решение:

4 × 100 = 400

9 + 8 = 17

7 + 17 = 24

24 − 4 = 20

400 − 20 = 380

Это решение использует 6 шашек. Компьютер сообщает еще через 45 с:

4 × 9 = 36

4 + 36 = 40

7 × 40 = 280

280 + 100 = 380

Это решение не использует шашки 8.

Не пытайтесь сделать эту программу, следуя методу игры: вытащить случайным образом 6 шашек, вытащить случайным образом число, которое нужно получить, сообщить и то, и другое и в продолжение следующих 45 в искать нужную комбинацию. У вас нет никаких шансов, чтобы это произошло (см. Головоломку 28). Действуйте лучше следующим образом.

Выберите случайным образом 6 шашек и их комбинацию. Если результат не лежит в промежутке от 100 до 999, — повторите выбор. Если результат допустим, то выведите сообщение, какие 6 шашек участвуют, расположив их, например, в возрастающем порядке, чтобы не было понятно, в каком порядке они были использованы; сообщите искомое число, затем сообщите оставшиеся секунды и, когда 45 с протекут, сообщите результат. Здесь есть неудобство: всегда есть хотя бы одно точное решение. И при том, что не приходится особенно обольщаться, то, что вы достигнете с его помощью, вы, может быть, сможете сделать по-другому только приближенно.

Внимание: случайным образом выбирать комбинацию на самом деле вовсе не всегда так просто, как в приведенном примере. Не забывайте, что вы можете использовать и не все шашки. Найдите способ получать ответ. Я не вполне удовлетворен своим собственным. Я предпочел бы знать и другие способы это сделать…

?** Игра 13. Две лисы и 20 кур.

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

Вот как я представляю эту игру на экране своего компьютера. Буквы представляют кур, звездочки — две лисы. Куры могут перемещаться на один шаг вверх, влево или вправо, но не назад и не по диагонали. Лисы также могут перемещаться только на один шаг, но также и вверх — как и вниз, влево и вправо. Лиса может съесть курицу — как в игре в шашки: если в горизонтальном или вертикальном направлении за курицей на один шаг следует свободное поле, то лиса перепрыгивает через курицу на свободное поле и берет ее. При этом трофеи складываются. На рис. 9 одна лиса может съесть курицу b, тогда как вторая лиса может съесть за один ход кур e и f. Лисы всегда обязаны есть и, когда у них есть выбор — как на рис. 9, — они обязаны осуществить наиболее длинное поедание. Если два приема пищи имеют одинаковую длину, осуществляется один из них — по выбору лисы.

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

Лисы выигрывают, если им удается съесть 12 кур, так как тогда оставшихся кур недостаточно, чтобы занять 9 верхних полей.

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

?** Игра 14. Одна лиса и 13 кур.

Это — вариант предыдущей игры. Та же конфигурация, но только одна лиса и 13 кур. Та же задача: 9 кур должны занять верхний квадрат. Лиса обязана есть, и притом по наиболее длинному пути.

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

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

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