学生の研究成果

Enhancement of Automata with Jumping Modes (ジャンピングモードによるオートマトンの強化)

 山村研究室の学生、星魁人君がメキシコのグアダラハラ大学にて開催された国際研究集会「The 25th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2019) 」において研究発表を行いました;Enhancement of Automata with Jumping Modes,
Szilard Zsolt Fazekas, Kaito Hoshi, Akihiro Yamamura,
AUTOMATA 2019, Lecture Notes in Computer Science,
Springer-Verlag Vol.11525 pp.62-76 (2019)

 オートマトンの研究は計算機科学基礎に分類され、離散数学の一つに当たります。オートマトンはコンピューターを数学的にモデル化したもので、入力文字列を順番に読んでいき有限状態を変化させます。入力文字列の組合せ論的性質を調べることが研究の大きな目的の一つとなっています。
 2012年に、有限オートマトンの入力文字列の読み方を従来のものから変化させたジャンピング有限オートマトンがA.Meduna and P.Zemek [1]により提案されました。
Meduna等は文字の読み方を変えることによって、一般の有限オートマトンと性能や能力が変化することを発見しました。
ジャンピング有限オートマトンの概念の提案以降、様々な研究者によってその拡張や研究がなされています。
 2016年には、千川原寛之氏(山村研究室・平成27年3月修士修了)がジャンピング有限オートマトンとは別の入力文字列の読み方を持った一方向ジャンピング有限オートマトンについて研究し、その結果を研究雑誌[2]において発表しました。
千川原氏は、一方向ジャンピング有限オートマトンとジャンピング有限オートマトンの性能や能力が異なることを示し、関連するポンピング補題や閉包性について解析しました。
 千川原氏等の研究成果を発展させ、星君はジャンピング有限オートマトンの研究を進め、一方向にテープヘッドが移動して入力文字列を読むジャンプモードを定義し、有限オートマトンとプッシュダウンオートマトンを含むオートマトン一般がジャンプモードの場合と従来のモードの場合で性能や能力にどのような変化が起こるのか研究しました。星君の研究は、有限オートマトンのみならずプッシュダウンオートマトンのようなさらに一般のコンピューターの数学的モデル化にジャンピングモードを拡張し、受理される語の数学的特徴を調べたことが特徴になっています。

関連文献
[1] A. Meduna and P. Zemek: Jumping finite automata, International Journal of Foundations of Computer Science, Vol.23, No.7, (2012) 1555-1578
[2] H.Chigahara, S.Z.Fazekas, and A.Yamamura: One-way jumping finite automata, International Journal of Foundations of Computer Science, Vol. 27, No. 3, (2016) 391–405

 

Knight-Amazons(平成27年度博士前期課程修了 加藤光くん)

 山村研究室の学生、加藤光くんが修士論文で取り組んだKnight-Amazonsの成果を以下のページで公開しています。

http://knightamazons.ie.akita-u.ac.jp

Knight-Amazonsは、The game of the Amazonsのルールに変更を加えたオリジナルゲームです。
Knight-Amazonsが人間にとって面白いゲームであるかを調査することを目的として、コンピュータプレイヤーとの対戦、オンライン対戦機能があります。ぜひ訪れてみてください。

以下は修士論文の序論になります。

 モンテカルロ法は現在与えられた状況から得られる平均利得が最も高くなるような手を選択するアルゴリズムであり,ゲーム AI 分野では 2000 年代以降特に囲碁 AI において利用され,高い成果を挙げる探索手法として注目されている.
一方 Amazon は二人零和確定完全情報ゲームに含まれる組合せゲームの一種であり,囲碁における地の多寡を競う要素と,チェスや将棋に見られる駒の移動の二つの要素を併せ持つ([1]を参照) . Amazon は着手可能手の総数が他のゲームに比べ非常に数が多く,将棋類のように駒別の価値という概念がないため囲碁等と同様,評価関数を作成することが難しいことが知られており[2],静的評価関数及びMini-Max 原理に基づいた従来的 AI 手法では最適着手を導き出すことが困難である.
通常の Amazon のルールでは 10 × 10 の盤に二人のプレイヤーがおのおの 4 つの駒を所定の位置に配置して対戦するが,これを一般化し n × n の盤に二人のプレイヤーがおのおの m 個の駒を任意の位置に配置して対戦するゲームを本論文では一般化 Amazon と定義する.
本論文では,モンテカルロ木探索のアルゴリズムである UCT を用いて,一般化 Amazon 及びその派生ゲームである一般化制限 Knight-Amazon における最適着手を求めるアルゴリズムの作成及び評価を行い,先手・後手の有利不利を検証する.

[1] J. P. Neto and J. N. Silva , Mathematical Games: Abstract Games , Dover Publications ,(2013)
[2] J.Kloetzer , Monte-Carlo Techniques: Applications to the Game of the Amazons ,博士論文,北陸先端科学技術大学院大学, (2010) http://hdl.handle.net/10119/8867