Microsoft Research берет на себя Go

Microsoft Research использовала F # и AI для реализации игры Go потребительского качества — возможно, самой сложной для реализации игры для двух человек.

Много времени было потрачено на создание ИИ, который может играть в китайскую настольную игру го. Если вы не знакомы с игрой, то хорошая новость заключается в том, что на обучение уйдет всего несколько минут. Плохая новость заключается в том, что, хотя правила и цели просты, сама игра потрясающе сложна и тонка. Если вы думаете, что шахматы — это хороший вызов, вам действительно нужно попробовать свои силы и ум в го. У китайцев есть поговорка: чтобы выучить Го, нужно всего несколько минут, а на освоение — целую жизнь.
Большая проблема Go — это огромное дерево игр. В шахматах, например, предусмотрено около 20 ходов на каждую ветку, а в Го — по 200 на каждую ветку. Сложность игрового дерева намного превышает количество атомов во Вселенной. Это означает, что алгоритмы поиска, используемые для таких игр, как шахматы, просто тратят слишком много времени на поиск нерелевантных областей.

Теперь Microsoft Research взялась за эту проблему и выпустила отточенную игру для XBox — The Path of Go. Вы можете скачать демоверсию игры бесплатно, но если вы хотите получить полный опыт, это будет стоить вам 400 очков (около 5 долларов).
Используемый алгоритм представляет собой машинное обучение на основе Монте-Карло. Команда обучила программу обучения на основе четверти миллиона экспертных игровых записей. Эксперты-люди сообщают, что хороший ход «имеет хорошую форму», и, поскольку это по сути двумерная геометрическая игра, имеет смысл попытаться узнать, какие модели «имеют хорошую форму». В дополнение к ранжированию двумерных паттернов в дереве игр был проведен поиск с использованием алгоритма «верхних доверительных интервалов», который в основном сокращает дерево игр так, чтобы исследуемые паттерны находились в более релевантных областях игры.
Алгоритмы были реализованы с использованием F #, а XNA использовалась для создания полноценной трехмерной сюжетной игры для XBox. Чтобы увидеть, как выглядел конечный результат, просмотрите видео.