Sorting Captures

[bob]

In Isa , I do the move ordering like this :

Code: Select all

int move_ordering(int type, int dep, int arr)
{
    int val = 0;

    if(type == PROMO_DAME)
        val = 4000000;
    else if&#40;type >= PROMO_CAVALIER && type < PROMO_DAME&#41;
        val = &#40;2000000 + valeur_piece&#91;type&#93;);
    if&#40;probe_move_ordering&#40;dep, arr, prof&#41;)
        val += 1000000;
    if&#40;type == CAPTURE&#41;
        val = &#40;3000000 + &#40;valeur_piece&#91;piece&#91;arr&#93;&#93; - valeur_piece&#91;piece&#91;dep&#93;&#93;));
    else
    &#123;
        if&#40;killer1&#91;prof&#93;.from == dep && killer1&#91;prof&#93;.dest == arr&#41;
            val +=  2000000;
        else if&#40;killer2&#91;prof&#93;.from == dep && killer2&#91;prof&#93;.dest == arr&#41;
            val += 1500000;
        else
            val += history&#91;dep&#93;&#91;arr&#93;;
    &#125;

    return val;
&#125;

You can see the promotions are ahead , then the hash move , then MVV / LVA with pieces values , no index (wrong?)
Then killer 1 and 2
Then history value

I use high values because the max value of history is 999999
So , with my scheme , q x q = 3000000 and pxr = 3000400
Ok I'm certainly doing something wrong

That's a different issue. We were only talking about ordering captures. My ordering goes like this:

(1) hash move
.. generate only captures ..
(2) captures in MVV/LVA order where SEE says they don't lose material (those are searched later)
(3) killer moves (2 from current ply, 2 from two plies back)
(4) counter moves (2)
(5) paired moves (a heuristic from early 80's, don't recall who proposed it, but basically this is a killer move that is only applicable when a specific move was played two plies back. IE Ng5/Nf7 where Ng5 enables Nf7...
.. generate non-captures ..
(6) if remaining depth >= 6 plies, I search 1/2 of the remaining moves based on history ordering
(7) rest of moves

I added counter and paired moves specifically because of LMR, as this puts a few good moves early in the list where they get reduced less.

[mjlef]

I will give away a tiny secret in Komodo. If you always generate your moves in the order Px then Nx then Bx then Rx then Qx then Kx, then assign score based on what they are capturing, then always use a stable sort, then move ordering will always be in the correct MVV LVA order. This is because you generate pawn captures first and so on and the stable sort will not put an say Q being captured ahead in the list (stable sorts work this way). It saves a little time you would have to spend "subtracting" the piece doing the capturing from the value you assign to the piece being captured. You get the same move ordering in a little less time.

Mark

[AlvaroBegue]

I will give away a tiny secret in Komodo. If you always generate your moves in the order Px then Nx then Bx then Rx then Qx then Kx, then assign score based on what they are capturing, then always use a stable sort, then move ordering will always be in the correct MVV LVA order. This is because you generate pawn captures first and so on and the stable sort will not put an say Q being captured ahead in the list (stable sorts work this way). It saves a little time you would have to spend "subtracting" the piece doing the capturing from the value you assign to the piece being captured. You get the same move ordering in a little less time.

Mark

Can you even measure a speed difference in that? Subtracting two integers is essentially free, in the context of a sorting algorithm.

[voyagerOne]

Actually no, it shouldn't. QxQ is at best an equal trade, so it gets a score of 0. PxR is a winning trade, so it gets searched first. Why would you search equal captures before winning captures?

No at best QxQ is winning a queen.

You need to get rid of the assumption that each piece is protected and if a piece is captured the attacker will get recaptured.

It is quite the opposite...
Chess engines brute forces the game tree...so the vast majority of positions will be laughable... hanging pieces all over the place.

Imagine that your Q is not protected.
So if you play PxR first.
Opponent will then play QxQ.
Taking your queen which you are not able to recapture theirs.



Regarding the formula:
score = MVV * F - LVA

F must be > than your QeenValue (highest PieceValue)

I doubt your queen value is 10.

[bob]

I will give away a tiny secret in Komodo. If you always generate your moves in the order Px then Nx then Bx then Rx then Qx then Kx, then assign score based on what they are capturing, then always use a stable sort, then move ordering will always be in the correct MVV LVA order. This is because you generate pawn captures first and so on and the stable sort will not put an say Q being captured ahead in the list (stable sorts work this way). It saves a little time you would have to spend "subtracting" the piece doing the capturing from the value you assign to the piece being captured. You get the same move ordering in a little less time.

Mark

Can you even measure a speed difference in that? Subtracting two integers is essentially free, in the context of a sorting algorithm.

Also in the framework of multiple-issue super-scalar architectures, the subtract gets buried in the loop anyway. I doubt you could measure the difference on today's machines...

[D Sceviour]

Schooner takes the initial move list from the furthest PieceBoard() square. That is, for white the next square is located by bitscanreverse BSR(), and for black BSF(). This make the piece closest to the enemy king considered first, and the friendly king considered last. The theory is that the most tactical piece move or capture should be considered first. It certainly helps find mates faster. The method produced fewer nodes on average than any other sort, although it has not been re-tested recently. I am making major changes to the move generator anyway since it seems too slow so move ordering is up for an overhaul. Mate hunting is good, but the engine needs depth too.

[jdart]

I think that method will give you a terrible branching factor.

What alpha-beta looks for is a move the refutes the previous opponent's move. Very often that is a winning capture so it makes sense to try those first (after the hash move, which was typically a previous refutation).

--Jon

[D Sceviour]

I think that method will give you a terrible branching factor.

What alpha-beta looks for is a move the refutes the previous opponent's move. Very often that is a winning capture so it makes sense to try those first (after the hash move, which was typically a previous refutation).

--Jon

I look at captures first. However, sometimes there are no good captures and this method tends to attack the king. It's one of the things that make Schooner an aggressive program. Free tip!

However, you are correct about the branching factor. In some positions the branching factor is poor. The best move sorting method might be the one that give the lowest average branching factor, but I am not sure what that it. MVV-LVA is a poor sort in itself, especially in positions that have no good captures.

[theturk1234]

I think I wasn't implementing MVV-LVA properly. I believe I was doing it backwards I'll try it the right way and see if the branching factor goes down. Thanks for all the replies!

David Cimbalista