ゲームの必勝法探索問題それ自身の困難性は、今のところ定義されておらず、ゲームのクラスに対する必勝法探索問題の困難性が定義されている。

ハミルトンゲームはNP完全問題である。（先手後手あわせて）n手で終了するゲームの必勝法を探索する問題は

<math>\sum_n P \cup \prod_n P</math>

に属する。

（一般化された）しりとりはPSPACE完全問題である。

尚、二人零和有限確定完全情報ゲームには必勝法があることが知られている。