Analysing with computer

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
glorscheid

Analysing with computer

Post by glorscheid » Sat Jul 14, 2007 8:36 pm

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.

User avatar
smrf
Posts: 484
Joined: Mon Mar 13, 2006 10:08 am
Location: Klein-Gerau, Germany
Contact:

Re: Analysing with computer

Post by smrf » Sat Jul 14, 2007 9:15 pm

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
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Analysing with computer

Post by Tord Romstad » Sat Jul 14, 2007 9:25 pm

glorscheid wrote: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

Re: Analysing with computer

Post by glorscheid » Sat Jul 14, 2007 9:44 pm

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
Posts: 2919
Joined: Fri May 26, 2006 1:00 am
Location: OH, USA

Re: Analysing with computer

Post by Michael Sherwin » Sat Jul 14, 2007 9:52 pm

Tord Romstad wrote:
glorscheid wrote: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
Regards,
Mike

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Analysing with computer

Post by Tord Romstad » Sat Jul 14, 2007 10:26 pm

Michael Sherwin wrote: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
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Analysing with computer

Post by Tord Romstad » Sat Jul 14, 2007 10:42 pm

glorscheid wrote: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
Posts: 2919
Joined: Fri May 26, 2006 1:00 am
Location: OH, USA

Re: Analysing with computer

Post by Michael Sherwin » Sat Jul 14, 2007 10:56 pm

Tord Romstad wrote:
Michael Sherwin wrote: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! :D

Mike
Regards,
Mike

glorscheid

Re: Analysing with computer

Post by glorscheid » Sat Jul 14, 2007 11:13 pm

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
Posts: 2919
Joined: Fri May 26, 2006 1:00 am
Location: OH, USA

Re: Analysing with computer

Post by Michael Sherwin » Sat Jul 14, 2007 11:53 pm

glorscheid wrote: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.
Regards,
Mike

Post Reply