Author: Dan Newman
Date: 22:27:00 01/17/99
Go up one level in this thread
On January 17, 1999 at 07:45:46, Frank Phillips wrote: >In Reply to: Re: 0x88 posted by Dan Newman on January 16, 1999 at 19:00:58: > >On January 16, 1999 at 19:00:58, Dan Newman wrote: > >>Posted by Frank Phillips on January 16, 1999 at 06:40:05: >> >>>I have vague thoughts of moving on from mailbox[] to 0x88 and would be >>>grateful for a bit more detail on the second part of Bruce’s 0x88 message >>>(Jan 12, message number 39133) about masks, particularly how to use them >>>(bfBishop | bfQueen for instance)? >>> >> >>The idea is to make an array of bitmaps which can be indexed by the >>difference in 0x88 coordinates of two squares. This index is in >>the range of -119 to 119 since on-board 0x88 coords range from 0 to >>119. This means the array must have at least 239 entries (I ususally >>"round" this up to 240 with the idea that that might improve alignment >>of data...). You can then index the array like this: >> >> array[coord2-coord1+119] >> >>What I usually do is set a pointer equal to array+119 and then >[SNIP] > >Thanks Dan. My first and current attempt started as a rip of TSCP but as grown >like topsy as I have added stuff and my understanding has increased - usually >in that order. I am looking for a reason to start again and stop me >constantly fiddling with what I have. So it is either plunging into bitboards >(doubtful) or 0x88 as the motivation for a complete redesign. > I really like 0x88, though I'm trying a (non-rotated) bitboard program now. The main disadvantages of 0x88 that I've found are 1) the doubling in size of many arrays and 2) the "holes" in the 0x88 coordinates that have to be filled or removed to prevent tables like the history heuristic table from becoming too large. >I do wonder what sort of speedup 0x88 might bring. In my experience 0x88 doesn't speed up move generation an awful lot, and even if it doubled move generation speed that would probably only make the program a few percent faster. It does make the move generator easy to code though. I think where 0x88 really shines is with the coordinate difference trick. This can make coding attack/in-check dection and SEE much easier and can make the code a good deal faster. I suspect it is quite useful in calculating certain eval terms too. >The biggest I managed so for >was after someone here (Werener I think) pointed out that his program spent >most of its time testing for check and I changed my approach from finding each >piece and seeing if it attacked to king, to working out from the king square >along diagonals, files and ranks, and testing whether knights and pawns where >located knight and pawn moves away. Obvious, and quicker since most paths to >king are usually blocked. Currently the program spends about 10% of its time >in the in_check function and about 10% generating captures. In my first program I hadn't yet heard of pseudo-legal move generation, and I tested each move in the move generator for legality using a brute force in-check function. When I profiled the code incheck() was taking 80% of the time. I knocked this down somewhat by using a piece inventory to skip unnecessary tests (no sense looking out along diagonal sliding vectors when the oponent no longer has any bishops or queens...). At some point I also switched to the more efficient "working out from the king" trick. (I suspect that 80% would only have been 40% if I'd had a decent amount of eval in the program.) >I pre-calculate moves at >intialisation, so move generation involves an array lookup, >nextsquare[piece][direction][sq], and an if() statement to check if it is -1 >and therefore off the board. > I used table lookup for to-squares in my first program but have used offset calculations since then, under the theory that it should be faster to add a constant than to retrieve a value from memory--but that's theory only as I haven't actually compared them. I think I'll have to try it again sometime; it looks like it would make for an nicely compact move generator. I typically unroll loops and do other things to avoid tests and end up with rather massive move generators--too much tweeking before I get a working program... Actually, when you consider how little of a chess program's time is spent generating moves and how much is probably going to be spent doing evaluation, it seems as if one probably should concentrate more on creating data structures and algorithms to support fast evaluation rather than fast move generation. I generally write my move generator first though, and that seems to get most of my effort in optimizing things. >Still aspiring to beat that pansy (as someone here called it) GNUchess though >:)) I'll have to try GNUChess (since it's *so* easy :). I've been playing my programs mostly against Comet and have only occasionally managed to draw it--this no doubt due to lack of any sophisticated eval and perhaps a bug or two... -Dan.
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.