Есть много шахматных AI вокруг, и, очевидно, некоторые из них достаточно хороши, чтобы победить некоторых из лучших игроков мира.
Я слышал, что было сделано много попыток написать успешный ИИ для настольной игры Go, но до сих пор ничего не было задуманный за пределами среднего уровня любителя.
Может ли быть, что задача математического вычисления оптимального движения в любой момент времени в Go является NP-полной проблемой?
Шахматы и Go - оба EXPTIME complete. IIRC, Go имеет более возможные ходы, поэтому я считаю, что это более высокий класс сложности, чем шахматы. В Wikipedia есть хорошая статья о сложности Go.
Даже если Go просто находится в P, все равно может быть что-то ужасное, как O(n^m), где n - количество пробелов, а m - некоторое (большое) фиксированное число. Даже будучи в P не делает что-то разумное для вычисления.
Ни шахматы, ни Go AI полностью не оценивают все возможности до принятия решения о движении.
Шахматные AI используют различные эвристики, чтобы сузить пространство поиска, и количественно определить, насколько "хорошая" позиция на доске. Это можно сделать рекурсивно, оценив возможные позиции доски на 14-15 вперед и выбрав путь, который приведет к хорошей позиции.
Там немного "магии" в том, как позиция на доске определяется количественно, так что на верхнем уровне ИИ может просто перейти Move A > Move B, поэтому позволяет перемещать A. Но поскольку существует ограниченное количество частей и все они имеют поддающееся количественной оценке значение, алгоритм "достаточно хорош" может быть реализован.
Но оказывается, что программе намного сложнее оценить две возможные позиции в поле Go и сделать это вычисление A > B. Без этой критической части его немного сложно сделать, чтобы остальная часть ИИ работала.