Max Home IndustryХорошо, новые доказательства того, что вещи NP трудные, настолько распространены, что мы отказались от них сообщать, но эта — новая игра от факультета математики и информатики Технологического университета Эйндховена — это весело. Это обобщение хорошо известных точек и прямоугольников.
Это правда, что для задачи даже с умеренно большим пространством поиска она оказывается NP сложной — в этом нет ничего удивительного. Однако это конкретное исследование представляет собой вариант преобразования точек и прямоугольников в точки и многоугольники. Имя не такое броское, но более интересное.
Если вы играли в Dots and Boxes, вы будете знать, что это раздражающая игра, которую вы можете проиграть, просто недостаточно сконцентрировавшись, потому что это кажется такой простой задачей. Учитывая регулярную сетку точек, все, что вам нужно сделать, это соединить соседние точки прямой линией и попытаться завершить квадрат. Когда игроки ходят по очереди, это похоже на Нима, где каждый игрок изо всех сил старается не оставлять трехсторонний ящик для следующего игрока.
Обобщение точек и многоугольников воспроизводится на множестве точек на плоскости. Каждый игрок по очереди рисует соединительную линию, которая не пересекает никакую другую точку или существующие ребра. Цель состоит в том, чтобы сформировать замкнутый многоугольник, и в общем победит тот, у кого максимальная площадь покрыта многоугольниками. Две разновидности игры — это точки, многоугольники и дыры, где многоугольники могут содержать другие многоугольники, и выпуклые точки и многоугольники, где они должны быть выпуклыми. Если вы попробуете игру, вы быстро обнаружите, что правило «запрета пересечений» является важной частью стратегии, заключающейся в том, чтобы не оставлять две стороны, которые может соединить ваш оппонент. Вы можете опробовать все три версии по адресу:
https://www.win.tue.nl/~kbuchin/proj/ruler/dotsandpolygons/
но заметьте, что это позволяет человеку противостоять только человеку. Интересным проектом было бы обучение нейронной сети для игры, поскольку для игры в нее нужны пространственные рассуждения, а также логика — что-то вроде более простого го. Исходный код также доступен.
Ключевым результатом исследования является то, что решить, возможен ли выигрыш в Dots and Polygons, непросто — вы можете найти подробности в статье, авторами которой являются Кевин Бучин, Ирина Костицына и другие.
Если вы увлекаетесь такими вещами, вам может понравиться последняя теорема:
Теорема 5. Пусть P — множество из n точек на плоскости в выпуклом положении. Для n = 3, 5, 7 игрок R может забить не менее половины площади, для n = 4, 6 игрок B может забить не менее половины площади.
Проблема для n> 7 открыта.
Майк Джеймс — автор «Руководства программиста по теории», в котором излагаются фундаментальные идеи информатики в неформальной и в то же время информативной форме и посвящена одна глава проблеме NP.