Whiteのふりーとーく

Wayne : すごろくはなんか違和感があるんです。でもその違和感が説明できないのでだめですね。「不完全な」人間が「乱数」と化す＝すごろくにおけるダイス/ルーレット　ってことだと思うんですがそれだと妙に違和感があります。その前提が違う？

white : いや、その前提で正しいです。ただ双六なのは途中までで、ゲーム木中でオラクル必勝の分木に入って以降は手順になるのですけど。

Wayne : 人間がダイスってことは、オラクルはすごろくプレイヤーですね。てことは、ソロでダイス転がして駒進めている、という状況？　それはそもそもすごろくなのかなぁ。すごろくってつまり複数人でダイス転がして「誰が一番6を多く出すか（もちろん実際のすごろく盤面は「○歩進む/戻る」「一回休み」etcがあって6が必ずしも最適ではないのだけど、ごく単純化すればそうなると思う）」というゲーｍ…ええと、とにかくそういうものだと思うのです。つまり違和感の原因は「ソロでプレイするすごろくはすごろくなのか？」しかしコレってつまり「どんなクソゲーでも他人が居ればゲームになる」の例か。

white : 人間はダイス兼(双六みたいなものの)プレイヤーなんだと思います。ゲーム理論的には人間が勝つのは確定している。でも人間はそこまで頭が良くない。ということで人間は「必勝ルートに乗り続けられるか」というダイスを振りまくることになる。ダイスの出目だけでゲームの結果が決まるからこれは双六みたいなもんだろう、とそういう話。

white : あ、双六は数学的には状態遷移関数で定義できるのかなー、とか思ってみた。

Wayne : 大分違和感があります。すごろくは確かにダイスの出目だけで結果が確定しますが、全プレイヤーが等条件なのが基本です（盤面に「歌を歌わないと一回休み」系のパーティ用は知りませんが）。でもこの「すごろくみたいなもの」のオラクルと人間って等条件なんでしょうか。人間必敗ルートに入るまでだとしてもです。人間側は先が見えないのでダイスを振らざるをえませんが、オラクル側は（人間の手選択を等確率とすれば）自分必勝の確率を計算可能なのだから最も高い確率になる手を選択すればいいはず……、問題は人間の選択が"等確率"ではないことか

Wayne : 自分必勝の確率てアレだ、言いたいことは自分の勝利確率。つまり分岐先の(相手勝利盤面数+自分勝利盤面数)/分岐可能盤面数　　それはともかくできるかも＞状態遷移関数　おーとまとん?

Wayne : まだおかしいですYO! 自分勝利盤面数/分岐可能盤面数…これで合ってるか？

white : それはまさしくこの議論の深みに至る部分、本来無限であったはずのオラクルの能力に拡張が要求されるという話になります。この場合は「単純な(分木ベースの)勝率計算ができないオラクル」「単純な(分木ベースの)勝率計算ができるオラクル」「人間の不合理の程度まで把握して勝率計算が可能なオラクル」って感じにわかれますかね。

white : ちなみに単純勝率は「現在分木下のオラクル勝利リーフノード数/現在分木のリーフノード数」ですね。なお、リーフノード＝終了型という意味です。為念。

Wayne : なるほど、なんとなくわかったような消化不良のような。リーフノードの件に関しては追記しようと思ったんだけど連投が恥ずかしかったので（笑）控えてました。了解してます。というかいつの間にか多重投稿しちゃってるし。

てらしま : たしかに、「ゲームのすべてを把握している」オラクルの能力に、人間がどんなミスをするのかというのは含まれていないですね。単純勝率の高い手を選んでいったとしても、それは人間の行動を予測できているわけではない。人間はけっこうあっさりと最善手を捜しだしてしまうかもしれないし、相手の人間の能力を推し量ることはこのオラクルの能力に含まれていない。けっきょく相手が「最善手を選ぶかミスをするか」の２択で、判断材料がないからさいころを振っているのと同じ。そうすると、「不確定になる」で正しかった気がします。前回の自分のコメントを翻しちゃいますが(笑)　あと、スゴロクは相手がいようがいまいがゲームじゃないので、同じことではないかと。

