checks in q-search.

[Dirt]

Code: Select all

Rank Name               Elo    +    - games score oppo. draws  ---------LOS----------
   1 Glaurung 2.1       181    5    5 20270   77%   -33   17%     100100100100100100100
   2 Fruit 2.1           68    5    4 20260   64%   -33   23%    0   100100100100100100
   3 opponent-21.7       27    4    4 20263   59%   -33   33%    0  0    99100100100100
   4 Glaurung 1.1 SMP    13    5    5 20261   56%   -33   21%    0  0  0   100100100100
   5 Crafty-22.2        -30    5    5 23504   43%    20   22%    0  0  0  0    67 99100
   6 Crafty-22.2R2      -32    4    4 38910   43%    20   22%    0  0  0  0 32    99100
   7 Crafty-22.2R1      -37    4    4 38909   42%    20   23%    0  0  0  0  0  0   100
   8 Arasan 10.0       -190    4    5 20269   29%   -33   19%    0  0  0  0  0  0  0   

To answer your question elsewhere, I'd never seen the tables side by side before, and I could not have told you how best to do it. It looks good, though.

[bob]

Code: Select all

Rank Name               Elo    +    - games score oppo. draws  ---------LOS----------
   1 Glaurung 2.1       181    5    5 20270   77%   -33   17%     100100100100100100100
   2 Fruit 2.1           68    5    4 20260   64%   -33   23%    0   100100100100100100
   3 opponent-21.7       27    4    4 20263   59%   -33   33%    0  0    99100100100100
   4 Glaurung 1.1 SMP    13    5    5 20261   56%   -33   21%    0  0  0   100100100100
   5 Crafty-22.2        -30    5    5 23504   43%    20   22%    0  0  0  0    67 99100
   6 Crafty-22.2R2      -32    4    4 38910   43%    20   22%    0  0  0  0 32    99100
   7 Crafty-22.2R1      -37    4    4 38909   42%    20   23%    0  0  0  0  0  0   100
   8 Arasan 10.0       -190    4    5 20269   29%   -33   19%    0  0  0  0  0  0  0   

To answer your question elsewhere, I'd never seen the tables side by side before, and I could not have told you how best to do it. It looks good, though.

I did it in a small (20 line) C program that executes BayesElo twice and then combines the output...

[Pradu]

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.

Buzz uses legal move generators for everything (Regular moves, Qsearch, Qsearch-Checks, Check Evasions...). Everything is rather fast with little overhead above pseudo-legal move generation... except generating king moves. I still have to come up with an idea to generate king moves efficiently...

[bob]

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.

But there's the fallacy. I don't have to do that. I generate _way_ more moves than I search, thanks to beta cutoffs. That's why I prefer the slightly _less_ efficient scheme of testing for legality as I make 'em, because many times I don't have to make them at all.

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.

If the information is useful somewhere else, then things change. But the idea of generating legal-only moves, by itself, sounds like it might be somewhat less efficient, although how much is debatable.

[Zach Wegner]

But there's the fallacy. I don't have to do that. I generate _way_ more moves than I search, thanks to beta cutoffs. That's why I prefer the slightly _less_ efficient scheme of testing for legality as I make 'em, because many times I don't have to make them at all.

Are you sure? I just made two quick measurements in the starting position: one for just the main search, and one for both the main and quiescent search. For the main search there were an average of about 27 moves generated for each move generation, and an average of 7.5 actually made. In the qsearch it shows an average of 4 moves generated and 2 made. I'd expect the proportion to get bigger in the middle game and smaller in the endgame. So it's not exactly clear cut. If you could make a legal move generator that had an extra cost of 2 in_checks(), then you'd have it equally fast. I would tend to say that it seems difficult but possible.

The issue isn't easy though. I don't think legal move generation has been explored to the extent that other types of generation have. It's possible that it could even be faster.

If the information is useful somewhere else, then things change. But the idea of generating legal-only moves, by itself, sounds like it might be somewhat less efficient, although how much is debatable.

Indeed. I really don't know which way is better. I think it should be possible to design a legal move generator with a comparable speed to a pseudo legal generator. I don't know if it's been done, but I want to try myself.

OTOH I wouldn't really bother with legal move generation, except for the other aspects. It is definitely more complex.

[Zach Wegner]

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.

Buzz uses legal move generators for everything (Regular moves, Qsearch, Qsearch-Checks, Check Evasions...). Everything is rather fast with little overhead above pseudo-legal move generation... except generating king moves. I still have to come up with an idea to generate king moves efficiently...

I actually read that earlier today in an old WB forum thread. I'll definitely check it out--though I will wait until after I implement mine before I look.

[grant]

Zack

Did you read this post by HG?

What I meant was that you could also start the other way around:
Code:
r = rookAttacks(oppositeRooksOrQueen, kingSquare);


followed by
Code:
index = pinMagic[kingSquare]*(occupancy&r)>>52;
switch(index)
{ // 4096 case labels, of only a few different kinds
case DOUBLE_CHECK:
p = possibleSafeEvasionSquares[index];
....
case DISTANT_CHECK:
p = checkRay[index];
....
case CONTACT_CHECK:
p = checker[index];
....
case PIN:
p = pinned[index];
....
}


