Компьютерные точки

логическая настольная игра точки искусственный интеллект аватарИскусственный интеллект (ИИ) — наука о создании интеллектуальных компьютерных программ и технических устройств. Термин машинная игра используется в области ИИ и означает разработку компьютерных программ, способных играть в игры. Разработка ИИ для игры в точки носит название компьютерные точки.

Различные программы, позволяющие играть в точки против ИИ, создаются с начала 2000-х годов. Тогда же появились и первые теоретические исследования на этот счет. Однако до настоящего времени ни одна программа не может составить серьезной конкуренции даже игроку среднего уровня. Точки — позиционная игра с колоссальным количеством возможных вариантов, что серьезно осложняет создание эффективных алгоритмов ИИ. Кроме того, к разработке программ не привлечены значительные интеллектуальные и материальные ресурсы.


ИИ в других играх

Разработка программ для машинной игры всегда являлась интересной и сложной задачей, привлекающей внимание всего человечества.

Так, в 1990-х годах была решена задача разработки сильного ИИ для игры в шашки, который способен составить конкуренцию сильнейшим игрокам. В последующие годы для шашек были разработаны программы, которые просчитывают все варианты игры. Такие программы победить невозможно; максимальный результат против такого ИИ — сыграть вничью.

В 2000-х годах разработаны программы по шахматам, играющие сильнее чемпиона мира, что было подтверждено в серии игр. В последующие годы программы по компьютерным шахматам стали еще сильнее, поэтому вопрос соревнований между человеком и ИИ уже не стоит на повестке дня.

В 2010-х годах появились сильные программы для игры в го, которые могут играть на уровне 6-го дана из 9 существующих. Позже к разработке ИИ для го подключились такие крупные компании как Google и Facebook. Однако на данном этапе (2016 год) программы по компьютерному го требуют значительных вычислительных ресурсов — минимум несколько десятков вычислительных ядер с современной архитектурой и высокой тактовой частотой.

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


ИИ в точках

Первой известной работой по ИИ в точках стала статья Павла Торгашова «Методы и алгоритмы» (2002 год). Свои идеи и алгоритмы автор реализовал в виде программы Points v.3.1c. Кроме того, в начале 2000-х годов появилось еще несколько малоизвестных программ с ИИ, вполне возможно под влиянием статьи Торгашова. Статья Торгашова описывает поиск ходов по алгоритму минимакса, оценку игровой позиции, оценку возможных ходов, уменьшение числа рассматриваемых вариантов развития событий на поле (усечение дерева вариантов).

В 2006 году польский игрок Bartek Dyda выложил в интернете свою программу под названием Kropki (разработку которой Bartek вел еще с 1999 года). Bartek использовал язык программирования C++. До 2011 года вышло несколько новых версий программы. В Kropki ход ищется по алгоритму минимакса с сужением области поиска при помощи альфа-бета-отсечения. При этом наиболее важным местом ИИ является способ оценки позиции. Программа пытается оценить, сколько точек соперника нужно для окружения каждой группы точек ИИ.

В начале 2010-х появился новый проект по ИИ, который позже разделился на программы Евгения Курневского OpenPointsAI (2015) на языке программирования rust и Ивана Кочуркина DotsGameAI (2012) на языке программирования C#. Вначале разработчики использовали алгоритм минимакса, затем деревья поиска Монте-Карло. В дополнение используются альфа-бета-отсечение и хеширование Зобриста.

В 2011 году вышла программа Алексея Приймака DotsAI (PointsAI) v.1. Написана на языке программирования java. Программа использует шаблоны игровых ситуаций размером 9х9 точек как основной способ поиска хода. Шаблоны имеют различную детализацию: многие точки в шаблонах являются незначимыми, т.е. неважно, поставлена ли точка и какого она цвета. Шаблоны делятся на различные типы в зависимости от целей их применения. База программы включает около 1000 шаблонов. Также в программе имеется конструктор деревьев последовательностей ходов, однако база деревьев еще слабо заполнена.

В 2016 году вышла следующая версия программы Алексея Приймака DotsAI v.2. Основные улучшения по сравнению с 1-й версией — это перенос всей логики игровых ситуаций в деревья ходов. Шаблоны используются теперь только для сравнения с игровой ситуацией. Логика стала более гибкой — появилась возможность добавлять условия применения к ходам ИИ в дереве ходов. Размер шаблонов увеличен с 9х9 до 15х15 точек. Большее значение приобрели шаблоны с абстрактными ходами. Использован новый алгоритм окружения. Поиск хода ИИ ускорен примерно в 2 раза. Произведено много улучшений в дизайне программы.