- 1 名前：デフォルトの名無しさん mailto:sage [2007/04/06(金) 15:33:11 ]
- できたらよろこんでやる。
前スレ
おまいら最強の将棋プログラムしてみろよ part5
pc11.2ch.net/test/read.cgi/tech/1109307327/
- 267 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:10:13 ]
- >>261
おまえが言っているのは、完全解析が不可能、ということじゃないか?
完全解析は「すべての局面の勝ち負けか引き分けかを決定すること」。
つまり、表を正しく完成させるということだぞ？
- 268 名前：デフォルトの名無しさん mailto:248 [2007/07/28(土) 06:14:36 ]
- >264
「完全解析とは、そのひとつの表を埋めて、完成させる事」
と言うそれが可能だと言う保証がどこにも無いんだよ。
後で整理する作業が必要ないと言うならそれを作る手順は？
- 269 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:15:26 ]
- >>266
> ＞区別ありの表」とか、「区別なしの表」なんていらない。
> まず仮定をぶち壊してるけどこれOKなの？
言葉が、足りませんでしたか。
完全解析時の作業用の表は、たくさん必要です。
完全解析を行った結果出力として、
>単に「局面情報と手番と結果」を持つ表が一つあるだけでよい。
という表があればよい。
ということです。
完全解析ができるということは、この表を得ることができるということです。
反論をお待ちしています。
- 270 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:19:19 ]
- >>267
いや、いま問題になっているのはそうじゃないよ
将棋のルールは、一見、局面（駒の配置と手番）だけでは
勝ち負けが確定しないように見えるじゃんか
同じ手でも千日手になる場合とそうでない場合があるからね
つまり、将棋において状態とは、駒の配置と手番だけではなくて
「局面の出現回数の履歴」も含めたものでなければならない
そう考えられるわけだよ。素朴には。
でも、もちろん感覚的には、そんなことはなくて、履歴などなくても
局面（駒の配置と手番）だけで判断がつくように思える
その感覚が正しいかどうかがいま問題になっているのだよ
将棋というゲームの状態変数として「駒の配置と手番」だけで
十分なのかどうかと
ルールを素朴に読んだだけでは、不十分に思えてしまうわけで
- 271 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:20:16 ]
- >>269
>>270
- 272 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:23:42 ]
- >>268
「将棋の完全解析は不可能」を主張しているわけだ。
これが不可能なら確かに>>206は成り立たないね。
でも、基本的に>>217にもある通り「可能」が、共通認識なんだけど。
つまり、あなたが「将棋の完全解析は不可能」を証明できなければ、
>>206を否定する必要がある。
がんばってくれ。
- 273 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:27:43 ]
- あはは。千日手模様。
>>268、>>270、>>271の最善手は、「千日手」に持ち込むことか。
- 274 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:28:57 ]
- >>272
横からだけどおまいさんの言う「完全解析」っていうのは
あくまで「駒の配置と手番」だけを状態変数としたものだろう
たとえば、三山崩しにおいて、ルールを読んだだけでは
状態変数として「１の山の個数」「２の山の個数」「３の山の個数」
という３つの状態変数が必要に思える
でも実際にはこんなにいらなくて、それらのXORだけあれば
勝ち負けが判定できる
このように状態変数を減らすことが、将棋でもできるかどうか
それが論点だよ
- 275 名前：248 mailto:sage [2007/07/28(土) 06:29:04 ]
- >267 >269
完全解析の定義を勝手に自己流に狭く定義しないでくれ。
その定義での完全解析ができるという保証は無いだろ？
実際に可能なのは手順込みの局面にラベルを貼る事。
- 276 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:31:29 ]
- >>270
完全解析の定義と、それが可能かどうかを、まず、答えてください。
ここの立場をはっきりしないとお話にならない。
いいですか？
はっきり明記してくださいよ？
- 277 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:33:23 ]
- >>272
＞二人零和有限確定完全情報ゲーム
「完全情報」ってのは手順の情報も含むんだが
君はこの情報を欠落させても欠落させない場合と等価な事を証明する必要がある
- 278 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:33:52 ]
- >>273
レッテル貼りの詭弁
>>272
共通認識というか定理だろう
将棋のルールは駒の配置と手番とそれらの履歴とで
記述されているわけだから、当然「区別ありの表」は
作れるわけだよ
そこから「履歴」を消してもWell-Definedになる、
というのは自明なことではないと思うよ
- 279 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:38:49 ]
- >>277
>>206
- 280 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:41:11 ]
- >>279
そのアンカじゃループしてるよ
何か別の事言ってよ
- 281 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:48:05 ]
- >>274
>>259
- 282 名前：248 mailto:sage [2007/07/28(土) 06:50:04 ]
- >206の言ってる事はずっと以前からループしてるんだよ。
区別は必要ないから区別しなくて良いってずーっと。
- 283 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:51:05 ]
- >>259
>>261
- 284 名前：248 mailto:sage [2007/07/28(土) 06:55:40 ]
- あー、疲れた。
この議論だけで徹夜しちまったよ。
- 285 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:56:36 ]
- 反論が無くなったようだしとりあえず寝るか
何かあればまた今夜にでも参加するよ
みんなお疲れ
- 286 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 06:57:56 ]
- >>284
俺もだ
土曜出勤なのにな
>>276に長レスを書いてたんだけどバカらしくなってきた
ああやって「これにレスできないとバカだ」みたいな言い方をするのは
釣り師が一般人を議論に引きずり込むときの常套手段なんだよなあ
- 287 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 07:00:10 ]
- >>278、>>280
>>276
よろしく。
- 288 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 07:00:41 ]
- >>276
可能
- 289 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 07:01:35 ]
- あ、定義もか
誰か出してなかったっけ
- 290 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 07:03:19 ]
- >>248、>>278、>>280
>>269にも回答よろ。
- 291 名前：248 mailto:sage [2007/07/28(土) 07:05:31 ]
- 皆さん、お疲れさま。
付き合ってくれてアリガトン。
- 292 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 07:06:06 ]
- 「局面情報と手番と手順と結果」を持つ表を作れる事が完全解析ができるということ
- 293 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 07:11:27 ]
- 自分も寝る
おやすみ
- 294 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 07:12:23 ]
- なんか急に伸びすぎﾜﾛﾀｗｗｗｗ
- 295 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 07:32:27 ]
- 俺は松原先生の本を昔図書館で何冊か読んだ程度で
ゲームの数学は全然わからないからあれだけど
記号や用語などもたぶんでたらめ
状態変数X1、X2、…、Xnはそれぞれ
有限集合A1、A2、…、Anに値をとる変数として
直積A := A1×A2×…×Anの要素 X = (X1, X2, …, Xn) を
このゲームの状態という
Aから、Aの部分集合全体P(A)への写像 M がある（可能な着手）
Aから集合R:={勝ち, 負け, 引き分け, それ以外}への写像Vがある
Aの元X0があり、これを初期状態という
k手からなる手順Fとは、Aのk乗の元 ( X1, X2, …, Xk ) であって
X1 は M(X0) の元
Xi は M(X[i-1]) の元 （i = 1, 2, …）
をみたすもの
Aの元Xが到達可能であるとは、あるkが存在して、Xk=Xとなる
k手からなる手順が存在すること
到達可能な元の全体からなるAの部分集合をA'とする
ゲームが添え数づけ可能とは、A'からN以下の自然数への写像
Sがあって、すべてのA'の元XとすべてのM(X)の元Yとに対して
S(X0) = 0
S(Y) = S(X) + 1
となること
- 296 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 07:33:13 ]
- 以下添え数づけ可能なゲームを考える
将棋は「局面の出現回数の総和」で添え数づけ可能
k手からなる手順が終わる手順であるとはV(Xk)が勝ち、負け、
引き分けのいずれかであること
あるKが存在して、k>Kのときk手からなる手順は存在しない
完全解析WとはA'からRへの写像で次をみたすもの
V(X) が勝ち、負け、引き分けのいずれかのときは
W(X) = V(X)
S(X)が偶数で、かつ、集合M(X)のSによる値域S(M(X))が
勝ち、負け、引き分けだけからなるとき、それが
・勝ちを含むならば、W(X)は勝ち
・勝ちを含まず引き分けを含むならば、W(X)は引き分け
・それ以外はW(X)は負け
S(X)が奇数で、かつ、集合M(X)のSによる値域S(M(X))が
勝ち、負け、引き分けだけからなるとき、それが
・負けを含むならば、W(X)は負け
・負けを含まず引き分けを含むならば、W(X)は引き分け
・それ以外はW(X)は勝ち
次が成り立つとき完全解析が存在する（十分）
A'の元Xについて、Xは次のいずれかを満たす
・M(X)は空ではない
・V(X)は勝ち、負け、引き分けのいずれか
証明はS(X)の有限性による
- 297 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 08:04:52 ]
- >>206はごちゃごちゃ言いすぎ。
完全解析を「すべての局面の勝ち負けか引き分けかを決定すること」と
手順を含まずに定義したんだから、解析後に手順が関係ないのは、自明。
この定義で、解析後に手順がどうのと文句つけるのがアホ。
>>292のように、
>「局面情報と手番と手順と結果」を持つ表を作れる事が完全解析ができるということ
と定義に、手順を入れれば、解析後も手順も関係するが、こんな定義初めて見たよ。
- 298 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 08:24:01 ]
- >>295, >>296 打ち込みサンクス！！
それによると、A'は履歴を含んでいるわけではないのだから、
やっぱり「完全解析」の定義は、局面だけであって、履歴は関係ないんだね
上の議論は、将棋固有のルールを反映したものではないけれど、
将棋もまた上の数学の枠内でのものなのでしょう
「M(X)は空ではない」ってのは、例えば両方ともパスするしかないような
状況はありえないって事だよね？更に勝ち・負け・引き分け以外の
終わり方は、将棋ではあり得ないから、やっぱり将棋は局面だけで、結論がでているんだ
- 299 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 11:21:25 ]
- 途中まで人間が指して、そのあと最強ソフトが指すならデータベースは使えないってことだろ
千日手があるから・・・
全局面をNとしたとき、その局面が何回現れたかを記録した
0から3までの数字列N個分を保持していなければならない
最終的には4のN乗程度の状態を保持しなければ、途中差しは出来ないって事だ
- 300 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 11:36:00 ]
- >>297
いやいや、>>292などは既存の常識に疑義を言ってるのだから、
「初めて見る」は非難にはならないよ
>>298
数式に惑わされたらだめだろ
>>295-296は何も新しいこと言ってないぞ
そしてさりげに>>295のAは履歴も含んでるよ
Sは手数とか言ってるしな
履歴を持ってないとVが千日手を判定できない
最後の条件は、勝敗未定ならば有効な手がある
ということ
たとえばもしルールでステールメイトを負けにするのを
忘れていたりすると、
M(X)が空（有効な手がない）で、しかも
勝ち負け引き分けのいずれでもない
という状況が発生するね
- 301 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 11:45:39 ]
- >>295, >>296 の論法で完全解析が可能であるというには、
駒の配置に加えて「この局面が何回目か」というパラメータも
ノードの状態変数として加える必要があるということ。
完全な履歴は必要ないが、何回目かは必要となる
これが「局面の出現回数の総和で添え数字づけ可能」の意味と理解した。
だとすると、途中で人間×２からコンピュータ×２に交代するとして、
全ての局面の出現回数を保持していなくても「この局面は何回目です」と
だけ伝えればいいんでないかい？後は事前に完全解析された結果に基づいて、
最強ソフトが「先手の勝ちです」「後手の勝ちです」「引き分けです」
とだけ伝えてオシマイになるはず。少なくとも十分条件としては。
- 302 名前：デフォルトの名無しさん [2007/07/28(土) 11:47:24 ]
- >>301
勝ち負けの決まっている手順の途中に千日手が現れる可能性有り
- 303 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 11:53:02 ]
- >>299
将棋というゲームの正しいイメージはこうかもしれないな
N個のマスと、それらをつなぐ線があり
マスのうちいくつかは赤か青に塗ってある
二人が交互にマスに石を置いていく
一つのマスには３個まで石を置ける
４個目の石を置いたら引き分けで終了
赤のマスに石を置いたら先手の勝ち
青のマスに石を置いたら後手の勝ち
ただし直前に相手が置いたマスから
線でつながっているいマスにしか置けない
- 304 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 12:11:18 ]
- >>300
だいぶ問題が絞られてきたね。
確かに、Aが履歴を含むのかどうかで、話は全く変わってくる。
Aに出てくるnって何だ？漏れはX1, X2が、例えば各駒の場所の様な変数で、
nが駒やボードに対応するものかと思った。で、その直積であるAは
履歴を含んでいないな、と。それだと千日手の判定が出来ないから、
少なくとも、「この局面が何回目か」という情報をAnとして加えてやれば、
完全解析の対象になる、という意味だと理解したんだが。
そしてある局面が何度でてくるかという情報は、手順から
考えれば何通りでもありそうなものだが、完全解析の対象としてみた場合、
最善の選択をして射影していくのだから、S(X)が決まってくるのかなと
思ったのだけど？
突き詰めると、やっぱり
> 将棋は「局面の出現回数の総和」で添え数づけ可能
のところが漏れには解らない。
うーん、難しいね、Anの意味とS(X)の意味、もし良かったら教えて
- 305 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 12:18:15 ]
- >>302
人間が指す以上、必ずしも最善手の連続ではないから、
それまでの履歴に、「完全解析」では出てこない履歴があって、
以後の手順に千日手をもたらす可能性がある。
そのため事前に用意した「完全解析」のテーブルが必ずしも
使えなくなる、でいい？
だとすると、これって結局、GHIの問題とほとんど同じだね
GHIの場合は、探索アルゴリズムが完全でないことに起因、
人間からコンピュータに替わる場合は、それまでの履歴が最善手でないこと
（勝ち負けを見落として、無駄な経路を辿っている）ことが原因
しかしこれらが、将棋の完全解析の可能性を排除するものではない
って、これでいいのかな？
- 306 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 12:25:55 ]
- >>304
今から出かけるから手早いけどごめん
X1、…、Xnが駒の場所などの変数で、
A1、…、Anがその値集合
たとえばX1は「先手玉の場所」で
A1は{「1一」、「1二」、…、「9九」}
みたいな感じ
それで、「同一局面４回」のルールを記述するために
（立会人に見せて「引き分けですね」と言ってもらうために）
局面の出現回数も、X1、…、Xnの中で持ってなきゃいけない
俺もおまいさんと多分だいたい同じ考えだよ
でも全部の局面の出現回数を持たなきゃいけないと思ってる
問題図までを指すのは神ならぬ人間なのだから、
神様に言わせれば変な手などもあるはず
そこから神様が引き継いだとして
勝つつもりで指してたら、途中で「その局面は４回目ですよ」
といわれて引き分けになっちゃうかもしれない
そんなわけでXnの中にはすべての（膨大な数の）局面に対して
その出現回数をあらわす変数が含まれてる
ことを俺は想定してた
- 307 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 12:29:34 ]
- >>306の続き
S(X)は「今の状況までの初手からの手数」で、
どうせ有限なのだからそんなの持ち出さなくてもいいのだけど
議論を簡単にするために出してみた
千日手がある以上、無限に多くの手数は指せない
だから手数の多いものから逆にさかのぼって
2000手以上は解明済み… 1000手以上は解明済み…
などとすることができる
>>305
たとえば簡単な状況で、自玉は必至、相手玉には
３種類の詰みが見えてるとする
ここで、もしその詰み手順の途中の局面が
３回出現済みだったら、自分は相手玉を詰めれない
だから千日手引き分けになる
もちろんそうでなければ勝ちになる
これは履歴が結論に影響を与えてるんじゃないかな
- 308 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 12:49:16 ]
- >>306
なるほど「局面の出現回数の総和」って「全ての(膨大な数の)局面に対してその出現回数」
っていう意味にも読めるね。確かにこれを全て保持したとしても、局面の数が有限であり、
千日手ルールで頭が押さえられているから、それを状態変数とみたてても、取る値は
高々有限集合になって、>>295 の条件を満たす
人間から神様に交代する場合は、確かに全部保持している必要があるだろうね。
先にも書いたように、勝ちの見落としがあるから、GHI問題と同じ現象が生じる。
で、問題なのは「将棋が完全解析されるには、状態変数として、その局面の出現回数だけで
良いのか、それとも全ての局面についての出現回数が必要なのか？」ってところに絞られてきた。
>>296 氏がさらりと書いた、『将棋は「局面の出現回数の総和」で添え数づけ可能』って
いう命題、この証明を載せた文献とかが解れば、それ見てはっきりするんだが
今から出かけるってことだけど、また暇な時に相手してね、サンクス
- 309 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 13:17:27 ]
- ところで、完全解析って、すべての局面の「勝ち」「負け」「引き分け」の
他に、「何回間違うと状態が変わるか」って情報いらないの？
対局は、必ず「詰み」まで指すものする。
神Aと神Bが対局して、神Aが先手。先手必勝と分かっている場合、神Aは単に「勝ち」を
選んでいけばいいが、「負け」しか選べない神Bはどんな情報を基にたくさんの「負け」の
中から手を選ぶのかな？
また、形勢差がついている局面から「人間vs神」が指し継ぎ、神が神が判断して形勢不利側を持つ。
このとき神は、差を詰めなければいけない訳だが、どんな情報を基に手を選ぶのかな？
- 310 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 13:25:12 ]
- よく考えたら、その局面の出現回数だけ保持していたとすると、
状態が遷移したとき、次の状態が何回目かなんて解りっこない
したがって、あるノードの千日手判定はできるが、そこから一つ前の手順に
後退解析することすら不可能になってしまう。なぜなら、ノードは
その局面の出現回数しか保持していないため、
局面A(1回目) → 局面B(4回目) → 千日手で引き分け
といったツリー構造があれば、
局面A(1回目) → 局面B(1回目)
局面A(1回目) → 局面B(2回目)
局面A(1回目) → 局面B(3回目)
というツリー構造も必ず存在するわけだから。したがって、全ての局面に
ついての出現回数がないと、そもそも完全解析の際に千日手に至る
手順を落としていくことが全く不可能になってしまう。
結論は「棋譜としての履歴は必要ないが、全ての局面についての
出現回数を保持する必要がある」ってことになりそうだ。
- 311 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 13:25:53 ]
- (つづき)
でも全ての局面について出現回数を保持するのは、理論的には簡単であっても、
現実的にはまず不可能。で、結局は順番はともかくどういった局面がこれまでに
出てきたか、その回数と共に保持していくことになる（これは実装上の問題であって、
理論的には全ての局面についての出現回数保持と同じ）。
最後の問題は、なぜ全ての局面の出現回数を保持しておけば、
将棋が添え数づけ可能になるかってことだ。>>296 の後半にある
「次が成り立つとき･･･」以下を証明なしに受け入れるとしても、
ここが争点として残る。でないと「以下添え数づけ可能なゲームを考える」
という前提から崩れてしまう
松原先生の本には、この辺の理論は載っているのかな？
- 312 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 13:27:04 ]
- >309
それを考慮するためには同じ「勝ち」「負け」「引き分け」の結論でも
どんな結果が「勝ち」 or 「負け」側にとってより良いとされる手なのか
その価値基準を事前に定義しておく必要があるよ。
つまり「勝ち」「負け」が既に分かっている局面で、形勢差はどう定義
されるべきなのか？
- 313 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 13:29:43 ]
- >>309
うーん完全解析の立場からいえば、その時は神様が「負けました」って
頭を下げるんだよ。で、ヘボな人間がキョトンとするという。
したがってその問題は、完全解析の枠内では無いと思うぞ
実際のプログラムを作る場合には、非常に重要になるには違いないが
余談だけど、プロ棋士も、負けのときに形を作って投げるよね
- 314 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 13:34:53 ]
- >>313
> うーん完全解析の立場からいえば、その時は神様が「負けました」って
> 頭を下げるんだよ。で、ヘボな人間がキョトンとするという。
これって、笑い話だよね？
結果は分かっているから「いきなり投了」ということで、実際は、指せば指せるよね？
指せないとなると、それはそれで変。
- 315 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 13:35:53 ]
- >>309
囲碁やオセロなどは目数や石数によって勝ち（負け）の価値が決められるけど、将棋は？
- 316 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 13:41:52 ]
- >>315
>囲碁やオセロなどは目数や石数によって勝ち（負け）の価値が決められるけど、将棋は？
相手玉を詰ませば勝ち。
- 317 名前：312 mailto:sage [2007/07/28(土) 13:42:14 ]
- >315
詰め将棋に準じて考えれば勝つ側はなるべく短い手数で勝つ手を選び
負ける側はなるべく長い手数で負ける手を選ぶべきなのだろうが、
結論が引き分けの時は？？？
また手数が同じならすべての手順は価値が同じなのか？
私には良く分からない。
- 318 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 13:44:13 ]
- >>314
笑い話かどうかともかく、相手のミスをどれだけ仮定するかは、実際の将棋対極では
非常に重要な要素に思うぞ、プログラム開発に限らず。いわゆるハメ手ってやつね。
相手がヘボなら、ハメ手を使って早々に対極を終わらせるだろうし、相手が上手ければ
ハメ手を見透かされて逆に咎められるだろうから、そんな手は使わないだろう。
ハメ手は、素人相手の、相手のミスを前提とした手法だが、プロでも形勢が悪いときは
それに近いことをするようだ。たとえば米長さんの本に、状況がこちらに不利であると、
ギャンブルっぽい手をあえて選ぶと書いてあった。
- 319 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 13:55:13 ]
- 神はどう相手にミスを期待して、手を選ぶのか。
神が神でいられるのは、初期局面だけなのだろうか・・・
- 320 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 14:02:00 ]
- 子ノードの勝ち手順の多寡かなぁ・・・
でも手順は少なくても簡明な勝ちもあるだろうし・・・
- 321 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 14:14:10 ]
- そうか
この議論は>>162-163に対する>>164のレスから始まってるのか
- 322 名前：180 mailto:sage [2007/07/28(土) 14:27:08 ]
- >321
そう。そして私が>165の意見に対してキツイ事を書いて
これだけ燃え上がってしまった。
今思えば、彼が考えていた前提（神様同士が初手から対局したと仮定）が
分からなかったとは言え、失礼な書き方をしてしまった。
>165さん
今更ですが済みません。ゴメンナサイ！
- 323 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 14:29:27 ]
- >>317
昔、ちょっとGAをやったとき、生き残り戦略はそんな感じにしてた。
引き分けの時、手数が同じ時は、駒得している手数が長いほうが有利としてた。
- 324 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 16:27:51 ]
- くどいようだけど、最後に一言だけ言わせて。
既存のゲームの理論を用いて、将棋の完全解析可能性を証明するには、
将棋が添え数づけ可能であることを示す必要があるのだろう。そして局面に、
全ての局面についての出現回数を保持すれば、それが添え数づけ可能になるようだ
しかし、それは「将棋が完全解析可能か」という命題には答えても、
我々が議論してきた問題とは微妙にずれているような気がする。
我々は「将棋を完全解析するのに、局面の出現回数（＝履歴）を保持する必要があるのか？」
という問題を議論してきたはず。これは「将棋は完全解析可能か？」とは違う。
「局面だけで完全解析が出来るか？」という命題は、>>296の理論にもとづいて
行おうとする限りにおいては、千日手の判定ができないため>>300 氏の言っている理由により
証明出来ない。しかしこれは、他の理論で証明することまでも不可能であると言っている訳ではない。
もし局面だけで完全解析が可能だとすると、少なくとも出現回数付きの完全解析から、
一意に射影できるはず。なぜなら後者は前者に情報を追加したものだから。
もし前者で完全解析が可能であるなら、追加した情報（＝局面の出現回数）は
余分な情報であって、後から射影作業によって取り除ける。
- 325 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 16:28:32 ]
- （つづき）
とりあえず「局面の出現回数つきのノードで考えると、完全解析が可能」を認めるとしようや。
上の「局面の出現回数」は、そのノードの出現回数だけではなくて、全ての局面の出現回数ね。
ここで、次の問題を考えてみる。
（＊）出現回数つきの状態で考えて、完全解析した状態ツリーを得たとする
このツリーに含まれる状態のうち、出現回数の項目だけ違っていて駒の配置が
同じものは、同じ結果（勝敗および千日手）がマークされているのか？
ここで、人間の勝ち筋見落としやGHI問題、また「その局面に至る途中で、
千日手の局面を経由した恐れがある」というツッコミは、不要。ミスなしは
前提であるし、「GHI」や「途中の千日手」といった問題は、出現回数つきの
状態ツリーではそもそも存在しえない。なぜなら、今議論の出発点としているのは、
回数まで出現回数まで含んだノードなんだから、「途中で千日手」を経由していないのは、
出現回数の情報から明らか。
- 326 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 16:29:13 ]
- （つづき）
何が言いたいかというと…
状態図にループ構造があると、数学的に完全解析の存在の証明が非常に難しそうだ。
で、状態変数に、全ての局面についての出現回数を保持するのは、そのループ構造を
千日手に至るまでの手順で展開し（添え数づけ可能にし）、数学で知られている
既存の完全解析の理論に乗っけるための便宜的な手法に過ぎないんじゃないかと。
もし（＊）が満たされれば、勝ち負けの情報を一意に保ったまま、折りたたんで、
局面だけの完全解析に移行できるように思うのさ。折りたたむと、当然ツリーから
ネットワーク構造（ループ含む）となる。
この段階で「局面だけだと、途中の千日手を経由しているかも」と議論するのは不要。
なぜなら、もともと出現回数つきのツリーから折りたたんでいるんで、先に述べた
理由から、考える必要がない。そして勝ち負けがつく局面（ノード）以外は、全て千日手の
局面のはず。当然、千日手の局面は千日手の局面で、閉じたネットワークを作る。
勝ち負けが決定したノードが千日手に繋がってないんだから。もはや勝敗・千日手とも
出現回数の差異によって、その間のツリー・ネットワークの交叉が変化しないのは明らか。
これはあくまでも、（＊）の前提が満たされた場合の話ね。
でだ、（＊）の問題について、誰か解るヤシはおらんか？これが鍵になる気がする。
何らかの簡単な論理で言及できそうにも思うのだが？
- 327 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 16:54:30 ]
- >>324-326
(*)については「出現回数の項目だけ違っていて駒の配置が同じもので、
結果が異なることはある」でしょ。
それも「しばしば経験する」からこそ、みんな困っていて、
transposition tableにやむを得ず経路を入れなくちゃいけないわけで。
- 328 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 17:04:55 ]
- >>327
きっとプロの方すね、了解しました
これで漏れの中では解決
サンクス！！
- 329 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 17:08:38 ]
- >>327
それGHI問題じゃないの？
- 330 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 17:13:16 ]
- >>327
反例を棋譜で示せる？
- 331 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 17:20:35 ]
- >>329
GHI問題だよ。
GHI問題は「駒の配置が同じなのに、経路によってその局面の
勝ち負けのラベル付けを変えなければならないことがある」ということだよ。
まさに325の(*)の話でしょ。
325が議論していた数え上げ方の言葉で説明するなら、
「aの局面が3回出現している状態でのbの局面は負けだが、
aが2回しか出現していない状態でのbの局面は勝ち」ということがしばしば起きる、
というのがGHI問題。
- 332 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 17:24:45 ]
- >>331
だとすると、GHI問題は、必ずしも探索アルゴリズムの問題とは限らなくて、
完全な探索を行ったとしても、局面から以前の局面の出現回数を取り除いたことに
起因して起こる、より本質的な問題だということになるのですね
上の方に出てきたPDFの説明では、この辺りがハッキリしない
それとも、そういった問題を総称して「GHI問題」っていうのが普通なんですか？
- 333 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 17:28:14 ]
- >>331
＞ここで、人間の勝ち筋見落としやGHI問題、また「その局面に至る途中で、
＞千日手の局面を経由した恐れがある」というツッコミは、不要。ミスなしは
＞前提であるし、「GHI」や「途中の千日手」といった問題は、出現回数つきの
＞状態ツリーではそもそも存在しえない。なぜなら、今議論の出発点としているのは、
＞回数まで出現回数まで含んだノードなんだから、「途中で千日手」を経由していないのは、
＞出現回数の情報から明らか。
ここ読んだ？
ここが間違ってるの？
- 334 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 17:32:26 ]
- >>333
漏れが意図したのは、探索アルゴリズムの問題による、見かけ状のGHI問題
PDFの2ページ目での説明では、こっちがメインだった
>>332 で書いたように、 完全な探索を行った上でもGHIが生じるのであれば
そっちのGHIは>>325 で書いたGHIには含まれないと解釈してくれ。
少なくとも、漏れが書いた意図としてはそう。
- 335 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 17:35:02 ]
- >>330
岸本さんに言えば出てくるかもしれないとは思うけど、自分では持ってないなぁ。
例えば234の論文の図3「続詰むや詰まざるや」42番が、
GHIを考えなければ間違えちゃうわけだから、
その証明木の中のどこかに(*)が満たされない部分があるということでしょ。
>>332
何かの探索アルゴリズムに起因した問題ではないよ。
「同一駒割の局面が必ずしも同じ局面としては扱えない」という問題の総称が
GHI問題、ということでしょう。
- 336 名前：デフォルトの名無しさん [2007/07/28(土) 17:45:14 ]
- (*)の反例は>>307の後半？
- 337 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 19:40:47 ]
- 自分も状態変数には出現回数が必要だと思ってるけど
不要だっていう意見の人まだ居る？
- 338 名前：デフォルトの名無しさん mailto:sage [2007/07/28(土) 19:55:14 ]
- >>324
すまん。
命題：「○○は△△△である」
→真 or 偽
の形で整理してくれないか？
問題がいくつあるのか、結論がなんなのか、結論の出ているもの、出ていないものがよく分からん。
- 339 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 08:20:49 ]
- >>337
そもそも「双方が最善を尽くす」という前提があるので、
「引き分け」でない局面の出現が一回目ではない、というのは、
前提条件を崩しているので議論の余地はないのでは？
- 340 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 09:22:22 ]
- >>339
一見すると、千日手のループであっても、入る場所が異なると
千日手と判定を下すタイミングが異なってくる。
したがって、ある手順では千日手のループの一部であっても、
別の手順で別の入り口から入ると、それが勝ち筋に必要な手順の一部となる。
いままでの議論を注意ぶかく読んで、 >>234 のPDFを見たらたぶん
そういう結論に至ると思うぞ。
- 341 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 09:29:58 ]
- >>339
あと、「最善を尽くす」ために、今すべての状態遷移についての
ツリーを作ろうとしていることも忘れないでくれ ツリーの一本一本は
必ずしも「最善」に絞られて作製しなくてはならないわけではない
- 342 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 10:05:36 ]
- 簡単のため将棋ではなく、>>234 のPDFの図1で考える
二度同じ局面が出てきた場合に千日手(引き分け)とするルールを考える
まず最初に、すべての局面の出現回数を含めたツリーを考えるとし、
その出現順序をABCDEFGHの順にならべて、カギ括弧の中に書くとする
あるツリーでは、以下の手順で千日手(今は2手だけど)が成立する
手順1) A[10000000]→B[11000000]→E[11001000]→H[11001001]→E[11002001]
H[11001001]はE[11002001]しか行き先がない。E[11002001]は千日手だから、
後退解析によりH[11001001]は千日手だ。しかし以下のツリーを考えると、
手順2) A[10000000]→C[10100000]→F[10100100]→H[10100101]→E[10101101]→G[10101111]
H[10100101]は明らかに勝ち筋に必要な局面だ。
もしカギ括弧をとっぱらったとすると、手順1)では千日手としか結論づけられない局面Hが、
手順2)では勝ち筋の一部。
したがってGHIがある限り、カギ括弧付きのツリーから、カギ括弧なしへのツリーは、
一意に射影できない。重複した写像のなかから、与えられた局面に対する正解
を選び出すには、結局、なんらかの方法でカギ括弧と同じ情報をツリー検索に
加えないと駄目。これがGHI問題の本質だと漏れは理解している。
- 343 名前：名無しさん＠そうだ選挙に行こう [2007/07/29(日) 10:16:58 ]
- >>340>>341>>342は、頭がおかしいんだろ
探索した手と、指された手が区別できていない
- 344 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 10:28:24 ]
- どんな指し手にも対応できるように、
すべてを検索してしまえって話をしているのだから、
区別する必要はないように思うぞ？それとも釣りかな？
- 345 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 10:56:37 ]
- >>340
じゃあ、言い方を変えます。
そもそも「双方が最善を尽くす」という前提があるので、
「引き分け」でない局面の出現が一回しかないのは明らかなので、
完全解析後のテーブルとしては、すべての局面(手番込み)の
「先手勝ち」「後手勝ち」「引き分け」の状態のみ持てばよいのでは？
ということです。
>自分も状態変数には出現回数が必要だと思ってるけど
当然のことながら、完全解析中のテーブルとしては必要です。
あなたの書き方は、「どのテーブルに、状態変数が必要か」が、あいまいです。
- 346 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 10:59:30 ]
- >>343
探索で考える手順と、実際に指される手順を区別しないと、
千日手の発生状況が異なるから、意味がないっていいたいのか？
それは「カギ括弧無しには一意に射影できない」といっているのと同じだぞ
もちろん実際に指される手順は、括弧付き（括弧の情報を含む）なんだよ。
「括弧無しで議論して、手順1)での探索から、手順2)のHまで千日手と結論づけてはいけない」
といっているんだよ。
おまいさんは、カギ括弧無しで考えていて、手順1)を「探索した手」と呼び、
手順2)を「指された手」と言っているように思うんだが？
- 347 名前：名無しさん＠そうだ選挙に行こう [2007/07/29(日) 11:03:51 ]
- >>346は完全な釣りですから・・・相手にするのはやめましょうね
- 348 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 11:05:00 ]
- 俺は門外漢なんで申し訳ないが
>>331の
325が議論していた数え上げ方の言葉で説明するなら、
「aの局面が3回出現している状態でのbの局面は負けだが、
aが2回しか出現していない状態でのbの局面は勝ち」ということがしばしば起きる、
というのがGHI問題。
というのがサッパリわからない
ここで言うaとかbとかってそれぞれ同じ局面なんでしょ？
なんで勝ち負けが変わったりするの？
- 349 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 11:06:40 ]
- >345
>そもそも「双方が最善を尽くす」という前提があるので、
>「引き分け」でない局面の出現が一回しかないのは明らかなので、
この『「引き分け」でない局面』でいうところの、「局面」は、
今までの全ての局面の出現回数を、情報として持っている？持っていない？
漏れの説明もあいまいだったかも知れんが、そちらの質問もまた漏れには
あいまいにうつってる。悪いが、言葉を補ってくれ。
- 350 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 11:13:55 ]
- >>349
完全解析後のテーブルとしては、持っていません。
ただし、対局である以上「棋譜」が生成されているので、
棋譜を見れば、その対局での「局面」の出現回数は分かります。
- 351 名前：名無しさん＠そうだ選挙に行こう [2007/07/29(日) 11:14:08 ]
- >>348
同一局面が4回現れると引き分けで指し直しになる
引き分けにあえて持ち込むか、勝ちを狙うかという違いが出てくる
- 352 名前：名無しさん＠そうだ選挙に行こう [2007/07/29(日) 11:16:29 ]
- 途中から、人間→CPUに切り替える場合のみ局面の回数が必要
はじめからCPUなら同一局面はあり得ない(単に手を延長するだけでしかないため)
- 353 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 11:16:40 ]
- >>351
>>339
- 354 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 11:18:58 ]
- >>352
>>339
「人間→CPU」は、対局上「双方が最善を尽くす」ではない。
- 355 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 12:36:08 ]
- そもそも千日手で引き分けは王手とか詰み回避の時しか成立しないじゃなかったか？
何の意味も無い議論をしてるようにしか見えないのだけど。
- 356 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 14:10:13 ]
- まあ、完全解析自体が計算量的に不可能なんだから
千日手を巧いこと処理して、1万倍の速度で解析したところで
全然意味ないし、始めから机上の空論なわけですよ。
- 357 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 14:15:14 ]
- 机上の空論もなかなか楽しいもんだぜ？
- 358 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 14:21:59 ]
- ja.wikipedia.org/wiki/%E5%8D%83%E6%97%A5%E6%89%8B
千日手のルールって結構最近出来たものなんだね
- 359 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 14:44:00 ]
- >>180は、「例え将棋の神様であっても」といってる
理論と現実の区別もついてなかったのか・・・
妙に納得
- 360 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 15:07:08 ]
- 因みに地球上の全ての原子に1ビットづつ記録しても、
全ての局面を記憶することはできないし
かと言って量子コンピューターで将棋ができる時代の遥か以前に
名人は負けてるでしょうし。彼は何が言いたかったんでしょうね
- 361 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 15:11:28 ]
- >>351
24でR2300ていどのヘタレの意見だから的外れかもしれないけど
同一局面が出てきた場合、そこで千日手か打開かの選択が生まれるってのは
対局中よくある話なんで理解できる
ただ、331は引き分け（千日手）or勝ち（打開）じゃなくって
負けor勝ちというふうになってる
そこが理解できない
- 362 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 15:32:27 ]
- >>361
連続王手の千日手なら引き分けじゃなくて負けになるよ。
- 363 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 16:20:51 ]
- >>362
するどいね。ただ>361 の意見にも一理あって、
>351 に、引き分けも加えるべきだろうね
それと「最後の審判」っていう詰め将棋の問題があるようだ
現在の将棋のルールには不備があって、
必ずしも勝ち・負け・千日手で閉じるわけではない
打ち歩詰めのルールは、やや特例的なものだから、
仮に全部探索したところで、このルールを適用すると、
一部の状態ノードの勝ち負けが重複してしまう
現状の詰め将棋のプログラムに「最後の審判」食わせたら、
ただしく「不定です」って答えるのかな？
- 364 名前：名無しさん＠そうだ選挙に行こう [2007/07/29(日) 19:28:20 ]
- 後手が王手を防ぐために打つあい駒の歩が逆王手になっている。
先手がそれを取って王手をすると千日手になってしまい先手は取れない。
しかしその局面は先手が歩を取れないと、先手玉は歩打ちで詰んでる。
- 365 名前：364 [2007/07/29(日) 19:30:41 ]
- 個人的な意見だけど、詰め将棋としては歩詰みで、対戦としては後手の勝ちでいいんじゃない?
同一局面が2回しか出ていないなら王手を外せるんだから
- 366 名前：名無しさん＠そうだ選挙に行こう mailto:sage [2007/07/29(日) 19:30:46 ]
- >>364
打ち歩詰めで後手の負け
- 367 名前：名無しさん＠そうだ選挙に行こう [2007/07/29(日) 19:33:47 ]
- 作者の作意では、歩の合駒が出来ないから(打ち歩詰め)後手の負けって事らしいね
|
 |
