(Internal) Iterative Deepening

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

Re: (Internal) Iterative Deepening

Postby H.G.Muller » 01 Mar 2006, 12:43

Daniel Shawul wrote:There are winning captures ,as predicted by SEE, which are really loosing
but I dont see why identifying this cases is important.(other than statistics).
OK, thanks for the explanation, this makes it completely clear.

However, I still I don't think that because in 40% of the cases in hindsight the IID turned out not to be necessary for move selection, you can or should draw the conclusion that it is not useful. I pay health insurance, and in 60% of the years I don't need any medicare whatsoever. Is that a reason to drop the insurance? Would I have been better off not having the insurance all those years? You can never conclude that. Even if in 9 out of 10 years I would not have needed any medical attention, but in the one year I did I was hospitalized for open-heart surgery, it still saved my a million bucks... Especially if I get most of my insurance premium back through a 'no-claim' arrangement in the years that nothing happened.

To judge the value of an insurance, you should look at the disasters that you prevent, which of necessity are infrequent but very costly. (Otherwise it would make no sense to take an insurance, you will just ride the odds and let the statistical 'law of large numbers' do its job.) This should be weighted against the certain cost of the premium. That the premium is wasted if nothing happens is understood.

IID is an insurance against engaging in a very deep search that could have been avoided, because the SEE was not abslutely reliable and you search a bad move before the one that gave the cutoff. The bad move doesn't do anything for your alpha, so you still have to spend an equal amount of search the move that does cause the beta cutoff. A pilot search 2 plies less deep would perhaps have cost only 1% of the superfluous search, and would intercept virtually all mis-predictions by the SEE. So even if in 90% of the cases the pilot search was 'wasted' because the SEE was correct, you have invested 10 times 1% to gain back 1 times 100%, i.e. the total search effort in this node on the average reduces from 11 full-depth searches (9 times the refutation move straight away, 1 time as the second) to 10.1 (10 times the refutation move straight away, but also 10 times a pilot search costing 0.01). So you save ~8%, despite the fact that 90% of the IID searches was 'wasted'.

In the same way, IID would be insurance against the event that you would mistakenly judge the node as an alpha node, while a good non-obvious (i.e. non-SEE-able) move is available that makes it a beta or PV node. The pilot searches in IID can be ridiculously cheap compared to a full-depth search, since even in a very rudimentary form (say 1-ply + QS only) they are likely to be far more reliable than a SEE. If the full remaining depth is at 6, such a pilot is nearly free. So the SEE- or node-type judgement must really be enormously reliable (say error rate les than 0,01%) before you lose on taking the IID insurance.
User avatar
H.G.Muller
 
Posts: 3453
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

PVS, IID and searching hash move first without movegen

Postby smcracraft » 07 Mar 2006, 00:01

I have tried all combinatiions of these and the one that
works best for me is plain PVS with a global movegen
at the top, with the hash move and pv moves sorted
to the top.

Any perturbatiion of this, with internal iterative deepening
and/or searching the hash move first without the global
movegen, produces worse results.

I think my implementation of the latter is probably flawed.

Can others say what they get for searching the hash move
first without movegen as opposed to generating a movegen,
scoring the hash move in that list to the top, and then
searching the list from top down?

Thanks,

Stuart
smcracraft
 
Posts: 65
Joined: 15 Jan 2006, 05:38

Re: PVS, IID and searching hash move first without movegen

Postby H.G.Muller » 07 Mar 2006, 08:54

smcracraft wrote:Can others say what they get for searching the hash move
first without movegen as opposed to generating a movegen,
scoring the hash move in that list to the top, and then
searching the list from top down?

If you generate moves before searching the hash move, and would always search the hash move before the generated moves anyway, the only effect of the movegen would be to waste time in cases where the hash move produces a beta cutoff...
User avatar
H.G.Muller
 
Posts: 3453
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Previous

Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 33 guests