Zach Wegner wrote:It's already getting interesting--since AFAIK there's no open source legal move generators, I have to just make it up.
Well, there may be no open source legal-only move generators in C/C++.
But in the snippets thread I've been posting Common Lisp versions for legal-moves-only generators (five classes: not-in-check, evasion, gainer, holder, checking) along with move counting and mate detection routines.
The mate solver chest has a legal move generator and it is open source program.
Gerd Isenberg wrote:Looking for pinned pieces for both sides can be combined with finding discovered checks for both sides if you use fill-stuff. Also, if side not to move has discovered (or even double) check at the tips we may reconsider standing pat with static eval >= beta.
Yes, I was thinking along these lines. I'm still thinking it through in my head, but I'm going to make 4 sets of bitboards for pieces pinned in each direction. I suppose to determine discovered/double checking status I will create these for both sides (i.e. pieces pinned against both kings). I might do this with a fill-based approach. I had considered it, but I'm not sure if there would be much difference. The loop method is likely fast, but IMO ugly. Fill techniques would likely be ugly too, as I have a method that takes direction as an enum. Each direction requires two fills that correspond to both positive and negative directions. This I suppose I would do with a table of function pointers.
So once you have these bitboards, you can determine which pieces can move in that direction by ANDing every other direction's pin set. Discovered checks are determined by whether a piece is pinned against the opponent king, and regular checks are determined by a regular attack set union.
I'm still not sure how I'd like to integrate this into my current setup. If I determine checking status of moves, it makes little sense to make in_check() calls elsewhere. I suppose in your case you get it for free though. Perhaps I will start keeping direction-based attack sets around, so that I get it for free.
sje wrote:Well, there may be no open source legal-only move generators in C/C++.
But in the snippets thread I've been posting Common Lisp versions for legal-moves-only generators (five classes: not-in-check, evasion, gainer, holder, checking) along with move counting and mate detection routines.
Ha, I knew there would be someone to correct me. I suppose I should've said "bitboard-based legal generators in C", but even then I'm not sure.
The main point is that I haven't seen one before, so I don't really have an example to go on.
Tord Romstad wrote:Delta pruning is the same as futility pruning, isn't it? I never futility prune checks (neither in the main search nor in the quiescence search), and it doesn't seem to hurt my branching factor much. Futility pruning of checks doesn't make sense at all, IMHO.
Tord
Basically. The difference between futility and delta pruning (as I define it...) is that a SEE value is used for the material gain instead of a simple material difference, and the move is also pruned if SEE<0.
I would guess that you don't search captures in qsearch with SEE<0? I don't, and logically you should also do the same to non-capture checks (searched after every capture).
Thanks for the clarification! You are right, I do prune checks with SEE<0. In fact I prune even discovered checks with SEE<0, which is stupid, because the SEE value is usually totally irrelevant for such checks. I should fix this some day.
Tord
Good point, in fact, and I actually generate the checks in two passes, direct first, discovered second, although it is possible that a direct check is also a discovered check. I don't generate them twice, but it would be at the front. I was thinking about a pointer to the first of the discovered checks (if more than one) and not SEEing those at all...
something to think about, although it is probably a tiny issue in reality.
I wonder why this order of generating.
It may be better to generate discover checks first because there are more dangerous and it may be logical to try them first.
Uri
Simple. 99.999% of all moves are refuted by a drect capture of the moving piece. This is why the only move that is searched prior to winning captures in normal search is one suggested by the hash table, which is quite often a capture. I don't want the most dangerous move ordered first. I want the move with the highest probability of causing a fail-high, and which requires the least amount of effort to do so, to be searched first. Often many moves will fail high, and in general a capture is the cheapest thing to try.
Tord Romstad wrote:Thanks for the clarification! You are right, I do prune checks with SEE<0. In fact I prune even discovered checks with SEE<0, which is stupid, because the SEE value is usually totally irrelevant for such checks. I should fix this some day.
Tord
Well, I'm actually way behind in this respect. My check generator doesn't even generate discovered checks (I went for simplicity mainly), and I don't look to see if a move is a check (discovered or not) before pruning it.
I have been looking into this matter in the past few days though. I wanted to set a flag in the move if it gives check, to use in pruning/reduction decisions. On a related note, I figured I'd bite the bullet and switch to legal move generation. It's been a while since I did that, and it can be ugly, but perhaps I can make it clean and efficient. It's already getting interesting--since AFAIK there's no open source legal move generators, I have to just make it up. I inevitably have more fun programming when that happens.
Crafty has had one for years (GenerateCheckEvasions()) if you are talking about generating legal moves when escaping check.
bob wrote:Crafty has had one for years (GenerateCheckEvasions()) if you are talking about generating legal moves when escaping check.
I have too, but I'm talking about pure legal. I'm considering even taking out my evasion generator if I can easily integrate it with the regular generator. We'll see about that though...
bob wrote:Crafty has had one for years (GenerateCheckEvasions()) if you are talking about generating legal moves when escaping check.
I have too, but I'm talking about pure legal. I'm considering even taking out my evasion generator if I can easily integrate it with the regular generator. We'll see about that though...
I personally don't think the cost is offset by the gain. most moves are legal, and it is, IMHO, better to delay verifying the legality until the very last minute, because you might not even search the move at all.
bob wrote:Crafty has had one for years (GenerateCheckEvasions()) if you are talking about generating legal moves when escaping check.
I have too, but I'm talking about pure legal. I'm considering even taking out my evasion generator if I can easily integrate it with the regular generator. We'll see about that though...
I personally don't think the cost is offset by the gain. most moves are legal, and it is, IMHO, better to delay verifying the legality until the very last minute, because you might not even search the move at all.
The payoff analysis depends on the other components of the program. For example, if pinned/frozen bitboards by color are used only during move generation and nowhere else, then maybe a legal only generator will be slower than the alternative of just in time legality checking.
But consider the case where pinned/frozen data is used for other tasks than only move generation. It can be quite helpful with improving an exchange evaluator. Pin status detection can also be used to refine positional evaluation, and a move ordering scheme could use pin data as well. A sophisticated program might use pin bitboards to work towards short term tactical goals.
bob wrote:Crafty has had one for years (GenerateCheckEvasions()) if you are talking about generating legal moves when escaping check.
I have too, but I'm talking about pure legal. I'm considering even taking out my evasion generator if I can easily integrate it with the regular generator. We'll see about that though...
I personally don't think the cost is offset by the gain. most moves are legal, and it is, IMHO, better to delay verifying the legality until the very last minute, because you might not even search the move at all.
I'm not so sure. Generating legal moves has a relatively small constant cost, while you have to verify every move for legality. The bitboard functions required for legal move generation are small--I'd guess they cost the same as a few in_check()s. Because you're going to average several moves searched each time, it's not clear which approach will be faster.
And as Steven points out, there are benefits in other aspects of the program. The information I generate in order to ensure move legality I also intend to use for evaluation, move ordering, extensions, reductions, and pruning.
Gerd Isenberg wrote:Looking for pinned pieces for both sides can be combined with finding discovered checks for both sides if you use fill-stuff. Also, if side not to move has discovered (or even double) check at the tips we may reconsider standing pat with static eval >= beta.
Yes, I was thinking along these lines. I'm still thinking it through in my head, but I'm going to make 4 sets of bitboards for pieces pinned in each direction. I suppose to determine discovered/double checking status I will create these for both sides (i.e. pieces pinned against both kings). I might do this with a fill-based approach. I had considered it, but I'm not sure if there would be much difference. The loop method is likely fast, but IMO ugly. Fill techniques would likely be ugly too, as I have a method that takes direction as an enum. Each direction requires two fills that correspond to both positive and negative directions. This I suppose I would do with a table of function pointers.
So once you have these bitboards, you can determine which pieces can move in that direction by ANDing every other direction's pin set. Discovered checks are determined by whether a piece is pinned against the opponent king, and regular checks are determined by a regular attack set union.
I'm still not sure how I'd like to integrate this into my current setup. If I determine checking status of moves, it makes little sense to make in_check() calls elsewhere. I suppose in your case you get it for free though. Perhaps I will start keeping direction-based attack sets around, so that I get it for free.
I do it all almost branchless with SIMD quadbitboards. Some bitboards are valid from initialization until first make or makenull only, as semantically noted by some kind of embedded scratch class in my tree object. That is fine for eval and movegen init.
As member of a stack, each ply has 16 legal move-target bitboards (yes, eight for knight, but no other movelist) + some book-keeping and stage of plausible mg (switch monster). The nice thing, the calculation hides the hash latency while calculating attacks (using prefetch), pinned and discovered checkers, and the fixed sized legal movelist. For none simd approaches I am not sure - probably too slow, even with x86-64. I guess this is really a SIMD domain. Of course I use a SSE2 wrapper class, which might be done with other SIMD-architectures as well. The whole approach has some taste of a hardware generator.
I keep let say Inter[dir8] = MetaKingAtta[dir8] & OppoSlider[oppodir8] as a union. It is either empty (most likely), may contain a pinned piece (same color as king), a potental discovered checker (other color), or in case of distant check all empty squares between king and checking slider. In check is for free.
