Author: Peter Fendrich
Date: 10:20:23 04/18/99
Go up one level in this thread
On April 18, 1999 at 08:36:17, Fernando Sansberro wrote: >I am converting the structures of my chess program to bitboards. >I know that programs like Tristram or Crafty makes use of bitboards and the >source code is available, but what I need is some strong explanation about how >bitboards work. I am searching some web page that deals with this. > >Thanks. >(Sorry for my english). > >Fernando Sansberro. >Montevideo-Uruguay >South America. There are some pages with bitoards explained. Take a look at: www.icdchess.com/ccc/resource/links/programming.html at least Dark Thought Homepage descibes bitboards quite well. Tristram's homepage has a really nice description of bitboards http://home.fda.net/~wzrdking/chessprg.htm Here are some short notes about bitboars. The main idea with bitboards is the fact that the chess board has 64 squares and a 64-bit integer occupies 64 bits of memory. Sometimes two 32-bits integers are faster but that's another story. So start with defining your bitboard type: typedef unsigned __int64 BITBOARD; (if your compiler don't have __int64 it probably have some other 64 bit integer type, like longlong or so) I recommend you to use unsigned because otherwise one never knows what compilers will try to do... :) Then you need some macros (or functions) to operate the board. The best thing with bitboards are all the bitwise operators available like bitwise AND, OR, XOR and so fort. Some other important functions: - Find first bit in the bitboard - Find last bit - count all bits in the bitboard - Set bit for square x - Remove bit for square x Here is your first real choice: Will you use the 'old' style of bitboards like Chess 4.5 used or the newer one with "rotated bitboards"? In all cases you will need to store update some basic information in bitboards, like all white pieces, all white bishops, black bishops and so on. If you try the "Chess 4.5" style you will have two arrays of bitboards: BITBOARD AttacksFrom[64] BITBOARD AttacksTo[64] The first one will keep track of all attacks from each square. AttacksFrom[0] is bitboard with all attacks from the square a1. The second one keep track of all the attacks to each square. AttacksTo[0] is a bitboard with all squares attacking the square a1. These two bitboards makes your MoveGeneration routine really fast, the fastest possible, but for every move you have to update these two arrays and when the move is undone during the tree search you have to retract all changes in these two arrays and that takes a lot of time. If you will apply the "rotated bitboard" style the program will work in another way. First you don't use the two arrays above any more. Instead you have a bunch of static bitboards describing all possible moves from all squares with all types of pieces. Now your MoveGenereration will take more time but your moving and 'unmoving' routines will be much faster because you don't have to update all these bitboards in the two arrays. I will not go in detail here but it is describe in DarkThought's Homepage mentioned above. To write a bitboard based program is more complicated than other more straight forward methods. You will introduce very peculiar bugs and spent hours and hours to find out what is wrong. The concept of "rotated bitborads" is yet more complicated. I would probably start with the "Chess 4.5" style and get it working. During that time you will get a feeling for bitboards and "think" bitboards. After that you could evaluate if you wan't to continue with rotated bitboards or maybe change to some other method. In fact I did start with the "Chess 4.5" style myself but only because there were no "rotated bitboards", to my knowledge, at that time - some 20 years ago. Now I use the "rotated bitboard" concept. //Peter
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.