Математические выводы с игры «Ростки».

Конвей предложил простое доказательство того, что партия в «Ростки» имеет не больше (3n— 1) ходов. Каждая точка имеет три «жизни» — три линии, которые могут встретиться в этой точке. Точку, из которой исходят три линии, называют «мертвой точкой», потому что к ней проводить линию уже нельзя. Игра, которая начинается с n точек, имеет 3n «стартовых» жизней. Каждый ход убивает две жизни, однако добавляет одну точку с одной жизнью. Значит, каждый ход уменьшает количество жизней на одну. Очевидно, что, когда останется только одна жизнь, игра продолжаться уже не может, потому что для хода требуется «сжечь» как минимум две жизни. Соответственно, никакая партия не может продолжаться дольше (3n— 1) хода.

Также легко показать, что партия должна длиться как минимум 2n ходов. Игра с тремя точками начинается с девятью жизнями и должна закончиться на восьмом ходу или перед ним, т. е. должна длиться по крайней мере шесть ходов.

Игра с одной точкой тривиальна. Первый игрок имеет только один возможный ход — соединить точку на саму себя. В этом случае выигрывает второй игрок (или проигрывает в варианте мизера), соединяя точки изнутри или снаружи. Оба хода второго игрока эквивалентны, поскольку с точки зрения топологии нет ничего, что бы отличало внутреннюю часть замкнутой кривой от наружной. Представьте себе, что мы играем на поверхности сферы. Если мы прокалываем поверхность во внутренней области замкнутой кривой, то можем вывернуть эту сферу так, что все точки, ранее находившиеся внутри кривой, оказываются снаружи и наоборот. Эквивалентность внутреннего и внешнего с точки зрения топологии очень важна, потому что это существенно упрощает анализ игры, начинающейся с двух или более точек.
две точки в игре «Ростки»
Если точек две, игра моментально обретает интерес. Очевидно, что у первого игрока пять возможных ходов. Но второй и третий, а также четвертый и пятый начала взаимно симметричны и, соответственно, эквивалентны. Поскольку внутренняя и внешняя части замкнутой кривой эквивалентны, то все четыре варианта (со второго по пятый) равнозначны. Значит, требуется анализ только двух топологически неравнозначных вариантов. Если построить полную диаграмму всех возможных ходов в виде графа, то его анализ покажет, что и при нормальной, и при обратной разновидности правил выигрышная стратегия у второго игрока.

Конвей установил, что по основным правилам в варианте с тремя точками (при правильном выборе стратегии) всегда может выиграть первый игрок, а в варианте мизера с тремя точками гарантированную победу имеет второй игрок. Студент-математик из Кембриджа Денис Моллизон показал, что в варианте четырех и пяти точек по основным правилам победную стратегию имеет первый игрок. Денис заключил пари с Конвеем на 10 шиллингов, что сможет провести анализ игры с шестью точками. Анализ Дениса занял 49 страниц и потребовал месяца работы :), а Конвей свой анализ закончить не смог. В итоге Денис Моллизон доказал, что при шести точках и основных правилах выигрышную стратегию имеет второй игрок. Кстати, оказалось, что второй игрок имеет победную стратегию и в варианте мизера с четырьмя точками.

Хотя стратегия оптимального выбора хода не сформулирована, к концу игры оказывается, что кривые делят плоскость определенным специфическим образом. Характер получающегося рисунка и подсказывает путь к победе. Возможность стратегического планирования делает игру «Ростки» настоящей интеллектуальной забавой и позволяет игроку бесконечно совершенствоваться. В ней возможны самые неожиданные построения, для которых, как представляется, просто не существует никакой стратегии, которая гарантировала бы кому-либо выигрыш.

Материалы по теме:
Поделиться с друзьями:
Оцените материал:
1 Star2 Stars3 Stars4 Stars5 Stars (Проголосуйте первым!)
Загрузка...

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *