Author: KarinsDad
Date: 09:05:27 06/13/99
Go up one level in this thread
On June 13, 1999 at 11:28:33, Charles L. Williams wrote: >On June 13, 1999 at 09:59:20, Michel Langeveld wrote: > >>I'm wondering what's the best way to write a movegenerator which prevents >>invalid moves(because of check). > > >I've been making the move and checking the legality afterward. This seems to be >the way most programs do it. Otherwise, you have to take pins into >consideration. Not so bad for knights, but if it's a slider, then you have to >consider the direction of the pin. > >For example, a rook pinned by another rook can still move two out of four >directions. It get complicated after a while, and the overhead begans to slow >things down. But during an alpha-beta search, many moves are never made because >of cutoffs, so the legality is never checked anyway. > > >Chuck I do check legality first. Here is how I do it: 1) I take the starting location of the king and using bitboards, check the legal directions away from the king for pieces of the same color where a pin can occur (up to 8 in the middle 16 squares of the board). For example, a king on g1 (say, after castling) cannot have a piece pinned from h1, from h2, or from off the board in 3 directions, so it has only 3 directions to check (f1, f2, and g2). 2) If I find a piece of the same color, I xor it out and re-do step #1 looking for pieces of the opposite color. 3) If I find a piece of the oppositie color, I check to see if it is a bishop or queen if this is a diagonal check (i.e. bitboard), a rook or queen if this is a horizontal or vertical check. 4) I set a byte for the piece pinned indiating the direction that it is pinned. For pawns, that is 7 directions except capturing in the direction of the pin. For knights, that is all 8 directions. For the other pieces, that is 6 directions. Then, when I am generating moves, I check the pin byte of each piece for non-zero. If it is non-zero, then the piece is pinned and has limited movement, based on the value of the pin byte. It seems reasonably fast for several reasons: 1) I'm using bitboards. 2) The percentage of pieces pinned is small (for most positions), so most of the pinned bytes get set to zero quickly anyway. 3) Many directions in many positions cannot have pins, so values of any pieces in those directions default to zero. I do not know if it is faster than checking whether a piece is pinned after the fact. I realize that a bunch of moves are cutoffs, and so pins will not be checked for each move in the other system. However, the way I do it seems like it may take a slightly shorter amount of time on average since not every piece or move is checked anyway either (just a few near the king), so the cutoff would have to be one or two moves for this system to be slower. On average, I think it is somewhat faster (but I have not done any tests to prove it). KarinsDad :)
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.