本研究の最終的な目標は,エキスパートのモデルを構築することである.すなわち,エキスパートと同様の仕組みで作動し,しかもエキスパート並のパフォーマンスを示すシステムを構築することである.現在のところ,このようなシステムは構築されていない.

　本研究では,ゲームを対象領域とした.ゲームは,物理的な制約がない,形式的に定義しやすい,などの理由で,モデル化を行ないやすい領域だからである.実際,人工知能や認知科学などの分野では,永年,研究対象としてゲームが広く用いられてきた.その中でもチェスは最もよく用いられてきた.1997年5月にコンピュータチェスシステムが人間のチャンピオンに勝利したが,これはコンピュータの驚異的な処理速度を利用した力任せ探索を行なっており,人間とは異なる方法をとっている.本研究では,チェスの次の目標として人工知能や認知科学で注目されている囲碁を取り上げる.チェスに比べて桁違いに探索空間の広い囲碁にはチェスのような力任せ探索は使えず,強い囲碁システムを構築するには人間を真似る必要があると考えられている.そのため,エキスパートのモデル化という本研究のアプローチは,人工知能,認知科学の両面に貢献するアプローチであると考えられる.

　本研究では知識に注目し,人間のエキスパートが持つような知識を大量に獲得することを目標とした.一般にエキスパートからの知識抽出が困難であることは,知識獲得のボトルネックとしてよく知られている.そのため,従来のシステムでは内省によって知識を入力していたが,小数の知識しか入力できなかった.そこで,機械学習の手法を用いて知識を自動獲得することが考えられるが,従来の手法では,定型的な知識しか獲得できず,人間のエキスパートが持つような多様な形の知識は獲得できなかった.そこで,本研究では,新しいアルゴリズムを提案し,エキスパートが持つような多様な形の囲碁知識を大量に自動獲得するシステムの構築を目指した.

　ここで,囲碁の知識を2つの基準で分類する.まず,妥当性に基づいて囲碁の知識を分類すると,strictな知識とheuristicな知識の二つに分類できる.strictな知識とは,その知識の妥当性を簡単に証明できるような知識であり,常に正しいような知識である.heuristicな知識とは,妥当性は簡単には証明できないが経験的に正しいと思われている知識で,状況によって正しくないこともありうるような知識である.次に,形態に基づいて囲碁の知識を分類すると,パタン・手順・格言の3つに分類できる.パタンとは,条件部が盤面配置であり、実行部が次の1手を指し示すようなルールである.手順は2手以上の着手を示すようなルールであり,定石や布石などがこれに当たる.格言とは,条件部,実行部に盤面状況を抽象化した用語を用いているルールである.

　本研究ではパタンと手順の獲得を行なう.これは,以下の2つの操作を意味する.まず,与えられた一連の手順の中から学習すべき適切な着手を同定することである.そして,与えられた盤面全体の中から適切な盤面上での部分を抽出することである.以下では,この2つの操作がどのように行なわれたのかを説明する.

　まず,strictな知識を獲得するモデルを提案する.人間の囲碁の初級者がパタンを獲得する様子を観察したところ,演繹的な方法を用いて,なぜ相手の手段が成功したのかを検討していることが分かった.この過程は説明に基づく学習(EBL)と呼ばれるアルゴリズムと類似していたため,このアルゴリズムを応用した.EBLでは,一例を与えられ,「説明」と呼ばれる段階で,その例が目標概念になぜ合致しているのかを説明する説明木を構成する.ここでは,ある囲碁の手段が成功した一例を,着手が成功した場面から一手ずつ遡って,その着手の意味を自分の持っている知識で説明しようと試みる.その説明できなかった着手が,自分には欠けているが良い着手であることが分かるので,それが学習すべき着手であると同定できる.次に,その着手にとって必要な要素(石や盤端)をその着手が行なわれた盤面全体から抽出する.EBLは,上記の説明木を構成する操作の際,不必要な要素を排除するという作用があるが,ここではこれを利用し,なぜ与えられた例ではその着手が成功したのかを説明する説明木を一手ごとに段階的に構成することで,盤面の中から必要な要素を抽出し,パタンを獲得した.ここでは,石を取る,という問題を例にとり,このモデルと初心者の学習結果を比較したところ,ある程度の類似性が見られた.

