caps->noncaps vs. goodcaps->noncaps->badcaps

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
bob
Posts: 20358
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: caps->noncaps vs. goodcaps->noncaps->badcaps

Post by bob » Thu Jul 19, 2007 12:04 am

jswaff wrote:
CRoberson wrote:There are two ways to do MVV/LVA:

1) do all queen captures then rook captures ....
2) perform pxb before rxq

I've tried both and 1 seems best.

I think the reason for 1 working better than 2 is the same as putting
bad captures before noncaptures.

Every capture reduces the branch factor and capturing the queen
will reduce it more than capturing the rook.
I've never considered number one. Intuitively number two seems much better. For example, QxQ would not be as attractive as, say, PxR.

--
James
It depends. What if the queen is undefended? Would you stilll try PxR first? :)

Hence SEE. MVV/LVA was specifically designed for hardware implementation. SEE can't be done in constant-time, while MVV/LVA can, which makes it more attractive for a finite state machine implementation.

jswaff

Re: caps->noncaps vs. goodcaps->noncaps->badcaps

Post by jswaff » Thu Jul 19, 2007 12:06 am

bob wrote:
jswaff wrote:
CRoberson wrote:There are two ways to do MVV/LVA:

1) do all queen captures then rook captures ....
2) perform pxb before rxq

I've tried both and 1 seems best.

I think the reason for 1 working better than 2 is the same as putting
bad captures before noncaptures.

Every capture reduces the branch factor and capturing the queen
will reduce it more than capturing the rook.
I've never considered number one. Intuitively number two seems much better. For example, QxQ would not be as attractive as, say, PxR.

--
James
It depends. What if the queen is undefended? Would you stilll try PxR first? :)
We are talking about MVV/LVA here - so yes, because I haven't taken the time to figure out if it's defended or not.

--
James

jswaff

Re: caps->noncaps vs. goodcaps->noncaps->badcaps

Post by jswaff » Thu Jul 19, 2007 12:13 am

BubbaTough wrote: One thing to note is that depending on how you are doing LMR reductions, move order effects move choice not just depth. For example, if you are reducing all non-captures not in the first 3 moves, doing bad captures first means you are usually reducing ALL non-captures non-cached moves...particularly if you do them before killer movers. Also a factor is whether you allow LMR to reduce killer moves.
Yes, I think there might be something to that. If the list of winning captures is very short (which it normally would be I would think), then with a moves_searched > 4 restriction some noncaptures are not eligible for the reduction that would be if *all* captures were searched first.

Thanks,
--
James

Karlo Bala
Posts: 299
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: caps->noncaps vs. goodcaps->noncaps->badcaps

Post by Karlo Bala » Thu Jul 19, 2007 12:34 am

jswaff wrote:
CRoberson wrote:There are two ways to do MVV/LVA:

1) do all queen captures then rook captures ....
2) perform pxb before rxq

I've tried both and 1 seems best.

I think the reason for 1 working better than 2 is the same as putting
bad captures before noncaptures.

Every capture reduces the branch factor and capturing the queen
will reduce it more than capturing the rook.
I've never considered number one. Intuitively number two seems much better. For example, QxQ would not be as attractive as, say, PxR.

I don't get your comment on reducing branching factor. If you can get a cutoff, you want to get it as soon as possible, meaning you want to play the most promising move as early as possible.


--
James
Charles is right. After QxQ you get smaller subtree than after PxR. If you are on CUT node, QxQ should be enough to get a cutoff. But there is another thing, after QxQ almost always is best to do (P|N|B|K)xQ, and then you can do PxR.
Best Regards,
Karlo Balla Jr.

jswaff

Re: caps->noncaps vs. goodcaps->noncaps->badcaps

Post by jswaff » Thu Jul 19, 2007 1:11 am

Karlo Bala wrote:
Charles is right. After QxQ you get smaller subtree than after PxR. If you are on CUT node, QxQ should be enough to get a cutoff.
I see the point - that queens can make a lot of moves, and so if you remove the queen the branching factor should go down. However, I'm not convinced that justification is sound enough to always try queen captures before other captures of less valuable pieces, because in the end it should be the net gain from the capture (sequence) that matters.

You want to get the cutoff with the least effort, I think we all agree on that.

Charles says it works best for him, so that's all that matters.

Edit:
If we could somehow (reliably) figure out an estimated work load per move and a confidence factor of getting a cutoff, we could decide which move to play as a function of the two. I suppose in a sense that's what Charles is doing. My guess is that kind of "speculation" will pay off at times and cost you at times.

I just "play it safe" and go for the capture that looks like it will win the most material.

--
James

CRoberson
Posts: 1985
Joined: Mon Mar 13, 2006 1:31 am
Location: North Carolina, USA
Contact:

Re: caps->noncaps vs. goodcaps->noncaps->badcaps

Post by CRoberson » Thu Jul 19, 2007 1:38 am

Bob,

Yes, you are correct. What I was talking about is a typical mistake
in coding MVV/LVA.

The proper way will put QxQ before PxR and RxR before PxB.
So, complete ordering is:
PxQ, B|NxQ, RxQ, QxQ, PxR, QxR, B|NxR, RxR, PxB|N, B|NxB|N,RxB|N, QxB|N, ........

However, the typical coding mistake (but also an intuitive alternative)
is to order the moves by V-A which puts PxB ahead of QxQ and RXR.

I considered the alternative as a method of MVV/LVA as it is a typical mistake in coding MVV/LVA.

jswaff

Re: caps->noncaps vs. goodcaps->noncaps->badcaps

Post by jswaff » Thu Jul 19, 2007 3:24 am

CRoberson wrote:Bob,

Yes, you are correct. What I was talking about is a typical mistake
in coding MVV/LVA.

