Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Couple of chess programming questions

Author: Vincent Diepeveen

Date: 14:16:00 09/10/02

Go up one level in this thread


On September 10, 2002 at 16:06:51, martin fierz wrote:

I need to refer to extensive proof i wrote down at CCC
which refuted that you overwrite the mainline.

For a search of 20 ply with a loading factor which is pretty
high, it is still true that with near sureness you have a
19 ply line at least (assuming no extensions otherwise
the line is longer).

That's true for bounds too of course.

The chance you overwrite a search depth of 1 ply left
is considerably smaller than you overwrite something of
0 ply left.

In fact i do 8 probes.

What loading factor do you talk about here, then fill in the
chances.



>On September 10, 2002 at 15:41:42, Vincent Diepeveen wrote:
>
>>On September 10, 2002 at 15:19:21, martin fierz wrote:
>>
>>>On September 10, 2002 at 14:45:27, Omid David wrote:
>>>
>>>>On September 10, 2002 at 14:30:56, martin fierz wrote:
>>>>
>>>>>On September 10, 2002 at 09:26:14, Eli Liang wrote:
>>>>>
>>>>>>A couple of chess programming questions:
>>>>>hmm, i only wrote a checkers program, but here's my take:
>>>>>
>>>>>>(1) Are there any uses for ProbCut and/or Multi-ProbCut in chess positions where
>>>>>>the variance of leaf-nodes is low?
>>>>>
>>>>>i've tried multi-probcut and it works well in checkers. i never tuned it as much
>>>>>as my own pruning algorithm, and it doesn't perform quite as well - but it is BY
>>>>>FAR better than no pruning. i'll be trying to tune it in the near future. for
>>>>>games where the eval doesnt swing wildly, MPC is a fantastic algorithm.
>>>>>
>>>>>>(3) Reading Aske Plaat's search & re-search paper, it really seems like mtd(f)
>>>>>>is something of a magic bullet.  But I note it seems that more programs don't
>>>>>>use it than do (for example Crafty).  What is wrong with mtd(f) which Plaat
>>>>>>doesn't say?
>>>>>
>>>>>i'm using MTD. i tried windowed search, PVS and MTD. in my tests, in long engine
>>>>>matches, MTD performed marginally (no statistical significance...) better than
>>>>>PVS. it typically searched a low 1-digit % less nodes for a given depth than
>>>>>PVS.
>>>>>i don't know how to get a PV out of MTD. in normal searches, a pv node is where
>>>>>the value is > alpha but < beta. in MTD, you never get this condition.
>>>>>retrieving a PV from the hashtable is possible, but in all probability, you will
>>>>>not get the full PV. which is real bad for debugging if you want to know what
>>>>>the program was thinking at the time... i once asked here how to get a pv from
>>>>>MTD but got no answer - and if you can't get the pv, then that is a major
>>>>>drawback.
>>>>
>>>>I haven't tried getting the PV out of MTD(f), but just a thought: why should
>>>>there be any problem in getting the PV out of hash table? Play the first move,
>>>>update the position, get the next best move from hash table, and so on... ?!
>>>
>>>there's no problem with that except that on any reasonably deep search, you will
>>>not have been able to store all pv nodes in the hashtable. so you end up with a
>>>search which says it was 23 ply deep and have e.g. 15 pv moves. if you just want
>>>to display it for the user, that's fine. but if your program plays a bad move,
>>
>>but then your hashtable management sucks ass, sorry to say so.
>
>but you don't use MTD! which means you *know* when you have a pv node, because
>"pvnode <=> alpha<value<beta". and then you can make sure it doesn't get
>overwritten in the hashtable. if you use MTD, you don't have this information -
>all your hashtable entries are either lower or upper bounds... so how do i know
>which ones i have to keep? i'd really glad to learn how to do this :-)
>so if you can tell me how to do it instead of saying i suck (well possible...),
>i'd love to try!
>
>aloha
>  martin
>
>
>>I get in Napoleon also only mainlines out of hashtable (with pvs)
>>wasting system time in the search to update all kind of stupid
>>arrays for it is a waste of time, and the next iteration you get
>>true bounds, so you can't get the mainline in arrays anyway (mtd
>>is different here). finding a win in 50 ply is no problem to display...
>>
>>
>>
>>>and you want to know what line it was considering as being best, e.g. because
>>>you want to know if your static eval is bad in the final node of the pv, you
>>>can't do it. IMO debugging your program and finding eval problems like this is
>>>MUCH more important than something like 5% more speed.
>>>
>>>aloha
>>>  martin
>>>
>>>
>>>>
>>>>>
>>>>>>(6) Has anyone found any real "practical" benefits to fractional-ply extensions?
>>>>>
>>>>>yes. i tried recapture extensions of different depth, and half a ply gave the
>>>>>best result. don't ask me why, it's just an observation.
>>>>>
>>>>>aloha
>>>>>  martin



This page took 0.2 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.