Author: Dave Gomboc
Date: 13:57:01 06/21/00
Go up one level in this thread
On June 21, 2000 at 14:52:34, Tom Kerrigan wrote: >On June 21, 2000 at 14:38:23, Christophe Theron wrote: > >>On June 21, 2000 at 13:33:14, Tom Kerrigan wrote: >> >>>On June 20, 2000 at 21:39:01, Robert Hyatt wrote: >>> >>>>On June 20, 2000 at 15:52:53, Tom Kerrigan wrote: >>>> >>>>>On June 20, 2000 at 15:03:48, Robert Hyatt wrote: >>>>> >>>>>>On June 20, 2000 at 14:07:39, Tom Kerrigan wrote: >>>>>> >>>>>>>On June 19, 2000 at 21:32:56, Robert Hyatt wrote: >>>>>>> >>>>>>>>On June 19, 2000 at 20:50:11, John Coffey wrote: >>>>>>>> >>>>>>>>>On June 19, 2000 at 19:48:36, Larry Griffiths wrote: >>>>>>>>> >>>>>>>>>>I have found bitboards to be an even trade-off on my Pentium system. I have to >>>>>>>>>>update about 6 bitboards when a piece moves and this generates a lot of >>>>>>>>>>instructions. I get it back in my IsKingInCheck code so it evens out. I like >>>>>>>>>>to have fast move generation code, but most of my gains have been through >>>>>>>>>>alpha-beta, hash-table, killer-move and movelist ordering etc. >>>>>>>>>> >>>>>>>>>>Larry. >>>>>>>>> >>>>>>>>> >>>>>>>>>Maybe I am too much of a novice, but I don't see yet why I should convert over >>>>>>>>>to bitboards. Is move generation faster? If so, why? My program scans the >>>>>>>>>board and uses simple loops to generate moves. Do you not have to do loops >>>>>>>>>with bitboards? >>>>>>>> >>>>>>>>Not to generate moves, No. You generate all the sliding piece moves with two >>>>>>>>table lookups... >>>>>>> >>>>>>>Hmmm. I do table lookups all over my program, and none of them seem to be >>>>>>>generating any moves... >>>>>>>The fact is that you DO need to loop to generate moves in a bitboard program. >>>>>>>Maybe it's not the same loop, but it's still a loop. >>>>>>> >>>>>>>-Tom >>>>>> >>>>>> >>>>>>Who says so? Ask the Dark Thought guys. >>>>>>Or Slate/Atkin. You only need to loop if you want to take the attack bitmap >>>>>>and turn it into a list of moves. This is not the way _all_ programs operate >>>>>>(chess 4.x, Dark Thought, others, any of which generate a few moves at a time, >>>>>>then take one and search it, without enumerating the other moves.) >>>>>> >>>>>>So loops are something you do (with bitmaps) if you want to, not because you >>>>>>have to. >>>>>> >>>>>>As far as your table lookups not generating any moves, that is a programming >>>>>>issue. Mine do. :) >>>>> >>>>>Maybe your makemove() function can take bitboards as input (i.e., here is a set >>>>>of squares that my pieces can move to) but mine sure can't. >>>>>-Tom >>>> >>>> >>>>You are missing the point. A move generator _can_ emit a single move, which >>>>can be fed into MakeMove(). Read "Chess Skill in Man and Machine", the chess >>>>4.x section. They explain this pretty well. It takes zero loops to emit a >>>>single chess move. You pick the source square. You do two table lookups for >>>>bishops (say) and you have all the target squares it can move to. A single >>>>FirstOne() and you have a <to> square, which is all you need to make the move, >>>>and recursively call Search(). >>> >>>So you end up having to call gen() a mess of times. I don't see how that isn't a >>>loop. >>>-Tom >> >> >>As I understand he says that in order to generate one move he doesn't have to >>loop. That's what James explains in another post. >> >>With 0x88 or 16x you have to loop thru empty squares, he says with bitboards you >>don't have to. For each rank, file or diagonal in any configuration (by >>configuration I mean set of empty squares in this rank/file/diagonal), you can >>have precomputed arrays that instantly give you the set of squares (a bitboard) >>a sliding piece can move to. >> >>Not that I support his point of view about bitboards. I prefer to "loop thru >>empty squares" in my L1 cache rather than clobbering the same cache with >>bitboards. And anyway, the time required to extract the rank/file/diagonal from >>the "occupied" bitboard and the time required to process the resulting set of >>"can move to" squares is not required in 0x88 or 16x. And for non-sliding pieces >>(which represent in average half of the pieces present on the board), the method >>does not apply. > >Exactly, it's necessary to process the resulting bitboards. Maybe you can do >some simple operations to get an interesting set of bits, but at some point, you >have to turn those bits into something useful. There has to be a loop somewhere >which extracts the bits and does appropriate things to them. If you're lucky, >your processor has BSF/BSR (or an equivalent) and this loop is relatively fast. >But if you don't have these instructions, I bet the pretty bit patterns aren't >helping you much. Personally, I'm a little sick of people saying, "oh, one AND >operation and I'm done!" and totally ignoring everything else that has to be >done. > >-Tom I don't have a particular belief re: which setup (board maps or bitmaps) are better, but I think more concreteness to the discussion would be valuable. Can you come up with some things that need doing... basic things, the kind of stuff that gets done hundreds of thousands of times per second in a chess engine. We could then proceed to discuss under what cases it is actually necessary to extract the bits, and what cases don't require that to happen. Dave
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.