　囲碁のような対戦型問題では,一つの正例を与えられただけでは完全な知識を得ることは出来ない.人間の中級者が,現在持っている知識が成り立たない例(負例)を与えられた際に,その例が成り立たなかった原因を演繹的に解明し,その知識を修正することが観察された.この過程を上述のモデルを拡張することでモデル化し,計算機に実装し,人間の中級者と類似した結果が得られた.EBLでは普通,正例のみを利用し負例は利用しないが,本システムでは負例をもEBLの枠組に採り入れることができることを示した.また,本システムは,囲碁のみならず対戦型問題において,得られたパタンを修正する初のシステムであり,人間の学習過程とのある程度の類似性が見られた初めての対戦型問題のパタン獲得・修正システムである.

　上述のシステムは,小数の例からでもある程度正確な知識が得られるという利点があったが,ある手段が成功したということが判定でき,さらにその手段が成功した理由を説明できなければならない,という制約がある.囲碁では,直接の目標が想定しにくい,探索空間が広いなどの理由で,ある手段の成功した理由を説明できることが非常にまれで,エキスパートでさえ,明確な説明をできない場合が少なくない.そこで,次に,このように明確には説明できないheuristicな知識を獲得するシステムについて考える.従来のheuristicな知識を獲得する研究としては,固定の領域をあらかじめ設定し,その領域に当てはまるパタンを単に蓄えるというものがある.しかし,実際に人間の持っている知識は固定の形をしているわけではない.本研究では,頻度を基準として,人間のプロ同士の対戦譜(棋譜)から,人間の持つような様々な形のパタンを獲得した.つまり,頻度を基準に,着手と盤面の要素を抽出した.ここでは,遺伝的アルゴリズムのような進化的な方法を用いた.囲碁は盤面が広く探索空間が非常に大きいため,全探索では計算量の爆発を起こすが,進化的な手法は少ない計算量で近似解を求めやすいことが知られているからである.しかし,従来の進化的方法は,最適化を目的としたものが多かったため,小数の解に収束しやすく,また,ほぼ毎回使われる知識しか得られなかった.また,交叉といったオペレータを用いる都合上,知識表現は固定されているものが多かった.

　本研究では,大量の人間の持つような様々な形のパタンを得ることを目的とする.そのため,以下のような新たな進化的アルゴリズムを提案した.まず,頻度を基準とするために,各個体に活性値を導入した.さらに,柔軟な知識表現を許すために,交叉に代わる分裂(split)という新たなオペレータを導入した.このオペレータは,現在の自分のルールにランダムに選んだ条件を一つ加えることによって,徐々に複雑なルールを構築する.これを囲碁のプロの棋譜に適用した.まずは,9路盤(9x9)からの知識獲得を行ない,獲得された知識を人間のエキスパートに評価してもらったところ,多くのものが適切であると評価された.さらに,19路盤(19x19)からの知識獲得を行なったが,9路盤よりも適切な知識の割合が減少した.その理由は,9路盤よりも圧倒的に探索空間が広がったことであった.そこで,探索空間を狭める領域固有のバイアス,視野(vision)を導入した.導入以前は分裂の際,可能なすべての条件の中からランダムに条件を選択していたが,視野の導入後は,「着手点から見える範囲」だけを候補の対象とした.視野を導入した結果,分裂の際の候補となる条件の数は90から6.5と約14分の1になった.その結果,19路盤で得られる適切な知識の割合が大幅に増えた.さらに,分裂の際の候補として,「何手前の着手か」という条件を加えることによって,手順知識も獲得できた.手順知識は,人間にとっては重要な知識であるにも関わらず,現在のコンピュータには欠けていたものである.

　獲得された個々の知識は適切と判断されたが,全体として十分な知識が獲得されているかどうかは評価できていない.これを行なうために,獲得された知識で詰碁を解くことを行なった.詰碁の知識はstrictな知識ではあるが,詰碁は正解が決まりパフォーマンスの評価が行ないやすいため,対象として選択した.詰碁は,短手数の棋譜とみなせるので,棋譜と同様に,詰碁の問題とその正解手順から詰碁における知識を獲得した.この段階ではすべての知識が対等であり,ある盤面に対して競合する知識が複数出てきてしまう.そこで,この獲得された知識に自動的に優先度を割り当てるアルゴリズムを考案し,各知識に優先度を割り当てた.この優先度を用いて詰碁を解かせたところ,人間の初段と同程度のパフォーマンスを示した.これにより,本システムで十分な知識が得られていることが示唆された.

