>>831
将棋の最善手決定という問題はNP困難で合っているで
自明すぎるので誰も書いていないんだと思う

補題として、本将棋と同じゲーム木を考え、その終局ノードに対し、任意の得点付けが行われる想定で、
局面Sから合法手で到達可能な終局局面の得点の合計を最大化する問題を考えつ
ただし、局面Sと同じ手番の局面においては、合法手の1個だけを選べるものとする
（一方、反対パスは全合法手を全て下る

まず有限ゲームなので、終局までの手数の上限はある整数Nで押さえられる。
また、合法手の数もある整数mで押さえられる。
とすれば、Sから終局に至るパスは、要素が整数値1〜mのN/2次元ベクトルvで現せるわけや
これに対し、目的関数は完全ゲーム木のvが規定する部分木の葉の得点の合計となりぬ
この目的関数を最大化するのだから、整数計画法に他ならないからNP困難。

で、本将棋のルールにおいて勝ちの終局局面の得点を1、それ以外の終局局面の得点を-∞とすると、
目的関数を最大化する部分木は必勝手順の部分木と一致するから、
完全解析の知識が無い状態で行う将棋の最善手決定という問題はNP困難に他ならない

※1 もちろん完全解析の知識があったらテーブルを引くだけなので（最短手順で！とかの拘りがなければ）Pで済むのは自明

※2 上の論法に穴があるとしたら、探索の必要性について証明できていない点
　　（ひょっとしたら本将棋のルールに依存した意外なショートカットが存在し、
　　探索せずとも結論を出せるかもしれない）という点がｱﾚだが、それは>>800の発言で織り込み済み