QS code

[Uri Blass]

I looked at Bruce Morlands site, and he does

Code: Select all

val = Evaluate();
if (val >= beta) return beta;
if (val > alpha) alpha = val;

at the start of the node, instead of what I was doing...(raising alpha if its not in check, and there were no captures made).


So, now I need to decide on something better than captures on last_to square.
Previously I examined all captures, and it was much slower in reaching any good depth. But I didn't have any MVV/LVA ordering on the captures, which is one reason the tree exploded.

I'm not sure if I should generate all captures, and order them, or just some. I feel that if I don't generate all then hanging pieces may be overlooked, but is it worth just generating some of the captures(I don't know which) so that the lack of accuracy gives a greater depth of search, and overall better performance?

Thanks

You can generate only captures of pieces that are heavy enough to raise the score above alpha.
This is what strelka is doing and strelka's qsearch does not generate all captures.
1)pawns captures are not generated if the score is smaller than alpha - 250
2)knight or bishop captures are not generated if the score is smaller than alpha-450
3)rook captures are not generated if the score is smaller than alpha-650
4)queen captures are not generated if the score is smaller than alpha-1050

Note that Movei does not make captures in similiar conditions but strelka is smarter and save time relative to movei because it even does not generate them in the first place.

I did not read the code of most free source programs so I do not know if not generating captures that are not high enough is used in other free source programs.

Uri

[Guetti]

MVV/LVA is all you need at the beginning, you can add a static exchange evaluation later. And it is really simple, all the information for MVV/LVA is usually already stored in the move anyway (i.e. moving_piece, captured_piece). I even do this directly in the special captures move generator.

enum piece = {NONE, PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING};
const int value [6] = {0, 100, 300, 330, 500, 880, 99999}; // or whatever

score = value[captured_piece] - moving_piece;

[Gerd Isenberg]

enum piece = {NONE, PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING};
const int value [6] = {0, 100, 300, 330, 500, 880, 99999}; // or whatever

score = value[captured_piece] - moving_piece;

Nice bug

[Guetti]

enum piece = {NONE, PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING};
const int value [7] = {0, 100, 300, 330, 500, 880, 99999}; // or whatever

score = value[captured_piece] - moving_piece;

Nice bug

Yes, but it was only for demonstration out of my head.
I program to much, now I start to count things already with zero.
0, 1, 2, 3, 4, 5, 6, perfect, there are six pieces.

[Guetti]

By the way, actually it is not a bug, but a syntax error, because no compiler, except MSCV perhaps, would compile it.
I just should get used to the current ways, and write it as

const int value [] = {0, 100, 300, 330, 500, 880, 99999};

but then, I'm not used to this new standards.

[cms271828]

Thanks, I don't quite get it though, do you mean something like this:

Code: Select all

int QS(int alpha, int beta)
{
    val = Evaluate();
    if (val >= beta) return beta;
    if (val > alpha) alpha = val;

    MOVES=GenerateAllCaptures();
    OrderMovesByMVVLVA(MOVES);

    for(each MOVE in MOVES)
    {
        if(val+Value[capturedPiece]+MARGIN < alpha ) continue
       
        MakeMove();
        val = -QS(-beta, -alpha);
        UndoMove();

        if (val >= beta)return beta;
        if (val > alpha) alpha = val;
    }

    return alpha;
}

What would the value of MARGIN be? Is it constant for each type of piece?

Thanks

[bob]

The advantage of this method is that it is much faster than a full qsearch. Since, as you say, qsearch is inherently inaccurate, e.g. in your example, if the static evaluation is above beta, you would stand pat and fail high even if your queen is hanging. We would need to test to see whether the speed would make up for the inaccuracy.

The problem is, I have already run that test. And the answer is "captures on last square is way too inaccurate." Way back in the 70's, I first tried that idea, and it was certainly better than just stopping the search when target depth was reached. But adding a normal q-search was significantly better overall. I've re-tested the idea more than once since, but each time it has hurt significantly...

[Tony]

Thanks, I don't quite get it though, do you mean something like this:

Code: Select all

int QS(int alpha, int beta)
{
    val = Evaluate();
    if (val >= beta) return beta;
    if (val > alpha) alpha = val;

    MOVES=GenerateAllCaptures();
    OrderMovesByMVVLVA(MOVES);

    for(each MOVE in MOVES)
    {
        if(val+Value[capturedPiece]+MARGIN < alpha ) continue
       
        MakeMove();
        val = -QS(-beta, -alpha);
        UndoMove();

        if (val >= beta)return beta;
        if (val > alpha) alpha = val;
    }

    return alpha;
}

What would the value of MARGIN be? Is it constant for each type of piece?

Thanks

Yep, looks good.

You can make MARGIN very sophisticated (different for pieces, different for normal pawns, passed pawns etc) but to start 1.5 pawns should do the trick.

Normal search, simple eval and this kind of qsearch together should give you a stable and predictable engine.

Now for something that took me years to understand: (well, not the first part) Implement Winboard or UCI protocol.
Then you can
a) let the engine play (90min/game) and have a look where it goes wrong, misses knowledge etc and
b) after every change, have it run overnight against a couple of engines to see if this new version is stronger. (1min/game should do it)

This all should also give you a change to have alpha-beta "sink in". Once you understand it, it is difficult to understand that you didn't understood it, but till that time it's like hanging on to a train with your fingertips.

Tony

[Gerd Isenberg]

enum piece = {NONE, PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING};
const int value [7] = {0, 100, 300, 330, 500, 880, 99999}; // or whatever

score = value[captured_piece] - moving_piece;

Nice bug

Yes, but it was only for demonstration out of my head.
I program to much, now I start to count things already with zero.
0, 1, 2, 3, 4, 5, 6, perfect, there are six pieces.

Oups, sorry. I assumed it should be

Code: Select all

score = value[captured_piece] - value[moving_piece];

for a very poor man's SEE to capture non enprise pieces

[Guetti]

enum piece = {NONE, PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING};
const int value [7] = {0, 100, 300, 330, 500, 880, 99999}; // or whatever

score = value[captured_piece] - moving_piece;

Nice bug

Yes, but it was only for demonstration out of my head.
I program to much, now I start to count things already with zero.
0, 1, 2, 3, 4, 5, 6, perfect, there are six pieces.

Oups, sorry. I assumed it should be

Code: Select all

score = value[captured_piece] - value[moving_piece];

for a very poor man's SEE to capture non enprise pieces

Hm, but MVV/LVA is
score = value[captured_piece] - moving_piece;

PxQ > RxQ
meaning (980 - 1) > (980 - 4)
correct?