- コンピュータが全手を調べ尽くした時代到来すると
886 ：名無し名人[sage]：2012/09/17(月) 17:12:05.97 ID:/oo7GlVX - P=NPなら、それはただちに、完全解析が、将棋の全局面でなくて、
多項式オーダーな個数の一部局面だけ見れば完了という話を意味するんだけど
数学者的には、どこをどう考えたらそれが有り得そうに思えるのだろうか、、
あるルールに従っておりランダムでない状態遷移には必ず圧縮の余地があるﾊｽﾞとかそんな感じなんだろうか
|
- コンピュータが全手を調べ尽くした時代到来すると
889 ：名無し名人[sage]：2012/09/17(月) 17:24:33.49 ID:/oo7GlVX - P=NPでもP≠NPでもどっちでもいいが、証明を企てている人たちのことだYO！
パッと見、>886の前半3行な具合でP≠NPは明らかなように思えるが、
さんざんっぱらやって証明できずにいるということは、
何がしかP=NPを導きかねない（P=NPを含意してしまうことを現時点では否定し難い）抜け道が存在することを意味する
証明を企てている当人ならそういうのを当然把握してるでしょう
|
- コンピュータが全手を調べ尽くした時代到来すると
893 ：名無し名人[sage]：2012/09/17(月) 19:01:50.27 ID:/oo7GlVX - >>890
将棋はEXPTIME完全らしかったorz
ttp://d.hatena.ne.jp/smoking186/20080809/1218289639
EXPTIME完全であれば仮にP＝NPであっても実質関係ない
ただし、問題の定式化によると注意書きがあるし、
多分ガチの完全解析（相手のあらゆる応手で生じ得る局面についての最善手決定）の場合だと思う
で、>886で思わず完全解析と書いてしまったが、
よく考えたらそのとき次↓↓↓の探索を意図してましたｽﾝﾏｿﾝ
（完全解析でなくて）対局中に生じた個別局面について最善手を求める
これなら、1対局がだいたい100手前後、多くとも700手台（≠指数関数オーダー）ということで、
多分PSPACEぐらいには収まるんｼﾞｬﾏｲｶ、（そうならP=NPの影響範囲内）
|
- コンピュータが全手を調べ尽くした時代到来すると
897 ：893[sage]：2012/09/17(月) 19:18:01.71 ID:/oo7GlVX - 訂正が必要っぽい
誤： 多分ガチの完全解析（相手のあらゆる応手で生じ得る局面についての最善手決定）の場合だと思う
正： 多分盤をn×nに拡張した一般化将棋の場合だと思う
ゲームの複雑性を論じるとき、なぜかわからないが盤面をn×nに拡張した一般化したゲームで解析するのが慣例っぽい
例： ttp://ci.nii.ac.jp/naid/110007123956
↑これはゲームを一般化しているが、問うているのは全局面でなく、所与の1局面の最善手決定の手間
>>895
普通の将棋ソフトの最善手は読み切って得たものでないから、真の最善手である保証（証明）が無い
ソフトによって答えが割れるし、誤答も探せばそこそこ出てくるはず
|
- コンピュータが全手を調べ尽くした時代到来すると
899 ：名無し名人[sage]：2012/09/17(月) 19:37:10.79 ID:/oo7GlVX - ３行で頼まれた、
・一般化将棋（n×n）の複雑性はEXPTIME完全（問題のサイズnに関してEXPTIME完全
・普通の将棋（n=9固定）における最善手決定の手間は、探索する段数dに対してPSPACEだと思う（漏れが
・普通の将棋（n=9固定）における最善手決定の手間が探索する段数dに対してPSPACEでありかつ
P=NPが証明されたら、最善手は多項式オーダーの局面だけ見て多項式時間で解けるハズ
・普通の将棋ソフトの最善手は読み切って得たものでないから、真の最善手である保証（証明）が無い
ゲームの複雑性を問うときの問題のサイズは盤の寸法nで与えられ、
最善手決定の手間を言うときの問題のサイズは探索の深さdで与えられる、みたいな
|
- コンピュータが全手を調べ尽くした時代到来すると
907 ：名無し名人[sage]：2012/09/17(月) 20:58:42.79 ID:/oo7GlVX - >>904
なんで真の最善手の決定の手間がPSPACEなのかぐらいは説明しないでもないが
「まだ証明はされていないが今の技術ではP以下の手間にならない見込みである」
というあたりを説明しようとすると技術論の詳細に踏み込まねばならずﾒﾄﾞｲんでﾊﾟｽ
だいたい普通の高校生が知ってどうこうなる知識でもないわけだし、
|
- コンピュータが全手を調べ尽くした時代到来すると
913 ：名無し名人[sage]：2012/09/17(月) 21:54:56.83 ID:/oo7GlVX - >>910
>970は、証明がなされていない現状ではきちんと説明するのが難しい、と書いてあるわけだが
>証明する必要は無いんだけど
ｵｲｵｲ
その返しはﾏｼﾞｶﾖ…
|