Author: Roberto Waldteufel
Date: 17:02:36 10/28/98
Go up one level in this thread
On October 28, 1998 at 15:39:00, Peter Fendrich wrote: >On October 28, 1998 at 13:57:24, Roberto Waldteufel wrote: > >>Hi Peter, >> >>I also test for king in check before recursing. I don't think it adds much >>overhead because of the data structure of the program. I maintain attack from >>and attack to tables for each square (2 arrays of 64 bitboards). I also maintain >>a two-element array king() that tells me the square of each side's king. So my >>king in check test code is as simple as : >> >>generate move >>make move >> >>if atktobits(king(side)) and allmenloc(opnt))=0 then >> >> swap sides >> v=-search(-beta,-alpha,depth-1) >> swap sides >> >>end if >> >>unmake move > >Yeah, I know! I used the same kind of bitboards before, inspired by Chess 4.5... >After reading Bob's posts about rotated bitmaps I converted to that and got some >increased performance but I had to change two things: >1) The complicated swapoff I used, wasn't doable anymore. I used >2) The KingInCheck became more expensive and I had to be more careful of when to >use it. > >Did I say two? Here is one more. >3) Some of the evaluation code became much much more expensive and I had to >rewrite that to. In fact this is still ongoing and will probably never stop :) > >> >>I think the real problem with testing for king in check comes when you don't >>maintain an atkto array of bitboards. They do take some overhead to maintain, >>but the check test becomes a piece of cake, as does MVV/LVA order capture >>generation. In Crafty I think Bob generates his attack maps on the fly, using >>rotated bitboards for very efficient sliding piece move generation. Of course >>rotated bitboards could also be used to help update the attack tables, but I >>think this would be overkill, as both the extra bitboards and the tables >>represent overhead to do the same job, and as long as you keep both attack from >>*and* attack to tables, it is possible to update them efficiently without the >>help of the rotated bitboards, since each table can be used to help update the >>other. The tables slow down my move making process, but they help in all sorts >>of other ways (like check detection), so it is not clear overall whether they >>are worthwhile or not. I am experimenting with generating moves using rotated >>bitboards, but to make it work well I may have to rethink things like check >>detection, because it becomes more expensive without those tables. >> >>Best wishes, >>Roberto > >I suppose that you have four routines to update your bitboards. Something like >CutAtttacksTo, ExpandAttacksTo, DeleteAttacksFrom and InsertAttacksFrom. If you >used rotated bitboards to get all the bits from a certain square you could OR >that into your atkfr table but you still had to loop through all these bits in >order to update the atkto table. So I agree, it would probably be an overkill... Well, I do something similar, but not quite like you say here. Remember that when a square is vacated, some of the attack maps for other pieces may change due to "discovered" attacks, so all the rays through that square need to be extended, whereas when a square that was empty becomes occupied, it is necessary to do the reverse and chop off any rays passing through the square. However, I use a nice little trick, only updating these changes when necessary. Thus when a capture takes place, only the from square needs to have its rays adjusted. Also, because I generate captures in MVV/LVA order, I often have a situation where I try several captures with the same to-square. In this case I don't have to do the ray adjustments. I use these functions: Putman places a given man of a given side to a previously empty square. Cutman removes a piece from a square, making that square empty. Repman replaces a man on a given square with some givenm other man of the same side (no ray adjustments) Chngman replaces a man on a given square with some given other man of the other side (no ray adjustments) All the bitboard updating is done in assembler, and runs quite quickly, but when I first coded this it was very tricky to get it just right. The pentium's bsf and bsr instructions are very handy for this. I also have found that the evaluations are a problem, since my currant evaluation function (also in assembler) makes very heavy use of the attack tables. The fact that the tables' utility is so diverse makes it very difficult to quantify and weigh up against the overhead of continually updating them. Best wishes' Roberto > >//Peter
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.