フレーム問題はコンピュータ将棋では解決できているんですか?

「フレーム問題」については「人工知能(Artificial Intelligence)」という言葉の生みの親であるJohn McCarthy氏とPatrick Hayes氏(この人の業績は私はよく知りません)がその著書において述べました。

言葉の定義の説明は面倒なので、詳細はWikipediaに譲ります。

フレーム問題が問題としているのは、考慮すべき空間が有限でない限り、無限の可能性について考えざるを得ないという点である(ただし、空間が有限でも、考慮すべき要素の組み合わせが爆発的に増加するので同じことである)。
自然界に発生した知性(人間の知性など)が、どのようにこのフレーム問題を解決しているかはまだ解明されていない。人間は実際にはフレーム問題を解決できておらず、フレーム問題にうまく対処しているかのように見えるだけだと唱える研究者もいる。
フレーム問題 – Wikipedia

私はコンピュータオセロを小学3年のときに作りました。それは石を打てる場所を、四隅→四隅に接しない辺→中央の4×4のボックス→…という風に順番に探しながら打つ(ゆえに四隅に打てるときは必ずそちらが優先されてそこに打つ)というアルゴリズムでした。小学5年ぐらいのときにはmin-max探索を用いて3手読みが出来るようにしました。

また当時の私は「フレーム問題」という言葉を聞きかじりで知っていました。「フレーム問題」とはそれをゲーム木探索の問題として捉えるなら、「ゲーム木の探索が終わらず、計算のために無限の時間を消費することがあるという問題」らしいと。

しかし3手読みできるオセロAIを完成させた私は、この「フレーム問題」についてはちょっと懐疑的でした。

「なんで無限に時間を消費するの?意味わかんない。それなら逆に、何故オセロのAIは無限に時間を消費しないのよ?オセロのAIだって3手で探索を打ち切れば思考時間を無限には消費しないよ?John McCarthyという人は、もしかして縦型探索(深さ優先探索)で探索打ち切り条件を書かないとでも言うの?そりゃ探索終わらないよね。この人、馬鹿なんじゃないの?」

当時小学5年生だった私が考えたのはそんなことでした。人工知能の神様John McCarthy氏を馬鹿扱い。本当に私は怖いもの知らずでした。いやまあ、怖いもの知らずはいまも全く変わっていませんが。

それはともかく、あれから30年ぐらい経ったいま見ても「フレーム問題」はちょっと問題の提起の仕方がおかしいんじゃないかと思うんですね。このことについて今日はだらだら書いてみます。

まず、「フレーム問題」をオセロや将棋を例に考えてみると、次の二つのことがわかります。

《無限1》 現実世界では考慮する事象が無限にある。

これは、オセロや将棋で言うと、ある局面の次の指し手(一手)が無数にあるということです。オセロでは最大でも残りのマス目(多く見積っても60通りで、実際にはもっと小さな数値)しかありませんし、将棋でも900通りすらありません。

John McCarthy氏は、ここが、現実世界の問題では考慮すべき事象は無限にあると言うわけです。

《無限2》 現実世界では考慮する事象をトリガーに次の考慮すべき事象が起き、その連鎖が無限にある。

将棋では何手で終局というのは決められていませんが、電王トーナメントでは256手ですし、少しの記事で書いたように普通のルールの将棋でも終局までの手数は有限です。しかし、その数は天文学的な数字なので、それを最先端のPCの1億倍速いPCが1億年かけてもすべて辿り切ることは不可能ですが、一応は有限です。

John McCarthy氏は、ここが、現実世界での事象の連鎖は無限だと言うわけです。まあ、オセロが最長60手で終局するとは言っても、ほとんどの人は直線的であれ60手先まで頭のなかで盤面を動かせませんから、無限どころか60ですら無限にあるのと同じような意味を持ちます。そういう意味では有限か無限かというのが問題なのではなく、人間が実時間で(1秒程度で)そこまで思考が到達できるかというほうがより重要です。

ともかく、《無限1》により、探索ツリーの節点(将棋で言うと1つの局面)は無限の枝(将棋で言うとその局面で可能な指し手)を持つことになり、《無限2》により、探索ツリーは無限の探索深さがあるということになります。

