不完全情報ゲームに対する階層化したモンテカルロ探索とそのぷよぷよへの適用

摘要

近年、囲碁をプレイする人工知能エージェントにおいてUCT探索に基づく先読みアルゴリズムの有効性が示され、注目を集めている。本研究では、ぷよぷよの大連鎖を目的として、UCT探索に基づく新しい先読みアルゴリズムを提案する。ぷよぷよは、落下型パズルゲームの一種であり、落下してくるピースを操作して大連鎖を構築するが、将来どんなピースが落下してくるかを事前に知ることができない。このような場に晒されていない情報が存在する不完全情報ゲームでは、その隠れた情報のために多くの可能性を考慮する必要が生じ、先読みを困難にする。提案するアルゴリズムでは、自分が選択可能な手と場から確率的に与えられる手を区別し、その区別をもとにした探索と評価値の更新を行う。これにより、ぷよぷよのような不完全情報ゲームにおいても、限られた計算時間内に、大連鎖を実現するような効率的な先読みが可能であることを示す。