論文タイトル: コンピュータ将棋における Magic Bitboard の提案と実装

言語: Ja

論文タイトル英語: Proposal and Implementation of Magic Bitboards in Shogi

著者所属: 東京大学大学院総合文化研究科;;東京大学大学院総合文化研究科;;東京大学大学院総合文化研究科;;東京大学情報基盤センター

著者所属英語: Department of General Systems Studies, Graduate School of Arts and Sciences, The University of Tokyo;;Department of General Systems Studies, Graduate School of Arts and Sciences, The University of Tokyo;;Department of General Systems Studies, Graduate School of Arts and Sciences, The University of Tokyo;;Information Technology Center, The University of Tokyo

著者名: 山本 一成;;竹内 聖悟;;金子 知適;;田中 哲朗

著者名英語: Issei Yamamoto;;Shogo Takeuchi;;Tomoyuki Kaneko;;Tetsuro Tanaka

論文抄録: 本稿では,将棋においてMagicBitboardを適用する手法を提案する.Bitboardはチェスなどの二人ゲームのゲーム木探索で盤面を表現するのに適した手法であり,チェスや将棋の強いプログラムで広く使われている.MagicBitboardは従来のBitboardの手法に比べ,よりシンプルなデータ構造を管理するだけで利きを算出することが可能となる近年開発された手法である.MagicBitboardはチェスの盤面が一つの64ビット整数で表現できることに依存した手法であり,盤面のマス目の数が81マスの将棋で,MagicBitboardを使う方法は知られていなかった.しかし我々は初めて,複数の整数で表現された盤面においてMagicBitboardを使って利きを算出する手法を発明し,Bonanzaを使った実験で我々の手法の効果を示した.

論文抄録英語: In this paper, we present a technique to apply magic bitboards into Shogi. A bitboard is a bitset representation of a position suitable for efficient game-tree searches in two-player games such as chess. They have widely been used in popular strong programs in chess and Shogi. Magic bitboards are recent improvements that can efficiently calculate attacks with simpler data than those needed to be maintained in previous bitboard techniques. While magic bitboards in chess depend on the fact that a chess board can be represented in one 64-bit integer, a board of Shogi has 81 squares. Thus, we first developed a technique to calculate attacks of a board represented in multiple integers. Then, we show the effectiveness of our techniques by experiments using the state-of-the-art Shogi program, Bonanza.