てらしま : あ、どうでもいい追記。「どの程度か知らないがこの相手はミスをしそうだ」とわかっているなら、単純勝率じゃなくてただ単にゲームを引き伸ばす方法をとったほうがいいかもですね。

white : 双六は、ゲーム理論的にはどう考えてもゲームじゃないんですが、遊んでいると確かにゲーム的な快感を感じるというのが実に厄介でありまして。双六から感じるそれがなんなのか説明できれば、人間にとってのゲームというものの半分ぐらいは説明できるんじゃないかと思うわけですよ。

てらしま : たしかに、ダイスを振れば普通は昂奮するんですよね。オラクルは「こう指せば敵はミスるはず！」と思いながら指して、思惑どおりいったら昂奮するわけか……（このモデルの場合、そう判断した根拠は存在しないから、つまりオカルト）。オラクルに宗教心があるのかというのは定義外の話ですが(笑)

Wayne : The Oracleって何だったっけ。検索するとデータベースばっかりでがっかりですよ。…アポロ神殿？　ギリシャ関係の…、よく調べもせずにしゃべってるけど、The Oracleは宗教バリバリじゃないですかね？（笑）　それはともかく、Oracle vs Oracleのとき、まあ確かに会戦前に勝敗は決まってるんですけど、必勝側は勝利リーフが複数ある場合、一体どういう基準でどの勝利リーフを選ぶんでしょうね？　必勝側をnotオラクルに格下げする前に、その辺に対するオラクルの定義って必要なんじゃないかなあ。

Wayne : 会戦->開戦　　あるいは、必敗側の敗北リーフの選択基準とか…、ああおかしいな。オラクルがオラクルじゃなくなっていく。

Wayne : また二重ですか。かなしい。いずれにせよオラクルvsオラクルのとき、「相手がオラクルであることは既知なのか」と「ゲームルール上で勝敗が決する前に勝負を終えることはありなのか」で、「未知」かつ「なし」（後者においては人vs人ではアリなこともあるけど）だとすれば、オラクルはお互い何らかの終了リーフの選択基準は持たないといかんと思うのです。

てらしま : 実際、このオラクルにとっての二人零和有限確定完全情報ゲームはただのデータベースだとは思いますが(笑)　ここで議論している「最小限のオラクル」の定義を言い換えれば「評価関数がブーリアン」ということだと思います。しかしそれでは、「どのゼロを選ぶか」「どの１を選ぶか」について判断する基準がない。そういうときになにを選ぶかというのは非常に人間くさい話だし、正解はもともと存在しないので「オラクルの個性次第」としかいいようがないという話かと。人間と同じでいろんなオラクルがいるんじゃないですかね？(笑)

Wayne : OK、つまり「本来無限であったはずのオラクルの能力に拡張が要求される」――価値関数がbooleanで万能であったはずのオラクルが、相手が万能ではない、あるいは万能ではないかもしれないことによって、能力の拡張が必要になる。と、こういうことか。

