不詰を正しく証明するアルゴリズム

• Item type: Symposium(1)
• 公開日: 2004-11-12
• タイトル: 不詰を正しく証明するアルゴリズム
• タイトル / 言語: en
• タイトル: A Correct Algorithm to Prove No-Mate Positions in Shogi
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: Department of Computer Science, University of Alberta
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, University of Alberta
• 著者名: 岸本, 章宏
• 著者名(英): Kishimoto, Akihiro
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 将棋では別手順によって同一局面に至ることがあるために，詰将棋解答プログラムはハッシュ表を用いるのが普通である．ハッシュ表の利用によって，探索に必要な空間を大幅に減らすことができるのだが，将棋には元の局面に戻る手順が存在するために詰将棋プログラムでは，詰む問題を不詰めと間違えるGHI（Graph History Interaction）問題を引き起こすことがある．本論文では[8]の手法を利用してGHI問題に対する正当でかつ効率のよい解決策を提案する．さらに本手法を詰将棋プログラムに実装した結果，詰みの性能を保持しつつ，難解な不詰の問題を解くことに成功した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Since identical positions can be reached by more than one path in Shogi, tsume-shogi solvers are typically enhanced with transposition tables. This approach can reduce the search effort by a large margin. However, because Shogi contains repetitions, tsume-shogi solvers suffer from the Graph History Interaction (GHI) problem. GHI may cause a solver to falsely regard proven positions as disproven. This paper presents an efficient and correct method to cure the GHI problem, based on the algorithm in [8]. A tsume-shogi solver with our GHI solution is now able to solve harder fu-tsume positions without degradation in the ability to solve tsume positions.
• 書誌情報: ゲームプログラミングワークショップ2004論文集; 巻 2004, p. 1-8, 発行日 2004-11-12
• 出版者 / 言語: ja
• 出版者: 情報処理学会