Author: KarinsDad
Date: 21:36:04 02/08/00
Go up one level in this thread
On February 08, 2000 at 17:15:13, leonid wrote:
[snip]
>>
>>No, I do not do this yet. But it sounds like a good idea. I actually do
>>something worse than most everyone else. Instead of generating all moves and
>>then checking for illegality at the point in time that the move is checked (and
>>hence, if you get a cutoff, you have not checked for illegality on a bunch of
>>moves that were not even used), I prevent the creation of illegal moves in move
>>generation.
>
>Very interesting what you are saying but I am almost sure that a lot of things I
>understand in a wrong way. For instance your passage:
>
>...if you get a cutoff, you have not checked for illegality on a bunch of
>moves...
>
>Maybe you want say that when you found a "cutoff" many moves will be useless to
>check for legality.
I'm not quite sure what you are trying to say, but I will rephrase it:
If a program generates 20 moves where it allows illegal moves (such as a pinned
knight is generated since you do not check to see if the king is in check after
moving the knight) and then it uses only 5 of those moves (due to a cutoff), the
program only had to check for legality for those 5 moves.
In my system, if you generate 20 moves, you know all 20 moves are legal already
since the move generator prevented illegal moves from being in the list in the
first place (such as a pinned knight moving).
>
>Anyway, from my side, only in some plies checking for legality of the king's
>moves goes at the end of the ply logic. In the logic, at the beginning, only
>legal moves beside the king moves are generated and alined. The most promissing
>goes first. Only if in those moves "cutoff" was never reached, king's moves are
>generated and revisioned. This help in cutting in checking the king's moves
>that are very expensive in "legality check".
Legality checking for the king is not TOO bad using bitboards, but you are right
in that it is more expensive then I want it to be.
You have to check the 3 to 8 squares around the king based on it's location.
Since I generate attack squares for the current position (i.e. which squares are
attacked by each side and how many times, etc.), I just check those 3 to 8
squares to see if they are attacked by an enemy piece. If so, the king is
prevented from moving in that direction. If not, then it cannot move in that
direction if a same color piece is there. If not, then it can move into the
square. Note: the attack squares structure keeps track of all attacks, including
those where the attack is in reality protecting a piece of the same color, so I
am using the exact same mechanism to see if the king can move into an empty
square or a square which contains a piece of the opposite color.
Overall, this takes from 3 to 8 ANDs, one table lookup (to figure out which 3 to
8 squares to check), from 6 to 16 conditionals, and some additions for the
indexing (i.e. to calculate row and columns from the byte returned from the
table). Overall, not that expensive. No too much more than most other pieces.
>
>>I do this in a sophisticated manner. I back away from the king in all directions
>>(using the bitboards) until I come to the next piece. If it of the same color, I
>
>I have strange impression that we are here more indentical that I thought at the
>beginning. Only you use bitboards that I never use. It could be that you are, in
>your own way, is explaining how you recollect data for checking the legality of
>all the moves (that are not the king's moves) before even generating them. And
>this is exactly what I do.
Sounds like we do something similar. My mechanism boils down to giving a one
byte "directions allowed" indicator to all pieces of the current color. If a
knight for example is pinned, it cannot move in any direction and the byte gets
set to zero. If a bishop is pinned by a bishop, it can only move in 2 directions
(maximum) (and the byte might be set to 5 for example, 1 bit for nw, 1 bit for
se). If a bishop is pinned by a rook, it cannot move (and the directions
indicator is set to 0).
>
>>then continue on the same row, column, or diagonal until I come to the next
>>piece. If it is of a different color and is a rook or queen (for rows and
>>columns) or a bishop or queen (for diagonals), I then eliminate certain types of
>>moves for the piece that was pinned. For example, a pinned bishop on a diagonal
>>can still move towards and away from the king, but not into the other
>>directions.
>
>Here I am a little bit lost but probably it is nothing but new wording that make
>me wonder. You look in all directions (after my understanding) like rook goes,
>like bishop and knight. You see, probably, in the same time what of your pieces
>that serve now as "human shield" could put in danger the king if they will
>change their place. In few words it is exactly how my logic works.
It works similar to my previous move generation bitmap explanation (several
posts up). Take the following for example:
. R . . n . k b
01000000 white row bitboard
00001011 black row bitboard
01001011 xor row bitboard
00001000 table1 lookup of xor row bitboard
(this table returns the next 1 bit over based on where the king
is located, for the direction I am checking)
00001000 table1 AND black row bitboard (is it a black piece?)
If this is equal to zero (i.e. this would have to be a white piece for this to
be zero), then there is no pin. Otherwise, save this value as you may need it
later.
01000011 table1 XOR xor row bitboard (I clear out the possible pinned piece)
01000000 table2 lookup (find the next piece)
01000000 table2 lookup AND white row bitboard (is it a white piece)
If this is equal to zero (i.e. black piece), then there is no pin.
If this is a white piece, then since we are checking a row, check the piece type
for the piece at that location to see if it is a "rook-like" piece (i.e. rook or
queen). If so, then a pin exists.
If a pin exists, set the pin directions for west and east for the pinned piece
(i.e. it cannot move nw, n, ne, se, s, or sw). The location of the pinned piece
was what was saved earlier 00001000.
Note: table1 and table2 access the same table, I just called them table1 and
table2 here to indicate that they are different lookups.
Overall, 2 ANDs, 1 XOR, and 3 conditionals maximum per direction or 16 ANDs, 8
XORs, and 24 conditions maximum to handle all pins. Of course, this maximum
would only occur if the king was in the middle of the board and had 8 pieces
pinned around him. Usually, it gets nowhere near this.
>
>>I do this before generating any moves, hence, each piece has directions of moves
>>which are allowed. All directions are allowed for non-pinned pieces, but only
>>certain directions are allowed for pinned pieces.
>>
>>Note: the problem with this approach is that you have to do special things for
>>EP moves.
>
>Here I am lost. What is EP move?
En-Passant.
> I wait until all moves are generated and then see if any were EP. If
>>so, then I go through special code to see if the EP taking pawn is pinned or the
>>combination of the EP taking and the EP taken pawns are pinned (i.e. you could
>>have a horizontal pin of both pawns where both pawns would be removed from the
>>row if the EP was allowed, but that would expose a king to check).
>>
>>And what is worse than this, I sort the moves before returning them. Actually,
>
>
>I miss completely this sentence: "I sort the moves before returning them."
I have a list of good and bad moves for the current position based on other
factors in my program. They consist of:
Pre-processor Good Moves
Killer Good Moves
Default Moves
Pre-processor Bad Moves
Killer Bad Moves
In order:
If the move is a PPGM (Pre-processor Good Move), it gets put into a PPGM array.
If it is a KGM, it gets put into a KGM array.
If it is a PPBM, it gets put into a PPBM array.
If it is a KBM, it gets put into a KBM array.
Otherwise, it gets put into a DM array based on the default order in which it
was generated.
I then create an overall array of moves whose order is based on PPGM first, KGM
second, DM third, PPBM fourth, and KBM last. Since I do SO much evaluation on a
given move, I want to get cutoffs as early as possible. Hence, I want to look at
moves that my pre-processor said should be good first, the killer moves in the
current portion of the tree second, etc. The last moves I want to look at are
ones which the current tree indicates are bad. If they were bad in a different
move order, then they are probably still bad.
Since it takes VERY little time to sort using this method (all of these arrays
are already sorted, you just have to stick the move in the proper slot), it does
not cost much (a single pass through each array at most per move).
>
>In general have now impression that we are probably very close. It could be that
>this impression is wrong. Problem is in my capabilty to recognize general
>picture from few details that you provide.
In the area of only legal move generation, I agree, we are probably close.
However, I doubt you are sorting your moves before returning them.
>
>Leonid.
>
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.