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

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

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

Вы чего?!

В шахматах существует выигрышная стратегия! Нахождение очередного хода вообще имеет константную сложность, если оппонент играет оптимально :-)