2 0 0 0 OA Ms. Pac-Manにおけるモンテカルロ木探索
- 著者
- 池畑 望 伊藤 毅志
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.52, no.12, pp.3817-3827, 2011-12-15
2007年よりIEEEのCIGシンポジウムの中でMs. Pac-Manの自動操作を競う大会が開かれている.この大会以来,Ms. Pac-Manは,デジタルゲームAIの研究対象として注目を集めつつある.これまでの大会では,知識ベースを用いた古典的な手法によるAIが最も良い成績を収めているが,その性能には限界が見え始めており,知識ベースに代わる新しいアプローチが求められている.そこで,本稿では囲碁で成功したモンテカルロ木探索によるMs. Pac-Manの自動操作システムを実現し,その有効性を検証した.モンテカルロ木探索は乱数によって生成された未来局面についてのシミュレーションを繰り返すことで,専門的知識に頼らずに期待値の高い次の手を求めることができる.性能評価実験ではモンテカルロ木探索による自動操作システムは過去にMs. Pac-Man Competitionに参加したすべてのプログラムよりも優秀な成績を示し,Ms. Pac-Manにおけるコンピュータの世界記録を上回る結果を得た.
2 0 0 0 Ms. Pac-Manにおけるモンテカルロ木探索
- 著者
- 池畑 望 伊藤 毅志
- 出版者
- 情報処理学会
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.52, no.12, pp.3817-3827, 2011-12-15
2007年よりIEEEのCIGシンポジウムの中でMs. Pac-Manの自動操作を競う大会が開かれている.この大会以来,Ms. Pac-Manは,デジタルゲームAIの研究対象として注目を集めつつある.これまでの大会では,知識ベースを用いた古典的な手法によるAIが最も良い成績を収めているが,その性能には限界が見え始めており,知識ベースに代わる新しいアプローチが求められている.そこで,本稿では囲碁で成功したモンテカルロ木探索によるMs. Pac-Manの自動操作システムを実現し,その有効性を検証した.モンテカルロ木探索は乱数によって生成された未来局面についてのシミュレーションを繰り返すことで,専門的知識に頼らずに期待値の高い次の手を求めることができる.性能評価実験ではモンテカルロ木探索による自動操作システムは過去にMs. Pac-Man Competitionに参加したすべてのプログラムよりも優秀な成績を示し,Ms. Pac-Manにおけるコンピュータの世界記録を上回る結果を得た.The competition of controller program for Ms. Pac-Man has been held in the CIG symposium of IEEE every year from 2007. Since this competition was held, Ms. Pac-Man has become to an attractive subject of research on digital game AI. In the competition by this year, the classical AI method by using the knowledge base has gotten the best result. But, since the improvement by this method is becoming a limit, a new approach is required. In this paper, we realized the Ms. Pac-Man controller by the using Monte-Carlo tree search which is effective on Go, and examined the effectiveness. By repeating the simulation about the future phase generated with the random number, the Monte Carlo tree search can select the next move with a high expected value, without depending on professional expertise. In an evaluation experiment, the controller by the Monte Carlo tree search showed results more excellent than all the programs which participated in Ms. Pac-Man Competition in the past.