Capture ordering

[adams161]

hi,

Now that i think of it, the idea that you are looking to force cuttoffs not find the best move, explains some of my test results in atomic chess with capture ordering.

In atomic when you capture you not only capture their piece but your own pieces is blown up or captured, and all pieces surrounding it ( except for pawns, a pawn can only be captured directly or when it captures ) are captured or blown up. So its a mess to figure out winning captures.

the best method so far is still just most valuable piece/least valuable defender. I have tried computing a value for all pieces involved in a capture and that is not as good for my program. Any one else with move ordering ideas that could be used in atomic, suggestions welcome.

Mike

http://www.adam16mr.org/pulsar.html

[hgm]

The primary task of move ordering in QS is to quickly terminate 'plunder raids' of super-pieces like Queen, Chancellor and Archbishop. An all-capture minimax tree contains enormously deep branches where both Queens graze the whole board empty. If you capture the Queen as soon as you can, these branchess are cut by alpha-beta.

I guess in atomic this risk is non-existent, as all captures imply suicide. I guess I would go for the Queen, or any piece next to it. But I would not expect a big effect. For the main search I would reorder by QS score, IID fashion.

[Dann Corbit]

I am considering two ways to implement capture ordering:

Method 1:
- Moves which less value pieces capture more or equal value ones
- Moves of positive gains, proved by SEE

Method 2:
- Moves of positive gains, proved by SEE

The advantage of method 1 is that if cut off occurs, we can save some calls of SEE. However, the method 2 seems to give us a better move ordering even SEE is called more than one.

Other methods and/or comments are highly appreciated.

1. MVV/LVA (most valuable victim, least valuable agressor) is the most common.
2. MVV/MVA (most valuable victim, most valuable agressor) is a surprising stategy that I have heard did well.
3. BMO (best move only, but do not search any non-pv nodes, so if they are not in the hash table, they will need evaluated to choose) It's basically a branching factor of 1 search forward. You have to decide on a stopping decision, because 'no more captures' or 'all subsequent captures are bad' does not apply here.
4. Rely on quiescent search.
5. Rely on hash, history and IID (and eval when the chips are down)

I guess that #1 is both easiest and best most of the time.
#4 is too expensive
#5 is probably of poor quality
#3 is hard to tune
#2 is counter-intuitive, but I know of one study that said it worked great.

You left out, 'poor blind man's SEE' that I use in RomiChess.

During move generation a bit is set in a u64 variable for every square that is attacked and then stored by ply.

So for move ordering it simply becomes (victim - fs-val + ts-val - (sqrAttacked) ? attacker/2 : 0;

The accuracy sucks, however, it is blazingly fast.

Gerd Isenberg also has mentioned switching to a 'poor mans SEE'!

And (not sure, not sure, not sure) but, the new Glaurung may use something similar.

This idea can be taken a step further. During move generation, all attacks can be precalculated so that every square has both black and white attacks by piece type along with pin, and half-pin bitmaps. For every square, you will know by the counts if it is safe to put a piece of type 'x' on the square. So your SEE can ignore any white knight moves to squares that are not white knight safe, etc.

It's really sort of an incrementally calculated SEE.

[Michael Sherwin]

I am considering two ways to implement capture ordering:

Method 1:
- Moves which less value pieces capture more or equal value ones
- Moves of positive gains, proved by SEE

Method 2:
- Moves of positive gains, proved by SEE

The advantage of method 1 is that if cut off occurs, we can save some calls of SEE. However, the method 2 seems to give us a better move ordering even SEE is called more than one.

Other methods and/or comments are highly appreciated.

1. MVV/LVA (most valuable victim, least valuable agressor) is the most common.
2. MVV/MVA (most valuable victim, most valuable agressor) is a surprising stategy that I have heard did well.
3. BMO (best move only, but do not search any non-pv nodes, so if they are not in the hash table, they will need evaluated to choose) It's basically a branching factor of 1 search forward. You have to decide on a stopping decision, because 'no more captures' or 'all subsequent captures are bad' does not apply here.
4. Rely on quiescent search.
5. Rely on hash, history and IID (and eval when the chips are down)

I guess that #1 is both easiest and best most of the time.
#4 is too expensive
#5 is probably of poor quality
#3 is hard to tune
#2 is counter-intuitive, but I know of one study that said it worked great.

You left out, 'poor blind man's SEE' that I use in RomiChess.

During move generation a bit is set in a u64 variable for every square that is attacked and then stored by ply.

So for move ordering it simply becomes (victim - fs-val + ts-val - (sqrAttacked) ? attacker/2 : 0;

The accuracy sucks, however, it is blazingly fast.

Gerd Isenberg also has mentioned switching to a 'poor mans SEE'!

And (not sure, not sure, not sure) but, the new Glaurung may use something similar.

This idea can be taken a step further. During move generation, all attacks can be precalculated so that every square has both black and white attacks by piece type along with pin, and half-pin bitmaps. For every square, you will know by the counts if it is safe to put a piece of type 'x' on the square. So your SEE can ignore any white knight moves to squares that are not white knight safe, etc.

It's really sort of an incrementally calculated SEE.

So my, "poor blind man" wins the lottery and recieves an eye operation!

[bob]

I was looking at the crafty code earlier, and noticed it uses bubblesort to order captures(I think)

If you were using MVV/LVA would you order the captures by the value V-A going from largest to smallest, where V is victim, A is the attacker?

Eg V=3(knight) A=1(pawn), V-A=2
And V=9(queen) A=5(rook), V-A=4

So there you would play RxQ before PxN

Thats how I would implement this, is this wrong?

Thanks

That is correct. Also you will play QxN before trying PxP. That's where MVV/LVA runs into difficulties...

[hgm]

As a cheap alternative to SEE, the following algorithm gives a nice improvement over MVV/LVA for engines that can cheaply find out whci pieces are defended:

Use MVV/LVA ordering, but only try High x Low captures (such as QxR, RxN) on undefended pieces. If the victim is defended, prune the move in QS, and sort it after the other captures (according to LVA) otherwise.

This method is known as BLIND (Better and Lower If Not Defended)

[bob]

hi,

Now that i think of it, the idea that you are looking to force cuttoffs not find the best move, explains some of my test results in atomic chess with capture ordering.

In atomic when you capture you not only capture their piece but your own pieces is blown up or captured, and all pieces surrounding it ( except for pawns, a pawn can only be captured directly or when it captures ) are captured or blown up. So its a mess to figure out winning captures.

the best method so far is still just most valuable piece/least valuable defender. I have tried computing a value for all pieces involved in a capture and that is not as good for my program. Any one else with move ordering ideas that could be used in atomic, suggestions welcome.

Mike

http://www.adam16mr.org/pulsar.html

Here is a classic example. Material is equal, score is equal, you are searching a branch where you have a pawn on the 7th. You can promote to anything, but most likely a knight is best. This gives the smallest sub-tree below the promotion, when compared to promoting to a queen which generally has enormous mobility in the endgame. You want to find the move with two characteristics:

(1) good enough to cause a cutoff (fail-high);

(2) produces the smallest sub-tree possible.

This was the idea behind the ETC hash table algorithm, if you can't find a hash entry at the current ply that will stop the search on the spot, try each move at the current ply and see if any of those lead to a position where a hash hit will stop the search immediately. If so, order that move first if you can't trick things up to avoid the search completely at that point by just failing low or high (opposite of what the hash entry for the next ply says to do)...

It is counter-intuitive, but it isn't about "best move" in the classic sense, it is about searching the "best move" from an effort required point of view...