《無限1》×《無限2》 = ごっつ無限(※)に節点があることになり、「探索終わらんのちがうか?」というのがJohn McCarthy氏の主張です。
※ 「ごっつ」= 関西弁「すごく」の意味。

私はまずここの論法に少しの疑問を感じます。

《無限1》だけでも、無限に節点はあるわけだし、《無限2》だけでも無限に節点があることになります。「節点が無限にあるから、探索が終わらん」と主張したいのであれば、《無限1》と《無限2》の二つも持ち出す必要がないのです。《無限1》か《無限2》だけでいいのです。

わざわざ二つの無限を持ちだしてきて、「《無限1》であかんし、それがなんとかなったとしても《無限2》があるから、どうせあかんでー」みたいな論法はなんだか怪しげなんですよね。《無限1》があるから本当に駄目だと思っているなら《無限1》だけ主張すればそれで十分なのに、どうして《無限2》の話を持ち出すのかと。John McCarthy氏は、《無限1》が解決したとしても、《無限2》も解決しないといけないので、人工知能の課題は色々あるということが言いたかったのかも知れませんが。

まず、《無限2》についてですが、オセロでも将棋でも人間はそんなに深くまで読んでませんよね。コンピュータもそうです。適当なところで探索を打ち切っています。

このようにゲーム木の深さが無限にあると考えられる場合でも、途中で探索を打ち切り、何らかの方法で終端ノード(現在の読み筋の最終局面)を評価することで近似解は得られるので、ゲーム木の深さが無限にあることは探索が終わらない理由にはならないのです。この意味で「《無限2》があるゆえに探索が終わらない」は間違っています。

そりゃ最善手(神様の指し手)を求めようとしたときは現実時間で終わらないでしょうけど、そんな探索は人間もやってないのは明らかなので(将棋の場合、人間もあらゆる局面で最善手を指せないので)、「人間には出来てコンピュータには解決出来ない問題がフレーム問題である」と言うのは間違っています。無限の探索深さまで読むことは人間も出来ないし、コンピュータも出来ないけど、ある程度の精度で近似解(現実的な解)を得ることはできます。

次に、《無限1》についても考えてみましょう。

まず、すべての事象について人間が考慮していないことは明らかです。(これについて脳科学的な証明をしようと思えばあと20年ぐらい待たないといけないのかも知れませんが…)

この意味において「(人間は)限られた枠内(フレーム内)でしか物事を捉えていない」というのは正しいと私は思います。自分が存在を認識していないものは少なくともその人にとっては(その人の頭のなかにある世界モデル上は)存在しないのでしょう。デカルトの存在論 「我思う故に我あり」ですね。だからときどき、人間は箪笥の角に足の小指をぶつけるわけですが。(笑)

しかしこれをもって、「人間は限られた枠内(フレーム)でしか物事を捉えていないから、フレーム問題が起きない」という説を主張する人がときどきいます。

これは明らかに間違っています。《無限1》が無限ではなく有限だとしても、《無限2》がありますから、《無限2》があるのに探索の打ち切り条件がないなら探索は終わりません。すなわち、フレーム問題は起こりえます。

将棋を例にすると、ある局面での可能な指し手はどの局面においても1000通りもありません。そういう意味では限られていますし、ルールは明快なのである局面で可能な指し手すべてを列挙することはアマ十級ぐらいの棋力でも十分出来ます。ただし、長手数の詰みを正確に読めるかと言われると、ほとんどの人がノーです。その組み合わせの数が人間の計算力で処理できる程度の有限の値とは限らないからです。

このように「限られた枠内」でだけ考えていたとしても(《無限1》が無限ではなく有限のごく小さな数だとしても)、ゲーム木を辿ろうとしたときに辿るべき節点が組み合わせ爆発していて(あるいは、それらの節点を正確に頭のなかで辿れなくて)、人間には対処できないケースというのは多々あるのです。だから、「(人間は)限られた枠内でしか物事を捉えていないから、フレーム問題が起きない」は間違っているのです。

