学生の研究成果
星魁人君（山村研究室・2020年3月修士課程修了）が論文「 Automata with One-way Jumping Mode」を発表しました
2020年2月に開催された研究集会「代数系、論理、言語と計算機科学の周辺Ⅱ」において講演した内容をまとめたもので、星君のこれまでの研究をまとめた内容です。
Automata with One-way Jumping Mode
Kaito Hoshi, Akihiro Yamamura, Szilard Zsolt Fazekas
数理解析研究所講究録 2188巻 (2021) pp. 125-130
https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/2188-19.pdf
星魁人君（山村研究室・2020年3月修士課程修了）が関わった研究論文が
Natural Computing に掲載されました
国際研究集会「The 25th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2019) 」において発表した内容をさらに発展させてジャンピングモードがオートマトンに与える能力について解析しました。
The effect of jumping modes on various automata models
Fazekas S.Z., Hoshi K., Yamamura A.
Natural Computing (2021)
https://link.springer.com/article/10.1007/s11047-021-09844-4
星魁人君（山村研究室・2020年3月修士課程修了）が関わった研究論文が
Theoretical Computer Science に掲載されました
国際研究集会「The Fourteenth International Frontiers of Algorithmics Workshop (FAW 2020)」において発表した内容をさらに発展させてジャンピングモードを持つ２方向オートマトンの計算能力について解析しました。
Two-way deterministic automata with jumping mode
Fazekas S.Z., Hoshi K., Yamamura A.
Theoretical Computer Science 864 92 – 102 (2021)
https://www.sciencedirect.com/science/article/pii/S0304397521001079
国際研究集会「The Fourteenth International Frontiers of Algorithmics Workshop (FAW 2020)」
国際研究集会「The Fourteenth International Frontiers of Algorithmics Workshop (FAW 2020)」（10/19-21, Haikou Hainan）において、星魁人君（山村研究室・2020年3月修士課程修了）が貢献した研究の発表を行いました。
「Two-way jumping automata 」というタイトルで２方向にテープヘッドがジャンプを許して動くオートマトンの言語受理能力とそのクラスの性質について国際研究集会 FAW2020（コロナウイルス感染症の影響でオンライン研究集会として開催）で研究発表を行いました。アルゴリズムに関する研究者が集まりインターネットを通して活発に討議を行いました。
修士課程を修了した星君は、オートマトンと形式言語理論に関する研究を実施し今回の研究発表に貢献しました。
湯本純君（理論物理学研究室三角グループ）の論文がPhysical Review Dに掲載されました
湯本純君と指導教員三角樹弘の共著論文「Varieties and properties of central-branch Wilson fermions」がアメリカ物理学会発行の学術誌Physical Review D Vol.102, No.03, 034516に掲載されました．
https://journals.aps.org/prd/abstract/10.1103/PhysRevD.102.034516
この論文では，場の量子論の数学的定義を与えるとともに数値的解析法を提供する「格子場の理論」について研究を行い，Central-branch法と呼ばれる新しい定式化の特性と数値計算への有効性を明らかにしました．
Physical Review Dは素粒子論・高エネルギー物理分野で最も権威ある学術誌の一つです．
湯本純君は関係する格子場の理論の研究成果について日本物理学会でも以下の講演を行っています．
日本物理学会第75回年次大会（2020）講演番号：17pH31-12
国際研究集会「The 15th International Computer Science Symposium in Russia (CSR 2020)」
国際研究集会「The 15th International Computer Science Symposium in Russia (CSR 2020)」（6/29-7/3, Ural Federal University, Ekaterinburg, Russia）において、加瀬力君（山村研究室・博士後期課程１年）が貢献した研究の発表を行いました。
「Groupoid Action and Rearrangement Problem of Bicolor Arrays by Prefix Reversals」というタイトルで亜群（Groupoid）と呼ばれる代数系が自然現象の偏作用や偏対称性を表現することに適していることを示す実例に関して、6月末に始まった国際研究集会CSR 2020（コロナウイルス感染症の影響でオンライン研究集会として開催）で研究発表を行いました。代数学、離散数学、コンピュータサイエンスを結びつける研究としてインターネットを通して活発に討議を行いました。
博士後期課程1年の加瀬君は、加瀬君は博士後期課程で代数学、離散数学、コンピュータサイエンスに関する研究を進めており、今回の研究では再配置可能性を分類することに貢献しました。
研究成果は以下の論文に掲載されました。
Groupoid Action and Rearrangement Problem of Bicolor Arrays by Prefix Reversal,
Akihiro Yamamura, Riki Kase, Tanya Jajcayova,
Computer Science – Theory and Applications,
Lecture Notes in Computer Science,
Springer-Verlag Vol. 12159 pp. 419-431 (2020)
RIMSの参加報告
2020年2月17-19に、京都大学数理解析研究所にて研究集会「代数系、論理、言語と計算機科学の周辺II」が開催されました。
「Automata with One-way Jumping Modes」というタイトルで、山村-Fazekas-新屋研究室の星魁人君(M2)が30分間の発表を行いました。
感想:
文字列を非順序に読み取るOne-way jumping finite automataの読み方を一般のオートマトンに適用したモデルについて発表しました。自分の研究に興味を持ってくださった研究者がいたのが非常に嬉しかったです。
他の方の発表では、代数学・論理学・計算機科学だけで無く、暗号論や機械学習など多岐にわたる研究発表がありました。全てを理解することはできませんでしたが、研究の過程で学んだことに関するものもあったので参考になる部分もありました。
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
渡邊悠介君（山村研究室・2016年3月修士課程修了）と津谷航平君（山村研究室・2017年3月修士課程修了）が研究論文誌に発表しました
渡邊悠介君（山村研究室・2016年3月修士課程修了）と津谷航平君（山村研究室・2017年3月修士課程修了）は大学院において人工知能（AI）の一つである群知能（メタヒューリスティック）の研究を行い、研究論文誌に発表しました。高い評価を受けており多くの世界の研究者から参照されています。群知能は、自然界における生物の群れ（アリ、ハチ、ホタル、鳥、細菌など）のふるまいの原理を様々な最適化問題や自動運転などに活用する研究が進んでいます。
渡邊君はミツバチの群れの採餌行動をモデルとして構成されたABCアルゴリズムをNP完全問題として知られる「容量制約なし施設配置問題」に応用する研究を論文にまとめました。
Fitness Function in ABC Algorithm for Uncapacitated Facility Location Problem,
Yusuke Watanabe, Mayumi Takaya, Akihiro Yamamura,
ICT-EurAsia/CONFENIS 2015, LNCS 9357 (2015) 129 – 138
https://www.springerprofessional.de/en/fitness-function-in-abc-algorithm-for-uncapacitated-facility-loc/2541418
に発表しました。
津谷君はホタルの発光現象をもとにしたホタルのアルゴリズムを「容量制約なし施設配置問題」に応用する研究を論文にまとめました。
Application of the firefly algorithm to the uncapacitated facility location problem,
Kohei Tsuya, Mayumi Takaya, Akihiro Yamamura,
Journal of Intelligent & Fuzzy Systems 32 ( 4 ) (2017) 3201 – 3208
https://content.iospress.com/articles/journal-of-intelligent-and-fuzzy-systems/ifs169263
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
藤原美早紀さん（山村研究室・2012年3月卒業）が研究論文誌に発表しました
藤原美早紀さん（山村研究室・2012年3月卒業）はチェス盤において、クイーン（飛車と角を合わせたものに相当）やルーク（飛車に相当）を、お互い当たりにならないように配置する方法を計算機で発見するエイトクイーン問題を、立方体の表面に拡張する研究を実施し、その配置数を正確に求める研究を行い研究論文誌に発表しました。
配置数を求めるためには本質的に同じ配置を二重にカウントしないように、対称性を明確にしなければなりません。藤原さんの研究では、代数学の群論の概念である正８面体群の作用に関してCauchi-Frobeniusの定理を応用して計算機実験を行なって配置数を求めました。
藤原さんの研究は高く評価されていて「2012年情報処理学会推奨卒業論文」と「情報処理学会 第74回全国大会 学生奨励賞」を受賞しています。
立方体上のn-クイーン問題およびn-ルーク問題
藤原美早紀、山村明弘
情報処理学会論文誌 53 ( 6 ) (2012) 1592 – 1601
https://ipsj.ixsq.nii.ac.jp/ej/?action=repository_uri&item_id=82600&file_id=1&file_no=1
