Почему для ИИ важны именно шахматы и как компьютер играет в них
В отличие от других игр, шахматную партию до сих пор невозможно просчитать до конца. Например, в игре «крестики-нолики» есть всего девять полей и два вида фигур. Вариативности не так много — партии может предсказать даже человек, и тем более компьютер.
Шахматы гораздо разнообразнее. Математик Клод Шеннон вычислил, что минимальное число неповторяющихся партий — около 10 в 120 степени. С текущими мощностями компьютер не может вычислить все возможные ходы соперника. Но из-за высоких требований игры именно на шахматах часто тестируют искусственный интеллект — например, методики оптимизации подбора или распознавания образов.
Есть две основные задачи, которые компьютеру нужно решать в шахматной партии.
- Оценивать позицию фигур на доске после каждого хода. Самый простой способ — посчитать количество материала на доске. Обычно за единицу берут пешку как самую слабую фигуру и считают в «пешках» другие фигуры. Конь или слон эквивалентны трем пешкам, ферзь — девяти. У кого больше пешек, тот в лучшей позиции.
Компьютер перебирает разные ходы и оценивает их по силе позиции. Преимущество такого алгоритма — в простоте, но она же приводит к поверхностной оценке. Например, можно забрать пешку противника, но открыть доступ к королю и проиграть. Первые компьютерные программы работали по такому алгоритму — их легко можно было обмануть.
Алгоритм станет более точным, если добавить критериев оценки. Например, не только количество материала, но и количество полей, которое контролирует каждая фигура. Чем качественнее компьютер оценивает позицию на доске, тем сильнее он играет в шахматы. - Уменьшать дерево вариантов. Перебирать все возможные варианты ходов — слишком долго. Например, белые фигуры могут начать партию 20 разными способами. Черные фигуры могут ответить на этот ход тоже 20 вариантами. В итоге только после первого хода может быть 400 вариантов позиций на доске.
Компьютерные алгоритмы обычно не считают максимальную глубину после каждого хода. Если направление развития событий по ходу ведет к победе, то останавливают перебор. Такие алгоритмы называются детерминированными — в них критерии выбора варианта известны. В одной и той же шахматной позиции такой алгоритм будет делать одинаковый ход в разных партиях.Но такая предсказуемость детерминированных алгоритмов может стать проблемой: например, компьютеры будут играть по критериям оценки, заложенным программистом. Эти критерии не всегда могут быть самыми лучшими. Это значит, что детерминированность ограничивает потенциал игры компьютера.
Зачем в шахматах нужен data science
Data science в большинстве случаев использует недетерминированные алгоритмы — это, например, глубокие нейронные сети. Они подстраиваются под обучающие примеры и меняют внутри себя наборы чисел. Поэтому недетерминированные алгоритмы сложно предсказать. Если систему остановить и попытаться понять, почему она принимает такие решения, ее логическую цепочку будет сложно восстановить.
В нашем примере с шахматами недетерминированные алгоритмы можно использовать для решения задачи как часть реального движка. При оценке позиции можно взять огромное количество размеченных сыгранных партий. У каждой позиции есть оценка — на наборе можно обучить нейросеть оценивать ситуацию.
Тогда отпадет нужда самостоятельно определять набор критериев вроде количества материала или расположения фигур. Нейросеть сама определит критерии исходя из набора. При этом можно совместить детерминированный и недетерминированный подходы. Детерминированные алгоритмы могут перебирать возможные варианты ходов, а недетерминированные — оценивать каждую позицию.
В 2017 году структура Google DeepMind выпустила систему AlphaZero, которая потрясла шахматное сообщество. Ее особенность в том, что ей нужны только правила игры. Затем она начинает играть против себя и обучается в процессе. AlphaZero делает выводы по стратегии и запоминает верные ходы. Так она переизобретает шахматную теорию — искусственный интеллект не использует опыт игры людей.
Система уже вносит новизну в многовековую игру — например, AlphaZero стала двигать крайнюю пешку. С подачи системы на этот прием обратили внимание большинство шахматистов. В отличие от других похожих систем, например, StockFish, нейросети AlphaZero сосредотачиваются на наиболее перспективных вариантах хода. Они анализируют около 80 тыс. позиций в секунду.
Нейросеть против шахматиста-человека: есть ли разница
Чтобы понять, приблизились ли мы к способности человека играть в шахматы, нужно определить, что мы оцениваем. С точки зрения силы игры в шахматы люди уже остались далеко позади: та же AlphaZero или Stockfish способны одолеть вообще всех профессиональных игроков.
Но есть и другой показатель — приблизились ли нейросети к человеческому мышлению? Детерминированные системы точно не обладают таким навыком — например, мы можем точно узнать, чем руководствуется алгоритм. Программист закладывает критерии оценки и алгоритм выбора вариантов, по которым учится система. Стратегию человека-шахматиста определяет слишком сложный набор параметров.
С недетерминированными алгоритмами ситуация еще сложнее. Дело в том, что мы даже не можем сравнить их стратегию игры со стратегией человека-шахматиста. Мы попросту не знаем до конца, как именно они работают. Обработка одних и тех же данных этими алгоритмами может приводить в разных ситуациях к разным результатам.
Эрнесто Инаркиев, российский гроссмейстер, чемпион Европы 2016, действующий чемпион России в командном зачете, тренер, основатель шахматной академии «ШАГИ CHESS»:
«Разработка Alpha Zero и внедрение нейронных сетей в свое время действительно изменили подход к подготовке шахматистов. Однако стоит отметить, что статистические алгоритмы мышления нейронных сетей так и не стали рациональными для людей. Выбирая ход, Alpha Zero разыгрывает большое количество партий сама с собой и выбирает продолжение, показавшее лучший результат в этих партиях. Метод очень энергоемкий и для анализа шахматной теории, поиска максимально правильного решения — эффективный. Но у человека есть другое преимущество — оценочные суждения, которые позволяют сокращать объем вычислений и быстрее принимать решение, тем не менее с более низкой точностью».