唯一の必勝法を持つ二人ゲームの複雑さ

概要

論文の詳細を見る
将棋やチェス,囲碁に代表される(完全情報)二人ゲームは,計算機科学の様々な分野で広く研究されている.特に,ゲーム上のある局面から最善の次手を選択することは,理論及び実験どちらの観点からも非常に難しい問題と考えられている.もしゲームのプレイヤが,相対する敵のいかなる指し手に対しても自身の優勢を保つような次手を指せるとき,プレイヤのそのような指し手全体は必勝法と呼ばれる.一般に完全情報二人ゲームにおいては,どちらかのプレイヤが必勝法を持つことが知られている.本稿では,どちらかのプレイヤが「唯一の」必勝法を持つという制限の付いた特殊な二人ゲームについて考察する.唯一の必勝法とは,プレイヤが指す最善手が一意的であり,それ以外の手を指すと優勢が逆転してしまうものである.本稿では,与えられたゲームを,唯一の必勝法を持つゲームに埋め込めることを示す.それに基づき,時間・領域限定交替性チューリング機械においては,いかなる入力の計算トレースも一意的である機械が,通常の(計算トレースが非一意的な)機械と同等の能力を持っていることを示す.
社団法人電子情報通信学会の論文
2001-03-09