　本システムで用いている知識表現は,盤面の石の配置という単純なもので,人間の知識と比較した場合,2級程度のものである.初段以上の被験者は,石の配置に加え,盤面状況を抽象化した言語的な情報も持っていることが報告されている.本システムの知識表現はプロダクションルールになっており,言語的な情報をも取り込める.人間が持っている言語的な情報を定義することによって,ルールに言語的な情報を取り込むことができ,より人間に近い知識が獲得できると期待される.また,システムで得られた知識を人間に示すことによって,人間が持っている知識を引き出すprobeになることも期待され,認知科学への貢献も期待される.

　学術修士 小島 琢矢 提出の論文は"Automatic Acquisition of Go Knowledge from Game Records:Deductive and Evolutionary Approaches"(棋譜からの囲碁知識の自動獲得:演繹的アプローチと進化的アプローチ)と題し,8章からなっている。

　人工知能や認知科学の分野では,研究対象としてゲームが広く取り上げられてきた。その中でもチェスは1950年代初頭から最も広く研究されてきたが,1997年5月にコンピュータチェスシステムが人間のチャンピオンに勝利し,人工知能研究のゲーム分野における次なる目標は囲碁システムの開発に移った。しかし,チェスに比べて桁違いに探索空間が広い囲碁においては,チェスの場合のような力任せ探索を利用することはできず,全く新しいアプローチが必要と考えられる。

　論文提出者は,囲碁システムの構築には,人間のエキスパートが持つような量的に膨大で質的に多様かつ柔軟な知識をコンピュータに持たせることが必要と考え,そのための具体的方法とアルゴリズムを提案している。一般にエキスパートからの知識抽出が困難であることは,知識獲得ボトルネックとしてよく知られている。そこでコンピュータが自ら学習することによって,多様で柔軟な囲碁知識を大量に自動獲得するシステムを構築し,その可能性と有効性を検討している。

　本論文の第1章は序論で,以上のような研究の背景や本研究の目的と意義を述べている。その上で,囲碁の知識は,比較的容易に妥当性を説明できるstrictな知識と,容易には説明できないが経験的に正しいと考えられているheuristicな知識とに分類できることを指摘し,その知識獲得にはそれぞれ異なるアプローチが必要であることを述べている。更に,形態に基づいて囲碁の知識をパタン・手順・格言の3つに分類し,本研究ではパタンと手順に関する知識獲得を目指すこととしている。

　第2章では本論に入る前の準備として囲碁の用語やルールを紹介している。

　第3章では,strictな知識を獲得するモデルを提案し,計算機に実装してその有効性を検証している。囲碁知識の獲得においては,与えられた一連の手順の中から学習すべき適切な着手を同定すること,および与えられた盤面全体の中から適切な盤面上の部分を抽出することが必要である。これを実現する方法として,機械学習の分野で「説明に基づく学習(Explanation Based Learning,以下EBL)」として知られるアルゴリズムを拡張して適用している。EBLでは,ある目標概念についての正例を与えられると,その例が目標概念に合致している理由を説明する説明木を構成する。ここでは,「石を取る」という問題を例にとり,ある手段が成功した例を,着手が成功した場面から一手ずつ遡って,それぞれの着手の意味を自分の持っている知識で説明しようと試みる。その際に説明できない着手が,自分の知識には欠けているが良い着手であることが分かるので,それが学習すべき着手であると同定できる。次に,その着手にとって必要な要素(石や盤端)をその着手が行われた盤面全体から抽出する。上記の説明木を構成する操作の際,不必要な要素は排除されるので,盤面の中から必要な要素だけを抽出し,パタン知識の獲得を実現している。

