Здравствуйте, tzragravorox, Вы писали:

D>>А если я решаю задачу нахождения оптимального хода не минимаксом, а другим способом ?
D>>Рендзю — игра тоже кажется NP, но найден выигрыш за начинающую сторону.

T>В математике Нет слово кажется

Нахождение лучшего хода в шахматах не является NP полной задачей, хотя это трудно строго доказать.
В качестве косвенного довода к этому утверждению является решение игры Рендзю.
(в Рендзю количество ходов в позиции больше чем шахматах, и значит она сложнее (правда только с формальной точки зрения))