Author: Roberto Waldteufel
Date: 10:57:24 10/28/98
Go up one level in this thread
On October 28, 1998 at 08:50:06, Peter Fendrich wrote: >In the Search, when a move is generated and made, I always call the KingInCheck >routine to find out if the side who moved is in check. If so the position is >illegal and a new move is generated. > >Sometimes it is proposed to skip the KingInCheck test and let the move >generator, in the next ply, capture the king. In that case stop that node and >return error. The idea is to gain performance by not calling the KnigInCheck at >all and that the illegal positions are so uncommon that it's worth the extra >overhead the few times it happens. > >I never liked that idea but started to think about it anyway... >I think it's somewhat unnatural to have possibly illegal positions around and it >makes the program more complex. Some thoughts: > >1) >When the NullMove starts at next ply, I certainly don't want to have illegal >positions around. >By making a call to KingInCheck before the NullMove the whole idea with delaying >the check is spoiled so that's not a solution. >Another way is to generate the first move in order to see if the position is >legal, before the NullMove is started. A capture of the King is supposed to be >the first thing to find and in that case return error, never letting the >NullMove start. > >2) >There ar other things that is done before the 'real' search is started, like >hash table look up, repetition check, end game tables and more. What are the >side effects? > >3) >What will happen in the Quiescence when the Evaluate is called in the beginning? >There might be an illegal position to Evaluate. Maybe not so dangerous but you >have to think about it when you do your evaluate coding. > >In short it's too complex for my taste (I don't have to invent bugs - I 'm happy >with the ones I have!) and I don't see any real performance gains. At least not >for my program. At least not in theory. > >Have you measured it and how do you handle situations like those above? > >//Peter 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 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
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.