Quixoの強解決

• Item type: Symposium(1)
• 公開日: 2020-11-06
• タイトル: Quixoの強解決
• タイトル / 言語: en
• タイトル: Quixo Is Solved
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 強解決
• キーワード / 主題Scheme: Other
• キーワード / 主題: Quixo
• キーワード / 主題Scheme: Other
• キーワード / 主題: Backward Induction
• キーワード / 主題Scheme: Other
• キーワード / 主題: Value Iteration
• キーワード / 主題Scheme: Other
• キーワード / 主題: 二人零和確定完全情報ゲーム
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 東京工業大学
• 著者所属: 東京工業大学
• 著者所属: Sorbonne Université, CNRS, LIP6
• 著者所属: 東京工業大学
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Sorbonne Université, CNRS, LIP6
• 著者所属(英): en
• 著者所属(英): Tokyo Institute of Technology
• 著者名: 田中, 智; ボネフランスワ, ティクシリューセバスチャン; 田村, 康将
• 著者名(英): Satoshi, Tanaka; Franc¸ois, Bonnet; Sebastien, Tixeuil; Yasumasa, Tamura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Quixo は5 × 5 グリッド上で行われる二人零和確定完全情報ゲームである．ゲームの目標は縦横斜めのいずれか一直線上に自身のマークを揃えることである．本研究では，Value Iteration とBackwardInduction を組み合わせたアルゴリズムによりすべての局面状態における勝敗(引き分けを含む) を明らかにし，Quixo が特に初期状態において引き分けであることを示した．また5×5 の場合に加え，4×4 および3×3 の場合について同様に解析を行い，具体的な勝利手順を明らかにした．妥当な時間とメモリ量での計算を可能とする状態表現および勝敗の記録方法，アルゴリズムの高速化について，論文中に説明を加える．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Quixo is a two-player game played on a 5 × 5 grid where the players try to align five identical symbols. Specifics of the game require the usage of novel techniques. Using a combination of value iteration and backward induction, we propose the first complete analysis of the game. We describe memory-efficient data structures and algorithmic optimizations that make the game solvable within reasonable time and space constraints. Our main conclusion is that Quixo is a Draw game. The paper also contains the analysis of smaller boards and presents some interesting states extracted from our computations.
• 書誌情報: ゲームプログラミングワークショップ2020論文集; 巻 2020, p. 181-188, 発行日 2020-11-06
• 出版者 / 言語: ja
• 出版者: 情報処理学会