ヨセ 総合スレ (285ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
222: 2018/08/29(水)01:32 ID:4gnLjTbZ(1/3) AAS
> 221
「PSPACE完全かつNP困難」というのをかみ砕いて説明すると、
「厳密な最善を探すためには、すべてを読み尽くす以外の方法がなさそう（な問題）」
というつもりでしたが、わかりにくかったですね、すいません。
せっかくですので、PSPACE完全とNP困難、について
個別に説明を書いてみました。お読みいただければ幸いです。
223: 2018/08/29(水)01:33 ID:4gnLjTbZ(2/3) AAS
○PSPACE完全とNP困難
PSPACE（ピー・スペース）問題とは、概ね「ある一定の手数まで読み尽くせば最善が
割り出せるゲーム」の問題に対応します。例えばオセロは、高々60手まで
しかないので、オセロ必勝法はPSPACE問題です。囲碁や将棋は、終局までの手数が
確定できないので、PSPACEより複雑な問題であることが証明されています。
単純化した囲碁のヨセは、各箇所のヨセの手数をすべて足した手数まで読み切れば、
最善が割り出せるので、PSPACE問題と言えます。PSPACE完全とは、
省13
224: 2018/08/29(水)01:34 ID:4gnLjTbZ(3/3) AAS
○「究極のヨセ手法」を開発しようとしている方へ
もしあなたが、どのような局面でも現実的な時間内に最善の手が選べる
「究極のヨセ手法」を開発したとしたら、それはPSPACE完全問題とNP困難問題を
解いたことになります。少なく見積もって、以下のようなことが起こるでしょう。
・PSPACE完全問題を解いたので、他のPSPACE問題すべてを解いたことになります。
あなたの「究極のヨセ手法」は割と簡単に「オセロ必勝法」とかその他PSPACEのゲーム
必勝法に変換できるはずです。残念ながら囲碁そのものはPSPACEではないので、
省9
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.079s*