- 1 名前：デフォルトの名無しさん mailto:sage [2007/04/06(金) 15:33:11 ]
- できたらよろこんでやる。
前スレ
おまいら最強の将棋プログラムしてみろよ part5
pc11.2ch.net/test/read.cgi/tech/1109307327/
- 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 ]
- 作者の作意では、歩の合駒が出来ないから(打ち歩詰め)後手の負けって事らしいね
- 368 名前：名無しさん＠そうだ選挙に行こう [2007/07/29(日) 19:35:59 ]
- >>366
先手の方から、同一局面への王手を外せるんだから
先手が繰り返す方が悪い
- 369 名前：名無しさん＠そうだ選挙に行こう [2007/07/29(日) 19:45:37 ]
- >>366
麻雀でいう形式テンパイを認めるっていうやつと同じだ
盤面をみただけでは打ち歩詰めではないのだからOKにしようぜ!
- 370 名前：名無しさん＠そうだ選挙に行こう [2007/07/29(日) 20:17:17 ]
- >>366
これ嫁
千日手の定義より、打ち歩詰めの定義の方が優先されている
歩で王手する手は、ルールによれば、打ち歩詰めの規定には当てはまらない
しかし、歩を取る4度目の王手は千日手の規定に当てはまる 後手の勝ちだ
「特に決められた禁手事項」
(将棋世界平成5年1月号付録の'93年版 将棋ルールブック)
３．打ち歩詰
持駒の歩を打って王手をした局面で
王手を解除することが不可能な状態になる時、その歩を打つ手
５．連続王手の千日手
一局中同一局面の最初と４回目の局面の間の
一方の指し手が王手の連続であった時、
王手をした側にとって４回目が出現したときの局面。
- 371 名前：デフォルトの名無しさん mailto:sage [2007/07/29(日) 20:55:46 ]
- 将棋のルールってこんなに複雑だったんだね
- 372 名前：デフォルトの名無しさん mailto:sage [2007/07/29(日) 22:10:18 ]
- 最初から完璧に考え抜かれて作られたルールじゃないから
想定外な状況に対処するために後付けルールを足して複雑になって来ている訳か
まるでこれは
- 373 名前：デフォルトの名無しさん mailto:sage [2007/07/29(日) 23:46:53 0]
- まるでこれは・・・何？
- 374 名前：デフォルトの名無しさん mailto:sage [2007/07/30(月) 00:03:11 ]
- 続きはWEBで
- 375 名前：デフォルトの名無しさん mailto:sage [2007/07/30(月) 00:05:43 ]
- 〃∩ ∧＿∧
⊂⌒（ ・ω・） はいはいわろすわろす
｀ヽ_っ⌒/⌒ｃ
⌒ ⌒
- 376 名前：デフォルトの名無しさん mailto:sage [2007/07/30(月) 02:02:41 ]
- >>350
ああ、やっと言いたいことが解った。
お互いが最善手を尽くせば、同一局面は二度あらわれないってのが
間違いだと思うぞ。それだと千日手に陥る局面というのはそもそも存在しない。
実際には、千日手ルールを無視した最善手だと千日手になってしまう局面が、
詰め将棋にあって今それを議論している。そして千日手は避けないといけないから、
それを効率よくコンピュータで処理する方法はどうかって話。
初期局面からの完全解析は当然無理だが、これは詰め将棋の問題を内包するし、
詰め将棋を適切に解く技術は、将棋のプログラム開発に必要
千日手になるタイミング云々の話は、そうしたことは当然わかっているものとして、
答えたんだよ
- 377 名前：デフォルトの名無しさん mailto:sage [2007/07/30(月) 02:19:16 ]
- どういった解釈が正しいかについては、議論があるだろうが、
いずれにせよプログラム開発の段階では、各ノードの結論として、
「先手勝ち」「後手勝ち」「千日手」に加え、「先手打ち歩詰め」と
「後手打ち歩詰め」を考慮しないと駄目だろうね。
- 378 名前：180 mailto:sage [2007/07/30(月) 02:34:52 ]
- >359-360
私のこの問題に関する（このスレでの）これまでの発言は
>180 >183 >185 >191 >199 >203 >211 >218 >223 >228 >233
>242 >248 >260 >263 >268 >275 >282 >284 >291 >312 >317
>322
言いたい事はこれがほぼ全てなのでそこから判断してください。
ちなみに「例え将棋の神様であっても……分からない」と言う意味は
人間、あるいは何も考えてないプレーヤー（機械を含む）が指した
将棋を途中から将棋の神様が引き継いだとしたら、それまでに
どの局面が何回現われたかと言う情報なしに指し継いだのでは
最善手が何か決められないし、千日手かどうかの判断もできない
と言う事です。
なぜなら、元々の話題が将棋の神様同士が対局した場合に現われる
局面だけではなく、理論上考えられるあらゆる局面に対して「勝ち」
「負け」「引き分け」の結論を出そうと言う話なのでそういうふうに
解釈したと言う事です。
- 379 名前：デフォルトの名無しさん mailto:sage [2007/07/30(月) 02:41:23 ]
- もひとつ追加すると、さっきも言ったが、「引き分け」の局面かどうかは、
その千日手ループにいつ突入したかで替わってくる。千日手判定が下る瞬間が違うんだから。
出現回数を保持していない局面のみの情報では、それが「引き分け」かどうか解らない
だから、
>「引き分け」でない局面の出現が一回しかないのは明らかなので、
> 完全解析後のテーブルとしては、すべての局面(手番込み)の
上記の「『引き分け』ではい局面」の、「局面」には出現回数を含ませる必要があって、
それなしには「引き分け」かどうか解らず、そして出現回数によって結果が違っているから、
出現回数の情報を単純にとっぱらうことは出来ない
おまいさんの言っている「解析中のテーブル」を「括弧付きのテーブル」、
「解析後のテーブル」を「括弧なしのテーブル」と読み替えて、>>340, 342 を見てくれ
それと>350で
1)「完全解析後のテーブルとしては持っていません」
2) 「ただし対局である以上「棋譜」が生成されているので、
棋譜を見れば、その対局での「局面」の出現回数は分かります。 」
棋譜の情報を保持していれば、出現回数が解るので、1)と2)は両立しないよ
もし仮に2)が実際の対局を想定していっているのであっても、
参照先である「完全解析後のテーブル」が、1)によって情報を失っているので、
付き合わせることは出来ない。ないのと一緒だ
- 380 名前：デフォルトの名無しさん [2007/07/30(月) 02:51:14 ]
- >>180は釣りか、解析後と解析中は判っていない
- 381 名前：デフォルトの名無しさん mailto:sage [2007/07/30(月) 02:54:22 ]
- >378
あんまし気にしない方がいいと思うよ、ここ2chだし
ちなみに量子コンピュータ関係で言うとね、まるで量子コンピュータが完成すれば
今コンピュータで扱っている問題がすべて並列に瞬間的に解けるとする
言説がまかり通っているけど、それは勉強不足
量子コンピュータでは、解きたい問題ごとにアルゴリズムを考える必要がある
自分の知る限り、Shor, Grover以外に、パッとする実用的な話はないのが現状
量子コンピュータで、例えば3x3オセロでも解くアルゴリムを作ったら
そりゃ後世に名を残す、いい仕事になると思う
だから仮に量子コンピュータデバイスが実現したとしても、
それを使って将棋を解くアルゴリズムが見つからない状況になると思うぞ
将棋は人間が作ったゲームだから、問題設定が非常に複雑だ
- 382 名前：180 mailto:sage [2007/07/30(月) 03:10:50 ]
- ついでに今、私の頭の中で整理されている（つもりの）イメージを
お話しますと局面と指し手の組の集合が3種類あります。
（細かく分けると4種類）
O(1):将棋の神様同士がお互いに最善手を指し合った場合の集合
O(2):将棋の神様が勝てる側（先手必勝なら先手、後手必勝なら後手）を
持って相手があらゆる手を指して来た場合に対応して勝つ手の集合。
結論が引き分けなら相手があらゆる手を指して来た場合に
悪くとも引き分けに持ち込む（相手がミスをすれば勝つ）手の集合。
O(3):ルール上許されるあらゆる手で初期局面からたどり着ける局面
及び指し手の集合（局面は指し手によりメッシュ状に連結される）
明らかにO(2)はO(3)の真部分集合であり、O(1)はO(2)の真部分集合です。
さらに
O(3)':ルール上許されるあらゆる手で初期局面からたどり着ける局面
をそこに至る手順で区別したもの及びそこからの指し手の集合
（局面と指し手は木構造で表現できる）
これまでこのスレで問題となっているのは「勝ち」「負け」「引き分け」の
区別を局面にラベル付けするにはO(3)の中で話しが閉じるのか、あるいは
O(3)'の集合に移行しなければならないのかと言う事ですよね。
私はGHI問題が存在するために局面を探索する途中のみならず、
その結果を保持するためにもO(3)'の集合上で表現しなければならない
（でなければ必要な情報が欠落する）と考えているわけです。
- 383 名前：デフォルトの名無しさん [2007/07/30(月) 03:26:02 ]
- 可能な局面数 Nにたいし、3回訪れた、0-2回訪れたという情報を持っていれば完全に解ける
2のN乗局面調べればいい
- 384 名前：180 mailto:sage [2007/07/30(月) 03:31:22 ]
- >381
いえ、私はほとんどたった一人の人を相手に話をしているつもりなのです。
それは将棋板の「将棋って数学に似てるの？」スレ
game12.2ch.net/test/read.cgi/bgame/1136526660/
で私とずっと議論を戦わせてた人（276)。この人に納得してもらいたい。
ちなみに私はそのスレで281の発言をした者です。
で、>359-360及びこのスレの>206他はその人の発言なんじゃないかな？と
もし違っていたらゴメンナサイ、誤ります。
- 385 名前：デフォルトの名無しさん [2007/07/30(月) 03:44:29 ]
- >>384よ、
可能な局面(N個とする) ごとに、3回訪れたかどうかの情報を持ち、かつ
局面データがあれば完全にとけているんだ 意味わかるか?
これ以上のことはないだろが どこが不満だ?
道筋は全く関係ない
まずは、初手からならば局面だけ持っていればいいことは判っているのか??
- 386 名前：デフォルトの名無しさん mailto:sage [2007/07/30(月) 04:08:11 ]
- >385
私も解析対象の局面に至る手順の情報全てを保持しなければならないとは
思ってません。ある程度（かなり？）、圧縮は効くでしょう。
ただ、実際に解析する際の手順としてはO(3)'上でゲーム木を展開するのが
いちばんシンプルで分かりやすいと思います。探索すべき局面は増えますが。
また初手から神プレーヤー同士が対戦するならば純粋な局面情報のみ保持
すれば良い、即ちO(1)上の結果にGHI問題が発生しないのは分かります。
まだ、いまいち良く分からないのはO(2)上の結果もそうなのか？
こちらの結果も経路により区別する必要は無いのか？と言う事です。
- 387 名前：デフォルトの名無しさん mailto:sage [2007/07/30(月) 04:15:33 ]
- >>378
ごめんね。
>>359は、>>355-357に対して、>>180をみれば「理論」の
話をしているのは分かるのに、「理論」だからこそ、
みんな付き合っているのに、「実行不可能」とか言い出すから、
いまさらそんなことを言うやつが出てくるのか、といった
意味合いの発言でした。
>>180に言ったわけではないです。
>妙に納得
は、
>>170と同じようなニュアンス。
ちなみに
> 人間、あるいは何も考えてないプレーヤー（機械を含む）が指した
> 将棋を途中から将棋の神様が引き継いだとしたら、それまでに
> どの局面が何回現われたかと言う情報なしに指し継いだのでは
この情報とやらは、棋譜で十分では?
それと、無責任なことはするなよ?
と思わなくもないのですが。
- 388 名前：378 mailto:sage [2007/07/30(月) 04:25:19 ]
- >387
ああ、そういう意味でしたか。それはこちらこそ失礼致しました。
引き継ぐべき情報はもちろん棋譜で十分ですね。
無責任な行為かも知れませんが、任意の局面に結論を出すためには
そのような仮定が必要になると思います。
- 389 名前：デフォルトの名無しさん mailto:sage [2007/07/30(月) 04:33:22 ]
- >>388
またまた、ごめん。
>それと、無責任なことはするなよ?
は、>>378に言ったのではなく、話の内容で、対局を引き継ぐのに
「千日手になるかならないかの瀬戸際で交代するなよ。せめて二回目の
局面で交代してやれよ。」と言う意味でした。
他の人もそう思ったかな?
- 390 名前：デフォルトの名無しさん mailto:sage [2007/07/30(月) 04:52:43 ]
- >>388
ちなみに
> 引き継ぐべき情報はもちろん棋譜で十分ですね。
とのことですので、>>379と意見が異なると言うことですよね?
>>379は、まったく、困ったもんですよね。
- 391 名前：デフォルトの名無しさん mailto:sage [2007/07/30(月) 12:46:16 ]
- >>378さん(>>379さんもかな)
>>217を、もう一度よく読んでみてください。
よく読むとわかると思うのですが、初期局面の駒配置については、
何の言及もされていないのです。
これは、「初期局面として、任意の局面を指定可能」という事でしょう。
上での議論は、「理論上考えられるあらゆる局面」を十分含んでいるので
心配しないでください。
- 392 名前：デフォルトの名無しさん mailto:sage [2007/07/30(月) 13:04:15 ]
- 将棋の完全解析って言うのは初手から終局までのすべての手筋を網羅した地図を作ることだろ？
当然そんなことは出来ないし意味が無いから勝敗に関係の有る部分だけ解析すればいいだけであって、
人間相手に最強を目指すなら同じ局面が何度来ようがその時に可能なベストの手を打ち続ければいいはず、
結果的にそれが千日手になっても将棋のルールに不備がある部分に達しても負けはしない。
- 393 名前：デフォルトの名無しさん mailto:sage [2007/07/30(月) 13:09:16 ]
- うん
それが何か？
- 394 名前：デフォルトの名無しさん [2007/07/30(月) 18:44:34 ]
- >>381
その通りで、量子コンピュータが実現すれば既存のコンピュータで難しい問題が
なんでも一瞬で解けるようになると思っている人間がいるから困る。
量子アルゴリズムがあって初めて高速な計算が可能になる。
ゲーム木の探索なんて量子アルゴリズムとは相容れないだろう。
- 395 名前：デフォルトの名無しさん mailto:sage [2007/07/30(月) 23:41:16 ]
- >>376、>>379
あなたは、>>345、>>350の内容を全然理解していないことがわかりました。
基本的に、話の発端である>>165と同じことを言っているんですよ？
あと、詰め将棋のルールと、指し将棋のルールが違うことを知っていますか？
ルールが違えば、検索方針も違うんですけど?
>>180の方は、
>引き継ぐべき情報はもちろん棋譜で十分ですね。
と納得したようですが、あなたは理解できましたか?
- 396 名前：デフォルトの名無しさん [2007/08/02(木) 14:41:33 ]
- >>394
>量子アルゴリズムがあって初めて高速な計算が可能になる。
高速な計算とは言わないだろ、手順を経て組み立てる計算なら高速であるが
局所的な超同時な仕組みでは計算しているというより状態の合成をしている
に過ぎないよな。
そもそも計算は「計って」、「数を算する」ことであて量子コンでは
計ってもないし、数も扱っていない。
量子コンピュータで致命的なものはソフトウエア、つまりプログラムの
仕組みが存在しないことだよな。
超同時演算にソフトウエアが存在したら、それが足を引っ張り
早いどころか亀速度になるｗ
量子コンピュータが学者の間で注目されないのは、ハードウエアとして
存在しなければいけないという前提があるからだろ。
電子回路な計算機で、ソフトウエアなしの計算機では利用価値などない。
「ソフトウエア」がどれだけ重要な発明であるか理解しておいたほうがいい。
- 397 名前：デフォルトの名無しさん mailto:sage [2007/08/02(木) 14:48:22 ]
- >>392
>将棋の完全解析って言うのは初手から終局までのすべての手筋を網羅した地図を作ることだろ？
「巡廻セールスマン問題」で完全解析を行ったというような話と同じだよな。
最適解だと証明したようなことを言う奴はいるが、結局は抜けが発生する。
類似問題を全数を判断せずに証明したと言い張るＤＱＮがいるが、
科学では仮説と実証だけでは、科学ではない。
仮説→実証→複数の反証で多面的に検証できなければ証明したことにはならない。
原理を解明したとか信じるヴァカも多いよな。まさしく宗教の域。
- 398 名前：デフォルトの名無しさん mailto:sage [2007/08/02(木) 20:57:04 ]
- >>396
禿げしく胴衣
- 399 名前：デフォルトの名無しさん mailto:sage [2007/08/03(金) 00:24:09 ]
- >>396
別にソフトウエア無でも超高速なデータベースとして機能すれば十分だろ
大体、計算機という翻訳語が変で、コンピューターは演算する機械だよ
つまり状態の合成をしているだけなんだがw
- 400 名前：デフォルトの名無しさん mailto:sage [2007/08/03(金) 00:50:10 ]
- >>396
量子コンピューターに対してどんだけ無学なんだよ、中学生か？
- 401 名前：デフォルトの名無しさん mailto:sage [2007/08/03(金) 00:54:27 ]
- 何の指摘にもなってないよ
- 402 名前：デフォルトの名無しさん mailto:sage [2007/08/03(金) 02:25:22 ]
- 量子デバイスでだって量子ゲートは設計できる。
即ちチューリングマシンが構成できるし、メモリーだって作れるので
原理的に現代のノイマン型コンピュータで可能な事はなんでもできる。
ただ量子エンタングルメントを利用した長いキュービットによる
超並列演算をしないと、現代のコンピュータより圧倒的には
速くならないと言うだけで。
長いエンタングルメントしたキュービットの列で
特殊用途の専用アキュムレータ(と専用アルゴリズム用特殊ハードウェア）を
構成して今のノイマン型コンビュータアーキテクチャの一部として
埋め込む事も出来るんじゃないかな？
周りのノイマン型の部分は既存のデバイスでも量子デバイスでも良いだろうし。
いずれにしろ、まだろくに存在していないものを
あれが出来てこれが出来ないと言うのは早計じゃないか？
アルゴリズムが無ければキュービットアキュムレータが働かない
（超並列演算が出来ない）のはその通りだろうが。
- 403 名前：デフォルトの名無しさん mailto:sage [2007/08/05(日) 02:01:57 ]
- >即ちチューリングマシンが構成できるし、メモリーだって作れるので
それではチューリングマシンであって、量子コンピュータではないだろ
頭変になったのか？
- 404 名前：デフォルトの名無しさん mailto:sage [2007/08/05(日) 02:24:09 ]
- 量子チューリングマシンと言うのが定式化されている。
- 405 名前：デフォルトの名無しさん mailto:sage [2007/08/07(火) 00:34:50 ]
- >>404
あたま悪そうだな。チューリングマシンの手順式手法に戻るのなら
従来技術に激しく勝てず、量子の意味すらなくなる。
手順式は手順を超える演算はできないんだよ。
量子チューリングマシンでは量子コンピュータが得意とする因数分解が
出来なくなるｗ
これでは古典的コンピュータの因数分解専用の演算回路に下った
たんなる量子トランジスタレベルだろう。
仕組みを手順通り行うという概念の壁が越えられないからこそ
古典的コンピュータには性能の限界があることすら知らないようだなｗ
- 406 名前：デフォルトの名無しさん mailto:sage [2007/08/07(火) 04:20:58 ]
- >405
量子チューリングマシンは古典的（決定論的）チューリングマシンとは
その動作原理自体が異なる。
決定論的チューリングマシンのアルゴリズムは量子チューリングマシン上では
（そのままでは）使えないだろうが、むしろ使う必要が無いとも言える。
参考：
results.atr.jp/atrj/ATRJ_25/08/main.html
- 407 名前：デフォルトの名無しさん mailto:sage [2007/08/07(火) 17:57:47 ]
- >>406
あたま悪いな。論理手順が存在する限る原理が異なろうが
手順を省略できないわけだ。手順が省略できなければ順番に実行する
以外ありえないわけ。勉強になった？
- 408 名前：デフォルトの名無しさん mailto:sage [2007/08/07(火) 18:00:07 ]
- >>406
そもそもチューリングマシンは命令語を受け取りそれを手順どおり実行する
タイプだろ。電送時間が存在しれば遅延する。
これでは古典的コンピュータが速度を上げられない理由と同じで
電送経路があるかぎり従来技術にはコスト的についてこれない。
つまり永久に開発されない。
- 409 名前：デフォルトの名無しさん mailto:sage [2007/08/07(火) 19:36:23 ]
- 量子チューリングマシンは古典的チューリングマシンが持つ能力を
全て保持しながら、なおかつ量子コンピュータ固有の機能も持っている。
量子ゲートに与えるデータ次第でどちらの働き方もできる。
量子チューリングマシンは計算可能性と言う点で
古典的チューリングマシンと全く同等であるが、
問題によっては（まさに）桁違いの計算能力を発揮する。
- 410 名前：デフォルトの名無しさん mailto:sage [2007/08/07(火) 19:46:16 ]
- どうでもいいけど将棋の話題しない？
振れるようなネタはないのだけど。
- 411 名前：デフォルトの名無しさん mailto:sage [2007/08/07(火) 20:07:00 ]
- うーん、難しいな。
Lispで将棋ブログラミングしたいと思っててまだ始めてないし。
と言うか、Schemeで書くべきかCommon Lispで
始めるべきかで早くも悩んでるしw。
- 412 名前：デフォルトの名無しさん mailto:sage [2007/08/07(火) 22:14:26 ]
- 非決定的チューリングマシンの話は出ないのか？
これが量子チューリングマシンで実現できればメチャ嬉しいのだが
- 413 名前：デフォルトの名無しさん mailto:sage [2007/08/07(火) 23:54:06 ]
- 量子コンピューターが出来る前に光子コンピューターの方が早く出来るでしょ。
|
 |
