コンピュータゲームプレイヤは人工知能の分野においてルールの決まった世界におけるアルゴリズム検証の場として長年にわたり研究されてきた.この長年の研究において,コンピュータゲームプレイヤを強くするという研究はその目的の明確さから広く行われてきた.このため多くのゲームにおいて強いプレイヤが作成されている.このような強いプレイヤの作成には一般化された効率的な探索手法とその対象とするゲーム特有の知識が必要とされる.この知識は評価関数や探索手法の効率化,知識データベースなど様々な場面において利用されるものである.

このようにゲーム特有の知識はコンピュータゲームプレイヤを強くするにあたり必要不可欠なものである.その知識の獲得には過去のゲームや探索結果などの過去の経験を入力データとして機械学習などの手法を用いて獲得する手法が広く研究されている.このような入力データは獲得対象となる知識を得るのに適した表現をしている必要がある.ここで問題となるのが,この知識を得るのに適した表現を実現する,その知識の含まれたデータやその知識そのものを上手く表現するための語彙の獲得である.この語彙としては現在は多くのコンピュータゲームプレイヤにおいては人手で選択したものが用いられている.この選択を行う際にはこの語彙にはその過不足や選択の難しさの問題があり,この語彙が不十分であると知識を得るのに必要な入力データそのものには含まれているであろう情報が欠落してしまう,もしくは重要な情報を抽出することが難しく知識が得られないという結果になる.またあるゲームで用いられた手法を別のゲームに適用したい場合にも語彙を前提とした手法であることが多く,その語彙の取得方法が不明瞭なため容易には適用できないという問題もあり,ゲーム研究全体の進展における大きな障害の1つとなっている.最後にゲームにおいて学習を行う際には少ないデータで良い結果が得られている例は少なく,大量の学習例・語彙を扱うことが一般的に行われている.これはゲームにおいては棋譜や自己対戦などから多くの学習例を獲得できるためである.しかし,一方で大量の学習例を用いた学習はそのコストが高く難しいため,多くの有用な機械学習手法の適用が困難になってしまっている.

本論文ではこのような対象ゲームや対象問題への語彙の不足・語彙の取得方法の欠如・大量例からの学習に関する問題に対処するために,ゲームの知識を表現できる適切な語彙を棋譜データから獲得する手法について提案する.本手法により語彙の取得方法を提案した上で語彙の不足を解消することができると共に適切な語彙に縮約することで大量の学習例を問題に必要な情報のみであらわされた縮約された学習例に変換することが可能となる.提案手法の前提として,一般に語彙を無から取得することは不可能であるので,獲得する語彙を表現する対象ゲームについての基本的な語彙は与えられているものとする.この語彙は対象ゲームのルールなどから獲得可能なものである.この既存の語彙で表現された棋譜データをもとにその共起する語彙を組み合わせることで不足している語彙の獲得を行う.この棋譜データにおける共起として主なものには指し手列に代表される時系列的な共起関係と同局面に現れる特徴に代表される空間的な共起関係があげられる.本論文ではこの棋譜データからの語彙の獲得手法として,この2つの共起関係それぞれついて提案し,評価を行った.1つは指し手列に起こる共起関係について注目し語彙を時系列的に組み合わせて新たな語彙を獲得するという手法を,指し手列の解析に基づく将棋における指し手の分類精密化手法において提案する.もう1つは局面に同時に現れる語彙から新たな語彙を発見するという手法を,コンピュータゲームプレイヤにおける評価要素の自動生成において提案する.