限られた枠内でしか物事を捉えていなくともフレーム問題は容易に起きるけれど、適当なところで探索を打ち切るから無限の計算資源を消費しない。探索を途中で打ち切って、大局観などでその節点(局面)の良し悪しを判断する。そしてそれは人間も機械も同じ。これが正しいのです。

現実世界のあらゆる可能性を考慮するなんてことは人間も出来ていないし、機械も当然ながら出来ないですが、人間も機械も現実世界をうまく乗り切ることが出来るのです。(機械の場合、その問題を解決するための適切なアルゴリズムを与えられる必要がありますが。)

最後に。

本記事では、《フレーム問題》をゲーム木探索の問題として扱いましたが、このような現実世界の問題を解決しようとするときに、それが本当にゲーム木探索の問題に帰着できるのかという別の問題があります。現実世界の問題をどう記号化して取り扱うのかについては、本記事の範疇を超えますので機を改めて書きたいと思います。

フレーム問題はコンピュータ将棋では解決できているんですか?」への10件のフィードバック

  1. 人間の持つフレームというのは基本的に生活から学んだ必要十分の壁ではないでしょうか。
    ここまでやっておけば回答に足りるという状況の統計だと思います。
    それをAIに反映するときの難しさを説こうと思って頑張ったけど風化しちゃったというのが実情に見えました。
    最初の人間は無限を検索しようと頑張っていたのかもしれませんが経験上必要ないとわかった後世の人間が割り切りを学習してフレームが発生すると。
    喋ってる人も科学者なので常人とは違った味のある思考をしていたのかもしれませんね。

    • 私が小学3年のときはPC-6001を使っていました。X68000は高校1年のときですね。とても欲しかったのを覚えています。しかしX68000を買っていたらゲームに夢中になってプログラミングどころではなかったかも知れませんね。

  2. > 現実世界のあらゆる可能性を考慮するなんてことは人間も出来ていないし、機械も当然ながら出来ないですが、人間も機械も現実世界をうまく乗り切ることが出来るのです。

    まだまだ人間の方が、正解に近い近似解(良いフレーム)を得られているのではないでしょうか?
    逆に言うと、将棋ソフトの製作者はコンピュータの設定するフレームは間違っている可能性があると考えているので、
    自分の評価値がかなり低くても、フレーム外に自分が勝つ方法があるから投了しない、という風に設定しているのだと思っていました。

    • > まだまだ人間の方が、正解に近い近似解(良いフレーム)を得られているのではないでしょうか?

      そのへんは問題ドメインによるのでは…。ナップサック問題とか、コンピュータは人間より遥かに少ない計算資源で解きますし。もちろん、現実世界の問題だと、人間のほうが優れていることが多いですが。

      将棋エンジンの投了設定は、自分の詰み(自分が詰まされる手順)を見つけるとマイナス無限大のような値になるのですが、相手がその詰みを見つけているとは限らないので(AWAKEが電王トーナメントで見せた63手詰めなんかもそうです)、自分の詰みを見つけたタイミングで投了するのはなんか違うかなと。

  3. 人間の「すごい」ところ&限界は、「すごい」ことができるんだけど、どうやってその機能を実装したのか自分で説明できない点じゃないでしょうかね。自転車に乗れるけど、どうやったら自転車に乗れるようになるのか説明できない。日本語を話せるけど、どうやったら日本語を話せるようになるのか説明できない。言い換えると、吐き出される低水準のコードが不透明なメタプログラミング言語を持っている。自分自身が自分自身のアルゴリズムへのアクセス権がない。それが強さでもあり限界でもあるような。けれど、コンピュータもやがてはそういうこともできるようになり、さらにそれを超えていくのかもしれませんね…。棋譜をたくさん読ませると勝手に学習して…というのも、そういうことでは? プログラムは「あなたはどうやって将棋が上達したのですか」という問いに対して、原理的には1ステップずつ再現可能な説明ができる。それ自体、既に人間よりすごいかも!

  4. 小林秀雄のエントリーでも書きましたが、やはり「人間の納得」が問題ですよね。

    人間というのは、天才やねうらおなどの生き物と違って、「安心感」を求める生き物です。

     これは政治家や政党に対する人々の反応をみてればわかることで、口々に「不安だー」「安心をくれー」って騒いでますよ。(んなモンいくら探しても現実にはあるわけないのに。)実際に統計的に安心かどうかなんて事は全く重要なことではない。そもそも統計が取れるような情報に、クリティカルに重要な情報はないわけで。

     節点が無限に爆発する問題も、結局は「安心」と「納得」の問題に帰結されると思います。

     今日も、昨日と同じように、解決不可能な問題が沢山起きてますから、そのことに対して人間の心情的APIを超人的な技巧で叩きまくって、「安心」と「納得」を力づくで提供している各業界の従業員が沢山います。

     天才は「安心」よりも「安全」に多くの思考を割きますが、多くの人は天才ではないので、「安全」には白い目を向けますが、「安心」を提供する人間にはすぐに反応します。安心は神話であり、実際には安全でもなんでもないのですが。
     天才などが、お前らが反応してるのは「安心」であってちっとも「安全」じゃないじゃん。「安心」って意味あんの?って言うと、ほうぼうから炎上の炎がまき上がります。不安に耐えられないのです。

     人々にとっては安心神話と、安全でなかった時に食ってかかれるクレームの対象物があることが重要であり、人工知能も「安心の確保」という目的に沿って使われる限り、検索の結果が深かろうが、正解率が高かかろうが、それは二次的な問題であって、一次的な課題にはならないわけです。
     36手先で敗北することが確実な人工知能であっても、人間がそれを何らかの理由で信頼刷る限り、問題なく実社会で使われ続けますし、「次の手で負けちゃうかもしれませんねえ〜、王取られちゃうかもしれませんねぇ〜、俺の責任じゃないけどね〜」とか言いながら使用者の不安を煽るような人工知能はあんまり採用されないわけです。
     まあ実際には訴訟対策で、何でも一度は不安煽っておくのが基本ですけどね。

    天才じゃない人にとってはね。

  5. というか、騒がれている人工知能という言葉が、閉じた条件だから実現できているものなのに、何でもでき
    る万能人工知能とごっちゃになって使われてるの
    がそもそもの間違いという気が・・・。

    また、フレーム問題は、万能人工知能が、持っている
    全知識の中から、今しようとしていることと関係ある
    知識と、関係ない知識を、いちいち知識のすべてを
    確認していてはとてもじゃないが、いつまでたっても
    終わらないが、その知識探索の打ち切りをどうする
    かというのが難しいという話なので、

    将棋などは、3手先まで読んだら終わりという条件
    を最初からつければ、すぐに終わりますが、
    あくまで何手先まで読むだけの閉じた条件なので、
    万能人工知能ではないです。

    人間は、将棋を指しているときも、腕を組んだり、
    お茶を飲んだり、時間を気にしたり、途中で電話が
    鳴ったら電話に出るとか、

    さまざまな行動をとりますが、万能人工知能にそれ
    をやらそうとすると、

    それぞれの知識をあらかじめ入れておく必要がある
    が、それ以外の知識についてはまた入れる必要が
    あり、

    将棋を指すだけではなく、なんでもできる万能人工
    知能になると、行動に対しての膨大な知識が必要
    になるが、それらの大量の知識から、今必要な
    情報を、どう抜き出せばいいのかがわからないと
    いう話になります。

    知識の中から、必要なものだけを抜き出せばいいと
    いうのは、結局のところ、必要の無い知識はどれか
    確認するということになってしまい、知識の全探索を
    何度も繰り返すことになり、

    それぞれの行動ごとに知識の全探索を行うため、
    事実上無限に知識を探索し続ける可能性もあります。

  6. 古い記事に対するコメントですみません。

    時々フレーム問題を少し間違って理解されている人がいますが、日本語版Wikipediaの記述が不正確またはあいまいなせいなのかもしれません。

    まずフレーム問題は、オセロや将棋や囲碁などのアクションとアクションが状態に及ぼす影響が明示的な状況「以外」の、現実環境の問題を扱う時の話です。つまり「将棋では・・」ということを議論すること自体が無意味です。

    英語版のWikipediaやStanford Encyclopedia of PhilosophyのFrame Problemの項を読まれるといいと思います。単に組み合わせの爆発をどうするかという話ではないことが分かると思います。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です