Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: QSearch() as PVS() ?

Author: Tord Romstad

Date: 09:48:54 01/15/04

Go up one level in this thread


On January 15, 2004 at 11:15:28, Anthony Cozzie wrote:

>>OK, but I don't think you played with MTD(f) long enough to make it work
>>really well.  You cannot simply replace PVS with MTD(f) and expect that
>>your engine will play as well as or better than before; it takes a long
>>time to learn all the tricks.  Many techniques which work well with PVS
>>are less effective with MTD(f), and the same holds true in the opposite
>>direction.  This, of course, makes it very difficult to make an objective
>>comparison of the two algorithms.
>
>1. I did the full upper/lower bound hash rather than limit/type.
>
>2. I tried probing in qsearch
>
>3. I experimented quite a bit with heuristics for varying the window, as opposed
>to plaat's next_try = current try-1.

And you used ETC, I hope?

>I probably spent about a week on it.

You're probably better than me, but I'm afraid a week is still not enough.
I think I used at least a month or two before my MTD(f) was clearly better
than my old search.  You could of course argue that my engine could have
improved equally much if I had spent the same amount of time on other
improvements, which is perfectly possible.  We'll never know.

>I think in the _average_ case MTD(f) can
>even be better than PVS() [my implementation was about equal] with some tuning.
>It can find tactical shots much faster, because it goes through the entire move
>list sooner than PVS().  It is the _worst_ case where MTD(f) falls apart; in my
>personal opinion the worst cast is more important.

We all agree about that, I think.  The worst case can be quite ugly in
PVS, too.  Personally I haven't found MTD(f) to be noticably worse in
this respect, but I haven't studied the problem very closely.

>Now, writing all this has given me an idea.
>
>You start out trying an MTD(f) window at prev_score - 8.  If it fails high, than
> you continue your MTD(f) ways.  If it fails low, you switch over to PVS().
>This is fresh off the neurons so it may not work/be stupid/make you feel less
>handsome/etc.

It is an interesting idea, but I am not sure how well it would work.  You
would probably have to clear your hash table before switching, which is
of course not very good.

Another possibility would be to switch only after an iteration is finished.
For instance, if the score has dropped two iterations in a row, you could
assume that the score will continue to drop, and switch to PVS for the
next iteration.

You could also try to base the choice between PVS or MTD(f) on the nature
of the root position.  For instance, I have noticed that MTD(f) seems to
be more effective in the endgame than in the middle game (I have no idea
why, and I am not entirely sure the observation is correct).

Tord



This page took 0.01 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.