指し手列の解析に基づく将棋における指し手の分類精密化ではコンピュータ将棋プレイヤ「激指」において利用されている指し手をその性質ごとに分けたカテゴリを既存の語彙として指し手列において連続して起こる指し手列を基に指し手のカテゴリを拡張する.実現確率打ち切り探索とは深さの代わりに探索するルート局面からのその局面へ至る確率 (実現確率) を閾値として探索を行う手法である.実現確率はあるカテゴリの手がその局面で選択される遷移確率を用いて計算される.カテゴリは指し手の性質に基づいて分けたものであり,その遷移確率は棋譜データから計算している.このカテゴリは局面と指し手から決定される.他の多くのゲームと同様に将棋においても重要な指し手列が存在していると言われている.この重要な指し手列には手筋などと呼ばれるように連続した指し手において特に特徴的なものが存在し,プレイヤに取り入れられている.実現確率を計算するカテゴリにもいくつかの決まった手筋は人手で入力されているが,その統一的な扱いや定式化はほとんどなされていない.このようなことから多くの棋譜を基に指し手の履歴としてカテゴリの履歴を抽出し,それをもとにこれまでの実現確率探索におけるカテゴリの遷移確率を指し手の履歴情報を考慮したカテゴリの遷移確率として拡張する.評価としてプロやインターネット将棋サーバの強いプレイヤの対局結果の棋譜47,321局から抽出したこの遷移確率を激指に実装し,1手5秒・220手で引き分けのルールで,この拡張を行った遷移確率を用いたコンピュータ将棋プレイヤとこの拡張を行わず従来どおりカテゴリの遷移確率を用いたプレイヤで150試合対戦を行った.また次の一手問題集への解答についても評価を行った.結果としては83勝67敗と元のプレイヤに勝ち越すことができた.またこの拡張を行ったプレイヤは元のプレイヤよりも次の一手問題集においてほぼ一手深く読んだプレイヤと同等数の問題を正解することができた.

コンピュータゲームプレイヤにおける評価要素の自動生成では既存の語彙として局面を区別して表現できる基本的な語彙を既存の語彙として棋譜に現れる局面に同時に現れる語彙を抽出し,選択することで局面を評価する評価関数における評価要素を作成する.評価関数はコンピュータゲームプレイヤにおいて探索結果に直接影響するコンピュータゲームプレイヤにおいて対象ゲームの知識を表現する主要部分である.このような評価関数における評価要素はこれまで多くのゲーム,特に将棋・囲碁などの比較的複雑なゲームにおいては人手で選択するのが一般的である.この人手での選択には対象とするゲームに関する深い知識が必要であり,そのゲームについて知らなければ作ることすらできない上に,知っていたとしてもコンピュータゲームプレイヤ作成者に大きな負担のかかる部分である.本手法では多くのゲームに応用可能な対局の勝ち・負けや詰み問題の詰み・不詰などの2クラスの分類問題を対象として既存の語彙のうち共起したものを組み合わせたのち選択することで評価要素を作成する.既存の語彙は2値であらわしたものを用い,局面に共起したものを論理積で表現し,そのうち頻度と条件付き相互情報量を用いて選択したものを評価要素とする.この生成された評価要素にこれまでに提案されている手法を用いて重みづけを行うことで評価関数の作成が可能である.また,ゲームでは既存の語彙が多い場合や学習対象とする棋譜が多い場合が多く,既存の多くの機械学習における特徴生成手法の適用が困難であった.本手法では問題を分割して処理する方法を同時に提案しており,このような多くの手法が適用困難な問題に対しても適用可能である上に並列化によって高速に処理を行うことも可能となっている.評価としては200,000局分のOthelloの局面を用い,Othelloの位置と色の192個の既存の語彙から評価要素の作成を行った.これにより分割処理によって大きな問題を扱うことができるとともに並列化により高速に実行できることを確認できた.また,生成した評価要素を用いたNaive Bayesian分類器は他の分類器による単純な特徴を用いた分類よりも良い精度で分類できることを示し,有用な評価要素が得られていることを確認した.

本論文ではこのような既存の語彙を共起関係に基づいて拡張する2つの手法の提案とその評価を通して,コンピュータゲームプレイヤにおいて棋譜の中で同時に起こる共起関係を基に既存の語彙を拡張することで新たな語彙の獲得が可能となることを示した.またその語彙を用いることで既存の語彙のみを利用した知識よりも有用な知識が得られることを示した.この拡張はこれまで多く人手でなされてきたことの代替となるものであり人手での抽出の負担を軽減することができ,また人手の偏った知識に依らず一般的な指標をお用いて拡張することができる.また特定のゲームに依存しない方法で語彙の獲得ができるため,多くのプレイヤに適用できる.さらにそれと共に大規模データについても語彙を獲得できる手法を提案することでこれまで対象とすることが難しかったゲームについても適用できる.

