Analysing with computer

[glorscheid]

A chess program is optimized to find the best move in a given position. If it first finds a risky move, which evaluates to +0.80, and later another more save one evaluating to +0.79 (or less) the second line is completely ignored. So correspondence chessplayers (I am no one) spend a lot of time with their engines to find these hidden alternatives.
Now I have the following idea: If I can limit the alpha/beta truncation in a way that variations no worse than e.g. 1 pawn value compared to the best variation are continued, I should get in the transposition cache much more positions with exact (not truncated) evaluation. The price is that the system will be slower of course. But then at any time it should be possible to use this transposition cache to create a pgn tree from the current position containing all interesting variations. But I don't know the impact on other heuristic optimizations used in chess programs today.
Does anybody already have played with this idea or know somebody who did? It may be also an interesting heuristic for programming of chess engines with a lower window of e.g. 0.2 pawns.

[smrf]

SMIRF acted in an optimal move pair iterative deepening manner, thus always searching for a second best move within an adaptive evaluation window.

[Tord Romstad]

A chess program is optimized to find the best move in a given position. If it first finds a risky move, which evaluates to +0.80, and later another more save one evaluating to +0.79 (or less) the second line is completely ignored. So correspondence chessplayers (I am no one) spend a lot of time with their engines to find these hidden alternatives.

That's why all serious chess programs have something called "Multi-PV mode": Instead of showing just the best move with its associated score and main line, the program shows the N best moves (where N is a number chosen by the user), each with its own score and main line.

Tord

[glorscheid]

I am not only interested in the second best move from the starting position. I would like to get all sequences of moves until depth n, which evaluate e.g. less than one pawn worse compared to the optimal variation.
(I could say that a game commented by Robert Hübner comes close to it).

[Michael Sherwin]

A chess program is optimized to find the best move in a given position. If it first finds a risky move, which evaluates to +0.80, and later another more save one evaluating to +0.79 (or less) the second line is completely ignored. So correspondence chessplayers (I am no one) spend a lot of time with their engines to find these hidden alternatives.

That's why all serious chess programs have something called "Multi-PV mode": Instead of showing just the best move with its associated score and main line, the program shows the N best moves (where N is a number chosen by the user), each with its own score and main line.

Tord

How is muti-PV impemented? Is it as simple as searching each root move with an open window or is there some trick so that too much speed is not lost? If it is simple to impement then I will try to put it in my next release. Does winboard protocol vs UCI protocol make a difference?

Mike

[Tord Romstad]

How is muti-PV impemented? Is it as simple as searching each root move with an open window or is there some trick so that too much speed is not lost?

There is no way to implement it without a big loss of speed. What I (and most other people, I guess) do is to use a normal PVS search, except that I search with an open window for the first N moves rather than just the first move. After the first N moves at an iteration have been searched, the remaining moves are searched with a zero-width window, with alpha equal to the lowest score among the N best moves found.

If it is simple to impement then I will try to put it in my next release. Does winboard protocol vs UCI protocol make a difference?

I no longer remember the Winboard protocol very well, but if I recall correctly it doesn't have a Multi-PV option. With UCI it is easy.

Tord

[Tord Romstad]

I am not only interested in the second best move from the starting position. I would like to get all sequences of moves until depth n, which evaluate e.g. less than one pawn worse compared to the optimal variation.

In that case, you can simply use multi-PV mode with a sufficiently big number of moves, and ignore all moves below your threshold. Admittedly this would take more time than searching all moves with a zero widow centered around a value of one pawn less than the best move found so far, but in practise this shouldn't matter much for a correspondence chess player, as both approaches are much slower and less efficient (and more boring!) than doing interactive analysis with the computer program.

Nevertheless, I would of course be willing to implement what you suggest if the UCI protocol supported it. It's only a 5 minute job, after all.

Tord

[Michael Sherwin]

How is muti-PV impemented? Is it as simple as searching each root move with an open window or is there some trick so that too much speed is not lost?

There is no way to implement it without a big loss of speed. What I (and most other people, I guess) do is to use a normal PVS search, except that I search with an open window for the first N moves rather than just the first move. After the first N moves at an iteration have been searched, the remaining moves are searched with a zero-width window, with alpha equal to the lowest score among the N best moves found.

If it is simple to impement then I will try to put it in my next release. Does winboard protocol vs UCI protocol make a difference?

I no longer remember the Winboard protocol very well, but if I recall correctly it doesn't have a Multi-PV option. With UCI it is easy.

Tord

Thanks Tord,

Then I guess that it is time Romi went UCI!

Mike

[glorscheid]

I think egines today show only a little bit of their knowledge they got during calculation. To get this out of them is in my eyes boring. Once I got it, it is very interesting to analyze it.
What I would like to get from my engine on the starting position is something like (here with depth of 2 and the helpfull assumption that all moves except 1.e4 and 1.d4 are worse)

1.e4 "0.2" (1.d4 "0.1" d5 (Nf6 "0.5" 2.c4 (2.Nf3 "0.2" d5) 2.c4 e6) e5 (c5 "0.3" 2.Nf3 (Nc3 "0.0") d6 (Nc6 "0.7") 2.Nf3 (2.Bc4 "0.0" Nf6 (Nc6 "0.3") Nc6 (d6 "0.5")

Ok, running it on the starting position is no good idea, because there are too many alternatives in the window. Bur running it on a complex position at move 15 may be interesting.
I an not sure whether I can get the result with multi-pv. Does it give me alternatives for both sides and sidevariations at depth n?

[Michael Sherwin]

I think egines today show only a little bit of their knowledge they got during calculation. To get this out of them is in my eyes boring. Once I got it, it is very interesting to analyze it.
What I would like to get from my engine on the starting position is something like (here with depth of 2 and the helpfull assumption that all moves except 1.e4 and 1.d4 are worse)

1.e4 "0.2" (1.d4 "0.1" d5 (Nf6 "0.5" 2.c4 (2.Nf3 "0.2" d5) 2.c4 e6) e5 (c5 "0.3" 2.Nf3 (Nc3 "0.0") d6 (Nc6 "0.7") 2.Nf3 (2.Bc4 "0.0" Nf6 (Nc6 "0.3") Nc6 (d6 "0.5")

Ok, running it on the starting position is no good idea, because there are too many alternatives in the window. Bur running it on a complex position at move 15 may be interesting.
I an not sure whether I can get the result with multi-pv. Does it give me alternatives for both sides and sidevariations at depth n?

This kind of output is certainly possible and it could be placed in a file on the hard drive. But, what you are looking for is most likely what Fritz can already do. It has been years since I have used Fritz so I do not remember what exactly it is called or does, however, IIRC it will analyze a position by searching to a certain depth and playing the N best moves one at a time repeating the process for each move and then backing up to try the next move. It was very impressive and it gives a very detailed report.