Закончена ли настольная игра "Go" NP?

Question

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

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

Может ли быть так, что задача математического вычисления оптимального хода в любой момент времени в Го является NP-полной задачей?

Answer 1

Шахматы и Го оба EXPTIME завершено . IIRC, в Go больше возможных ходов, так что я думаю, что это более высокий коэффициент, чем класс шахмат. В Википедии есть хорошая статья о сложности Go.

Answer 2

Даже если Go находится просто в P, это может быть что-то ужасное, например O(n^m), где n - это число пробелов, а m - это некоторое (большое) фиксированное число. Даже находясь в P, нет ничего разумного для вычисления.

Answer 3

Ни Шахматы, ни Ио не полностью оценивают все возможности, прежде чем принять решение о движении.

Шахматные ИИ используют различные эвристические методы, чтобы сузить пространство поиска и количественно оценить, насколько «хорошей» является данная позиция на доске. Это можно сделать рекурсивно, оценивая возможные позиции доски на 14-15 шагов вперед и выбирая путь, который ведет к хорошей позиции.

Существует немного «волшебства» в том, как количественно определяется позиция на доске, так что на верхнем уровне ИИ может просто перейти на Движение A> Движение B, поэтому позволяет выполнять Движение A. Но поскольку количество фигур все они имеют поддающееся количественному измерению значение, и может быть реализован «достаточно хороший» алгоритм.

Но оказывается, что для программы гораздо сложнее оценить две возможные позиции на доске в Go и выполнить расчет A> B. Без этой критической части немного сложнее заставить остальную часть ИИ работать.