Author: Sune Fischer
Date: 02:49:02 09/30/02
Go up one level in this thread
On September 29, 2002 at 18:09:02, Arshad Syed wrote: >Would bitboards be the best way in which to represent piece positions or would >this be inefficient since the current Pentiums use 32 bit architecture. Also, >which would be the best alternate way, if not bitboard currently? > > >Thanks in advance, >Arshad I agree with Russell's post here, it isn't easy to answer. You should at least consider 0x88 also, it is a very elegant method. Most open source programs use either bitboards or 0x88, so you can get a lot of ideas from those which ever you decide on. I have never tried 0x88, but I can only say I like bitboards more and more. Some claim bitboards are 2.0 times slower, this is hard to confirm, but it is true that right now on 32 bit chips it isn't optimal. However we are so close to 64-bit chips that this argument is pretty much moot. Here are some pros and cons for bitboards relative to 0x88 that I can think of: pros: *) you can generate captures or non-captures at about the same rate as standard moves, and mostly this is what you need. *) parallel operations! A bitboard is a representation of all 64 squares, so in principle you can do 64 operations in parallel. When generating pawn moves this is really cool, you have a bitmap of the 8 pawns, shift 8, mask out occupied squares and extract the bits/moves. In 0x88 you need to go and check for every pawn if it can do the move, this requires (slow) indexing into your piece list array for each pawn and the blocked pawns are simply not filtered out automaticly, so you waste time on those. *) bitboards are "maps" of the board, you can answer all kinds of questions by pretty bitwise operations, so you have no need for looping the board. Say you want to know if there is a white pawn on 7th rank, instead of running through possibly all 8 squares asking if there is a white pawn here, you can simply AND the 7th rank with the white pawns. Not too long ago a very fast passed pawn floodfiller algorithm was posted here, real nice for evaluation. So bitboards are "easier" to handle mentally IMO, I can visualize a board and instantly know what bitwise operations to apply to do some task (maybe this requires some getting used to). In 0x88 you can probably do the same, but you have to struggle with some not very intuitive mathematical relations more often I think. *) no need to update a piece list, you can make one if you like, but you really don't "need" it. cons: *) generating all moves is probably not faster, you may save a conditional but in return you have to extract the first bit and mask it out of a bitboard, and you need to generate the attack bitboard first. *) if you use rotated you need large tables, this is assumably cache inefficient, however there has been some interesting posts recently by Gerd and Steffan where everything is done without tables. This could develop into something really interesting in the years to come. *) some questions are more easily (faster) answered in 0x88, typically things like the relation between two squares. For instance it believe it is a bit faster in 0x88 to see if two squares are on the same diagonal, file or rank. Some (if not most) use hybrid solutions, they try and use the best of both worlds. -S.
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.