Magic Bitboard Magic Bitboard Bitboard Magic Bitboard Bitboard Magic Bitboard 64 81 Magic Bitboard Magic Bitboard Bonanza Proposal and Implementation of Magic Bitboards in Shogi Issei Yamamoto, Shogo Takeuchi, Tomoyuki Kaneko and Tetsuro Tanaka In this paper, we present a technique to apply magic bitboards into Shogi. A bitboard is a bitset representation of a position suitable for ecient 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 eciently 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 rst developed a technique to calculate attacks of a board represented in multiple integers. Then, we show the eectiveness of our techniques by experiments using the state-of-the-art Shogi program, Bonanza. 1. Bitboard Bitboard 1 1 Bitboard Rotated Bitboard Department of General Systems Studies, Graduate School of Arts and Sciences, The University of Tokyo {issei,takeuchi,kaneko}@graco.c.u-tokyo.ac.jp Information Technology Center, The University of Tokyo ktanaka@ecc.u-tokyo.ac.jp Magic Bitboard Magic Bitboard 8Ö8 64 9Ö9 81 Magic Bitboard Magic Bitboard Bonanza Rotated Bitboard 2. Bitboard 8Ö8 64 64 Bitboard 9Ö9 81 81 Bonanza 1 32 3 Bitboard Knight http://www.geocities.jp/bonanza_shogi/ 1-42 -
Occupied Bitboard 8 2 Occupied Bitboard 10 7 8 2 2 7 1 9 1 Bonanza Bitboard Rook Bitboard 3 2 Bitboard Bitboard Occupied Bitboard 3 3. Bitboard 3.1 Bitboard Bitboard Fruit YSS GPS 2 Bitboard 1 1 Bitboard Bitboard 2 Occupied Bitboard http://www.fruitchess.com/ http://www32.ocn.ne.jp/~yss/index_j.html http://gps.tanaka.ecc.u-tokyo.ac.jp/gpsshogi/ 2-43 -
3.2 Rotated Bitboard 2 Bitboard Rotated Bitboard 1),2) 90 ±45 Occupied Bitboard 4 Occupied Bitboard 90 Occupied Bitboard 5 Magic Bitboard Rotated Bitboard 2 2 Rotated BitBoard Magic Bitboard Rotated Magic Occupied Bitboard 4 1 4. Magic Bitboard 4 90 Occupied Bitboard 3.3 Magic Bitboard Magic Bitboard 90 ±45 Occupied Bitboard Magic Bitboard 3 Rotated Bitboard 5 Rook Rook 12 0 Occupied Bitboard Rook (64-12) Magic Bitboard 1 StockFish 2 Glaurung 3 Magic Bitboard Occupied Bitboard Rotated BitBoard 1 http://chessprogramming.wikispaces.com/magic+bitboards 2 http://www.stockshchess.com/ 3 http://www.glaurungchess.com/ 4.1 Magic Bitboard Bitboard Algorithm 1 1 bb[0] bb[1] 64 q 4 6 6 q Bonanza Bitboard 4 C union 3-44 -
0 Occupied Bitboard q bb[2] q bb[2] XOR 5 7 Algorithm 1 ( 1 ) Bitboard bb[0] bb[1] q b[2] 64 ( 2 ) 0 Occupied Bitboard ( 3 ) 64 ( 4 ) 2 XOR ( 5 ) 6 1,000,000 3 3 Core i7 950 windows Algorithm 2 ( 1 ) ( 2 ) ( 3 ) 64 ( 3 ) ( 4 ) 2 3 3 7 Magic Bitboard 1 5 5 1 >1,000,000 >1,000,000 >1,000,000 2 189,704 116,971 60,249 3 11,288 15,961 7,898 4 16,164 41,504 356,239 5 867,446 552,592 872,409 6 >1,000,000 >1,000,000 >1,000,000 4.2 Algorithm 2 Algorithm 2 3 1 5 5 3 1 5. Bonanza Magic Bitboard Rotated BitBoard Bonanza Bonanza 4 Bitboard Bonanza Original Magic Bitboard Magic Bitboard Bonanza Simple 3 Tord Romstad Bonanza Feliz 0.0 4-45 -
4 Bonanza Bitboard (24 ) Bitboard Bitboard (Occupiued Bitboard) Bitboard (Occupiued Bitboard) 90 Bitboard (Occupiued Bitboard) 45 Bitboard (Occupiued Bitboard) 45 Bitboard (Occupiued Bitboard) Bitboard Bitboard Bitboard Bitboard Bitboard Bitboard 3) 216 15 9 6 15 Original Simple FileM FileR NPS 92,769 86,146 87,543 90,240 Time 148.00 159.33 157.00 152.00 100.00% 92.89% 94.27% 97.37% Magic Bitboard FileM Magic Bitboard FileR Rotated Bitboard 5 Occupied Bitboard Occupied Bitboard Xor- File SetClearFile XorDiag1 2 SetClearDiag1 2, Ö AttackRook AttackBishop AttackFile AttackRank AttackDiag1 2 BishopAttack0 1 2 R Rotated Bitboard M Magic Bitboard MM Magic Bitboard 5 Original Simple FileM FileR Occupied Bitboard 4 1 1 2 XorFile Ö Ö SetClearFile Ö Ö XorDaig1,2 Ö Ö Ö SetClearDiag1,2 Ö Ö Ö AttackRook R M M M AttackBishop R M M M AttackFile R MM M R AttackRank R R R R AttackDiag1,2 R MM MM MM BishiopAttack0,1,2 R M M M 6 7 NPS 1 Time Original NPS Core i7 950 Windows 7 MSC 32 7 9 Original Simple FileM FileR NPS 128,159 112,130 118,957 123,762 Time 362.22 414.00 390.24 375.09 100.00% 87.49% 92.81% 96.56% Original FileR FileM Simple FileR 90 Rotated BitBoard Simple Simple Original FileM Simple 6 Magic Bitboard Original Bonanza Rotated Bitboard 8 Bonanza b_gen_checks() Attack- Diag1() AttackDiag2() Attack- Diag1 2 Magic Bitboard Magic Bitboard 2 Magic Bitboard AttackDiag1() AttackDiag2() AttackBishop() Magic Bitboard Visual Studio 2010 /DNDEBUG 5-46 -
unsigned int * b_gen_checks( tree_t * restrict ptree, unsigned int * restrict pmove ) { /* */ bb_diag1_chk = AttackDiag1( sq_wk ); bb_diag2_chk = AttackDiag2( sq_wk ); 8 Bonanza genchk.c b_gen_checks() Magic Bitboard Bonanza Original FileR Magic Bitboard Magic Bitboard Occupied Bitboard Bitboard Bitboard 6 7 10 10 5 4 5 6 9 64 Bitboard 6. Magic Bitboard 4 Magic Bitboard Rotated Bitboard Rotated Bitboard FileR Rotated Bitboard Bitboard 2 Bitboard 1 9 10 5 Bonanza Bitboard Bitboard 1 11 1 11 Bitboard Bitboard Bonanza Bitboard Bitboard Bitboard 9 Bitboard 7. Rotated Bitboard Magic Bitboard Bitboard 6-47 -
11 81 Magic Bitboard Magic Bitboard Bonanza Rotated Bitboard Bonanza Magic Bitboard Bonanza Magic Bitboard Bonanza Bitboard Magic Bitboard Magic Bitboard Rotated Bitboard http://www. graco.c.u-tokyo.ac.jp/~issei/magicnumber.txt 1) Hyatt, R. M.(1999).Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4, pp. 213222. 2) R. Grimbergen.(2007). Using Bitboards for Move Generation in Shogi.ICGA Journal Vol. 30, No. 1, pp. 25-34. 3) (2002)... 7-48 -