2005 年度卒業論文 オセロ最善手筋の並列処理による解法の提案と 縮小版オセロによるその評価 提出日 : 2006 年 2 月 3 日 指導 : 筧捷彦教授 早稲田大学理工学部情報学科 学籍番号 1G02P801-1 三浦 琢磨 概 要 キーワード:完全情報ゲーム, 探索アルゴリズム, 並列処理 簡単なルールと奥深いゲーム性から人気のあるボードゲームのオセロは、数学的に二人零和有限 確定完全情報ゲームに属する。将棋・囲碁・チェスなども属するこのクラスのゲームは展開に偶然 の要素が入らないため理論上終局までの先読みが可能である。これは、ルールと初期状態が決まれ ば最善手筋が一意に決定されることを意味する。 実際には、ゲーム展開を読み進むにつれて計算量が爆発的に増大するため、最善手筋の算出はほ とんどのゲームで事実上不可能となっている。オセロも最善手筋の未解明なゲームのひとつであ り、その