Author: Dan Newman
Date: 22:19:39 11/25/99
Go up one level in this thread
On November 25, 1999 at 16:21:12, Bas Hamstra wrote: >On November 25, 1999 at 08:09:49, Jari Huikari wrote: > >>On November 24, 1999 at 16:54:36, Dan Newman wrote: >> >>>The first chess program I wrote (about 4 years ago) generated only legal >>>moves. Initially 80% of the cpu time was taken by the in-check detection >>>code. >> >>1. When in-check not used and illegal move tried: >>Program sees that king will be captured, and king-capture gives penalty >>of 10000 points? Or what? > >If in-check detection is costly for your datastructures, cheapest way is to >ignore illegal moves and watch for every capture if the king is captured. If >so, you return simply mate. Same for search and qsearch. What I usually do is make the move and then immediately test to see if the king has been left en prise with a special function made just for that purpose. You could rely on generating captures of the king, but I've always figured that would be difficult in the full width part of the search if you want to try the hash table move before generating captures--you would be searching from an illegal position which might not work too well... Recently I've been using knowledge of what the last move was to make the legality test cheaper. If you aren't in check already, then your king can only be taken by a slider that was unblocked by the last move. (In fact I built in this legality test into make() which returns 0 if the move isn't legal.) Bitboards and 0x88 make it easy to determine if one of these unblocked squares lies along the same sliding vector as the king. If it doesn't (and you aren't in check) then the move is legal. > >To prevent illegal moves actually being played in the game, you do the costly >in check detection only at the root: check for every move if it leaves the king >in check. If so, skip that move. If at the root there are no moves left it's >either mate (when king is in check) or draw (stalemate). > >>2. Is in-check necessarily so slow? How do you detect it? I do this >>still very crudely, but I think there is many helping rules, that one >>can conclude that certain moves can't be illegal. > >That all depends on your datastructures. For most programs it is not cheap. You >simply have to know all attacks to the kingsquare. So you have to do some >looping stuff. Unless you keep your attacks up to date every move anyway. > >Regards, >Bas Hamstra. My first in-check was very slow. I simply scanned the board in every direction for enemy pieces that directly attack the king. This required looking out along the 8 sliding directions and looking at the (potenially) 8 squares from which a knight could attack. I sped this up later using the piece inventory to skip over unnessesary tests. Very brute force. Later still, I found it cheaper to simply run through the enemy piece list and use a table lookup to determine if any piece directly attacks the king. (Or potentially attacks the king in the case of sliders. If the a slider is found to line up on the king, a further test must be made for blockers.) Now, I use knowledge of the last move made to do this even faster. -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.