Математические головоломки и развлечения
Шрифт:
Второй игрок может победить в тех случаях, когда число клеток, прилегающих к стороне, нечетное.
Поиграв немного в гекс, читателю, может быть, захочется поломать голову над тремя задачами, возникающими в процессе игры.
Они изображены на рис. 36.
Рис. 36 Три задачи из игры в гекс.
Вопрос для всех трех задач один и тот же: найти такой первый ход, который обеспечивает «белым» победу.
* * *
В гекс можно играть на самых разных досках, топологически эквивалентных полю, составленному из шестиугольников. В качестве игрового поля можно, например, использовать доску, состоящую из равносторонних треугольников; фишки здесь ставятся в точки пересечения границ между клетками. Обычная шахматная доска изоморфна игровому полю гекса, если предположить, что квадраты связаны по диагонали только в одном направлении (например, в направлении с северо-востока на юго-запад, но не в направлении с северо-запада на юго-восток).
Предлагались и другие, неромбические формы доски для гекса.
Например, создатель теории информации. К. Шеннон предложил игровое поле в форме равностороннего треугольника. Выигрывает тот, кто первым построит цепь, соединяющую все три стороны треугольника. Угловые клетки считаются принадлежащими обеим сторонам угла. Нэш доказал, что побеждает первый игрок. Метод доказательства без труда переносится и на случай треугольного игрового поля. (Здесь также выигрывает тот, кто начинает.)
Несколько предложений было внесено с целью уменьшить слишком сильное преимущество первого игрока. Так, первого игрока можно лишить права начинать с короткой диагонали. Решая, кому принадлежит победа, можно учитывать сделанное выигравшим число ходов. Открывая игру, первому игроку разрешается делать лишь один ход, после чего каждый из игроков по очереди делает по два хода за один раз.
Напрашивается предположение, что если на доске размером n х (n + 1) — например 10 х 11 — начинающий игру берет себе более удаленные друг от друга стороны, то относительные преимущества игроков должны уравниваться. К сожалению, обнаружилась очень простая стратегия, с помощью которой второй игрок наверняка одерживает победу. Эта стратегия основана на зеркальной симметрии относительно центральной оси. Если второй игрок — это вы, то представьте себе, что все клетки разбиты на пары так, как показано на рис. 37.
Рис. 37 Как должен расставить свои фишки второй игрок на «укороченной» доске, чтобы выиграть партию в гекс.
Куда бы ни сделал ход противник, вы делаете ход на вторую клетку, обозначенную той же буквой, что и занятая им клетка. Поскольку расстояние между вашими сторонами меньше, ваш проигрыш невозможен!
Несколько слов об общей стратегии игры в гекс. По сообщениям многих читателей, они были разочарованы, обнаружив, что первый игрок очень легко одерживает победу, если занимает центральную клетку и продолжает от нее строить цепь до краев доски. Эти читатели полагают, что запереть первого игрока невозможно, поскольку он всегда может сделать ход, присоединив к своей цепочке одну из двух клеток. Сторонники подобной точки зрения просто не обладают достаточным опытом игры в гекс, иначе бы они обнаружили, что для того, чтобы запереть противника, совсем не обязательно занимать клетки, примыкающие к концам цепи. Игра в гекс намного хитрее, чем кажется с первого взгляда. Блокирование цепи часто происходит внезапно, в результате действий, не имеющих, казалось бы, к этому ни малейшего отношения.
Более изощренная стратегия основана на следующем методе.
Сделайте первый ход в центр, а затем постарайтесь занять отдельные клетки по диагонали или по вертикали так, как это сделано на рис. 38.
Рис. 38
Если ваш противник помешает вам достроить вертикаль, вы придете по диагонали. Если он попытается помешать вам достроить диагональ, вы сделаете ход, заняв клетку на вертикали.
Как только вам удастся соединить стороны вашего цвета «прореженной» цепочкой, запереть вас уже невозможно, а отсутствующие звенья цепи вы сможете восстановить, потратив на каждое из них по два хода. Такая стратегия очень эффективна при игре против новичка, но опытный игрок сможет парировать ее.
Совсем иной принцип положен в основу стратегии машины для игры в гекс, сконструированной К. Шенноном и Э. Ф. Муром. Вот описание этого устройства.. [15]
После исследования игры мы пришли к заключению, что достаточно разумный ход можно было бы находить следующим образом: создать двумерное потенциальное поле, соответствующее игральной доске, белые фишки заменить положительными зарядами, черные фишки — отрицательными. Верх и низ «доски» должны нести отрицательный заряд, а ее правая и левая стороны — положительный. Очередному ходу соответствует некоторая вполне определенная седловая точка поля.
15
Шеннон К. Работы по теории информации и кибернетике. — М.: ИЛ, 1963, стр. 162–180.
Для проверки наших предположений было построено аналоговое устройство, состоящее из сети сопротивлений и щупа для обнаружения седловой точки. Если не считать небольших усовершенствований, подсказанных практикой, общий принцип оказался вполне пригодным. Если машина делала первый ход, то, играя с людьми, она выигрывала около 70 % всех партий.
Нередко ей случалось озадачивать своих создателей странными на первый взгляд ходами, но при более подробном рассмотрении эти ходы неизменно оказывались вполне разумными. Принято считать, что вычислительные машины прекрасно справляются с длинными вычислениями, но малопригодны для решения более сложных, логических задач. Как ни парадоксально, но построенная нами машина вполне разумно оценивала позицию в игре.
Хуже всего она играла в конце партии, когда игра приобретала комбинационный характер. Любопытно заметить также, что машина для игры в гекс заменила обычную вычислительную процедуру на обратную, решив существенно дискретную проблему с помощью аналогового устройства.
Желая подшутить над специалистами по теории игр, знающими о существенных преимуществах первого игрока, Шеннон построил еще одну машину для игры в гекс, которая, к немалому удивлению знатоков, выигрывала даже в тех случаях, когда делала второй ход.
Доска, на которой играла эта машина, в одном направлении была короче, чем в другом (размеры доски 7x8 клеток), но Шеннон, установив ее на прямоугольной подставке, замаскировал неравенство сторон. Лишь немногие из игроков, заподозрив неладное, догадывались пересчитать клетки вдоль сторон доски. Машина играла в соответствии с выигрышной стратегией, описанной выше. Ответные ходы она могла бы делать мгновенно, но специально предусмотренные термисторы замедляли ее «реакцию». Перед каждым ходом машина «размышляла» от одной до десяти секунд, создавая у зрителей впечатление, будто она проделывает сложнейший анализ положения на доске.