2 人ゲームの先手(後手)必勝判定問題はゲームにループがなければ
PSPACE-Complete(ATIME(poly)-Complete)。
オセロが後手必勝かどうかは 6x6 では分かってるけど、
8x8はまだ未解決だと思う。