I guess it would not work with normal rookAttacks, as you would only want to have rays in the set where there actually is a slider at the end. But you could tabulate those as well, of course. (I have no idea if 12 bits would be enough, of course.)

http://64.68.157.89/forum/viewtopic.php ... t&start=90

I am trying this at the moment. It is a very good idea.

Grant

[bob]

But there's the fallacy. I don't have to do that. I generate _way_ more moves than I search, thanks to beta cutoffs. That's why I prefer the slightly _less_ efficient scheme of testing for legality as I make 'em, because many times I don't have to make them at all.

Are you sure? I just made two quick measurements in the starting position: one for just the main search, and one for both the main and quiescent search. For the main search there were an average of about 27 moves generated for each move generation, and an average of 7.5 actually made. In the qsearch it shows an average of 4 moves generated and 2 made. I'd expect the proportion to get bigger in the middle game and smaller in the endgame. So it's not exactly clear cut. If you could make a legal move generator that had an extra cost of 2 in_checks(), then you'd have it equally fast. I would tend to say that it seems difficult but possible.

The issue isn't easy though. I don't think legal move generation has been explored to the extent that other types of generation have. It's possible that it could even be faster.

If the information is useful somewhere else, then things change. But the idea of generating legal-only moves, by itself, sounds like it might be somewhat less efficient, although how much is debatable.

Indeed. I really don't know which way is better. I think it should be possible to design a legal move generator with a comparable speed to a pseudo legal generator. I don't know if it's been done, but I want to try myself.

OTOH I wouldn't really bother with legal move generation, except for the other aspects. It is definitely more complex.

That looks like what I was saying. You made about 1/4 of the moves generated. Which means you would waste about 3/4 of the overhead of generating legal mvoes vs testing as they are made. How that works out in terms of cost I couldn't guess without seeing code. I don't maintain any sort of "pinned pieces" information, and not moving the king to squares under attack would be yet another issue...

[bob]

But there's the fallacy. I don't have to do that. I generate _way_ more moves than I search, thanks to beta cutoffs. That's why I prefer the slightly _less_ efficient scheme of testing for legality as I make 'em, because many times I don't have to make them at all.

Are you sure? I just made two quick measurements in the starting position: one for just the main search, and one for both the main and quiescent search. For the main search there were an average of about 27 moves generated for each move generation, and an average of 7.5 actually made. In the qsearch it shows an average of 4 moves generated and 2 made. I'd expect the proportion to get bigger in the middle game and smaller in the endgame. So it's not exactly clear cut. If you could make a legal move generator that had an extra cost of 2 in_checks(), then you'd have it equally fast. I would tend to say that it seems difficult but possible.

The issue isn't easy though. I don't think legal move generation has been explored to the extent that other types of generation have. It's possible that it could even be faster.

If the information is useful somewhere else, then things change. But the idea of generating legal-only moves, by itself, sounds like it might be somewhat less efficient, although how much is debatable.

Indeed. I really don't know which way is better. I think it should be possible to design a legal move generator with a comparable speed to a pseudo legal generator. I don't know if it's been done, but I want to try myself.

OTOH I wouldn't really bother with legal move generation, except for the other aspects. It is definitely more complex.

That looks like what I was saying. You made about 1/4 of the moves generated. Which means you would waste about 3/4 of the overhead of generating legal mvoes vs testing as they are made. How that works out in terms of cost I couldn't guess without seeing code. I don't maintain any sort of "pinned pieces" information, and not moving the king to squares under attack would be yet another issue...

[sje]

Here is the code in the "not-in-check" move generation function from the CIL Toolkit for generating moves by a sweeper piece:

Code: Select all

          ((is-piece-sweeper? fr-piece)
            (let ((to-bb (bb-and2 atk-fr-sq-bb target-bb)))
              (when (sq-set? rstrct-bb fr-sq)
                (bb-and2d to-bb (fetch-beamer-bb act-king-sq fr-sq)))
              (loop-bb (to-bb to-sq)
                (push (mm-capt fr-sq to-sq fr-man (get-man board-vec to-sq)) result))))

Where is the pinned calculation overhead here? It's just one bit test plus one bitboard mask, and this happens only once per slider piece:

Code: Select all

              (when (sq-set? rstrct-bb fr-sq)
                (bb-and2d to-bb (fetch-beamer-bb act-king-sq fr-sq)))

The symbol rstrct-bb has the restricted bitboard value; this is the bitboard produced only once per move execution that contains the pieces that are pinned against the king but are not frozen. (Frozen pieces are pinned pieces that are pinned along a direction in which they can't move.) The pinned and frozen bitboards themselves are also computed once per move execution.

A beamer bitboard is the set of squares that is the open ray from the first square in the first square to second square direction.

At the start of move generation, the bitboard of active color piece locations is masked by the frozen bitboard, so the from-square scanner loop doesn't even do a dispatch.