実験 2：実験結果と考察

実験結果を図5.4に示す．まず，FSS2012で優勝したアルゴリズムである遺伝ア ルゴリズムは，学習のみで行動している．Infinite Tuxにおいて，１つのステージ をクリアするためには，非常に多くの行動の組合せから選択する必要がある．そ のため，学習のみでそれらを取得しようとする場合，10000ステージ分のデータ 量でも十分ではない．そのため，スコア基準ではある程度の点数を得ることはで きたが，大きな壁が出現するようなステージではクリアするまでには至らなかっ た．対して，提案手法の学習は先程も述べたとおり，プランの学習であり，2000 ステージ分という少ないデータ量でも十分に学習ができた．結果として，遺伝ア ルゴリズムとは大きな差がついたことがわかる．

更に，A*アルゴリズムと提案手法を比較すると，クリア回数では約29.9%，ス コアでは約11.4%の性能向上が見られた．これから，提案手法は2009年度優勝ア ルゴリズムとくらべても有効であることがわかる．これは，A*アルゴリズム単体 で進むことができない状況においても，Q学習によりプランニングすることでそ の状況を突破することが可能となったためである．クリア回数とスコアで性能に 変化があった理由としては，A*アルゴリズム単体で進む場合，ステージ中に大き な壁が出現するまでは，提案手法と同じように進むことが可能であるため，クリ アできないステージでもある程度のスコアを得ることができたからである．

これらの結果から，プランナー数と学習に用いるデータ量を適切に調節するこ とができれば，制限された環境下において有効であることがわかる．

表 5.4: 提案手法と他手法の比較

クリアステージ数 コンペティションスコア

提案手法 330.2 1,735,076

A*アルゴリズム単体 254.2 1,512,285 遺伝アルゴリズム 0 291,335

第 6 章 まとめと今後の課題

本研究では，計算時間，得られるデータ量，計算リソースの三つの制限が課せ られている環境であるプラットホームゲームベンチマーク「Infinite Tux」を題材 とし，制限された環境下において自律的に効率よくプランニングできるアルゴリ ズムの開発を目指す．「Infinite Tux」はIEEEのコンペティションでも使用されて おり，特にA*アルゴリズムやルールベースシステムなどが好成績を残している．

しかし，A*アルゴリズムはエージェントの行動探索において優秀であるが，状況 によっては膨大な探索時間を必要とするため，制限された環境下においてはA*ア ルゴリズム単体でのプランニングでは難しい場合もある．また，ルールベースシ ステムは，ルール作成の負担やルールの環境特化などが問題となる．

このような制限された環境下において効率的にプランニングを行うために，本 研究では，エージェントが遭遇する状況に合わせ，その状況に特化された学習型プ ランナーを選択することで，プランニングを行う手法を提案した．各プランナー はそれぞれが担当する状況でのみプランニングを行うため，計算時間，得られる データ量，計算リソースが少ない環境下においても有効に働く．更に，学習型プ ランナーを使用するため，細かいルール作成などの手間も必要としない．具体的 には，行動はA*アルゴリズムで探索し，プランナーはA*アルゴリズムの目標節 点の位置をQ学習により学習し，変更することでプランニングを行う．

本手法の性能には，プランナーの数と各プランナー自身の性能の二つが関係す る．そこで，プランナーの数と，プランナーが学習に用いるデータ量を変化させた 時のプランニングの有効性について実験を通じて調査し，より効率よくプランニ ングできる条件について調査し，各プランナーがある程度のデータを持つことが 可能であれば，各プランナーが特定の状況に対して効果的にプランニングするこ とができ，結果全体的なプランニングができたと考えた．最後に，提案手法の有 効性を確かめるため，提案手法と，コンペティション優勝アルゴリズムであるA*

アルゴリズム，日本で開催された国内コンペティション優勝アルゴリズムである 遺伝的アルゴリズムを使用したプランニング手法との比較実験を行った結果，約

29.9%の性能向上が見られた．

本稿では，Q学習を使用するプランナーのみを使用している．本手法において は，Q学習以外にも様々なプランナーを適用することが可能であることが考えら れる．そこで，今後どのような状況にどのようなプランナーを割り当てればよい かについて検討する必要がある，更に，今回は状況認識をハードコーディングで 行っているため，今後は自律的な状況認識についても検討する．また，今回の手 法は題材としたInfinite Tuxでのみ実験を行った．本手法が様々な制限された環境 下において有効であるかどうかについて，Infinite Tux以外の制限された環境を利 用し調査する必要がある．

謝辞

本論文は，著者が三重大学にて行った研究をまとめたものである．本論文を進 めるにあたり，懇切丁寧なご指導と御督励を賜った三重大学の鶴岡信治教授，高 瀬治彦准教授，川中普晴助教，北英彦准教授，および立命館大学の高野敏明特任 教授に感謝いたします．また，日頃熱心に討論していただいた情報処理研究室の 皆様方に厚く御礼申し上げます．

最後に，本論文をまとめるにあたり，助言，討論，その他お世話になったすべ ての方々に感謝いたします．

参考文献

[1] 福田敏男 編著: インテリジェントシステム―適応・学習・進化システムと計 算機知能―，昭晃堂 (2000).

