Difference between revisions of "Position Representation"
(28 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
− | + | == Bitboard == | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | Bitboard is the best presentation of a chess position. The presentation contains a set of 64-bit integer numbers. Both sides have six numbers for all different types of pieces. For example, the position below has the following white pawns | + | Bitboard is the best presentation of a chess position. Main advantage of that representation is a speed becaus it based on bitwise operations. The presentation contains a set of 64-bit integer numbers. Both sides have six numbers for all different types of pieces. For example, the position below has the following white pawns |
presentation: | presentation: | ||
− | + | <center> | |
+ | <table width ="80%"><tr><td> | ||
{{Chess diagram|= | {{Chess diagram|= | ||
| tright | | tright | ||
− | | | + | | |
|= | |= | ||
− | |||
8 |rd| | | | |rd|kd| |= | 8 |rd| | | | |rd|kd| |= | ||
7 |pd|pd| | | |pd|pd| |= | 7 |pd|pd| | | |pd|pd| |= | ||
Line 32: | Line 18: | ||
1 |rl| | | | |rl|kl| |= | 1 |rl| | | | |rl|kl| |= | ||
a b c d e f g h | a b c d e f g h | ||
+ | | | ||
+ | }} | ||
+ | </td><td width="50px"></td> | ||
+ | <td> | ||
+ | <font size="+2"> | ||
+ | 0 0 0 0 0 0 0 0 <br><br> | ||
+ | 0 0 0 0 0 0 0 0 <br><br> | ||
+ | 0 0 0 0 0 0 0 0 <br><br> | ||
+ | 0 0 0 0 0 0 0 0 <br><br> | ||
+ | 0 0 0 0 1 0 0 0 <br><br> | ||
+ | 0 0 0 0 0 0 1 0 <br><br> | ||
+ | 1 1 0 0 0 1 0 1 <br><br> | ||
+ | 0 0 0 0 0 0 0 0 <br><br> | ||
+ | </font> | ||
+ | </td> | ||
+ | </tr></table> | ||
+ | </center> | ||
+ | The 64-bit presentation allows a fast move generator and a fast evaluation function. For example, the expression (WhitePawns << 8) & ~AllSquares is used to represent all possible destination squares of white pawns for one square up. Let us see this expression in grater detail. Firstly, the | ||
+ | presentation of white pieces was shifted by 8 bits or moved for one square up. Then with negation of presentation of all pieces we get presentation of empty squares. Finally, with bitwise operation AND between both presentations we get | ||
+ | presentation of destination squares. This presentation and presentation of white pawns enables generating all possible moves for white pawns for one square up. Similarly, we can calculate all possible moves for pawns, knights, and the king. For generating moves for sliding pieces we use addition information which is | ||
+ | described below. | ||
+ | |||
+ | == Rotated bitboard == | ||
+ | The standard bitboard presentation described above is very useful in generating moves for all pieces except sliding ones (bishop, rock, queen). Rotated bitboard provides additional information for certain types of pieces, namely the sliding ones. Bitboard is rotated by 45, 90, and 135 degreees. The 45 and 135 degrees | ||
+ | rotations are used for calculating diagonal and the 90 degrees for calculating vertical moves. The speedup of rotated bitboard relies on quick discovery of attacks on certain squares without the need to use program loops which is the case for all other representations. | ||
+ | |||
+ | == Links == | ||
− | + | * [http://en.wikipedia.org/wiki/Bitboard Wiki:Bitboard] | |
− | + | * [http://supertech.lcs.mit.edu/~heinz/dt/node6.html Bitboard Engine] | |
+ | * [http://www.fzibi.com/cchess/bitboards.htm An Introduction to BITBOARD] | ||
+ | * [http://www.cis.uab.edu/hyatt/pubs.html Online technical papers] | ||
+ | * [http://www.cis.uab.edu/info/faculty/hyatt/bitmaps.html Rotated bitmaps, a new twist on an old idea] | ||
+ | * [http://www.frayn.net/beowulf/theory.html#bitboards Bitboards] | ||
− | + | [[Category:Borko Bošković]] | |
− | + | [[Category:Research activity]] | |
− | + | [[Category:Chess program BBChess]] | |
− | + | [[Category:Representation of Chess Game]] | |
− | + | [[sl:Bitna predstavitev igre]] | |
− | |||
− | |||
− |
Latest revision as of 08:40, 19 October 2006
Bitboard
Bitboard is the best presentation of a chess position. Main advantage of that representation is a speed becaus it based on bitwise operations. The presentation contains a set of 64-bit integer numbers. Both sides have six numbers for all different types of pieces. For example, the position below has the following white pawns presentation:
0 0 0 0 0 0 0 0 |
The 64-bit presentation allows a fast move generator and a fast evaluation function. For example, the expression (WhitePawns << 8) & ~AllSquares is used to represent all possible destination squares of white pawns for one square up. Let us see this expression in grater detail. Firstly, the presentation of white pieces was shifted by 8 bits or moved for one square up. Then with negation of presentation of all pieces we get presentation of empty squares. Finally, with bitwise operation AND between both presentations we get presentation of destination squares. This presentation and presentation of white pawns enables generating all possible moves for white pawns for one square up. Similarly, we can calculate all possible moves for pawns, knights, and the king. For generating moves for sliding pieces we use addition information which is described below.
Rotated bitboard
The standard bitboard presentation described above is very useful in generating moves for all pieces except sliding ones (bishop, rock, queen). Rotated bitboard provides additional information for certain types of pieces, namely the sliding ones. Bitboard is rotated by 45, 90, and 135 degreees. The 45 and 135 degrees rotations are used for calculating diagonal and the 90 degrees for calculating vertical moves. The speedup of rotated bitboard relies on quick discovery of attacks on certain squares without the need to use program loops which is the case for all other representations.