Author: leonid
Date: 05:21:02 02/09/00
Go up one level in this thread
On February 09, 2000 at 00:36:04, KarinsDad wrote: >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. Now I understood. You check all your moves for legality, but few can check in only partial way. For some reason you can find that they are already illegal and more advanced revision are dropped. Like the fact that king is under the two fires is the reason of not generating the moves for not king pieces. When this happen you go directly to generate the moves for your king. Here if some move existe it could be only kings move. >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). Once again your move generator check the legality of the moves completely. It recollect the data that will be used for this revision (like my logic) even before the moves are produced. Sometime this data says to you that there are no use to generate certain moves. They will be illegal anyway. Pretty advanced. >>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. Maybe here you use the bitboard where they could be very helpful. For me three kings moves will ask as much time as generation of all the moves (not for king) and verification of their legality. I make my count in approximate way. One kings move take almost the same time (and logic resemble very much) as recollection of the data for legality of all not king moves. Second cheking for legality of the kings move will take as much time as the logic need to recognize what move will check the opposit king. And the last kings move will take as much time as generation of all the not king moves that must be check later for legality. >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. Your description is very close to mine way of doing this. It is all the time possible that I see in your description something that I know in my own logic. Anyway, to be sincere I even doubt sometime if I should even care that much about the efficency of the move generation. Until now, after verification, I have the impression that it is the the best branching factor that is the key of success. Success that likely is not on my side. >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. It sound good. I am not sure that my logic is that efficent. I am not sure at what speed checking of the kings legality goes, but total procedure should be around 700 lines of code. It must take some time to go through. Sorry, it is not true. Inside of those 700 lignes must be added some next 100 lines that calculate hidden length of macros. >>>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). I believe that we really have very similar logic. This is very interesting since this part of my game was done when I was completely alone in my writing. Contact by Internet came later. So people, finally, come sonner or later to the same logic pattern when they create the same mechanism. Difference boils down to some minor sofistication of this or other part of this mechanism in order to speed it up. >>>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 Did you wrote the logic (for the sake of higher speed) that do work only for certain color or some kind of general logic? In mine not only generation of the moves have color attached logic but even all the logic is split in two. When I spoke before with one programmer he said me that he use logic that is color independent. >>>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. Must try it some day. Only this way sound to me as memory expensive. Could be good to try it when I will move to the "memory indifferent" system. For now it is done for DOS. >>>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. This is true. "En passant" I even don't care that much to have special extra brain. Since it is so rare, in general moves number, it is verified in the most primitive way. Move is deposed on the board and king is verified for "sustained injury". >> 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, When I found that after stistics "en passant" have very little impact on the speed of the logic, I dropped all the code complicated procedures. But maybe you way give some modest but real speeding. >>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 Here I do come back to my impression that "our logics are quit different". It is funny that this is so usual. In one instance you feel that two logics are the same and the next one that they are completely apart. In my logic actually I care only about "shield pieces" to be moved. "Shield piece" - piece that have behind enemy fire. All those "shield" I find in "data collection". And if the king is under the one fire (if two fires there are no moves for the pieces beside king) is to see where friendly piece must enter in order to defend the king. >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. What is the Pre-processor Good Move? >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. You want to say aligning your moves before returning them from moves generator? All my moves are 100% ply independent. They are produced in the same way for every ply and in the same manner for two logics. Move generator was created at the beginning for speecial "logic for solving the mate containing position". It stay the same. Leonid >>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.