コンピュータ将棋における Magic Bitboard の提案と実装

書誌事項

タイトル別名
  • Proposal and Implementation of Magic Bitboards in Shogi

この論文をさがす

抄録

本稿では,将棋において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.

収録刊行物

詳細情報

問題の指摘

ページトップへ