Wayne : 能力の拡張が必要になる＝次の手に順位付けを行える能力が必要になる。(価値関数がbooleanだと、次の手が指せない、あるいは指せてもそれが最適ではない可能性があるので）

white : オラクルvsオラクルはゲーム開始と同時に「あなたの勝ちだ」で終了するように思います。相手がオラクルかどうかわからない場合でも「私の勝ちだ」「確かにあなたの勝ちだ」で終わり。相手に普通のプレイヤーが来る可能性があるなら、しばらく手順を実行してから「どうやら双方オラクルらしいからあなたの勝ちだ」とか。

white : いやそもそも相手への問い合わせ能力があるかは謎なのですが。選択基準ですが、どの分岐もオラクルにとっては等価なのでどうでもいい、のだと思いますよ。

Wayne : なんか枠が広がってますねん(笑)。Web2.0。まあそれはともかく、新規レイヤーが必要だと思うのですよ。
1.オラクルvsオラクル、互いに相手がオラクルであることが既知：勝負は開始されない。あるいは開始直後に必敗側が投了。
2.オラクルvsオラクル、互いに相手は未知かつ確認不能：必敗側は投了しない。なぜなら相手が「オラクル未満」である可能性があり、その場合には自分が勝利できる可能性がある。
3.オラクルvs"未満"：既知にしろ未知にしろ、オラクルは仮に必敗側で開始しても勝利できる可能性がある。
で、新規レイヤーは2．この場合はなんらかの価値基準を持って次の手が指せる必要があると思うのです。どの手を選んでも負けリーフにしかたどり着かない分木(≒詰め将棋の詰められる側)に入ってしまえば投了すればいいのですが(それが人間にとって本当に勝負がついているかぱっと見判別不能であってもかまわない)、ゲーム開始直後は少なくともそうではないし、勝利リーフが見えている限りは抗う意味があるからです。となれば必勝側としても、相手の勝利リーフを減らす方向を選ぶのが合理的である、と言えるような気がします。「どの分木もオラクルにとって等価」というのは，1.の場合だけじゃないでしょうか。
ところで囲碁とかだとふつーに地の数(だっけ?)でリーフの価値ができちゃったりしそうだけどこの場合はどうでもいいか…、というかその前に囲碁の終了条件が未だにわかりません。囲碁ソフトで、9路地4石置きのハンデを貰ってではじめたら、あっさりパスしやがってこっちとしてはサッパリです。
ところで、こちら(http://www.fairyland.to/BakaMemo/2005-12.php)の357ゲームがちょうど「オラクルと私」を再現してくれています。この場合プログラムがオラクル役をやってくれます。もしかすると、必敗側ではじめても貪欲に勝とうとする357ゲームのプログラムの印象が強くて、どの分木も等価とかどうとかってのが引っかかっちゃってるのが一連の私のつっかかりの原因かもしれません。

Wayne : Deep Fishですね＞357ゲームのオラクル

white : 2の場合に絞って話をします。
必勝側にとっては全ての（勝てる）選択が等価でしょう。相手の選択を減らす価値はありません。なにせどうやっても勝てますから。時間に価値を感じるオラクルなら最短手を選択するぐらい？
必敗側はどうかと言うと、多分あんまり選択肢はありません。どの分木に入るか決めるのは必勝側なので、まあ作業が続くでしょう。最善ということでなら極力敗北の確定を引き伸ばす手を指すような気はしますけど。時間に価値を感じるオラクルだとどうなるかというのはややこしいので別途。

そもそもオラクルは人間が将棋やら囲碁やらチェスやらをやってる途中で行う戦局判断をする必要がありません。戦局判断というのは自分の入っている分木の行く末がわからないから行うものであって、オラクルにはそれがわかってますから。

white : 2のケースで必敗側が時間に価値を感じるオラクルだった場合の話。
この場合、このオラクルはしばらく自分の負けを最大まで引き伸ばせる手を指します。このオラクルが最低限の能力しか持たないのであれば詰みが確定するまで続けるのですが、「時間に価値を感じる」ので多分少々拡張されているでしょう。ということで、どこかで引き伸ばしをやめて相手がオラクルかどうか判断するための手を打つかもしれません。この場合、それに相手が付いてきたらそこで投了。

Deep Fishの敵アルゴリズムは時間に対し価値を感じないでしょうから、この思考実験を続ける上では忘れたほうがいいと思います。まあ相手がオラクルだとわからないなら引き伸ばすのは合理的なんですが、それが合理的だと理解してはいないと思います。

てらしま : 　Deep Fishの場合、勝つときは最短の手筋、負けてるときは最長の手筋を選ぶようです。それがDeep Fishに与えられた性格なんですね。
　そこでふと思ったんですが、ほんとに盤面を０か１だけで評価できる（だけの）オラクルなら、全検索して０しかなければ単純に投了、ということでいいと思います。必敗側でゲームを続けているということ自体、すでにオラクルの定義を拡張していると考えるべきでは（Deep Fishみたいな単純な奴でさえ）。

Wayne : そいやなんか混乱してますね(私が)。「全探索して0のみ」って状況ってどこにあるんでしょう。詰め将棋の詰められる側ですら、詰める側がミスをしたら詰まなくなるのだから、「全探索して0のみ」ではないような気がするのです。(いや詰める側に王がいないような気がするので逆転勝ちは無理かもしれないけど…)
このオラクルの場合、たとえば将棋なら、ゲーム開始直後からして詰め将棋状態のハズですね。そこで「全探索して0のみ」という「全探索」ってのは、「相手が最善の手を尽くす」ことが前提なんですよね。だからオラクルvsオラクルのときはなんの問題もないんですけど、相手がオラクル未満のときはその前提が崩れてしまっているんですよね。
結局、オラクルは万能だがその万能性ゆえに次の手を指す能力を失ってしまっている(指す必要がないから)。だからオラクルvsオラクル未満を考えたとき、変な話になっているのではないでしょうか。
「全探索(ただし相手は最善の手を尽くす)して0しかなければ投了」だと、「オラクルが必敗側でオラクルvs人間のゲームを行った場合」は、「オラクルはゲーム開始直後投了」するのであって、すごろくでもなんでもないような気がします。

てらしま : 　まずDeep Fishに話を絞ります。彼女は（上のわたしの定義では）「投了しない」性格づけをされた拡張オラクルです。
　Deep Fishは、ゲームを始める前にすべての局面を評価しています。これは実際に、ブーリアンです（盤面の「高さ」が偶数か奇数か）。これはゲームのルールだけから導き出していて、相手が誰であっても関係ありません。
　全検索した結果が「全部ゼロ」でも、絶対投了しないようにプログラムされているDeep Fishは、まあ感情を持っているとすれば「相手のミスを期待して」できるかぎりゲームを引き伸ばそうとします（ここではブーリアン以外の評価を使っているが、どの手も勝利につながってはいない。Deep Fishの宗教心ですねｗ）。
　相手がミスをするかどうかは知らないしミスの発生にどんな変数が関与するかも知らないけど、引き伸ばす。とにかくそういうスタイルのゲームプレイヤーなんですよね。
　つまり、Deep Fishにとっては、相手がオラクルでも人間でも関係ありません。絶対投了しないので。
　彼女がやっていることは、スゴロクといってもいいと思います。

　少し本題から外れて「相手がオラクルなら投了する」アルゴリズムに関してですが……。これは疑問です。
　相手がオラクルであることを証明することは、情報が盤面だけでは不可能です。「１万回に１回ミスる似非オラクル」かもしれないから。証明するためには相手のソースをよく見なければなりませんが、これができるならすでに彼女は「最大限のオラクル」です。
　けっきょく、上の１、２、３でいえば、２しかありえない。Deep Fishの「絶対投了しない」アプローチは現実的だと思います。

　で、おそらく「（わたしの定義でいう未拡張オラクルは）相手が誰でも勝率５割」という部分に引っかかっているのだと思うのです。万能のくせに５割しか勝てないのかと。しかしオラクルに「勝ちたい」という欲求があるかどうかは別の問題だし、オラクルは強いはずだというのは我々の願いでしかありません。５割しか勝てないでいいのでは。
　……というのがわたしの結論ではあるんですが。

てらしま : ＞けっきょく、上の１、２、３でいえば、２しかありえない
　ごめんなさい。２は違いますね。「相手がなんであるかはわからない」ですね。

Wayne : おや、なんで「相手が誰でも勝率5割」なんだろう？

white : 「相手がオラクルなら投了する」は（できるとしても）かなりの拡張を受けたオラクルでないと確かに無理ですね。話そのものもゲーム理論よりは情報理論とかの話に近づいてるし。

名前 m7DIRDjf:spam避けのため、この行を1行目に残したまま、2行目以降にコメントを書いてください。

TrackBack: