詰将棋を解くプログラムにおける効率的なハッシュの利用法について

• Item type: SIG Technical Reports(1)
• 公開日: 2001-07-27
• タイトル: 詰将棋を解くプログラムにおける効率的なハッシュの利用法について
• タイトル / 言語: en
• タイトル: A Method to use Hash Table Efficiently When Solving Tsume - Shougi
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学大学院理学系研究科情報科学専攻
• 著者所属: 東京大学大学院理学系研究科情報科学専攻
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Science, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Faculty of Science, University of Tokyo
• 著者名: 長井, 歩; 今井, 浩
• 著者名(英): Ayumu, Nagai; Hiroshi, Imai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 将棋やチェスなどの思考ゲームの探索アルゴリズムに関してはこれまでよく論じられてきた。しかし、深さ優先探索法につきものである、ハッシュの実際の実装法については殆んど論じられることはなかった。詰将棋を解くアルゴリズムの研究はこの10年 の間に大きく進歩したが、ハッシュの実装についてはこれまでと同様に、あまり論じられることはなかった。我々は詰将棋を解くアルゴリズムの研究を行ってきて、十分な成果を挙げてきたが、これまであまり論じられることのなかった、ハッシュの実装について、この論文で論じたい。我々の実装しているハッシュでは、占有率が80％になると、SmallTreeGCを用いて、全ハッシュの30％を捨て、80％未満ならSmallTreeReplacementで置き換えている。この2つのパラメータの根拠となるデータを提示する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The algorithms to search adversary-agent games like Shogi or Chess have been widely discussed. Although hash tables (transposition tables) are always implemented with depthfirst algorithms, they are rarely discussed. This situation is also the same with Tsume-Shogi. We have already studied an algorithum to solve Tsume-shougi problems. In this paper we would like to take up our implemention of hash table. Our hash table removes 30% of all entries by SmallTreeGC when load factor exceed 80%. While lode factor is under 80%, the hash table replaces an entry with a new one by SmallTreeReplacement. We would like to show some figures that are grounding these numerical values.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2001, 号 79(2001-AL-079), p. 21-26, 発行日 2001-07-27
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会