Author: leonid
Date: 15:17:59 02/09/00
Go up one level in this thread
On February 09, 2000 at 16:19:32, Heiner Marxen wrote: >On February 09, 2000 at 08:21:02, leonid wrote: > >>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. > > >Yes, I do that also. > > >>>>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. > > >Here, my approach (Chest) is quite different. I do not use bit boards, >but Chest has always actual attack information within each square. >The attacks are a set of pieces (at most 32), not a set of squares (64). Feel me lost. >To always have them, execution of a move must update this attack info, >what make it an expensive operation, but for me it pays off: In my logic when the moves are generated all the information is found on the spot. This make the move generator logic (I have two logics in my chess game) independent and help somehow in preventing the propagation of possible bugs during the game. >- whether a king may legally step to some target square is a simple test: > the attacks to that square must not contain any opposing piece. > No search for the bad guys: they already spread their effect into all > possible targets. (Exact details are a bit more complex) >- Whether or not there is a pin, can also be very cheap with attack information. > First, of course, there must be a geometric relation between the pinned > piece and its king. That can be done by simple test on the square indexes, > or a table lookup. When there is such a relationship, there must also > be an opponents attack in the square of the pinned piece. And that attack > must be from a B, R or Q. In my logic (I am afraid that I understand partially your explanation) checking the legality of the kings move is very simple. Just look in all direction and find if the king is not under the fire. When logic look to recollect the data about the legality of future non kings moves it goes the same way. Only this time it look not only if the king is under the direct fire but find also where king is protected by friendly pieces. 1) If king is under more that one fire. No use to look for the moves of not king itself. Go directly to look for the kings move. 2) King under the one fire. Use the data during the generation of the moves of not king in order of entering into certain square. When the friendly piece will enter there king will be under protection, or its personal offender will die instantly. 3) If king is not under direct fire and there are no "human shield", you are free to generate not verified non kings moves. This how it is done in my logic. >That does recognise most cases, where there is no pin. Chest goes one >step further: it also always has "indirect attacks" within each square. >An indirect attack does go through (X-rays) exactly one piece, and is >generated only for B, R and Q. Now, the test for being pinned consists >of a test, whether the direct attacks in the pinned piece AND the indirect >attacks within its king are not empty. > >This test can easily proove the non-existence of a pin. If the AND is not >empty, we are not yet sure that there really is a pin, but that can be >corrected. > > >>>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. > > >Yes! I have found this to be true for a mate solver, also. >Effective branching factor is very important. > > >>>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. > >Generating legal moves for a B, R or Q normally needs to look in 4 or 8 >directions. If the piece is pinned, that set of directions is restricted >down to the direction of the pin and its opposite. That result may turn >out to be empty, and the piece is skipped. After having restricted the >set of directions, no further work is necessary to avoid leaving a pin. > > >>>>>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. > > >You probably refer to me. I always avoid to write something twice, with >only small modifications. Either I use a macro, and expand twice, or I >write a parameterized function. As a principal. Improves maintainability. No. I spoke recently with one student from States. It wrote its really good chess game. He use color independent and ply independent logic. By speeking with him I found that my logic is more that far away from some games. But there are surpises. Recently I found that Rebel author, like me, generate all the legal moves in his game before using them. >>>>>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. > > >We all seem to effectively do similar things, albeit in a different way, >since our data is quite different. > >[snip] > >>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 special "logic for solving the mate containing position". It >>stay the same. > >For mate solving logic, at least for the last ply a special move generator >can be advantegous, since here we are only interested in those legal moves, >which have a chance to mate the opponent. Those moves, which surely do not >mate the opponent, can safely be discarded. E.g. if the king to be mated >has 3 or more flight squares, without any "indirect attack" in them, they >all must be attacked now by the piece to move. A pawn or knight cannot >do 3 or more of them: all moves of such pieces dropped. Inside of "mate logic" and "positional logic" I have special two plies that goes in particular way. They have few types of distinct moves generator, but this is exception of the rule. Once Hyatt said also that his first ply in done in special way, as well, for efficency. Leonid. >Heiner > > >>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.