Публикацию попросили убрать с кастрированного Хабра и перенести сюда, что я и делаю.

Кроме жанра, игры имеют форму. Это как искусство — есть поэмы и даже романы, а есть стихотворения. Пушкин, например, порой по десятку стихов за неделю в 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-ом — дополнительный день жизни…