Author: Gerd Isenberg
Date: 15:44:22 08/30/03
Go up one level in this thread
On August 30, 2003 at 17:35:40, Vincent Diepeveen wrote: >On August 30, 2003 at 17:07:47, Gerd Isenberg wrote: > >>On August 30, 2003 at 14:37:44, Tord Romstad wrote: >> >>>My program has reached the stage where it is so complicated and ugly that I >>>no longer understand clearly how it works (it's rather miraculous that it >>>works at all), and there are many parts of the code which I am afraid of >>>touching because I am sure I will break something. Besides, the program >>>is horribly slow, searching only about 120 kN/s on a PIV 2.4 GHz. >>> >>>Because of this, I think it is time to throw away all the old code and >>>start from scratch. Before I do this, I will consider replacing my >>>data structures with something more efficient. >>> >>>Today, my board representation consists of a 256-byte array of squares >>>(visualised as a 16x16 board with the real board in the left half of >>>the middle 8 ranks) and a Phalanx-style piece list. At every node in >>>the tree, I generate "attack tables" similar to those found in Rebel, >>>Phalanx and Diep (the tables are not updated incrementally). >>> >>>I have never really liked bitboards, but because my next computer will >>>almost certainly be a PowerMac G5, I am considering to give them a try. >>>First, however, I have a few questions to the more experienced bitboard >>>users: >> >> >>Thinking bitboards takes some (hard) time, but you will don't regret it. >>Not for generating moves, but for eval patterns and abstraction level. >>Generating pattern is a rather loopless and uncondition task with botboards. >>Unconditional bitwise, arithmetic and shift operations with bitboards have most >>often a loop equivalent in other approaches. >> >>One possible weakness of bitboards is the "conversion" from bitboard metric to >>square index metric. If you have a particular square index "sq", the single > >Wrong. The real problem of bitboards is that you have in a huge word of 8 bytes >just 1 bit of relevant information about a particular color at a particular >square. But on the other hand the popularty of a bitboard don't cares - it simply avoid loops if more bits are set, e.g. to get a set of squares, pieces of same kind may reach in 2 (or n) moves. A lot of my bitboards have more bits set than one. > >So in todays chess software where knowledge is important and concentration of >knowledge about squares is important, bitboards need too much overhead to >evaluat for a pattern X just 1 square or pattern. > >You need TOO MANY bitboards and to combine all of them using square metrics. > >The classical way to detect a pattern is by doing a bunch of 'if then else' >around a certain pawn or queen to find a pattern. > >Finding a pattern in bitboards is way way slower because you need to extract all >the bits from the different bitboards. > >Even just doing a simple 'AND' won't do because you need to AND like 14 >bitboards just like that. > >If you try to do it branchless in bitboards you need to scan through *all* the >patterns, so that isn't a good idea either because i just need to scan through > >Log n > >of all the patterns as a simple IF can eliminate them. > Your general point is, that it is better to have a bunch of easy to predict conditional jumps inside a loop, rather than more disjoint less populated loops, with small unconditional bodies, but where the while-condition breaks quickly with missprediction. I do have respect to this point and do consider it. Anyway, even BTB is a limited ressource. There are pattern where bitboard preselection makes sense. Each "and" outside a loop avoids an "if" inside a loop. Sometimes it makes even sense to traverse final bitboards by serializing them into a stream of square metrics - and to handle these squares in your "classical" way with further "if then elses". >the basic idea of bitboards is clearly written down by hyatt several times and >that is: "we want a rude estimation of the position quickly". > >A few things you can do quickly with bitboards. > A lot - and thanks to the set theory, more elegant and more effiecient than other approaches. >Do those quickly and never again say that writing knowledge in bitboards is fun. > >It is horror & co, and besides that dead slow too. hehe, i guess set theory wasn't your favourite school subject? Maybe as a strong chessplayer, you concentrate on a single property of a particular square, rather than looking for property sets of squares. Gerd > <snip>
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.