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