Author: Heiner Marxen
Date: 16:01:01 12/30/01
Go up one level in this thread
On December 29, 2001 at 17:32:41, leonid wrote: >Hi, Heiner! Hi Leonid! >I already wrote my response to this portion when I felt that I am not sure if >what I wrote is right. Some description of mate solver corresponded to chess >playing part. Confusion probably came from the fact that I was very little with >my mate solver for the last 4 years. Each time when went back was for putting >into it something that I had already in chess playing program. Will later >indicate where exactly was my mistake. > > >>For white moves this is the only sorting I do: pulling checking moves to the >>front of the list. > >This is very intereting part. Waht exactly you mean when you say "white moves"? >Probably you wanted to say for the side that should find mate. Yes. Chess problems are normally stated as "white to move and mate in N moves", so it is sometimes shorter and easier to read to just say "white" where is meant "the side to do the mate", and "black" instead of "the side that is to be mated". Sometimes I use "attacker" for the side to mate and "defender" for the side to be mated, but this is not standard terminology. > Do you really >have attacking and defending side going into different move sorting (alignment)? Yes. Sorting defender moves can become expensive, and for the attacker I do normally not expect any speed up from sorting, since most of the time anyhow all attacker moves are to be searched. OTOH, the above is not always true. We have had positions in this forum (at least one from you) where attacker sorting could have made a significant difference. But that is comparatively rare. >In my program (never mind what side was initially asked to look for mate) all >"move sorting" for two colors (for two move sortings) goes in identical way. >Reason for identical search (at least in my mind) is in the fact that defending >side also will look for many possible mates during entire search. Each time when >"defensive side" will respond with mate, offensive side will stop searching. >This will speed entire hunt for mate. Aha! I see! That is what I call the "anti" heuristic, although in Chest it is very limited (to immediate mate moves). >>> No material evaluation ever done but something close to this >>>exist. Just after "first alignment" that was done in move generator (checking >>>moves are put there as first to go) come second aligment. >> >>It is most probably more efficient to do this already as part of the >>move generator (I have done that many years ago). Currently Chest does it >>as a separate function, to make the move generator less complex. > >I found that it was more effective for me to do both things inside of one move >generator. Move generator mate a search for general vulnerability for opposit >king and use this data later during the production of all legal moves. > >I do have other specialized move generators but the above generator is the most >in demand. It is identical for mate solver and chess playing part inside of my >program. > >>> Each move that take >>>some enemy piece, or make promotion, is aligned after expected gained value in >>>very rough way. For instance, taken of knight and bishop are not differentiated. >>>Taken of queen and every pawn promotion is regarded as equal. >> >>Well, yes, that is similar to what I do for black moves. >>Capturing yields the usual material values, and checking is like capturing >>a rook. The amount of flight squares around the black king is also used: >>each flight is worth a pawn. > >Have nothing like your attention to "flight squares" around the king. It could >be that here is the point that make speed difference for us in lower plys but it >could be something else. I think this will make (part of) the difference. Escapes (flight squares) are easily recognized in Chest, once a move is executed, since as part of the board all attack sets are updated. An empty square beneath the king is not a legal escape, if the enemies attack set is non-empty in that square: that is just a test of a 32-bit int. >>If the depth is greater than 2, much more complicated things are done. >>Checking moves are differentiated whether they give away material or not, >>and the branching factor for white in the next two moves is estimated, >>in order to minimize their product. > >Completely different! Yes, I expected you to say that :-) >>> On the most responsive plys >> >>"most responsive" is near the leaves? > >I am afraid to make my next mistake, even if I have seen already few times this >expression. For me "most responsive" plys are the plys on other side from >initial position of search. The most specialized are that bottom two plys. In >total they are 6. Ok, so I guessed right. >>> two best moves are saved and used for "second aligment". One >>>move is "active" and second is "passive". Active move - move that is ckecking >>>move, or one that bring material advantage. Passive move - move other that >>>active. > >Here was my mistake! For mate solver second sorting put active at the head and >passive at the end, just like was said, but best move is only one. In chess >playing part I have separate savings for active and passive move. > >>Is that some king of "killer move" heuristic? > >Here once again I must take care. Will give rustic and simple explanation. Best >move in mate solver is the move that lead to mate. Previously found best move is >used for putting the most successful at the head of chain. Each best move for >its ply. Here also one important moment. If previous best move was "passive >move" it will not jump to the head of move chain over "active moves". It will go >only at the head of passive moves. That really sounds like a (special sort of) killer heuristic. >>How exactly are these moves "used"? >>What exactly triggers the saving of another move (replacement)? > >Only when next move that lead to mate for this ply ply was found. Only then >previous best move will be replaced. So a defensive move only is remembered as "best active" move, if it does mate the attacking side? Sounds a bit restrictive. While it may help in many of your crowded many-queen positions, in more quiet positions (say typical chess problems) this will be extremely rare, I think. >>I don't have such a thing. Might be worth trying. > >It could be that my previous explanation was obscure. Now it is exact and I hope >more clear to read. Yes, thanks, it is much clearer now. >>>Is this really close to what you have? >> >>It matches my basic sorting, yes. >>With more depth to go, Chest's function is much more complex, and not >>easy to explain. It is a little "magic" in that function. >>For white's moves you appear to do a bit more than I do. > >Probably here you speak about attacking side but not about white side. Yes, correct. Sorry for the confusion. >>>Even if I wanted few times to read what you have done, I still never make my >>>reading. Partially it is because I am lazy for every possible reading but even >>>more so because I don't remember any more C language. >> >>Even if you were fluent in C, and would have the time and motivation to read >>it, I doubt you would understand much of it just from the sources. >>I myself have a hard time to re-read it. :-( > >Ha, ha, ha!!!! It look like myself going to some parts of my program that I not >touched for years. Very often it is very obscure to me what I wrote there. This >is why I leave a lot of description. ... which only helps if that description contains more detail than just "it works best this way" :-) > Problem only when you change it one >thousand of times. Finally some old description is left and make everything very >strange when you read it. Yes. Know that: an outdated comment can be worse than no comment. >>My co-author Holger Pause developped the complex part of this move sorting >>by try and error, until he was satisfied with the results for a certain >>benchmark. That way some of the things in it are hard to explain, beyond >>"it works well that way". > >All my move sortings was done only after statistical data. Nothing was left to >my personal preferences. Even my mistake about "best passive" and "best active" >in my mate solver, probably, come from the fact that I tried them in mate solver >but came later to something else. Respect! That is the best way to do it: first measure, then decide. Scientific. Sometimes I do not do a complete measuring (too lazy), and even if I do, I often do not document the results of my experiments in a way that can be understood years later. :-( Well, it is not rocket science, it is just for fun :-) A happy new year to all of you! Heiner
This page took 0.01 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.