東京工科大学 メディア学部 ブログ

メディア学部の渡辺です。こんにちは。

11月6日から8日まで、NICOGRAPH2021 という学会が開催されました。私の研究室からは、1件のフルペーパー口頭発表と3件のポスター発表として採録されました。2回に渡ってそれらの研究を紹介したいと思います。

まず、大学院修士1年の吉田涼真君の研究を紹介します。題目は「スタート地点とゴール地点が変化した際の経路探索手法に関する研究」というもので、フルペーパーとして採録されました。道路地図や迷路のような「マップ」内に出発地と目的地を設定し、出発地から目的地までの経路を求める「経路探索」という理論があります。これはカーナビや地図サイトなどでお馴染みの技術ですが、ゲームAIにも重要な理論です。経路探索のもっとも典型的な問題は、最短となる経路を算出する「最短経路探索」であり、数ある経路探索の問題のなかでももっとも多く研究されてきています。しかしながら、多くの理論は出発地と目的地を固定した上で一回だけ探索することを前提としており、目的地が移動するようなケースは想定されていません。これは、多くの応用分野では目的地自体が移動するということがないからなのですが、ゲームAIにおいては「敵の追跡」という重要な機能を実現するためには、目的地の移動に対応した経路探索が必要となります。現在のゲームでも、ほとんどの場合は単純に再探索を行うだけで、以前の結果を利用しません。吉田君の研究は、再探索の際に以前の探索結果を利用することで処理を高速化するためのものです。ある程度限定的な状況ではありますが、これまでの理論よりも高速な探索を実現しました。

経路探索アルゴリズム説明の図

もう一つ、学部4年の佐藤淳史君の研究も紹介します。題目は「イロレーティングシステムを用いたオンライン対戦ゲームにおけるマッチングアルゴリズムの改善」というものです。対戦型のオンラインゲームが多くのユーザーに遊ばれていますが、マッチングの待機時間が長いということがしばしば問題になります。マッチングにおいては、待機時間の他にも「レーティング」という要素も考える必要があります。レーティングというのは、平たく言えばできるだけ同じ実力のプレイヤーをマッチングする(換言すれば、実力のかけ離れたプレイヤーをできるだけマッチングしないようにする)ということなのですが、レーティングを重視するとマッチング時間が長くなってしまい、逆にマッチング時間を短くすると実力差が大きなプレイヤー同士のマッチングが起きやすくなります。この問題に対し、1978年に A.E.Elo が提案した「イロレーティング」という理論を用いて改善する方法があります。佐藤君の研究は、このイロレーティングに対しマッチング時間に応じた処理を加えて改善を行っています。

イロレーティングを応用したレーティング算出式

次回は、今回紹介していない2つのポスター発表を紹介したいと思います。

渡辺大地 (メディア学部教授)