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

Нет, этот великий философ не играл в такие игры — по крайней мере, насколько я знаю. Эту игру предложил мне М. Дюма,_: профессор лицея Бергсона. Еще одна игра для двоих, в которой компьютер — ваш неумолимый партнер. Потому что если вы обнаружите выигрывающую стратегию, то компьютер не оставит вам никаких шансов, ведь у него и память есть…

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

Вот последовательность возможных ходов. Вначале — 50 спичек.

Игрок А берет	Остается	Игрок Б берет	Остается
1	49	2	47
4	43	8	35
16	19	19	выиграл

На каждом ходе, кроме последнего, каждый из игроков брал максимальное возможное количество, и игрок Б легко выиграл, взяв на последнем ходе 19 спичек, на что имел полное право, так как 1 ≤ 19 ≤ 2 × 16 = 32. Конечно, это очень плохая стратегия. Вот другая партия:

Игрок А берет	Остается Игрок Б берет	Остается
3	47	4 43
1	42	2 40
1	39	1 38
1	37	2 35
1	34	2 32
3	29	6 23
2	21	4 17
4	13	2 11
3	8

Игрок А близок к победе. Если Б возьмет 3 спички и останется 5, то А имеет право взять последнюю. Это тем более верно, если Б возьмет более чем 3 спички (4, 5 или 6). Игрок Б не может взять больше и во всех случаях дает игроку А все права, чтобы он мог взять последнюю спичку). Единственными случаями, подлежащими обсуждению, остаются поэтому случаи, когда Б берет одну или две спички.

Если Б берет одну, то остается 7, А берет 2 и остается 5. Если Б после этого берет более одной, то А берет последнюю; если Б берет одну и остается 4, то А берет одну и остается 3; Б может взять только одну или две, и кончает игру А.

Если Б берет 2 и остается 6, то. А берет одну и остается 5, и А выигрывает тем же способом.

Я так подробно разбирал этот пример, чтобы познакомить вас с основными идеями. Тщательно изучите этот пример. Всегда ли игрок А заведомо выигрывает, как только он оставляет в куче 8 спичек…

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

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

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

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

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

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

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

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

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

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

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

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