[2] 金子知適:最近のコンピュータ将棋の技術背景とGPS将棋，情報処理，Vol.50，

No.9，pp.878–886 (2009).

[3] 一丸貴則: WCSC21ツツカナ アピール文章，http://www.computer-shogi.

org/wcsc21/appeal/tsutsukana/WCSC21_tsutsukana_20110327.pdf， (2014/1/13アクセス).

[4] 山本一成:第 22 回世界コンピュータ将棋選手権 Ponanaza アピール文章，

http://www.computer-shogi.org/wcsc22/appeal/ponanza/appeal.pdf， (2014/1/13アクセス).

[5] D.A. Ferrucci, E.W. Brown, J. Chu-Carroll, J. Fan, D. Gondek, A. Kalyanpur, A. Lally, J.W. Murdock, E. Nyberg, J.M. Prager, N. Schlaefer, C.A. Welty:

Building Watson: An overview of the DeepQA project，AI Magazine，Vol.31，

pp.59–79 (2010).

[6] 金子知適，田中哲朗: GPS将棋とテキストプロトコルによる大規模将棋ソ フトウェアの組み立て，コンピュータソフトウェア，Vol.29，No.1，pp.75–81 (2012).

[7] Darla W.Jackson: Watson, Answer Me This: Will you Make Librarians Ob-solete or Can I Use Free and Open Source Software and Cloud Computing to Ensure a Bright Future?，LAW LIBRARY JOURNAL，Vol.103:3，pp.497–

505 (2011).

[8] Andr´e R. Brodtkorb, Trond R. Hagen, Christian Sehulz, Geir Hasle: GPU computing in discrete optimization. Part I: Introduction to the GPU, EURO

Journal on Transportation and Logistics， Vol. 2， Issue 1-2， pp.129–157 (2013).

[9] Christian Schulz, Gair Hasle, Andr´e R. Brodtkorb, Trond R. Hagen: GPU computing in discrete optimization. Part II: Survey focused on routing prob-lems，EURO Journal on Transportation and Logistics， Vol. 2， Issue 1-2，

pp.159–186 (2013).

[10] Yuta Tsuchida, Michifumi Yoshioka: Acceleration of Neural Network Learn-ing by GPGPU, Electronics and Communications in Japan， Vol. 96， Issue 8， pp.59–66 (2013).

[11] 阪田史郎， 高田広章: 組込みシステム，オーム社 (2006).

[12] Platformer AI Competition， http://platformersai.com/ (2014/2/5アク セス).

[13] Noor Shaker Personal Website， http://noorshaker.com/index.html (2014/2/5アクセス).

[14] 鴨井良介，佐藤圭佑，酒井英明，竹内信一: 迷路探索法に基づく6自由度アー ム型ロボットの動作計画，日本ロボット学会誌，Vol.28，No. 8，pp. 915–922 (2010).

[15] 狩野均: 遺伝的アルゴリズムを用いたカーナビのための経路案内方式，情報 処理学会研究報告. ITS, [高度交通システム]，Vol. 2002, No. 21, pp. 51–58 (2002).

[16] Stuart Russell, Peter Norvig著，古川康一 監訳: エージェントアプローチ 人 工知能，共立出版 (1997).

[17] Richard S. Sutton, Andrew G. Barto著，三上貞芳，皆川雅章 訳：強化学習，

森北出版 (2000).

[18] 小林一郎: Computer Science Library-13 人工知能の基礎，サイエンス社 (2008).

[19] Julian Togelius, Sergey Karakovskiy, Jan Koutn´ık, J¨urgen Schmidhuber: Su-per Mario Evolution，Proceedings of the IEEE Symposium on Computational Intelligence and Games， pp.156–161 (2009).

[20] Sergey Karakovskiy Julian Togelius: The Mario AI Benchmark and Compe-titions，IEEE Transactions on Computational Intelligence and AI in Games (TCIAG)， Vol. 4，Issue 1，pp. 55-67 (2012).

[21] Julian Togelius, Sergey Karakovskiy, Robin Baumgarten: The 2009 Mario AI Competition， Proceedings of the 2010 IEEE Congress on Evolutionary Computation(CEC)， pp. 1–8 (2010).

[22] Slawomir Bojarski, Clare Bates Congdon: REALM: A Rule-Based Evolu-tionary Computation Agent that Learns to Play Mario， the Proceedings of the 2010 IEEE Symposium on Computational Intelligence and Games(CIG)，

pp.83–90 (2010).

[23] 半田久志: Mario AI における Deep Boltzmann Machine 適用の検討， シス テム・情報部門学術講演会2013論文集， pp. 633–636 (2013).

[24] Ruslan Salakhutdinov, Geoffrey Hinton: Deep Boltzmann Machines， Inter-national Conference on Artificial Intelligence and Statistics， pp. 448–455 (2009).

[25] Sergey Karakovskiy, Julian Togelius: Mario AI Competition @ CIG 2009，

http://julian.togelius.com/mariocompetition2009/

CIG2009Competition.pdf (2014/2/5 参照).

[26] 高野敏明: 同一エージェント間での転移学習を用いた強化学習の高速化に関 する研究，三重大学大学院工学研究科博士論文 (2012).