Extended Futility Pruning - anyone tried it?
Tom King
"Extended Futility Pruning", by Ernst Heinz.
He indicates good results for DarkThought when using this pruning idea.
Anyone else tried it? What results?
--
Tom King
Chris Whittington
Tom King wrote in message ...
>In the June 1998 ICCA journal, there's an interesting article on
>"Extended Futility Pruning", by Ernst Heinz.
>
>He indicates good results for DarkThought when using this pruning idea.
He is doing a kind of pruning just before the horizon.
>Anyone else tried it?
Yes. CSTal does this but more extensively. It prunes on various chess
knowledge grounds for several plys before the horizon.
> What results?
At 1000 nodes/sec on a P90, CSTal doesn't have much choice but to be pruning
the tree :)
The idea is to tree search more like a human. No chess player looks at all
moves and all replies to a fixed depth, does he ? So no need for a program
to do this either. Better spend the time in the important areas of the tree.
Pruning and extending as appropriate.
Chris Whittington
>--
>Tom King
Ernst A. Heinz
>Tom King wrote in message ...
>>In the June 1998 ICCA journal, there's an interesting article on
>>"Extended Futility Pruning", by Ernst Heinz.
>>
>>He indicates good results for DarkThought when using this pruning idea.
>
>He is doing a kind of pruning just before the horizon.
If you define 2 plies or 3 plies ahead of the horizon as "just before" it,
then your statement is true. Otherwise you should re-read my article ...
Futility pruning at pre-frontier nodes statically forward-prunes at depth = 2
and limited razoring does so at depth = 3.
>
>>Anyone else tried it?
>
>Yes. CSTal does this but more extensively. It prunes on various chess
>knowledge grounds for several plys before the horizon.
How far up do your "several plies" go? Do you employ static forward-pruning
everywhere in the search tree?
=Ernst=
Chris Whittington
Ernst A. Heinz wrote in message <6rbn5p$nmt$1...@nz12.rz.uni-karlsruhe.de>...
Difficult to say, since CSTal doesn't really have a defined horizon; it's a
kind of fuzzily, splodged area somewhere inbetween the start of pruning and
the end of the extensions.
It may be, that we do ourselves a disservice to talk of a "horizon" with
pruning before it and "extensions" beyond it. Language problem (again).
Pruning sort of equals not-extension and vice versa, doesn't it ?"
>Do you employ static forward-pruning
>everywhere in the search tree?
It is static, yes. Although CSTal also takes backward information from the
search (especially this info conflicts with its static) and acts on this.
And everywhere ? No. No need. There appears to be no great advantage in
pruning way below the "horizon". Its just dangerous without, IMO, any great
speed-up advantages. Pruning has the most effect, and the least danger,
getting on into the outer reaches.
btw I did read your article.
Chris Whittington
>
>=Ernst=
Tord Kallqvist Romstad
>In the June 1998 ICCA journal, there's an interesting article on
>"Extended Futility Pruning", by Ernst Heinz.
Is this article available online? If not, could somebody please explain
the idea?
Tord
Komputer Korner
isn't it?
--
--
Komputer Korner
The inkompetent komputer
To send email take the 1 out of my address. My email address is
kor...@netcom.ca but take the 1 out before sending the email.
Chris Whittington wrote in message
<903441304.17336.0...@news.demon.co.uk>...
Chris Whittington
Komputer Korner wrote in message ...
>Well then your definition of forward pruning is more like razoring
>isn't it?
Is it ? Is it important ? I know in the bean-counter paradigm they like to
have soem language:
horizon - what they nominally search to
extension - if they want to go beyond their horizon
pruning - if they want to cut the seacrh before the horizon
then they have various words for the pruning function like razoring and so
on. IMO these words are not valuable in terms of chess knowledge. They are
non-chess knowledge words.
I look at it different:
A node in the tree is a chess position.
Whether to open this node (look deeper), or close it (call it a day), is,
for me, a judgement call which depends on a whole load of factors. Chess
knowledge ones being rather important, IMO.
Chris Whittington
Chris Whittington
Tord Kallqvist Romstad wrote in message ...
There was some talk about iccaj articles going on-line. Not sure if this has
happened. I think (not absolutely sure) that Ernst said something or other
about him putting the article on-line himself.
Explanation ? Ernst will probably wildly disagree, but essentially it
involved some forward pruning below the horizon if the predicted material
value of the position was some way below alpha, and therefore unlikely to be
improved. I guess he would have played safe in the case of checks and stuff.
Chris Whittington
>
>Tord
Ernst A. Heinz
>Tord Kallqvist Romstad wrote in message ...
>>In article <xblgkHA6...@hatbulb.demon.co.uk>, Tom King wrote:
>>>In the June 1998 ICCA journal, there's an interesting article on
>>>"Extended Futility Pruning", by Ernst Heinz.
>>
>>Is this article available online? If not, could somebody please explain
>>the idea?
>
>There was some talk about iccaj articles going on-line. Not sure if this has
>happened. I think (not absolutely sure) that Ernst said something or other
>about him putting the article on-line himself.
Yes, I will put it up on our "DarkThought" WWW page at URL =
<http://wwwipd.ira.uka.de/Tichy/DarkThought> as soon as I find the time to
do so (maybe the coming week-end).
> Explanation ? Ernst will probably wildly disagree, [...]
Why should I wildly disagree if you give a reasonable explanation.
> [...] but essentially it
> involved some forward pruning below the horizon if the predicted material
^^^^^
above (at depth = 2 and depth = 3)
> value of the position was some way below alpha, and therefore unlikely to be
> improved. I guess he would have played safe in the case of checks and stuff.
Right, similar to normal futility pruning at frontier nodes (depth = 1).
All the safety precautions are described in the article which also provides
detailed experimental evaluation of the new pruning schemes on more than
2000 test positions (879 ECM + 300 WAC + 1001 WCS).
BTW, Tord, have you ever thought of joining the ICCA in order to receive
the ICCA Journal first-hand? Just a suggestion ...
=Ernst=
Chris Whittington
Ernst A. Heinz wrote in message <6reaa2$n6u$1...@nz12.rz.uni-karlsruhe.de>...
Since we're not 'wildly' disagreeing :) I'll try and answer your question as
to how many plies above/below (we differ, I look at it the other way round,
but that is typisch,as they say :) CSTal is forward pruning.
CSTal horizon is very fuzzy, but, in simplistic terms, it is kind of the
depth searched to shown by the main line, just as long as the position (main
line) doesn't have any extensions applied to it. With that as the fuzzy
definition, CSTal will prune on a chess knowledge basis for 5 plies below
that.
It then hands the pruned node to the extension handler which might cause a
mind change to be made, though :)
Chris Whittington
Tord Kallqvist Romstad
In article <6reaa2$n6u$1...@nz12.rz.uni-karlsruhe.de>, Ernst A. Heinz wrote:
>BTW, Tord, have you ever thought of joining the ICCA in order to receive
>the ICCA Journal first-hand? Just a suggestion ...
I was a member a few years ago, but I did not find very many interesting
articles in the ICCA Journal. A few articles were very good, but not many
enough to make it worth the membership fee (I am a student and do not have
a big income). I might join the ICCA again some time in the future.
Tord
--
"The true Christian should be aware of mathematicians and those who make empty
prophecies. Chances are already there that mathematicians have made a covenant
with the Devil to darken the spirit and confine man in the bounds of Hell"
- St. Augustin
Komputer Korner
assume this because it would cost him too much time in the search,
then with alpha beta how is it possible to implement ANTI-GM? The
only way I see is that Ed now effectively has 3 different engines in
Rebel 10 with the anti-GM being one of them. Of course a lot of
programs have had the possibility to change the engine algorithm style
EX: aggressive, defensive, attacking...........etc but Ed must have
extensively changed his engine to produce antiGM. So in the end
anti-GM must be the equivalent engine that plays best against humans
and the other engines are for using against computers. This is a good
thing and maybe everybody will have 2 versions of their program. Even
Bob Hyatt switches somewhat whenever Crafty plays in a computer
tounament.
--
--
Komputer Korner
The inkompetent komputer
To send email take the 1 out of my address. My email address is
kor...@netcom.ca but take the 1 out before sending the email.
f...@accountant.com wrote in message
<35DACE5C...@accountant.com>...
>btw, how does anti-GM work?
>
>Kind regards
>
>fca
>
>> "The true Christian should be aware of mathematicians and those who
make empty
>> prophecies. Chances are already there that mathematicians have made
a covenant
>> with the Devil to darken the spirit and confine man in the bounds
of Hell"
>> - St. Augustin
>
>PS: In those days, most mathematicians were astrologers too, and....
Not
>that I would argue with the applicability today!