Winboard Forum

How do you implement the UCI MultiPV support?
I mean without losing search time.
I know this have been discussed before but my memory fails me...
/Peter

Peter Fendrich wrote:How do you implement the UCI MultiPV support?
I mean without losing search time.

You can't do it without losing search time. If you use a standard PVS search and the first move at the root remains the best during a full iteration (which is what usually happens), you have no way of knowing the second best move, because all the moves after the first were searched with a zero width window.

The most straightforward (and the fastest, I think) way to implement it is to modify PVS to search the first k moves at the root with a full window, and not just the 1st move. The remaining moves are searched with a zero window around the worst of the k first moves. There are a few other small details you must take care of, but I'm sure you will be able to figure them out yourself when you try to implement it.

Tord

Tord Romstad wrote:

Peter Fendrich wrote:How do you implement the UCI MultiPV support?
I mean without losing search time.

You can't do it without losing search time. If you use a standard PVS search and the first move at the root remains the best during a full iteration (which is what usually happens), you have no way of knowing the second best move, because all the moves after the first were searched with a zero width window.

The most straightforward (and the fastest, I think) way to implement it is to modify PVS to search the first k moves at the root with a full window, and not just the 1st move. The remaining moves are searched with a zero window around the worst of the k first moves. There are a few other small details you must take care of, but I'm sure you will be able to figure them out yourself when you try to implement it.

Tord

Thank you Tord,
Don't have to high expectations about what I can figure out myself

Other ideas I have are much more complicated and will probably not gain anything in the end...
Is your mtd(f) search better in this respect? (In case you still use that)

/Peter

Peter Fendrich wrote:Thank you Tord,
Don't have to high expectations about what I can figure out myself

I'm sure you'll manage. I have great confidence in your abilities: As you probably remember, you were the one who first taught me chess programming.

Other ideas I have are much more complicated and will probably not gain anything in the end...
Is your mtd(f) search better in this respect?

For MultiPV analysis, you mean? I don't think so. If anything, I would guess that implementing MultiPV efficiently would be more difficult in an MTD(f) search.

(In case you still use that)

I don't. Gothmog used MTD(f), but Glaurung has been a PVS searcher since the beginning.

Tord