Author: Robert Hyatt
Date: 14:16:05 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 You are not nearly so sick of hearing that as I am sick of hearing people talk about what you can and can't do with bitboards _without_ ever having tried them. Again, there is _no_ need for a loop. I can generate a single move (capture) with no loop of any kind. Anybody can generate a non-capture (single move) without a loop, of course. But captures are way more common to want, since they are usually tried first. I've done 0x88, 8X8, 16x16, 10x12, and probably others. I don't think that move generation is the separating point for bitboards vs the others, except for the fact that I can generate captures far easier. Bitboards help in other places as well. And on 64 bit architectures, they make a lot of sense. You ought to do what I did 5 years ago. Say "I am going to try this for a couple of years, to see if this is worthwhile." It takes a lot of time and experience and false starts to do bitboards. But they _can_ work quite well. I can point to several programs that prove this, from Kaissa and chess 4.x in the 1970's, thru Crafty and several others in 2000. But they _do_ take time to learn, just like a programming language does.
This page took 0.01 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.