07/07/27 22:50:42
オセロって完璧に全手解明されてなかったっけ？
177:デフォルトの名無しさん
07/07/27 22:54:29
>>176
オセロ（通常は８ｘ８の事）もまだ解明されてないよ
６ｘ６盤は解かれてるけど
178:デフォルトの名無しさん
07/07/27 22:58:44
>>177
そうでしたか
179:デフォルトの名無しさん
07/07/27 23:11:50
8x8は解明したと力説する奴は結構いるんだけどな。
ぽえむ君だから仕方が無いんだけど、
180:デフォルトの名無しさん
07/07/28 00:18:54
>165の意見は強烈だなぁｗ。
一目、局面を見ただけで千日手（無限ループ）だと分かる？
今まで何回、同じ局面が出てきたか記憶しないで？
最強の者同士が戦ってるってどこから来た仮定？
例え将棋の神様であっても、これまでに現れた局面を
記憶しない限りループにはまってるかどうかは分からんだろ？
久々に笑わせてもらったよ。
181:デフォルトの名無しさん
07/07/28 00:25:56
>>180
おまえ変だ
完全に勝敗が決まっていたら、勝ちか負けか千日手しかない
182:デフォルトの名無しさん
07/07/28 00:33:30
>>180
勘違いしてるバカ
183:デフォルトの名無しさん
07/07/28 00:39:40
>181
意味不明！
184:デフォルトの名無しさん
07/07/28 00:45:26
全ての局面と試合結果の組データを構築する場合
局面・・・駒の配置と手番の情報だけが必要
結果・・・その局面から全探索した結果（勝ち・負け・千日手）だけが必要
185:デフォルトの名無しさん
07/07/28 01:03:20
>184
同じ形の局面でもそれが何回目の出現かを区別しないで
どうやって千日手だと判定するんだ？？？
もしかして特定の形をした局面が千日手になるか
ならないかはその形から自動的に決まると思ってる？
186:デフォルトの名無しさん
07/07/28 01:13:35
>>185
勝ちでも負けでもない局面はあいこだろが
187:デフォルトの名無しさん
07/07/28 01:15:00
>>185
だからそれは別の問題なんだって。
そっちの話題に関してはもちろん思ってないよ。
188:デフォルトの名無しさん
07/07/28 01:35:13
それよりお前ら開発してるのか？
189:デフォルトの名無しさん
07/07/28 01:39:39
>>180は、こっちで完全無視されたやつじゃないのか?
ｽﾚﾘﾝｸ(bgame板)
解析中と解析後の区別がついてないから始末が悪い。
190:デフォルトの名無しさん
07/07/28 01:41:50
>>188
スレは見てるけど最近将棋の開発はしてないなー
ちょっと前は高速化のためにSSE2の勉強やってたけどどんなところに使えるかな
191:デフォルトの名無しさん
07/07/28 01:45:49
だから特定の局面の勝ち、負け、引き分けを
正確に判定するためにはその局面に至る手順で
区別して扱わない限りそもそも不可能なんだよ。
言葉だけで説明するのは非常に難しいので、
後は"GHI問題"でググるなどして自分で勉強してくれ。
ちなみに特定の局面から全探索する場合、
そこから先の局面は手順により区別されている。
ところが探索の開始局面にその区別がなかったとすると
情報は蓄えられずにどんどん失われて行く。
192:デフォルトの名無しさん
07/07/28 01:51:14
>>191
おめー頭悪いな
193:デフォルトの名無しさん
07/07/28 01:53:00
>>180, >>185
どんな探索をしていっても、自分が勝った局面に、どちら側がどう工夫しても
持って行けない局面は、探索ツリーの中で閉じたループ状の構造となる。
ループ状の構造であれば、、局面の数は莫大とはいえ有限なので、
それを辿っていくと同じ局面が必ず繰り返されるので、千日手。
言いたかったのは上記のことで、ツリーの構造を議論するのに、
時系列で追う発想はもはや必要はない、ってこと。
194:デフォルトの名無しさん
07/07/28 01:57:41
>>191
＞ところが探索の開始局面にその区別がなかったとすると
＞情報は蓄えられずにどんどん失われて行く。
この部分の解説希望
失われて行く情報とは？
195:デフォルトの名無しさん
07/07/28 02:02:04
>>194
191は頭悪いよ
詰め将棋を解く(勝敗を決定)する事と、
すでに決定されている事の区別が出来ていない
196:デフォルトの名無しさん
07/07/28 02:04:10
千日手が決定している局面は、そこに至る手順に関係なく千日手なんだよ
197:デフォルトの名無しさん
07/07/28 02:07:06
>>165で言っている事と>>196は同じ事だ
>最強のもの同士が闘っているのだから、
>その局面が出た瞬間に、これは無限ループ＝千日手と解るはずだから
198:デフォルトの名無しさん
07/07/28 02:08:26
つまり
1) 探索ツリーを作る段階での議論
2) すでに完成した探索ツリーの構造の議論
がゴッチャになっているのかな？
その点では、>>191 氏にもミスはあるように思うが、
でも「GHI問題」ってのが 1)ではあるんだね
ちょっとググって勉強してみるよ 情報サンクス
199:デフォルトの名無しさん
07/07/28 02:17:01
>193
千日手になるのは単純な見て分かるループだけじゃない。
大きな流れの中で同一の節（局面）を4回通過するだけで起きる。
千日手にならない手順と容易には区別できない。
局面だけで区別するとゲーム木はツリー構造ではなく
メッシュ構造になるので辿りかたが全く決まらない。
そこら中がループしていて、
ループしていないところとの区別は存在しないんだよ。
200:デフォルトの名無しさん
07/07/28 02:23:21
>>199
将棋の完全解析は不可能、を主張しているということでOK?
201:デフォルトの名無しさん
07/07/28 02:23:33
>>199
手順は関係ない
勝ちと負けと引き分けしか無いのだから、局面が与えられればそれは決定するんだよ
探索によって結果が変わるなら、その探索が間違っているだけだ
202:デフォルトの名無しさん
07/07/28 02:30:16
勝敗が決定する局面では、次の指し手は一つに絞られる
千日手の局面では、一つに絞られないから、確かにメッシュ構造になるんだろう
でも、ループでもメッシュでも、ノードの数は有限だから、やはり千日手は千日手
確かにループになるって書いたのは間違いだったけど、
最初の議題「何度目の局面の情報は必要か」っていう点では、同じ結論になるんじゃないかな？
203:デフォルトの名無しさん
07/07/28 02:39:59
>200 >201
違う、違う。
その局面に至る手順により区別して（別の物として）
扱わない限り、その局面が勝ち負けか引き分けかを
決定できないと言ってるんだよ。
つまり局面をその現れる順番で展開したゲーム木を作れば良い。
手順に関係なく局面が与えられれば勝ち、負け、引き分けが
決定するはずと言うのが単なる思いこみなんだよ。
204:デフォルトの名無しさん
07/07/28 02:46:24
>>203は釣りですから無視しましょう
205:not 203
07/07/28 02:48:18
>>201
局面pがあって、その子供がc1,c2のみで、ともにXの負けの(一手詰みの)局面とする。
GHIがない場合、後退解析では
c1, c2の局面がXの負けとわかる->c1,c2だけを子供に持つ局面pはXの負けとわかる
だけど、もしGHIがあったら、pに来た時点で経路によっては4回目の同一局面になって、
引き分けになるかもしれない。
連続王手の千日手になってXの勝ちになるかもしれない。
だから、pの局面は結局勝ち負けが一意に定まらないというわけ。
それでも完全解析は理論的には可能で、要するに局面数Nだったのが、
ある局面に至るまでの経由局面を全て考慮しなくてはならないと言う意味で、
最悪の記憶量がO(N!)になるというだけでしょ。
ずいぶん爆発的に増えちゃうとはいえ、どちらの場合にせよ天文学的な局面数なので、
まぁそんなにまじめに考えてもしかたないと思うけど。
206:デフォルトの名無しさん
07/07/28 02:57:34
>>203
> その局面に至る手順により区別して（別の物として）
> 扱わない限り、その局面が勝ち負けか引き分けかを
> 決定できないと言ってるんだよ。
「区別が必要」という仮定で、手順により区別して
勝ち負けか引き分けかを決定したとするよね?
そうすると完全解析済みになるよね?
後は完全解析済みの結果を参照するだけでよいよね？
再解析の必要は無いよね?
その局面は参照するだけで、勝ち負けか引き分けか決定してるよね？
これは、あなたの主張する「区別が必要」と矛盾するよね?
この矛盾は、仮定が間違っていいたためであり、「区別の不要」
ということになる。
証明終わり。
これ背理法っていうんだけど、問題ある?
207:デフォルトの名無しさん
07/07/28 02:59:37
>>205
よーく言いたいこと解った！！サンクス！！
後退解析だけでは駄目なんだね 経路が必要なんだね
で、結局、局面だけでは判断できない･･･ってことか
ちょい目から鱗が落ちたよ 漏れの勉強不足を痛感した
208:デフォルトの名無しさん
07/07/28 03:05:35
例えば、勝ちと判別されている局面があったとして
勝つ手順がわかっていたとしても、
既にその局面が3回現れていたとしたらそこへは指せない
と言うことなんだろ???しかし、この場合、1回目で勝っている
209:デフォルトの名無しさん
07/07/28 03:08:47
>>207
局面だけ決着しているって
おまえも頭が悪いやつの仲間入りか???
GHI問題というのは、探索の中で現れるだけで実際に指した手ではないんだぞ
一回目で、勝ち負けが決していたら2度目は無いダロが
210:デフォルトの名無しさん
07/07/28 03:10:21
>>206 氏の意見は、O(N!)とO(N)がゴッチャになっていて、
「局面へ至る手順により区別」と「局面による区別」がすり替わっているように思う
その点において、>>203 氏の意見の方が正しそう
O(N!)からO(N)への射影は、一意には決まらないのじゃないか？
>>205 氏は、それをもって「決定できない」と言っているのだと思うよ。
211:デフォルトの名無しさん
07/07/28 03:10:50
>206
問題があります。
なぜなら勝ち、負け、引き分けが決定するのは飽くまでそこに至る手順により
区別された局面であり、その区別を外して形だけで同一視した局面は
一般的には決定不能だからです。
212:デフォルトの名無しさん
07/07/28 03:14:01
GHIとか言ってるやつは、よく聞け!!!
勝ち負け引き分けが分かっていたら、同じ局面は2度現れない
よく考えろ!!
213:デフォルトの名無しさん
07/07/28 03:19:23
>>210
確認。
完全解析の定義は「すべての局面の勝ち負けか引き分けかを決定すること」。
認識は、あってる?
「局面へ至る手順により区別」して、完全解析する。
完全解析後に、「局面による区別」し、参照する。
問題あるなら何行目か具体的に指摘してくれるか?
214:デフォルトの名無しさん
07/07/28 03:21:18
>>211
完全解析の定義は?
で、完全解析はできるのできないの？
215:212
07/07/28 03:22:26
同じ局面が現れるならそれは千日手である、という点が抜けていた
216:212
07/07/28 03:24:29
手順に関係なく完全解析は出来るよ
勝ち負けが決している局面は1度しか訪れないし、2度訪れるなら千日手
ただこれだけだ
217:212 これ嫁
07/07/28 03:28:03
二人零和有限確定完全情報ゲームは、
ゲーム理論で扱われるゲームの分類のひとつである
チェス・オセロ・石取りゲーム・囲連星・連珠・五目並べ・三目並べなどが該当し、
偶然に左右されない読みの深さを競う。
概要
これに分類されるゲームの特徴は、理論上は完全な先読みが可能であり、
双方のプレーヤーが最善手を打てば、必ず先手必勝か後手必勝か
引き分けかが決まるという点である。
Wikipedia
218:デフォルトの名無しさん
07/07/28 03:28:37
>213
分からないかな？
局面の形だけで区別したのでは答えが複数あるんだよ。
どういう手順によりその局面に至ったかにより異なる答えが。
219:デフォルトの名無しさん
07/07/28 03:30:01
>>213 氏の言う「完全解析」がもし可能であるとすると、O(N!)→O(N)への射影が可能
しかし、後退解析を使って「完全解析」するのは、GHI問題があるために不可能
どうやって「完全解析」するかの、方法論、つまりアルゴリズムの問題を除けば、
確かに>>208, >>209 氏の言うことにも一理あるようで、「完全解析」出来るのかも知れない
もし「完全解析」が可能であるとすれば、>>213 氏に漏れは同意 ここまでが漏れの今の認識
少なくとも、後退解析が持つ問題点と、完全解析が可能かどうかは、分けて議論すべき感じだね
220:デフォルトの名無しさん
07/07/28 03:32:57
>>218
そんなことは聞いていない。
(1)完全解析の定義はあってるかどうか。
(2)>>206の何行目が間違い。
を
(1)Yes or No
(2)X行目
と簡潔に答えてくれ。
221:デフォルトの名無しさん
07/07/28 03:33:59
>>208の言う通りだろう
千日手を回避して勝ちがあるなら初めからその手にすればいいし
回避しても価値がないならそのまま千日手を狙うのが最善
222:デフォルトの名無しさん
07/07/28 03:36:21
>>218の言いたいのはこういうことかな
現在の局面がある
この局面からは勝ち筋があるが
勝ち筋の途中である局面Aを通過する
よって、局面Aが「すでに3回登場しているのか」
「そうではないのか」によって違いが生じる
でもその場合局面Aから現在の局面になるのだから
結果は千日手なのだよな
223:デフォルトの名無しさん
07/07/28 03:36:37
>212
千日手になるためには同じ局面が"4回"現れる必要があるぞ。
2回目が現れたらその途端に千日手になるわけじゃない。
224:デフォルトの名無しさん
07/07/28 03:37:32
千日手のパラドックス
225:212
07/07/28 03:37:52
>>223
頭を使え!!!
226:デフォルトの名無しさん
07/07/28 03:43:17
>>223
イメージ的に、対局で、詰めろが回避できないと諦めた段階で投了するか、
詰まされるまで指し続けるかの違いかな。
227:デフォルトの名無しさん
07/07/28 03:44:41
>>209, 212
スマン、「で、結局、局面だけでは判断できない･･･ってことか」は、
後退解析の途中で現れる局面についての話題ってことに読み直してくれ。
しかし完全解析って、後退解析以外にそもそも定義できなそうだから、
正しくは後退解析の実行手順の問題と言い換えるべきか？ これで正しい？
228:デフォルトの名無しさん
07/07/28 03:58:02
>222
うん、つまりはそういう事。
すでに以前、局面Aを3回通過してれぱ頑張っても千日手にしかならないが、
そうでなければ（2回あるいは1回通過）勝ち筋があるというわけ。
そして局面Aから現在の局面に来たとしても、必ずしもそこに戻るとは限らない。
229:デフォルトの名無しさん
07/07/28 03:59:50
>>223
神同士が対局してるものとして、
同じ局面が現れる（2回目）って事は、仮に千日手ルールが無ければ3、4、5・・・回目も必ず現れるよね？
んで千日手ルールがあった場合、2回目が現れた時点でその局面は千日手（4回目）なのと同じでしょ？
230:デフォルトの名無しさん
07/07/28 04:21:24
なんだかプログラマというより数学板みたいな感じですね
231:デフォルトの名無しさん
07/07/28 04:28:20
>>230
そう。
>>180は、最初こっちでやってて、逃げ出したみたい。
「将棋って数学に似てるの？」
ｽﾚﾘﾝｸ(bgame板)
こっちでも完全無視。
ｽﾚﾘﾝｸ(bgame板)
で、ここで叩かれていると。
232:デフォルトの名無しさん
07/07/28 04:35:39
>>228
ちょっと待って、整理させてくれ
その「戻らない」場合っていうのを
盤面はもちろんなくていいから例示してくれないか
局面Aから現在の局面に来た過程では、
相手方の協力があったから来たわけだよな
つまりこの千日手含みの手順に入ったからには
相手としても「回避すれば負ける」という事情が
あったわけで、するとやはり千日手が結果の気が
するのだけど
233:デフォルトの名無しさん
07/07/28 04:38:15
うーん、どこで話が噛み合わなくなってるか何となく分かってきた。
皆さんは将棋の神様同士が双方最善を尽くす場合の棋譜を考えてるよね。
だから千日手になるのを避けるために特定の局面を通らない事もあると仮定している。
そう考えるとその時点での局面の形から指し手が一意に定まると（少なくとも結果は同じ）。
私はルール上許される全ての局面に勝ち、負け、引き分けのラベルを貼る事を考えている。
そうすると後退解析するしか方法がなくて、すると>205が書いているように
GHI問題を考慮する必要が出てくる。
234:デフォルトの名無しさん
07/07/28 04:38:59
で、漏れはGHI問題についてググって以下のPDFに辿り着いた
ここの2ページ目だけ読めば、GHI問題については理解した（つもり）
URLﾘﾝｸ(www.fun.ac.jp)
これって詰め将棋のように、手順に基づいて探索ツリー作製していったとき、
サイクル手順に出てくる局面を、「無闇に」不詰として、ハッシュ表に登録することから生じる問題みたい
この「無闇に」ってところが重要で、ホントは2ページ目の局面Aは詰む局面
したがって「完全解析」の是非や、それに何回目の局面の情報が必要か、といった問題じゃなく、
あくまでも探索アルゴリズムの問題だね。最初の議論と、GHI問題の関係は、微妙だよ？
235:デフォルトの名無しさん
07/07/28 04:40:34
>>231
なるほど、横からだが把握した
この板IDないしな
236:デフォルトの名無しさん
07/07/28 04:44:46
>>233 釣りはやめろ
237:デフォルトの名無しさん
07/07/28 04:48:01
>>233
勝ち、負け、引き分けのラベルを貼る＝神同士の対局
238:デフォルトの名無しさん
07/07/28 04:48:10
>>234
ひとまずその2ページ目は見た
言いたいことはわからないでもないが
それは探索の実装の問題ではないかね
ハッシュが誤作動するとかいう問題と
結論がどうであるかということとは関係ない
もっといいアルゴリズムに替えたらいいだけ
この例でいえばEは「千日手」が結論なわけで
何も不明解さはないだろう
連続王手の千日手はまた別にして。
239:デフォルトの名無しさん
07/07/28 04:49:47
>>238は間違えた。「先手勝ち」な。
240:デフォルトの名無しさん
07/07/28 04:52:30
悪い、いろいろ間違えた。
>>238で俺が言いたかったことは>>234が言ってたな。
241:デフォルトの名無しさん
07/07/28 04:55:31
>233
GHI問題は、必ずしも「後退解析」（←これって勝ち筋から手を逆算していくことですよね？）の問題じゃないみたい
手順を追ってツリーを構築していく際に、ある経路では、千日手のように”みえる”局面が、
別の局面では勝ち筋に必要な局面ということ もちろん探索の途中で、うっかり千日手と
登録してしまったところに問題があるのであって、本当は、当然詰む局面
そもそも局面をハッシュしなければ、こういった問題は生じない
ハッシュするにしても、なんらかの形で辿った経路を情報として残せば、問題ない
また、図1で最初にA→Cと探索すれば、最初からこんな問題は生じない
とりあえずGUI問題について語るには、上のPDFの2ページ目を読もうよ
さっきから漏れも色々考えているのだが この論文の2ページ目以上に、簡単にGHI問題を説明するのは無理ぽ
242:デフォルトの名無しさん
07/07/28 04:56:16
>237
初手からの神同士の対局と任意、それも手順を含めた
任意の局面からのそれをごっちゃにしてない？
243:デフォルトの名無しさん
07/07/28 05:00:06
>>242
解析中と解析後はちゃんと区別しろよな
解析後に同一局面が出てくるなら引き分け、そうでなければ同一局面は出てこない
244:デフォルトの名無しさん
07/07/28 05:03:19
>>242
してないよ
245:デフォルトの名無しさん
07/07/28 05:04:58
神様同士の対局というのは、完全なる「次の一手」マシンのことだろ
完全なる「次の一手」マシンというのは、どんな局面を与えられても
勝ち筋があればそれを指し、なければ千日手に持ちこめる順を指し、
それもなければ何か指すというようなものだと思う
このようなマシンを作成することと、すべての局面の勝ち負けがわかる
完全な一覧表を作ることは等価だよ
マシン作成→与えられた局面からマシンに一人将棋をさせる→その勝ち負け
一覧表作成→有効手の中から、移行後の局面が「勝ち」であるものを
（なければ「千日手」を）さがす→それが次の一手
246:デフォルトの名無しさん
07/07/28 05:11:23
現時点での漏れの結論
1) 完全な後退解析が出来れば、
局面だけで勝ち・負け・千日手が解る（→完全解析）
2) 現実のアルゴリズム（これは後退解析でない）で
ツリー構造を作るには、ハッシュ表を使うことが多い
3) むやみにループする局面を千日手としてハッシュ表に登録していくと、
本来の勝ち筋を千日手と間違える問題が生じる(GHI問題)
4) 上記問題を回避するには、ハッシュ表に、千日手と判断するに
至った経路を登録して、局面だけでなく経路を区別する必要がある
5) 4)の事情があるために、「局面だけでは勝ち負けは決まらない」という
誤解が生じている
247:デフォルトの名無しさん
07/07/28 05:17:50
うん、それだ
今>>246がいいこと言った
248:デフォルトの名無しさん
07/07/28 05:18:28
それじゃあ任意の局面が与えられてそこから次の一手を決定する時、
そこまでどんな局面(経路)を辿って来たかについてどんな仮定を置いて
決めるんだい？
どんな経路を辿って来たとしても同じだと言うんならその根拠は？
249:デフォルトの名無しさん
07/07/28 05:20:14
「後退解析」をよくわかってないんだけど何かいい資料無い？
250:デフォルトの名無しさん
07/07/28 05:21:26
ひとり何役やってるの？
まあ、役者不足、ってやつだよね。
251:デフォルトの名無しさん
07/07/28 05:22:23
最低３～４人は居そうだけど
252:デフォルトの名無しさん
07/07/28 05:22:22
>>248
次の一手問題なら経緯は調べないだろが
勝ち負けの判定ならその局面へくる前に勝敗か引き分けが決まっている
253:デフォルトの名無しさん
07/07/28 05:22:54
>>248
いや別に
その「完全なる次の一手全集」を見ながら
バカみたいに指していくだけでいい
もしその局面からは千日手が最善なのであれば
全集には千日手になる手が書いてある
それを指せば、もし一回目や二回目なら
また同じ局面に戻ってくるわけだし
三回目なら、千日手になる
254:デフォルトの名無しさん
07/07/28 05:25:26
>>251
俺、俺より賢い奴、俺と同じくらいの奴、変なことを言う奴
の少なくとも４人はいると俺は思ってる
あと、見てる奴や１レスくらいしかしてない奴が多数
255:デフォルトの名無しさん
07/07/28 05:26:32
>>248
不完全な指し手が指したところから、勝敗を判定するなら
千日手は考慮しなければならない
データベースは使えない
256:デフォルトの名無しさん
07/07/28 05:26:45
>>248
すでに>>206で、「区別の不要」と証明されているんじゃないの？
否定できるなら、してみれば？
まず、>>220の形式で答えるのかな。
257:デフォルトの名無しさん
07/07/28 05:32:06
>>256
横からだけど、ちょっと待って
棋譜は有限だから、「指し手履歴込みの局面」も有限
それらをすべて列挙して勝ち負けを調べればよい
で、「同じ局面でも、指し手履歴の内容によって結論が異なる」
という現象はあるのかないのか
そこが本当の焦点なんじゃないのかと思う
258:デフォルトの名無しさん
07/07/28 05:36:42
>>254
>>185-248辺りでどのレスが誰？
自分のレスがどんな奴だと思われてるかちょっと気になる
259:デフォルトの名無しさん
07/07/28 05:38:36
>>257
「同じ局面でも、指し手履歴の内容によって結論が異なる」 と「区別の必要」の違いは?
とにかく、他にどんな問題があっても、単純に>>206を否定できなければ
「区別の不要」という結論は覆らないでしょう。
260:248
07/07/28 05:45:24
>256
区別が不要だといったいどこで証明されているんだ？
206の主張はトートロジーだよ。
区別が不要だから不要だと言ってるに過ぎない。
>246の1も未証明な仮定だと思うぞ。
261:デフォルトの名無しさん
07/07/28 05:46:07
>>259
えー俺は釣られてるのかな
それとも俺がバカなのか
> その局面は参照するだけで、勝ち負けか引き分けか決定してるよね？
具体的にはここだろう
今は「区別の必要がある」という仮定で話をしているのだろ？
そして、手順を区別した上で勝ち負け表を作ったのだろ？
つまり、同じ局面でも手順が違うものは別物として勝ち負けを
判定したのだろ？
それを整理して、局面だけから勝ち負けがわかるようにするのだろ？
でも、その整理ができるという保証がないよ
「区別の必要がある」という仮定のもとでは
つまり、区別ありの表から区別なしの表を作るときに、
もし区別ありの表において、ひとつの局面が
手順によって勝ちだったり負けだったり結論が異なっていたら、
区別なしの表にまとめることはできないじゃないか
そして、「区別の必要がある」という仮定はまさに
手順によって結論が異なるかもしれないという意味だ
だからこれは「他の問題」なんかじゃなくて本質的な問題だよ
262:デフォルトの名無しさん
07/07/28 05:48:55
>>261
あ、先に言われた
同意
263:248
07/07/28 05:58:14
あー、ようやく分かってくれる人が居た。
264:デフォルトの名無しさん
07/07/28 06:02:15
>>261
> つまり、区別ありの表から区別なしの表を作るときに、
「区別ありの表」とか、「区別なしの表」なんていらない。
単に「局面情報と手番と結果」を持つ表が一つあるだけでよい。
完全解析とは、その一つの表を埋めて、完成させること。
解析後は、「局面情報と手番」から「結果」を参照するだけ。
>でも、その整理ができるという保証がないよ
後で整理する作業は発生しない。
全く問題にならない。
よって、>>206の否定にはならない。
反論をお待ちしています。
265:デフォルトの名無しさん
07/07/28 06:08:05
>>264
おまいさん釣りだろう
議論ごっこなら付き合わないぞ
> 「区別ありの表」とか、「区別なしの表」なんていらない。
> 単に「局面情報と手番と結果」を持つ表が一つあるだけでよい。
> 完全解析とは、その一つの表を埋めて、完成させること。
> 全く問題にならない。
これらは>>206の論証の結果として得られるものだろう
それを論証の過程で使うのは「結論先取の詭弁」という詭弁
266:デフォルトの名無しさん
07/07/28 06:09:57
>>264
＞「区別が必要」という仮定で、手順により区別して
＞勝ち負けか引き分けかを決定したとするよね?
＞「区別ありの表」とか、「区別なしの表」なんていらない。
まず仮定をぶち壊してるけどこれOKなの？
267:デフォルトの名無しさん
07/07/28 06:10:13
>>261
おまえが言っているのは、完全解析が不可能、ということじゃないか?
完全解析は「すべての局面の勝ち負けか引き分けかを決定すること」。
つまり、表を正しく完成させるということだぞ？
268:デフォルトの名無しさん
07/07/28 06:14:36
>264
「完全解析とは、そのひとつの表を埋めて、完成させる事」
と言うそれが可能だと言う保証がどこにも無いんだよ。
後で整理する作業が必要ないと言うならそれを作る手順は？
269:デフォルトの名無しさん
07/07/28 06:15:26
>>266
> ＞区別ありの表」とか、「区別なしの表」なんていらない。
> まず仮定をぶち壊してるけどこれOKなの？
言葉が、足りませんでしたか。
完全解析時の作業用の表は、たくさん必要です。
完全解析を行った結果出力として、
>単に「局面情報と手番と結果」を持つ表が一つあるだけでよい。
という表があればよい。
ということです。
完全解析ができるということは、この表を得ることができるということです。
反論をお待ちしています。
270:デフォルトの名無しさん
07/07/28 06:19:19
>>267
いや、いま問題になっているのはそうじゃないよ
将棋のルールは、一見、局面（駒の配置と手番）だけでは
勝ち負けが確定しないように見えるじゃんか
同じ手でも千日手になる場合とそうでない場合があるからね
つまり、将棋において状態とは、駒の配置と手番だけではなくて
「局面の出現回数の履歴」も含めたものでなければならない
そう考えられるわけだよ。素朴には。
でも、もちろん感覚的には、そんなことはなくて、履歴などなくても
局面（駒の配置と手番）だけで判断がつくように思える
その感覚が正しいかどうかがいま問題になっているのだよ
将棋というゲームの状態変数として「駒の配置と手番」だけで
十分なのかどうかと
ルールを素朴に読んだだけでは、不十分に思えてしまうわけで
271:デフォルトの名無しさん
07/07/28 06:20:16
>>269
>>270
272:デフォルトの名無しさん
07/07/28 06:23:42
>>268
「将棋の完全解析は不可能」を主張しているわけだ。
これが不可能なら確かに>>206は成り立たないね。
でも、基本的に>>217にもある通り「可能」が、共通認識なんだけど。
つまり、あなたが「将棋の完全解析は不可能」を証明できなければ、
>>206を否定する必要がある。
がんばってくれ。
273:デフォルトの名無しさん
07/07/28 06:27:43
あはは。千日手模様。
>>268、>>270、>>271の最善手は、「千日手」に持ち込むことか。
274:デフォルトの名無しさん
07/07/28 06:28:57
>>272
横からだけどおまいさんの言う「完全解析」っていうのは
あくまで「駒の配置と手番」だけを状態変数としたものだろう
たとえば、三山崩しにおいて、ルールを読んだだけでは
状態変数として「１の山の個数」「２の山の個数」「３の山の個数」
という３つの状態変数が必要に思える
でも実際にはこんなにいらなくて、それらのXORだけあれば
勝ち負けが判定できる
このように状態変数を減らすことが、将棋でもできるかどうか
それが論点だよ
275:248
07/07/28 06:29:04
>267 >269
完全解析の定義を勝手に自己流に狭く定義しないでくれ。
その定義での完全解析ができるという保証は無いだろ？
実際に可能なのは手順込みの局面にラベルを貼る事。
276:デフォルトの名無しさん
07/07/28 06:31:29
>>270
完全解析の定義と、それが可能かどうかを、まず、答えてください。
ここの立場をはっきりしないとお話にならない。
いいですか？
はっきり明記してくださいよ？
277:デフォルトの名無しさん
07/07/28 06:33:23
>>272
＞二人零和有限確定完全情報ゲーム
「完全情報」ってのは手順の情報も含むんだが
君はこの情報を欠落させても欠落させない場合と等価な事を証明する必要がある
278:デフォルトの名無しさん
07/07/28 06:33:52
>>273
レッテル貼りの詭弁
>>272
共通認識というか定理だろう
将棋のルールは駒の配置と手番とそれらの履歴とで
記述されているわけだから、当然「区別ありの表」は
作れるわけだよ
そこから「履歴」を消してもWell-Definedになる、
というのは自明なことではないと思うよ
279:デフォルトの名無しさん
07/07/28 06:38:49
>>277
>>206
280:デフォルトの名無しさん
07/07/28 06:41:11
>>279
そのアンカじゃループしてるよ
何か別の事言ってよ
281:デフォルトの名無しさん
07/07/28 06:48:05
>>274
>>259
282:248
07/07/28 06:50:04
>206の言ってる事はずっと以前からループしてるんだよ。
区別は必要ないから区別しなくて良いってずーっと。
283:デフォルトの名無しさん
07/07/28 06:51:05
>>259
>>261
284:248
07/07/28 06:55:40
あー、疲れた。
この議論だけで徹夜しちまったよ。
285:デフォルトの名無しさん
07/07/28 06:56:36
反論が無くなったようだしとりあえず寝るか
何かあればまた今夜にでも参加するよ
みんなお疲れ
286:デフォルトの名無しさん
07/07/28 06:57:56
>>284
俺もだ
土曜出勤なのにな
>>276に長レスを書いてたんだけどバカらしくなってきた
ああやって「これにレスできないとバカだ」みたいな言い方をするのは
釣り師が一般人を議論に引きずり込むときの常套手段なんだよなあ
287:デフォルトの名無しさん
07/07/28 07:00:10
>>278、>>280
>>276
よろしく。
288:デフォルトの名無しさん
07/07/28 07:00:41
>>276
可能
289:デフォルトの名無しさん
07/07/28 07:01:35
あ、定義もか
誰か出してなかったっけ
290:デフォルトの名無しさん
07/07/28 07:03:19
>>248、>>278、>>280
>>269にも回答よろ。
291:248
07/07/28 07:05:31
皆さん、お疲れさま。
付き合ってくれてアリガトン。
292:デフォルトの名無しさん
07/07/28 07:06:06
「局面情報と手番と手順と結果」を持つ表を作れる事が完全解析ができるということ
293:デフォルトの名無しさん
07/07/28 07:11:27
自分も寝る
おやすみ
294:デフォルトの名無しさん
07/07/28 07:12:23
なんか急に伸びすぎﾜﾛﾀｗｗｗｗ
295:デフォルトの名無しさん
07/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:デフォルトの名無しさん
07/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:デフォルトの名無しさん
07/07/28 08:04:52
>>206はごちゃごちゃ言いすぎ。
完全解析を「すべての局面の勝ち負けか引き分けかを決定すること」と
手順を含まずに定義したんだから、解析後に手順が関係ないのは、自明。
この定義で、解析後に手順がどうのと文句つけるのがアホ。
>>292のように、
>「局面情報と手番と手順と結果」を持つ表を作れる事が完全解析ができるということ
と定義に、手順を入れれば、解析後も手順も関係するが、こんな定義初めて見たよ。
298:デフォルトの名無しさん
07/07/28 08:24:01
>>295, >>296 打ち込みサンクス！！
それによると、A'は履歴を含んでいるわけではないのだから、
やっぱり「完全解析」の定義は、局面だけであって、履歴は関係ないんだね
上の議論は、将棋固有のルールを反映したものではないけれど、
将棋もまた上の数学の枠内でのものなのでしょう
「M(X)は空ではない」ってのは、例えば両方ともパスするしかないような
状況はありえないって事だよね？更に勝ち・負け・引き分け以外の
終わり方は、将棋ではあり得ないから、やっぱり将棋は局面だけで、結論がでているんだ
299:デフォルトの名無しさん
07/07/28 11:21:25
途中まで人間が指して、そのあと最強ソフトが指すならデータベースは使えないってことだろ
千日手があるから・・・
全局面をNとしたとき、その局面が何回現れたかを記録した
0から3までの数字列N個分を保持していなければならない
最終的には4のN乗程度の状態を保持しなければ、途中差しは出来ないって事だ
300:デフォルトの名無しさん
07/07/28 11:36:00
>>297
いやいや、>>292などは既存の常識に疑義を言ってるのだから、
「初めて見る」は非難にはならないよ
>>298
数式に惑わされたらだめだろ
>>295-296は何も新しいこと言ってないぞ
そしてさりげに>>295のAは履歴も含んでるよ
Sは手数とか言ってるしな
履歴を持ってないとVが千日手を判定できない
最後の条件は、勝敗未定ならば有効な手がある
ということ
たとえばもしルールでステールメイトを負けにするのを
忘れていたりすると、
M(X)が空（有効な手がない）で、しかも
勝ち負け引き分けのいずれでもない
という状況が発生するね
301:デフォルトの名無しさん
07/07/28 11:45:39
>>295, >>296 の論法で完全解析が可能であるというには、
駒の配置に加えて「この局面が何回目か」というパラメータも
ノードの状態変数として加える必要があるということ。
完全な履歴は必要ないが、何回目かは必要となる
これが「局面の出現回数の総和で添え数字づけ可能」の意味と理解した。
だとすると、途中で人間×２からコンピュータ×２に交代するとして、
全ての局面の出現回数を保持していなくても「この局面は何回目です」と
だけ伝えればいいんでないかい？後は事前に完全解析された結果に基づいて、
最強ソフトが「先手の勝ちです」「後手の勝ちです」「引き分けです」
とだけ伝えてオシマイになるはず。少なくとも十分条件としては。
302:デフォルトの名無しさん
07/07/28 11:47:24
>>301
勝ち負けの決まっている手順の途中に千日手が現れる可能性有り
303:デフォルトの名無しさん
07/07/28 11:53:02
>>299
将棋というゲームの正しいイメージはこうかもしれないな
N個のマスと、それらをつなぐ線があり
マスのうちいくつかは赤か青に塗ってある
二人が交互にマスに石を置いていく
一つのマスには３個まで石を置ける
４個目の石を置いたら引き分けで終了
赤のマスに石を置いたら先手の勝ち
青のマスに石を置いたら後手の勝ち
ただし直前に相手が置いたマスから
線でつながっているいマスにしか置けない
304:デフォルトの名無しさん
07/07/28 12:11:18
>>300
だいぶ問題が絞られてきたね。
確かに、Aが履歴を含むのかどうかで、話は全く変わってくる。
Aに出てくるnって何だ？漏れはX1, X2が、例えば各駒の場所の様な変数で、
nが駒やボードに対応するものかと思った。で、その直積であるAは
履歴を含んでいないな、と。それだと千日手の判定が出来ないから、
少なくとも、「この局面が何回目か」という情報をAnとして加えてやれば、
完全解析の対象になる、という意味だと理解したんだが。
そしてある局面が何度でてくるかという情報は、手順から
考えれば何通りでもありそうなものだが、完全解析の対象としてみた場合、
最善の選択をして射影していくのだから、S(X)が決まってくるのかなと
思ったのだけど？
突き詰めると、やっぱり
> 将棋は「局面の出現回数の総和」で添え数づけ可能
のところが漏れには解らない。
うーん、難しいね、Anの意味とS(X)の意味、もし良かったら教えて
305:デフォルトの名無しさん
07/07/28 12:18:15
>>302
人間が指す以上、必ずしも最善手の連続ではないから、
それまでの履歴に、「完全解析」では出てこない履歴があって、
以後の手順に千日手をもたらす可能性がある。
そのため事前に用意した「完全解析」のテーブルが必ずしも
使えなくなる、でいい？
だとすると、これって結局、GHIの問題とほとんど同じだね
GHIの場合は、探索アルゴリズムが完全でないことに起因、
人間からコンピュータに替わる場合は、それまでの履歴が最善手でないこと
（勝ち負けを見落として、無駄な経路を辿っている）ことが原因
しかしこれらが、将棋の完全解析の可能性を排除するものではない
って、これでいいのかな？
306:デフォルトの名無しさん
07/07/28 12:25:55
>>304
今から出かけるから手早いけどごめん
X1、…、Xnが駒の場所などの変数で、
A1、…、Anがその値集合
たとえばX1は「先手玉の場所」で
A1は{「1一」、「1二」、…、「9九」}
みたいな感じ
それで、「同一局面４回」のルールを記述するために
（立会人に見せて「引き分けですね」と言ってもらうために）
局面の出現回数も、X1、…、Xnの中で持ってなきゃいけない
俺もおまいさんと多分だいたい同じ考えだよ
でも全部の局面の出現回数を持たなきゃいけないと思ってる
問題図までを指すのは神ならぬ人間なのだから、
神様に言わせれば変な手などもあるはず
そこから神様が引き継いだとして
勝つつもりで指してたら、途中で「その局面は４回目ですよ」
といわれて引き分けになっちゃうかもしれない
そんなわけでXnの中にはすべての（膨大な数の）局面に対して
その出現回数をあらわす変数が含まれてる
ことを俺は想定してた
307:デフォルトの名無しさん
07/07/28 12:29:34
>>306の続き
S(X)は「今の状況までの初手からの手数」で、
どうせ有限なのだからそんなの持ち出さなくてもいいのだけど
議論を簡単にするために出してみた
千日手がある以上、無限に多くの手数は指せない
だから手数の多いものから逆にさかのぼって
2000手以上は解明済み… 1000手以上は解明済み…
などとすることができる
>>305
たとえば簡単な状況で、自玉は必至、相手玉には
３種類の詰みが見えてるとする
ここで、もしその詰み手順の途中の局面が
３回出現済みだったら、自分は相手玉を詰めれない
だから千日手引き分けになる
もちろんそうでなければ勝ちになる
これは履歴が結論に影響を与えてるんじゃないかな
308:デフォルトの名無しさん
07/07/28 12:49:16
>>306
なるほど「局面の出現回数の総和」って「全ての(膨大な数の)局面に対してその出現回数」
っていう意味にも読めるね。確かにこれを全て保持したとしても、局面の数が有限であり、
千日手ルールで頭が押さえられているから、それを状態変数とみたてても、取る値は
高々有限集合になって、>>295 の条件を満たす
人間から神様に交代する場合は、確かに全部保持している必要があるだろうね。
先にも書いたように、勝ちの見落としがあるから、GHI問題と同じ現象が生じる。
で、問題なのは「将棋が完全解析されるには、状態変数として、その局面の出現回数だけで
良いのか、それとも全ての局面についての出現回数が必要なのか？」ってところに絞られてきた。
>>296 氏がさらりと書いた、『将棋は「局面の出現回数の総和」で添え数づけ可能』って
いう命題、この証明を載せた文献とかが解れば、それ見てはっきりするんだが
今から出かけるってことだけど、また暇な時に相手してね、サンクス
309:デフォルトの名無しさん
07/07/28 13:17:27
ところで、完全解析って、すべての局面の「勝ち」「負け」「引き分け」の
他に、「何回間違うと状態が変わるか」って情報いらないの？
対局は、必ず「詰み」まで指すものする。
神Aと神Bが対局して、神Aが先手。先手必勝と分かっている場合、神Aは単に「勝ち」を
選んでいけばいいが、「負け」しか選べない神Bはどんな情報を基にたくさんの「負け」の
中から手を選ぶのかな？
また、形勢差がついている局面から「人間vs神」が指し継ぎ、神が神が判断して形勢不利側を持つ。
このとき神は、差を詰めなければいけない訳だが、どんな情報を基に手を選ぶのかな？
310:デフォルトの名無しさん
07/07/28 13:25:12
よく考えたら、その局面の出現回数だけ保持していたとすると、
状態が遷移したとき、次の状態が何回目かなんて解りっこない
したがって、あるノードの千日手判定はできるが、そこから一つ前の手順に
後退解析することすら不可能になってしまう。なぜなら、ノードは
その局面の出現回数しか保持していないため、
局面A(1回目) → 局面B(4回目) → 千日手で引き分け
といったツリー構造があれば、
局面A(1回目) → 局面B(1回目)
局面A(1回目) → 局面B(2回目)
局面A(1回目) → 局面B(3回目)
というツリー構造も必ず存在するわけだから。したがって、全ての局面に
ついての出現回数がないと、そもそも完全解析の際に千日手に至る
手順を落としていくことが全く不可能になってしまう。
結論は「棋譜としての履歴は必要ないが、全ての局面についての
出現回数を保持する必要がある」ってことになりそうだ。
311:デフォルトの名無しさん
07/07/28 13:25:53
(つづき)
でも全ての局面について出現回数を保持するのは、理論的には簡単であっても、
現実的にはまず不可能。で、結局は順番はともかくどういった局面がこれまでに
出てきたか、その回数と共に保持していくことになる（これは実装上の問題であって、
理論的には全ての局面についての出現回数保持と同じ）。
最後の問題は、なぜ全ての局面の出現回数を保持しておけば、
将棋が添え数づけ可能になるかってことだ。>>296 の後半にある
「次が成り立つとき･･･」以下を証明なしに受け入れるとしても、
ここが争点として残る。でないと「以下添え数づけ可能なゲームを考える」
という前提から崩れてしまう
松原先生の本には、この辺の理論は載っているのかな？
312:デフォルトの名無しさん
07/07/28 13:27:04
>309
それを考慮するためには同じ「勝ち」「負け」「引き分け」の結論でも
どんな結果が「勝ち」 or 「負け」側にとってより良いとされる手なのか
その価値基準を事前に定義しておく必要があるよ。
つまり「勝ち」「負け」が既に分かっている局面で、形勢差はどう定義
されるべきなのか？
313:デフォルトの名無しさん
07/07/28 13:29:43
>>309
うーん完全解析の立場からいえば、その時は神様が「負けました」って
頭を下げるんだよ。で、ヘボな人間がキョトンとするという。
したがってその問題は、完全解析の枠内では無いと思うぞ
実際のプログラムを作る場合には、非常に重要になるには違いないが
余談だけど、プロ棋士も、負けのときに形を作って投げるよね
314:デフォルトの名無しさん
07/07/28 13:34:53
>>313
> うーん完全解析の立場からいえば、その時は神様が「負けました」って
> 頭を下げるんだよ。で、ヘボな人間がキョトンとするという。
これって、笑い話だよね？
結果は分かっているから「いきなり投了」ということで、実際は、指せば指せるよね？
指せないとなると、それはそれで変。
315:デフォルトの名無しさん
07/07/28 13:35:53
>>309
囲碁やオセロなどは目数や石数によって勝ち（負け）の価値が決められるけど、将棋は？
316:デフォルトの名無しさん
07/07/28 13:41:52
>>315
>囲碁やオセロなどは目数や石数によって勝ち（負け）の価値が決められるけど、将棋は？
相手玉を詰ませば勝ち。
317:312
07/07/28 13:42:14
>315
詰め将棋に準じて考えれば勝つ側はなるべく短い手数で勝つ手を選び
負ける側はなるべく長い手数で負ける手を選ぶべきなのだろうが、
結論が引き分けの時は？？？
また手数が同じならすべての手順は価値が同じなのか？
私には良く分からない。
318:デフォルトの名無しさん
07/07/28 13:44:13
>>314
笑い話かどうかともかく、相手のミスをどれだけ仮定するかは、実際の将棋対極では
非常に重要な要素に思うぞ、プログラム開発に限らず。いわゆるハメ手ってやつね。
相手がヘボなら、ハメ手を使って早々に対極を終わらせるだろうし、相手が上手ければ
ハメ手を見透かされて逆に咎められるだろうから、そんな手は使わないだろう。
ハメ手は、素人相手の、相手のミスを前提とした手法だが、プロでも形勢が悪いときは
それに近いことをするようだ。たとえば米長さんの本に、状況がこちらに不利であると、
ギャンブルっぽい手をあえて選ぶと書いてあった。
319:デフォルトの名無しさん
07/07/28 13:55:13
神はどう相手にミスを期待して、手を選ぶのか。
神が神でいられるのは、初期局面だけなのだろうか・・・
320:デフォルトの名無しさん
07/07/28 14:02:00
子ノードの勝ち手順の多寡かなぁ・・・
でも手順は少なくても簡明な勝ちもあるだろうし・・・
321:デフォルトの名無しさん
07/07/28 14:14:10
そうか
この議論は>>162-163に対する>>164のレスから始まってるのか
322:180
07/07/28 14:27:08
>321
そう。そして私が>165の意見に対してキツイ事を書いて
これだけ燃え上がってしまった。
今思えば、彼が考えていた前提（神様同士が初手から対局したと仮定）が
分からなかったとは言え、失礼な書き方をしてしまった。
>165さん
今更ですが済みません。ゴメンナサイ！
323:デフォルトの名無しさん
07/07/28 14:29:27
>>317
昔、ちょっとGAをやったとき、生き残り戦略はそんな感じにしてた。
引き分けの時、手数が同じ時は、駒得している手数が長いほうが有利としてた。
324:デフォルトの名無しさん
07/07/28 16:27:51
くどいようだけど、最後に一言だけ言わせて。
既存のゲームの理論を用いて、将棋の完全解析可能性を証明するには、
将棋が添え数づけ可能であることを示す必要があるのだろう。そして局面に、
全ての局面についての出現回数を保持すれば、それが添え数づけ可能になるようだ
しかし、それは「将棋が完全解析可能か」という命題には答えても、
我々が議論してきた問題とは微妙にずれているような気がする。
我々は「将棋を完全解析するのに、局面の出現回数（＝履歴）を保持する必要があるのか？」
という問題を議論してきたはず。これは「将棋は完全解析可能か？」とは違う。
「局面だけで完全解析が出来るか？」という命題は、>>296の理論にもとづいて
行おうとする限りにおいては、千日手の判定ができないため>>300 氏の言っている理由により
証明出来ない。しかしこれは、他の理論で証明することまでも不可能であると言っている訳ではない。
もし局面だけで完全解析が可能だとすると、少なくとも出現回数付きの完全解析から、
一意に射影できるはず。なぜなら後者は前者に情報を追加したものだから。
もし前者で完全解析が可能であるなら、追加した情報（＝局面の出現回数）は
余分な情報であって、後から射影作業によって取り除ける。
325:デフォルトの名無しさん
07/07/28 16:28:32
（つづき）
とりあえず「局面の出現回数つきのノードで考えると、完全解析が可能」を認めるとしようや。
上の「局面の出現回数」は、そのノードの出現回数だけではなくて、全ての局面の出現回数ね。
ここで、次の問題を考えてみる。
（＊）出現回数つきの状態で考えて、完全解析した状態ツリーを得たとする
このツリーに含まれる状態のうち、出現回数の項目だけ違っていて駒の配置が
同じものは、同じ結果（勝敗および千日手）がマークされているのか？
ここで、人間の勝ち筋見落としやGHI問題、また「その局面に至る途中で、
千日手の局面を経由した恐れがある」というツッコミは、不要。ミスなしは
前提であるし、「GHI」や「途中の千日手」といった問題は、出現回数つきの
状態ツリーではそもそも存在しえない。なぜなら、今議論の出発点としているのは、
回数まで出現回数まで含んだノードなんだから、「途中で千日手」を経由していないのは、
出現回数の情報から明らか。
326:デフォルトの名無しさん
07/07/28 16:29:13
（つづき）
何が言いたいかというと…
状態図にループ構造があると、数学的に完全解析の存在の証明が非常に難しそうだ。
で、状態変数に、全ての局面についての出現回数を保持するのは、そのループ構造を
千日手に至るまでの手順で展開し（添え数づけ可能にし）、数学で知られている
既存の完全解析の理論に乗っけるための便宜的な手法に過ぎないんじゃないかと。
もし（＊）が満たされれば、勝ち負けの情報を一意に保ったまま、折りたたんで、
局面だけの完全解析に移行できるように思うのさ。折りたたむと、当然ツリーから
ネットワーク構造（ループ含む）となる。
この段階で「局面だけだと、途中の千日手を経由しているかも」と議論するのは不要。
なぜなら、もともと出現回数つきのツリーから折りたたんでいるんで、先に述べた
理由から、考える必要がない。そして勝ち負けがつく局面（ノード）以外は、全て千日手の
局面のはず。当然、千日手の局面は千日手の局面で、閉じたネットワークを作る。
勝ち負けが決定したノードが千日手に繋がってないんだから。もはや勝敗・千日手とも
出現回数の差異によって、その間のツリー・ネットワークの交叉が変化しないのは明らか。
これはあくまでも、（＊）の前提が満たされた場合の話ね。
でだ、（＊）の問題について、誰か解るヤシはおらんか？これが鍵になる気がする。
何らかの簡単な論理で言及できそうにも思うのだが？
327:デフォルトの名無しさん
07/07/28 16:54:30
>>324-326
(*)については「出現回数の項目だけ違っていて駒の配置が同じもので、
結果が異なることはある」でしょ。
それも「しばしば経験する」からこそ、みんな困っていて、
transposition tableにやむを得ず経路を入れなくちゃいけないわけで。
328:デフォルトの名無しさん
07/07/28 17:04:55
>>327
きっとプロの方すね、了解しました
これで漏れの中では解決
サンクス！！
329:デフォルトの名無しさん
07/07/28 17:08:38
>>327
それGHI問題じゃないの？
330:デフォルトの名無しさん
07/07/28 17:13:16
>>327
反例を棋譜で示せる？
331:デフォルトの名無しさん
07/07/28 17:20:35
>>329
GHI問題だよ。
GHI問題は「駒の配置が同じなのに、経路によってその局面の
勝ち負けのラベル付けを変えなければならないことがある」ということだよ。
まさに325の(*)の話でしょ。
325が議論していた数え上げ方の言葉で説明するなら、
「aの局面が3回出現している状態でのbの局面は負けだが、
aが2回しか出現していない状態でのbの局面は勝ち」ということがしばしば起きる、
というのがGHI問題。
332:デフォルトの名無しさん
07/07/28 17:24:45
>>331
だとすると、GHI問題は、必ずしも探索アルゴリズムの問題とは限らなくて、
完全な探索を行ったとしても、局面から以前の局面の出現回数を取り除いたことに
起因して起こる、より本質的な問題だということになるのですね
上の方に出てきたPDFの説明では、この辺りがハッキリしない
それとも、そういった問題を総称して「GHI問題」っていうのが普通なんですか？
333:デフォルトの名無しさん
07/07/28 17:28:14
>>331
＞ここで、人間の勝ち筋見落としやGHI問題、また「その局面に至る途中で、
＞千日手の局面を経由した恐れがある」というツッコミは、不要。ミスなしは
＞前提であるし、「GHI」や「途中の千日手」といった問題は、出現回数つきの
＞状態ツリーではそもそも存在しえない。なぜなら、今議論の出発点としているのは、
＞回数まで出現回数まで含んだノードなんだから、「途中で千日手」を経由していないのは、
＞出現回数の情報から明らか。
ここ読んだ？
ここが間違ってるの？
334:デフォルトの名無しさん
07/07/28 17:32:26
>>333
漏れが意図したのは、探索アルゴリズムの問題による、見かけ状のGHI問題
PDFの2ページ目での説明では、こっちがメインだった
>>332 で書いたように、 完全な探索を行った上でもGHIが生じるのであれば
そっちのGHIは>>325 で書いたGHIには含まれないと解釈してくれ。
少なくとも、漏れが書いた意図としてはそう。
335:デフォルトの名無しさん
07/07/28 17:35:02
>>330
岸本さんに言えば出てくるかもしれないとは思うけど、自分では持ってないなぁ。
例えば234の論文の図3「続詰むや詰まざるや」42番が、
GHIを考えなければ間違えちゃうわけだから、
その証明木の中のどこかに(*)が満たされない部分があるということでしょ。
>>332
何かの探索アルゴリズムに起因した問題ではないよ。
「同一駒割の局面が必ずしも同じ局面としては扱えない」という問題の総称が
GHI問題、ということでしょう。
336:デフォルトの名無しさん
07/07/28 17:45:14
(*)の反例は>>307の後半？
337:デフォルトの名無しさん
07/07/28 19:40:47
自分も状態変数には出現回数が必要だと思ってるけど
不要だっていう意見の人まだ居る？
338:デフォルトの名無しさん
07/07/28 19:55:14
>>324
すまん。
命題：「○○は△△△である」
→真 or 偽
の形で整理してくれないか？
問題がいくつあるのか、結論がなんなのか、結論の出ているもの、出ていないものがよく分からん。
339:名無しさん＠そうだ選挙に行こう
07/07/29 08:20:49
>>337
そもそも「双方が最善を尽くす」という前提があるので、
「引き分け」でない局面の出現が一回目ではない、というのは、
前提条件を崩しているので議論の余地はないのでは？
340:名無しさん＠そうだ選挙に行こう
07/07/29 09:22:22
>>339
一見すると、千日手のループであっても、入る場所が異なると
千日手と判定を下すタイミングが異なってくる。
したがって、ある手順では千日手のループの一部であっても、
別の手順で別の入り口から入ると、それが勝ち筋に必要な手順の一部となる。
いままでの議論を注意ぶかく読んで、 >>234 のPDFを見たらたぶん
そういう結論に至ると思うぞ。
341:名無しさん＠そうだ選挙に行こう
07/07/29 09:29:58
>>339
あと、「最善を尽くす」ために、今すべての状態遷移についての
ツリーを作ろうとしていることも忘れないでくれ ツリーの一本一本は
必ずしも「最善」に絞られて作製しなくてはならないわけではない
342:名無しさん＠そうだ選挙に行こう
07/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:名無しさん＠そうだ選挙に行こう
07/07/29 10:16:58
>>340>>341>>342は、頭がおかしいんだろ
探索した手と、指された手が区別できていない
344:名無しさん＠そうだ選挙に行こう
07/07/29 10:28:24
どんな指し手にも対応できるように、
すべてを検索してしまえって話をしているのだから、
区別する必要はないように思うぞ？それとも釣りかな？
345:名無しさん＠そうだ選挙に行こう
07/07/29 10:56:37
>>340
じゃあ、言い方を変えます。
そもそも「双方が最善を尽くす」という前提があるので、
「引き分け」でない局面の出現が一回しかないのは明らかなので、
完全解析後のテーブルとしては、すべての局面(手番込み)の
「先手勝ち」「後手勝ち」「引き分け」の状態のみ持てばよいのでは？
ということです。
>自分も状態変数には出現回数が必要だと思ってるけど
当然のことながら、完全解析中のテーブルとしては必要です。
あなたの書き方は、「どのテーブルに、状態変数が必要か」が、あいまいです。
346:名無しさん＠そうだ選挙に行こう
07/07/29 10:59:30
>>343
探索で考える手順と、実際に指される手順を区別しないと、
千日手の発生状況が異なるから、意味がないっていいたいのか？
それは「カギ括弧無しには一意に射影できない」といっているのと同じだぞ
もちろん実際に指される手順は、括弧付き（括弧の情報を含む）なんだよ。
「括弧無しで議論して、手順1)での探索から、手順2)のHまで千日手と結論づけてはいけない」
といっているんだよ。
おまいさんは、カギ括弧無しで考えていて、手順1)を「探索した手」と呼び、
手順2)を「指された手」と言っているように思うんだが？
347:名無しさん＠そうだ選挙に行こう
07/07/29 11:03:51
>>346は完全な釣りですから・・・相手にするのはやめましょうね
348:名無しさん＠そうだ選挙に行こう
07/07/29 11:05:00
俺は門外漢なんで申し訳ないが
>>331の
325が議論していた数え上げ方の言葉で説明するなら、
「aの局面が3回出現している状態でのbの局面は負けだが、
aが2回しか出現していない状態でのbの局面は勝ち」ということがしばしば起きる、
というのがGHI問題。
というのがサッパリわからない
ここで言うaとかbとかってそれぞれ同じ局面なんでしょ？
なんで勝ち負けが変わったりするの？
349:名無しさん＠そうだ選挙に行こう
07/07/29 11:06:40
>345
>そもそも「双方が最善を尽くす」という前提があるので、
>「引き分け」でない局面の出現が一回しかないのは明らかなので、
この『「引き分け」でない局面』でいうところの、「局面」は、
今までの全ての局面の出現回数を、情報として持っている？持っていない？
漏れの説明もあいまいだったかも知れんが、そちらの質問もまた漏れには
あいまいにうつってる。悪いが、言葉を補ってくれ。
350:名無しさん＠そうだ選挙に行こう
07/07/29 11:13:55
>>349
完全解析後のテーブルとしては、持っていません。
ただし、対局である以上「棋譜」が生成されているので、
棋譜を見れば、その対局での「局面」の出現回数は分かります。
351:名無しさん＠そうだ選挙に行こう
07/07/29 11:14:08
>>348
同一局面が4回現れると引き分けで指し直しになる
引き分けにあえて持ち込むか、勝ちを狙うかという違いが出てくる
352:名無しさん＠そうだ選挙に行こう
07/07/29 11:16:29
途中から、人間→CPUに切り替える場合のみ局面の回数が必要
はじめからCPUなら同一局面はあり得ない(単に手を延長するだけでしかないため)
353:名無しさん＠そうだ選挙に行こう
07/07/29 11:16:40
>>351
>>339
354:名無しさん＠そうだ選挙に行こう
07/07/29 11:18:58
>>352
>>339
「人間→CPU」は、対局上「双方が最善を尽くす」ではない。
355:名無しさん＠そうだ選挙に行こう
07/07/29 12:36:08
そもそも千日手で引き分けは王手とか詰み回避の時しか成立しないじゃなかったか？
何の意味も無い議論をしてるようにしか見えないのだけど。
356:名無しさん＠そうだ選挙に行こう
07/07/29 14:10:13
まあ、完全解析自体が計算量的に不可能なんだから
千日手を巧いこと処理して、1万倍の速度で解析したところで
全然意味ないし、始めから机上の空論なわけですよ。
357:名無しさん＠そうだ選挙に行こう
07/07/29 14:15:14
机上の空論もなかなか楽しいもんだぜ？
358:名無しさん＠そうだ選挙に行こう
07/07/29 14:21:59
URLﾘﾝｸ(ja.wikipedia.org)
千日手のルールって結構最近出来たものなんだね
359:名無しさん＠そうだ選挙に行こう
07/07/29 14:44:00
>>180は、「例え将棋の神様であっても」といってる
理論と現実の区別もついてなかったのか・・・
妙に納得
360:名無しさん＠そうだ選挙に行こう
07/07/29 15:07:08
因みに地球上の全ての原子に1ビットづつ記録しても、
全ての局面を記憶することはできないし
かと言って量子コンピューターで将棋ができる時代の遥か以前に
名人は負けてるでしょうし。彼は何が言いたかったんでしょうね
361:名無しさん＠そうだ選挙に行こう
07/07/29 15:11:28
>>351
24でR2300ていどのヘタレの意見だから的外れかもしれないけど
同一局面が出てきた場合、そこで千日手か打開かの選択が生まれるってのは
対局中よくある話なんで理解できる
ただ、331は引き分け（千日手）or勝ち（打開）じゃなくって
負けor勝ちというふうになってる
そこが理解できない
362:名無しさん＠そうだ選挙に行こう
07/07/29 15:32:27
>>361
連続王手の千日手なら引き分けじゃなくて負けになるよ。
363:名無しさん＠そうだ選挙に行こう
07/07/29 16:20:51
>>362
するどいね。ただ>361 の意見にも一理あって、
>351 に、引き分けも加えるべきだろうね
それと「最後の審判」っていう詰め将棋の問題があるようだ
現在の将棋のルールには不備があって、
必ずしも勝ち・負け・千日手で閉じるわけではない
打ち歩詰めのルールは、やや特例的なものだから、
仮に全部探索したところで、このルールを適用すると、
一部の状態ノードの勝ち負けが重複してしまう
現状の詰め将棋のプログラムに「最後の審判」食わせたら、
ただしく「不定です」って答えるのかな？
364:名無しさん＠そうだ選挙に行こう
07/07/29 19:28:20
後手が王手を防ぐために打つあい駒の歩が逆王手になっている。
先手がそれを取って王手をすると千日手になってしまい先手は取れない。
しかしその局面は先手が歩を取れないと、先手玉は歩打ちで詰んでる。
365:364
07/07/29 19:30:41
個人的な意見だけど、詰め将棋としては歩詰みで、対戦としては後手の勝ちでいいんじゃない?
同一局面が2回しか出ていないなら王手を外せるんだから
366:名無しさん＠そうだ選挙に行こう
07/07/29 19:30:46
>>364
打ち歩詰めで後手の負け
367:名無しさん＠そうだ選挙に行こう
07/07/29 19:33:47
作者の作意では、歩の合駒が出来ないから(打ち歩詰め)後手の負けって事らしいね
368:名無しさん＠そうだ選挙に行こう
07/07/29 19:35:59
>>366
先手の方から、同一局面への王手を外せるんだから
先手が繰り返す方が悪い
369:名無しさん＠そうだ選挙に行こう
07/07/29 19:45:37
>>366
麻雀でいう形式テンパイを認めるっていうやつと同じだ
盤面をみただけでは打ち歩詰めではないのだからOKにしようぜ!
370:名無しさん＠そうだ選挙に行こう
07/07/29 20:17:17
>>366
これ嫁
千日手の定義より、打ち歩詰めの定義の方が優先されている
歩で王手する手は、ルールによれば、打ち歩詰めの規定には当てはまらない
しかし、歩を取る4度目の王手は千日手の規定に当てはまる 後手の勝ちだ
「特に決められた禁手事項」
(将棋世界平成5年1月号付録の'93年版 将棋ルールブック)
３．打ち歩詰
持駒の歩を打って王手をした局面で
王手を解除することが不可能な状態になる時、その歩を打つ手
５．連続王手の千日手
一局中同一局面の最初と４回目の局面の間の
一方の指し手が王手の連続であった時、
王手をした側にとって４回目が出現したときの局面。
371:デフォルトの名無しさん
07/07/29 20:55:46
将棋のルールってこんなに複雑だったんだね
372:デフォルトの名無しさん
07/07/29 22:10:18
最初から完璧に考え抜かれて作られたルールじゃないから
想定外な状況に対処するために後付けルールを足して複雑になって来ている訳か
まるでこれは
373:デフォルトの名無しさん
07/07/29 23:46:53 0
まるでこれは・・・何？
374:デフォルトの名無しさん
07/07/30 00:03:11
続きはWEBで
375:デフォルトの名無しさん
07/07/30 00:05:43
〃∩ ∧＿∧
⊂⌒（ ・ω・） はいはいわろすわろす
｀ヽ_っ⌒/⌒ｃ
⌒ ⌒
376:デフォルトの名無しさん
07/07/30 02:02:41
>>350
ああ、やっと言いたいことが解った。
お互いが最善手を尽くせば、同一局面は二度あらわれないってのが
間違いだと思うぞ。それだと千日手に陥る局面というのはそもそも存在しない。
実際には、千日手ルールを無視した最善手だと千日手になってしまう局面が、
詰め将棋にあって今それを議論している。そして千日手は避けないといけないから、
それを効率よくコンピュータで処理する方法はどうかって話。
初期局面からの完全解析は当然無理だが、これは詰め将棋の問題を内包するし、
詰め将棋を適切に解く技術は、将棋のプログラム開発に必要
千日手になるタイミング云々の話は、そうしたことは当然わかっているものとして、
答えたんだよ
377:デフォルトの名無しさん
07/07/30 02:19:16
どういった解釈が正しいかについては、議論があるだろうが、
いずれにせよプログラム開発の段階では、各ノードの結論として、
「先手勝ち」「後手勝ち」「千日手」に加え、「先手打ち歩詰め」と
「後手打ち歩詰め」を考慮しないと駄目だろうね。
378:180
07/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:デフォルトの名無しさん
07/07/30 02:41:23
もひとつ追加すると、さっきも言ったが、「引き分け」の局面かどうかは、
その千日手ループにいつ突入したかで替わってくる。千日手判定が下る瞬間が違うんだから。
出現回数を保持していない局面のみの情報では、それが「引き分け」かどうか解らない
だから、
>「引き分け」でない局面の出現が一回しかないのは明らかなので、
> 完全解析後のテーブルとしては、すべての局面(手番込み)の
上記の「『引き分け』ではい局面」の、「局面」には出現回数を含ませる必要があって、
それなしには「引き分け」かどうか解らず、そして出現回数によって結果が違っているから、
出現回数の情報を単純にとっぱらうことは出来ない
おまいさんの言っている「解析中のテーブル」を「括弧付きのテーブル」、
「解析後のテーブル」を「括弧なしのテーブル」と読み替えて、>>340, 342 を見てくれ
それと>350で
1)「完全解析後のテーブルとしては持っていません」
2) 「ただし対局である以上「棋譜」が生成されているので、
棋譜を見れば、その対局での「局面」の出現回数は分かります。 」
棋譜の情報を保持していれば、出現回数が解るので、1)と2)は両立しないよ
もし仮に2)が実際の対局を想定していっているのであっても、
参照先である「完全解析後のテーブル」が、1)によって情報を失っているので、
付き合わせることは出来ない。ないのと一緒だ
380:デフォルトの名無しさん
07/07/30 02:51:14
>>180は釣りか、解析後と解析中は判っていない
381:デフォルトの名無しさん
07/07/30 02:54:22
>378
あんまし気にしない方がいいと思うよ、ここ2chだし
ちなみに量子コンピュータ関係で言うとね、まるで量子コンピュータが完成すれば
今コンピュータで扱っている問題がすべて並列に瞬間的に解けるとする
言説がまかり通っているけど、それは勉強不足
量子コンピュータでは、解きたい問題ごとにアルゴリズムを考える必要がある
自分の知る限り、Shor, Grover以外に、パッとする実用的な話はないのが現状
量子コンピュータで、例えば3x3オセロでも解くアルゴリムを作ったら
そりゃ後世に名を残す、いい仕事になると思う
だから仮に量子コンピュータデバイスが実現したとしても、
それを使って将棋を解くアルゴリズムが見つからない状況になると思うぞ
将棋は人間が作ったゲームだから、問題設定が非常に複雑だ
382:180
07/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:デフォルトの名無しさん
07/07/30 03:26:02
可能な局面数 Nにたいし、3回訪れた、0-2回訪れたという情報を持っていれば完全に解ける
2のN乗局面調べればいい
384:180
07/07/30 03:31:22
>381
いえ、私はほとんどたった一人の人を相手に話をしているつもりなのです。
それは将棋板の「将棋って数学に似てるの？」スレ
ｽﾚﾘﾝｸ(bgame板)
で私とずっと議論を戦わせてた人（276)。この人に納得してもらいたい。
ちなみに私はそのスレで281の発言をした者です。
で、>359-360及びこのスレの>206他はその人の発言なんじゃないかな？と
もし違っていたらゴメンナサイ、誤ります。
385:デフォルトの名無しさん
07/07/30 03:44:29
>>384よ、
可能な局面(N個とする) ごとに、3回訪れたかどうかの情報を持ち、かつ
局面データがあれば完全にとけているんだ 意味わかるか?
これ以上のことはないだろが どこが不満だ?
道筋は全く関係ない
まずは、初手からならば局面だけ持っていればいいことは判っているのか??
386:デフォルトの名無しさん
07/07/30 04:08:11
>385
私も解析対象の局面に至る手順の情報全てを保持しなければならないとは
思ってません。ある程度（かなり？）、圧縮は効くでしょう。
ただ、実際に解析する際の手順としてはO(3)'上でゲーム木を展開するのが
いちばんシンプルで分かりやすいと思います。探索すべき局面は増えますが。
また初手から神プレーヤー同士が対戦するならば純粋な局面情報のみ保持
すれば良い、即ちO(1)上の結果にGHI問題が発生しないのは分かります。
まだ、いまいち良く分からないのはO(2)上の結果もそうなのか？
こちらの結果も経路により区別する必要は無いのか？と言う事です。
387:デフォルトの名無しさん
07/07/30 04:15:33
>>378
ごめんね。
>>359は、>>355-357に対して、>>180をみれば「理論」の
話をしているのは分かるのに、「理論」だからこそ、
みんな付き合っているのに、「実行不可能」とか言い出すから、
いまさらそんなことを言うやつが出てくるのか、といった
意味合いの発言でした。
>>180に言ったわけではないです。
>妙に納得
は、
>>170と同じようなニュアンス。
ちなみに
> 人間、あるいは何も考えてないプレーヤー（機械を含む）が指した
> 将棋を途中から将棋の神様が引き継いだとしたら、それまでに
> どの局面が何回現われたかと言う情報なしに指し継いだのでは
この情報とやらは、棋譜で十分では?
それと、無責任なことはするなよ?
と思わなくもないのですが。
388:378
07/07/30 04:25:19
>387
ああ、そういう意味でしたか。それはこちらこそ失礼致しました。
引き継ぐべき情報はもちろん棋譜で十分ですね。
無責任な行為かも知れませんが、任意の局面に結論を出すためには
そのような仮定が必要になると思います。
389:デフォルトの名無しさん
07/07/30 04:33:22
>>388
またまた、ごめん。
>それと、無責任なことはするなよ?
は、>>378に言ったのではなく、話の内容で、対局を引き継ぐのに
「千日手になるかならないかの瀬戸際で交代するなよ。せめて二回目の
局面で交代してやれよ。」と言う意味でした。
他の人もそう思ったかな?
390:デフォルトの名無しさん
07/07/30 04:52:43
>>388
ちなみに
> 引き継ぐべき情報はもちろん棋譜で十分ですね。
とのことですので、>>379と意見が異なると言うことですよね?
>>379は、まったく、困ったもんですよね。
391:デフォルトの名無しさん
07/07/30 12:46:16
>>378さん(>>379さんもかな)
>>217を、もう一度よく読んでみてください。
よく読むとわかると思うのですが、初期局面の駒配置については、
何の言及もされていないのです。
これは、「初期局面として、任意の局面を指定可能」という事でしょう。
上での議論は、「理論上考えられるあらゆる局面」を十分含んでいるので
心配しないでください。
392:デフォルトの名無しさん
07/07/30 13:04:15
将棋の完全解析って言うのは初手から終局までのすべての手筋を網羅した地図を作ることだろ？
当然そんなことは出来ないし意味が無いから勝敗に関係の有る部分だけ解析すればいいだけであって、
人間相手に最強を目指すなら同じ局面が何度来ようがその時に可能なベストの手を打ち続ければいいはず、
結果的にそれが千日手になっても将棋のルールに不備がある部分に達しても負けはしない。
393:デフォルトの名無しさん
07/07/30 13:09:16
うん
それが何か？
394:デフォルトの名無しさん
07/07/30 18:44:34
>>381
その通りで、量子コンピュータが実現すれば既存のコンピュータで難しい問題が
なんでも一瞬で解けるようになると思っている人間がいるから困る。
量子アルゴリズムがあって初めて高速な計算が可能になる。
ゲーム木の探索なんて量子アルゴリズムとは相容れないだろう。
395:デフォルトの名無しさん
07/07/30 23:41:16
>>376、>>379
あなたは、>>345、>>350の内容を全然理解していないことがわかりました。
基本的に、話の発端である>>165と同じことを言っているんですよ？
あと、詰め将棋のルールと、指し将棋のルールが違うことを知っていますか？
ルールが違えば、検索方針も違うんですけど?
>>180の方は、
>引き継ぐべき情報はもちろん棋譜で十分ですね。
と納得したようですが、あなたは理解できましたか?
396:デフォルトの名無しさん
07/08/02 14:41:33
>>394
>量子アルゴリズムがあって初めて高速な計算が可能になる。
高速な計算とは言わないだろ、手順を経て組み立てる計算なら高速であるが
局所的な超同時な仕組みでは計算しているというより状態の合成をしている
に過ぎないよな。
そもそも計算は「計って」、「数を算する」ことであて量子コンでは
計ってもないし、数も扱っていない。
量子コンピュータで致命的なものはソフトウエア、つまりプログラムの
仕組みが存在しないことだよな。
超同時演算にソフトウエアが存在したら、それが足を引っ張り
早いどころか亀速度になるｗ
量子コンピュータが学者の間で注目されないのは、ハードウエアとして
存在しなければいけないという前提があるからだろ。
電子回路な計算機で、ソフトウエアなしの計算機では利用価値などない。
「ソフトウエア」がどれだけ重要な発明であるか理解しておいたほうがいい。
397:デフォルトの名無しさん
07/08/02 14:48:22
>>392
>将棋の完全解析って言うのは初手から終局までのすべての手筋を網羅した地図を作ることだろ？
「巡廻セールスマン問題」で完全解析を行ったというような話と同じだよな。
最適解だと証明したようなことを言う奴はいるが、結局は抜けが発生する。
類似問題を全数を判断せずに証明したと言い張るＤＱＮがいるが、
科学では仮説と実証だけでは、科学ではない。
仮説→実証→複数の反証で多面的に検証できなければ証明したことにはならない。
原理を解明したとか信じるヴァカも多いよな。まさしく宗教の域。
398:デフォルトの名無しさん
07/08/02 20:57:04
>>396
禿げしく胴衣
399:デフォルトの名無しさん
07/08/03 00:24:09
>>396
別にソフトウエア無でも超高速なデータベースとして機能すれば十分だろ
大体、計算機という翻訳語が変で、コンピューターは演算する機械だよ
つまり状態の合成をしているだけなんだがw
400:デフォルトの名無しさん
07/08/03 00:50:10
>>396
量子コンピューターに対してどんだけ無学なんだよ、中学生か？
401:デフォルトの名無しさん
07/08/03 00:54:27
何の指摘にもなってないよ
402:デフォルトの名無しさん
07/08/03 02:25:22
量子デバイスでだって量子ゲートは設計できる。
即ちチューリングマシンが構成できるし、メモリーだって作れるので
原理的に現代のノイマン型コンピュータで可能な事はなんでもできる。
ただ量子エンタングルメントを利用した長いキュービットによる
超並列演算をしないと、現代のコンピュータより圧倒的には
速くならないと言うだけで。
長いエンタングルメントしたキュービットの列で
特殊用途の専用アキュムレータ(と専用アルゴリズム用特殊ハードウェア）を
構成して今のノイマン型コンビュータアーキテクチャの一部として
埋め込む事も出来るんじゃないかな？
周りのノイマン型の部分は既存のデバイスでも量子デバイスでも良いだろうし。
いずれにしろ、まだろくに存在していないものを
あれが出来てこれが出来ないと言うのは早計じゃないか？
アルゴリズムが無ければキュービットアキュムレータが働かない
（超並列演算が出来ない）のはその通りだろうが。
403:デフォルトの名無しさん
07/08/05 02:01:57
>即ちチューリングマシンが構成できるし、メモリーだって作れるので
それではチューリングマシンであって、量子コンピュータではないだろ
頭変になったのか？
404:デフォルトの名無しさん
07/08/05 02:24:09
量子チューリングマシンと言うのが定式化されている。
405:デフォルトの名無しさん
07/08/07 00:34:50
>>404
あたま悪そうだな。チューリングマシンの手順式手法に戻るのなら
従来技術に激しく勝てず、量子の意味すらなくなる。
手順式は手順を超える演算はできないんだよ。
量子チューリングマシンでは量子コンピュータが得意とする因数分解が
出来なくなるｗ
これでは古典的コンピュータの因数分解専用の演算回路に下った
たんなる量子トランジスタレベルだろう。
仕組みを手順通り行うという概念の壁が越えられないからこそ
古典的コンピュータには性能の限界があることすら知らないようだなｗ
406:デフォルトの名無しさん
07/08/07 04:20:58
>405
量子チューリングマシンは古典的（決定論的）チューリングマシンとは
その動作原理自体が異なる。
決定論的チューリングマシンのアルゴリズムは量子チューリングマシン上では
（そのままでは）使えないだろうが、むしろ使う必要が無いとも言える。
参考：
URLﾘﾝｸ(results.atr.jp)
407:デフォルトの名無しさん
07/08/07 17:57:47
>>406
あたま悪いな。論理手順が存在する限る原理が異なろうが
手順を省略できないわけだ。手順が省略できなければ順番に実行する
以外ありえないわけ。勉強になった？
408:デフォルトの名無しさん
07/08/07 18:00:07
>>406
そもそもチューリングマシンは命令語を受け取りそれを手順どおり実行する
タイプだろ。電送時間が存在しれば遅延する。
これでは古典的コンピュータが速度を上げられない理由と同じで
電送経路があるかぎり従来技術にはコスト的についてこれない。
つまり永久に開発されない。
409:デフォルトの名無しさん
07/08/07 19:36:23
量子チューリングマシンは古典的チューリングマシンが持つ能力を
全て保持しながら、なおかつ量子コンピュータ固有の機能も持っている。
量子ゲートに与えるデータ次第でどちらの働き方もできる。
量子チューリングマシンは計算可能性と言う点で
古典的チューリングマシンと全く同等であるが、
問題によっては（まさに）桁違いの計算能力を発揮する。
410:デフォルトの名無しさん
07/08/07 19:46:16
どうでもいいけど将棋の話題しない？
振れるようなネタはないのだけど。
411:デフォルトの名無しさん
07/08/07 20:07:00
うーん、難しいな。
Lispで将棋ブログラミングしたいと思っててまだ始めてないし。
と言うか、Schemeで書くべきかCommon Lispで
始めるべきかで早くも悩んでるしw。
412:デフォルトの名無しさん
07/08/07 22:14:26
非決定的チューリングマシンの話は出ないのか？
これが量子チューリングマシンで実現できればメチャ嬉しいのだが
413:デフォルトの名無しさん
07/08/07 23:54:06
量子コンピューターが出来る前に光子コンピューターの方が早く出来るでしょ。
414:デフォルトの名無しさん
07/08/08 17:16:07
量子コンピュータでチューリングマシンはできる、しかし現状の性能には
激しく達し得ないというのでＦＡ。
まあマヌケ君はできないことを誇張するのが得意だから、またデンパするんだろう
415:宮本
07/08/08 17:37:03
URLﾘﾝｸ(www.geocities.jp)
URLに「宮本定跡が激指５に使われている」とありますが、本当でしょうか。
事実なら「激指６」ではどうなっているのでしょうか。
なるべく詳しい事情を知りたく思います。
416:デフォルトの名無しさん
07/08/08 19:39:38
>414
誰が正しいかでは無くて真実は何なのかを知ろうとする方が有益だぞ。
417:デフォルトの名無しさん
07/08/09 07:09:58
スレ違いかどうか気づける能力を持つ方が重要だ。
418:デフォルトの名無しさん
07/08/09 12:43:22
最近はスレ違い、スレ違いとやたらうるさい人が居るな。
まるで縦割行政が好きな役人か自分の専門分野にコモッテル蛸壷学者だ。
そういう考え方からは学際領域にある分野が発展する事は決してあり得ない。
419:デフォルトの名無しさん
07/08/09 14:02:16
とは言うものの量子コンピュータ及び分子コンピュータや
光コンピュータなどに関するスレを新たに立てた方が
良いかとも思ったが、どの板に立てたら良いのか良く分からん。
それとも既にどこかにあるのかな？
420:デフォルトの名無しさん
07/08/09 14:27:17
量子コンピュータ 3qubit
ｽﾚﾘﾝｸ(sci板)
過疎ってるな
421:デフォルトの名無しさん
07/08/09 18:16:55
>>418
お前がスレ違いだろ。別に学問を発展させようなんて思ってない
422:デフォルトの名無しさん
07/08/09 18:37:44
>>418
お前こそ将棋のプログラマじゃないだろ
423:デフォルトの名無しさん
07/08/09 22:19:33
>420 Thanks
物理板か。
しかも寂れていると言うか荒れているようだな。
計算理論やアルゴリズム論、計算量理論から見た
量子コンピュータ スレがあっても良い気もするな。
424:デフォルトの名無しさん
07/08/09 22:41:47
量子コンピュータなんてやっている奴は約１名の２ｃｈ中毒ニート以外
いないだろ。
425:デフォルトの名無しさん
07/08/09 23:54:00
量子コンピュータまず量子縺れ状態のシュミレーションから、かなり高度な量子力学の知識が必要。
どちらにしても量子コンピューターシュミレーターってあるらしいけど一般公開して無いだろ、動かすのにたぶんスパコン必須？
426:デフォルトの名無しさん
07/08/11 08:39:18
みんなで激指を買って遊ぼうよね♪（ ＾ω＾）
激指 定跡道場
商品紹介
2005年世界コンピュータ将棋選手権で全勝優勝を飾った「激指」のシリーズ最新作。
序盤戦術を体系立てて学習できるモードを搭載、最強の思考エンジンに加えて学習補助機能が充実しました。
定跡講座は所司和晴七段が全面協力、プロ将棋の最先端を無理なく身につけることが出来ます。
427:デフォルトの名無しさん
07/08/11 23:40:57
コピペうぜぇ氏ね
428:デフォルトの名無しさん
07/08/12 13:28:16
量子信者はカエレ！
429:デフォルトの名無しさん
07/08/12 22:26:06
町はずれの教会をシルクのような霧雨が包んでいます。
傘も差さずにレンガの階段にもたれていると
遠い町明かりがいくつも輝いては滲んで行きます。
あの人はガードレールをのりこえて空の向こうに何を見たかったのでしょうか。
あの人が星になったなんて嘘ですよね？
430:デフォルトの名無しさん
07/08/13 00:30:19
ポエムはポエム板でおｋ
431:デフォルトの名無しさん
07/08/13 17:17:58
>>429
我々は重要な事を見逃していたようだ、
このポエムの中に封印された古代の将棋の英知が詰まっているのだよ！！(AA略)
432:デフォルトの名無しさん
07/08/14 12:04:06
だから量子コン厨は物理板で爺でもしておけ。
スレ違いだよ、キミのような量子ウンコは
433:デフォルトの名無しさん
07/08/14 12:40:05
>429
リョウコ信者w
最近の厨はググって出てこないと何も調べられないのか
434:デフォルトの名無しさん
07/08/14 22:09:55
夏厨の季節
435:デフォルトの名無しさん
07/08/14 22:38:58
>>429 これかｗｗ URLﾘﾝｸ(jp.youtube.com)
436:デフォルトの名無しさん
07/08/15 10:35:39
うはぁ、なんという音程……
437:デフォルトの名無しさん
07/09/10 08:35:42
量子って、武豊の嫁？
438:デフォルトの名無しさん
07/09/14 10:29:21
銀星将棋おもろいな。思考タイプに強引、慎重なんてのがあって
強引にすると思考レベル最低でも強引に攻め込んでくる。
ずっとこういうの待ってたんだよな。重みのさじ加減弄るだけで
技術的にはなんも難しくないのになぜ今までなかったのかが不思議なくらいだ。
全AIにこのオプションをつけてくれ。
439:デフォルトの名無しさん
07/09/14 17:19:50
B-TRONの体験版・・・(超漢字のご先祖)
1B/V3体験版のご案内
URLﾘﾝｸ(www.personal-media.co.jp)
fURLﾘﾝｸ(ftp.personal-media.co.jp)
1BV3体験版
URLﾘﾝｸ(tat.soga.in)
「超漢字」を体験させてほしい
URLﾘﾝｸ(homepage1.nifty.com)
オープンギャラリー:1B/V3の環境
URLﾘﾝｸ(www.ne.jp)
オープンギャラリー：プラットフォームコーナ
URLﾘﾝｸ(www.ne.jp)
440:デフォルトの名無しさん
07/09/18 10:52:04
ほ
441:デフォルトの名無しさん
07/09/18 18:49:11
しゅ、しゅって言いたい訳じゃないんだからねっ！
442:デフォルトの名無しさん
07/09/19 10:05:02
ぬは、書かれちまったw
443:デフォルトの名無しさん
07/09/19 17:25:23
ダリか初心者にも分かるように
評価関数における評価項目のつけ方まとめてもらえませんか
444:デフォルトの名無しさん
07/09/19 19:32:30
>>443
・駒割
・王将8近傍の敵・味方の利きの数
・王将との相対位置による評価
って感じの情報でいいのか？
445:デフォルトの名無しさん
07/09/19 19:56:23
玉の安全度を考えるをON/OFFで自己対戦すると２７勝３敗だった。
終盤は駒得より完全に玉の安全度だね。
446:デフォルトの名無しさん
07/09/19 20:44:00
>>444
>>445
ありがとうございます。
評価項目の全体的な全体的な優先順位や
細かい設定などはありますか？
447:デフォルトの名無しさん
07/09/19 20:58:55
優先順位ってのは評価項目の重みの事？
序盤は駒得や囲いが重要だけど、終盤は王将の安全度の方が重要だろうし・・・
大雑把な方針としては、試行錯誤して最適な重み・設定を見つけるか、学習で何とかするかの二択じゃないかな。
自分の棋力とかコンピュータ将棋にかけれる時間と相談しながら決めてくれい。
448:デフォルトの名無しさん
07/09/19 21:34:35
>>447
分かりました！がんばります！！
449:デフォルトの名無しさん
07/09/25 12:35:31
ほ
450:デフォルトの名無しさん
07/09/26 03:26:24
し ひゅうま
451:デフォルトの名無しさん
07/09/26 04:25:07
あ
452:デフォルトの名無しさん
07/09/26 15:40:34
そ
453:デフォルトの名無しさん
07/09/26 15:53:49
こ
454:デフォルトの名無しさん
07/09/27 10:12:06
455:デフォルトの名無しさん
07/10/01 11:07:00
ほ
456:デフォルトの名無しさん
07/10/01 19:46:05
あたぁ！
457:デフォルトの名無しさん
07/10/02 20:38:46
[人工知能]革新AI囲碁ｿﾌﾄ『Crazy Stone』@ﾓﾝﾃｶﾙﾛ法
ｽﾚﾘﾝｸ(gamestones板)
[人工知能]"Crazy Stone"@モンテカルロ法
ｽﾚﾘﾝｸ(bgame板)
458:デフォルトの名無しさん
07/10/03 01:23:13
> これまでのアルゴリズムとは異なり、モンテカルロ法のアプローチでは
> 非常に簡単に並行処理ができるので、
> 新世代プロセッサーのマルチコア構造を活用できる。
459:デフォルトの名無しさん
07/10/03 09:36:05
モンテカルロ法自体は並列化しやすいだろうが、
それとともに使われて成果を上げているUCT（だっけ？）
とか言う探索アルゴリズムは並列化しにくいらしいよ。