　ただし,囲碁のような対戦型問題では,正例だけから完全な知識を得ることはできない。現在持っている知識が成り立たない例(負例)を与えられた際に,その例が成り立たなかった原因を演繹的に解明し,その知識を修正する必要がある。本論文ではこの過程をも上述のモデルを拡張して実現し,知識の頑健化を図っている。EBLでは普通,正例のみを利用し負例は利用しないが,本システムは負例をもEBLの枠組に採り入れることができることを示したものである。

　第4章と第5章では,heuristicな知識の獲得方法について述べている。上述のシステムは,少数の例からでもある程度正確な知識が得られるという利点があるが,ある手段が成功したということが判定でき,さらにその手段が成功した理由が説明できなければならない,という制約がある。囲碁では,直接の目標が設定しにくい,探索空間が広いなどの理由で,ある手段が成功した理由を明確に説明できることはむしろ稀で,エキスパートでさえ明確な説明ができない場合も少なくない。そこで,著者は,このように明確には説明できないheuristicな知識を獲得する新しいモデルとアルゴリズムを提案し,知識獲得システムを構築して,その有用性を検証している。

　heuristicな知識の獲得では,人間が持つような大量かつ多様な形のパタン知識を得ることを目的とするので,人間のプロ棋士同士の多数の対戦譜(棋譜)を教師データとして,計算機に繰り返し学習を続けさせ,自ら知識(ルール)を創出させつつ,個々の知識の使用頻度を基準として,着手と盤面の要素を抽出し,有用な知識を蓄積していくという方法を採っている。このような方法の具体化のために,遺伝的アルゴリズムからヒントを得て,新しい進化的な方法を提案している。

　著者の提案する進化的アルゴリズムでは,個々の知識を生態系の個体になぞらえ,使用頻度を基準とするため,各個体に活性値を導入する。さらに,柔軟な知識表現を許すために,遺伝的アルゴリズムにおける交叉に代えて変異をともなう分裂(split)という新たなオペレータを導入している。このオペレータは,現在の自分のルールに盤面状況の中からランダムに選んだ条件を一つ加えることによって,徐々に複雑なルールを構築する。その際,盤面状況に関する探索空間を狭めるためのバイアスとして視野(vision)を導入して,着手点から見える範囲だけを候補の対象とすることにより計算の効率化を図っている。棋譜からの学習において,一手ごとに,教師データにマッチしない個体群の活性値は一定値ずつ減じられ,教師データにマッチする個体群のうち,より特化された個体群に配分される。そして活性値が一定値以下になった個体群は消滅し,逆にある閾値以上に達した個体群は分裂を繰り返して,より特化された知識を創出する。

　こうして獲得された大量の知識を複数のエキスパートの評価にかけたところ,全体の6〜8割の知識が,有用な知識であると判定された。さらに,分裂の際の付加条件の候補として「何手前の着手か」を加えることにより,手順知識も獲得された。手順知識は重要な知識であるにも拘らず,従来のコンピュータ囲碁システムには欠けていたものである。

　第6章では,前の第4,5章の方法で獲得される知識の,全体としての十分性を検証するため,獲得された知識で詰碁問題を解き,そのパフォーマンスを評価している。詰碁は短手数の棋譜とみなせるので,詰碁の問題とその正解手順から詰碁における知識を獲得する。この段階では全ての知識が対等であり,ある着手に対して競合する複数の知識が存在し得る。そこで,獲得された知識に自動的に優先度を割り当てるアルゴリズムを考案し,この優先度を用いて詰碁を解かせたところ,人間のアマチュア初段と同程度のパフォーマンスを示した。これにより,本システムでほぼ十分な知識が獲得されているものと想定される。

　第7章では,本論文の成果や今後の課題について多方面から検討している。また第8章は結論で本論文で得られた成果をまとめている。

　以上を要するに,論文提出者は,囲碁知識の自動獲得を目指して,strictな知識とheuristicな知識に,それぞれ演繹的アプローチと進化的アプローチを試み,いずれにおいても従来にない新しいモデルと斬新なアルゴリズムを提案するとともに,計算機上に知識獲得システムを実装して,実際に獲得された知識の有用性を実証したものであり,人工知能,認知科学,情報科学などの諸学問上貢献するところが大きい。

　よって本論文は博士(学術)の学位請求論文として合格と認められる。