対象ゲーム・対象問題に適した語彙なしには対象問題に対する知識を表現することは難しい.このため対象ゲームへの語彙の獲得なしにはコンピュータゲームプレイヤの研究における強いコンピュータゲームプレイヤの一般的な手法での作成という課題の解決はできないと考えられる.本論文ではそのような課題の解決策の1つとして,既存の語彙を拡張することで問題対象の知識を記述する語彙をゲームの知識に依らない方法で獲得する手法を提案し,探索の効率化・評価関数について有用な語彙を獲得できることを示した.

本論文は「ゲーム知識を表現する語彙の棋譜データからの自動獲得」と題し、機械学習によって獲得するゲーム知識の表現に用いる基本要素(語彙)を、人間のゲーム知識に基づく人手により構成するのではなく、ゲームの表層的な表現と棋譜データから自動的に獲得する手法について述べたものであり、六章からなる。

第一章は導入であり、まずコンピュータゲームプレイヤと、そのためのゲーム知識の自動獲得について概説し、ゲーム知識の表現に用いる基本要素である語彙を人手により構成する通例の方法が持つさまざまな問題点を指摘している。次いで、これの問題の解決のために有効である、人間の知識に依存せず自動的に語彙を獲得する手法についての既存研究を概観し、本論文に述べる研究の目的と提案する手法の概略およびその利点を述べている。

第二章は「コンピュータゲームプレイヤにおける知識獲得」と題し、関連する既存研究を広く俯瞰している。まず、コンピュータゲームプレイヤに一般的に用いられる木探索とその効率化の技術と、静的評価関数などへのゲーム知識の利用法について概観している。次いで、従来ゲームプレイヤの研究の中で提案されてきた知識獲得の諸手法について概説している。

第三章「機械学習における特徴生成手法」では、機械学習に際して対象とする問題を記述するための特徴を自動的に獲得するための特徴生成手法について概観している。特徴生成の諸手法を特徴抽出,特徴選択,特徴構築に大別し、各々について従来提案されている数多くの手法のうちの代表的なものを、その前提、モデル、コストなどについて述べ、それぞれの長所短所を明らかにしている。

第四章「指し手列の解析に基づく将棋における指し手の分類精密化」は、本論文の主たる新たな提案のひとつである、語彙を時系列的に組合せて新たな語彙を獲得する手法について述べている。具体的には、棋譜データベース中の将棋の指し手列を解析し、それに基づき指し手の分類を精密化するものである。この情報をコンピュータ将棋プレイヤの探索打切り制御に用いることによって、単一の指し手による場合よりも適切な制御が可能になることを、実験を通じて確認、語彙を時系列的に組合せて新たな語彙を獲得する手法の有効性を示している。

第五章「コンピュータゲームプレイヤにおける評価要素の自動生成」は、本論文のいまひとつの主たる提案について述べている。第四章に述べた時系列での組合せと異なり、同時に現れる語彙を組合せて新たな語彙を構成することによってコンピュータゲームプレイヤの評価要素を自動生成する手法を提案し、その評価結果を示している。ゲームのルールから直接導かれる基本語彙は少数でも、その組合せは非常に多数になるが、提案手法は大規模な棋譜データベースに頻出し勝敗との関連性が高いものを自動的に抽出するもので、単純な手法では膨大になる計算量を低減する諸方式についても併せて述べている。この手法で獲得した語彙を用いたオセロゲームの局面に対する勝敗予測器は、基本語彙を直接的に用いるものに勝ることを示し、基本評価要素の組合せを自動生成する手法が有効であることを示している。

最終章である第六章は論文に記した研究をまとめ、ゲーム研究における位置づけを述べるとともに、今後の研究の展望を与えている。

以上これを要するに、本論文は機械学習枠組の根本となる表現語彙をデータから自動的に獲得する手法を、コンピュータゲームプレイヤの評価関数を対象として提案し、実験を通じてその有効性を実証しており、その成果はゲームに限らず自動知識獲得に広く適用できるものであり、情報学の基盤に貢献するところが少なくない。

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