Author: Christophe Theron
Date: 11:38:23 06/21/00
Go up one level in this thread
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.
Christophe
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.