The proper way will put QxQ before PxR and RxR before PxB.
So, complete ordering is:
PxQ, B|NxQ, RxQ, QxQ, PxR, QxR, B|NxR, RxR, PxB|N, B|NxB|N,RxB|N, QxB|N, ........

However, the typical coding mistake (but also an intuitive alternative)
is to order the moves by V-A which puts PxB ahead of QxQ and RXR.

I considered the alternative as a method of MVV/LVA as it is a typical mistake in coding MVV/LVA.
You're right, that is what I'm doing, and I've been doing that for a while. I can see that it's not "MVV/LVA", but "V-A".

Well, that doesn't make a lot of sense to me honestly, but it's worth testing. Thanks.

Good luck this weekend!
--
James

mjlef
Posts: 1367
Joined: Thu Mar 30, 2006 12:08 pm
Contact:

Re: caps->noncaps vs. goodcaps->noncaps->badcaps

Post by mjlef » Thu Jul 19, 2007 7:01 am

The value of a move is based on two things: How likely it is to be found as best and part of the PV, and how large the search tree under it is. Captures have a lot smaller subtrees, so although an apparently Losing: cature might have a lowe chance of being selected, it makes up for this with less effort in being searched. You can use the UCI protocal to see what order some programs search at least the root node. You will be surprised. Many great programs do place "losing" captures higher in the list that some others. Also, captures are fewer and faster to generate, so if one of them does cause a cutoff, it saves time.

I am beginning to think this is a better move ordering than most use:

hash move (or IID move or move from PV from last itteration)
mate killer
Winning captures
Equal captures
killer moves
losing captures
non-captures sorted by history

Mayeb Tord can run that ordering in his tests and see how it goes. This is my current move ordering at the root, but I use something a little different deeper in the search.

One other note: in generating pawn moves, I think putting double pawn moves ahead or single steps is better by a little bit. A more advanced pawn is generaly worth more I also suspect in ordering moves or rooks or bishops, moves at 90 degrees from its last move might be a little better and worth a small bonus. These represent new moves in the position.

Harald
Posts: 261
Joined: Thu Mar 09, 2006 12:07 am

Re: caps->noncaps vs. goodcaps->noncaps->badcaps

Post by Harald » Thu Jul 19, 2007 8:25 am

CRoberson wrote:Bob,

Yes, you are correct. What I was talking about is a typical mistake
in coding MVV/LVA.

The proper way will put QxQ before PxR and RxR before PxB.
So, complete ordering is:
PxQ, B|NxQ, RxQ, QxQ, PxR, QxR, B|NxR, RxR, PxB|N, B|NxB|N,RxB|N, QxB|N, ........

However, the typical coding mistake (but also an intuitive alternative)
is to order the moves by V-A which puts PxB ahead of QxQ and RXR.

I considered the alternative as a method of MVV/LVA as it is a typical mistake in coding MVV/LVA.
There was a little error. The complete ordering is:
PxQ, B|NxQ, RxQ, QxQ, PxR, B|NxR, RxR, QxR, PxB|N, B|NxB|N, RxB|N, QxB|N, ........

MVV/LVA is something like 100*V-A or if you use centipawns V-A/100.

Harald

User avatar
hgm
Posts: 23014
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: caps->noncaps vs. goodcaps->noncaps->badcaps

Post by hgm » Thu Jul 19, 2007 8:54 am

CRoberson wrote: The proper way will put QxQ before PxR and RxR before PxB.
So, complete ordering is:
PxQ, B|NxQ, RxQ, QxQ, PxR, QxR, B|NxR, RxR, PxB|N, B|NxB|N,RxB|N, QxB|N, ........
There was a discussion about move MVV/LVA and other 'static' move orderings (i.e. not adapting to the fact if the victim is defended) on CCC some months ago.

The Achilles heel of orthodox MVV/LVA is of course that QxR is ordered before PxB|N, while it can bring disaster if the R is defended, and the second is 'always' good.

That QxQ (which can be neutral) is better tried before 'obviously good' captures like PxR is already explained above: if he does not recapture you gained a Q, and if he does, you almost always do the PxR on the third ply anyway. So QxQ will have almost always as least as good a score as a competing PxR, but QxQ is a lot safer (because after starting with PxR the opponent will play QxQ, to bring disaster if your own Q happened to be undefended!).

QxR is a more tricky move. If the R turns out to be defended, though, the recapture of your Q will be tried by the opponent as first reply. In QS (or in fact at any depths <= 2) this in general immediately ends the sub-tree, as all remaing captures you have are likely to be futile after the loss of a Q for a R, and the XxQ refutation would thus be a cut move. So a 'gambling' QxR wastes only 2 nodes, even if the R turns out to be defended. This should be weighed against the possibility for an RxQ retaliation on your PxB alternative: if the Q attacks the R along a file/rank, the R attacks the Q back!

So a refinement could be to make te ordering depend on if QxR is along an orthogonal or a diagonal. PxN before QxR(orth) (or QxB(diag)) is really doomed, while trying one of the latter first at leat might work out if the victim is undefended. Even if you don't look which of your pieces is under attack in general, some of these mutual attacks you can recognize for free. Even QxP (the very last MVV/LVA move) offers more chance for success than any other capture if a P attacks the Q back...

The way Joker orders the moves is initially MVV, but after that for HxL captures the victim value is downgraded to the SEE value. And in a depth>=1 node, where null move is tried before any captures, so that we know which of our pieces is under attack if the null move is refuted, any victim value below the threatened piece is replaced by the see value as well, and the SEE value of the null-move-refuting move is added to the sort score of captures with the threatened piece, or of the attacker of it. Of all moves with equal sort score, the one with the LVA is then tried first.

Post Reply