著者

岩田 茂樹 武永 康彦 笠井 琢美 伊藤 大雄

出版者

電気通信大学

雑誌

基盤研究(C)

巻号頁・発行日

2011

---

本研究は、ゲーム情報学全般にわたる研究のうち、(1) And-Or 木のコンピュータによる探索、と (2) ゲームやパズルの複雑さに関する研究を行う、ことを目的とする。And-Or 木(ゲーム木)のコンピュータによる探索では通常、評価関数が用いられる。ゲーム木の自然なモデルを定め、ゲーム木のある深さにおいて深さ優先探索により探索する局面数を考える。完全な評価関数に確率 p(0<p<1) で近い評価関数を用いたときは、完全な評価関数と比べて、ゲーム木の深さの多項式倍の数の局面数を探索することを示した。ゲームやパズルの複雑さの研究では、いくつかのゲーム・パズルの計算複雑さを明らかにした。