Публикацию попросили убрать с кастрированного Хабра и перенести сюда, что я и делаю.
Кроме жанра, игры имеют форму. Это как искусство — есть поэмы и даже романы, а есть стихотворения. Пушкин, например, порой по десятку стихов за неделю в Appstore выкладывал. И мы пашем иной раз не хуже гения. Ай да мы с Пушкиным, ай да сукины сыны!
Одна из игр, написанная намедни, мне показалась достойной внимания широкой математической общественности, которая обожает геометрические головоломки, соревнования и самоиронию.
Постановка задачи
На плоскости задано случайное конечное число точек.
Два игрока ходят по очереди.
За один ход игрок может соединить любые две точки прямой линией.
Линия не до��жна пересекать другие фигуры.
Цель игры
Если в результате хода образуется треугольник, не содержащий внутри себя других точек — то игрок получает призовое очко.
Игра заканчивется, когда построены все треугольники.
Необходимо набрать очков больше чем соперник.
Модификация игры
Если в результате хода образуется треугольник, не содержащий внутри себя других точек — то игрок добавляет в свой актив площадь образовавшегося треугольника.
Необходимо завоевать большую, чем соперник, площадь.
Особенности геометрической реализации
Для начального расположения точек я обрезаю экран iPhone до прямоугольника 300 на 400 и делаю по краям поля шириной по 10 пикселей.
Расстояние между точками ограничиваю числом не менее 16 пикселей (для удобного захвата пальцем).
Число точек задается случайно в диапазоне от 12 до 30 штук.
При построении запрещаю проходить линии ближе 5 пикселей до любых точек, находящихся на пути.
Особенности интеллекта
В качестве соперника выбран процессор фирмы Apple. Он играет в двух состояниях.
При рейтинге игрока менее 25 баллов, Apple думает на один ход вперед, случайно соединяя точки, если нет варианта с немедленным получением очка.
При рейтинге игрока 25 баллов и выше, соперник думает на 2 хода вперед, проверяя четность полученных после хода возможностей построения треугольников.
В процессе разработки я увеличивал глубину хода до 10, после чего программа уходила в глубокой транс и падала мордой в салат.
В процессе игры выработались стандартные трюки, с помощью которых иногда можно выигрывать. Надеюсь, Вы их найдете сами.
Математическую теорию игры не строил, но примитивные варианты раскладов для расположения 4-х точек рассматривал.
В зависимости от выпуклости 4-ех точечного шаблона, при оптимальной игре с обеих сторон игрок, ходящий первым играет либо выигрывает 2-0, либо проигрывает 1-2.
Выпуклый шаблон. Игрок, ходящий первым, побеждает 2-0.
Невыпуклый шаблон. Игрок, ходящий первым, терпит поражение 1-2.
Для 5-ти точечного шаблона, игрок, ходящий первым всегда проигрывает.
5-ти точечный выпуклый шаблон. Игрок, ходящий первым всегда проигрывает.
Игра порой чем-то напоминает снукер, когда соперник получает ход и не может построить казалось бы очевидно получающийся треугольник — загораживают другие фигуры.
Всех с Новым Годом — он с бонусом! В 2016-ом — дополнительный день жизни…
