I have the Stockfish 7 engine loaded. I was playing through a variation of the Ruy Lopez [Open Berlin Defense], up to move 15, using SFish. I let the engine run to a search depth of 25, and selected the best move. A short time later, I played the same sequence of moves and, at move 10, the suggested move and subsequent line of play had changed. On the first analysis, it suggested 10.Nc3-e2, and on the second run through, it came up with 10.Nc3-e4, and the followup line was, of course, completly different. So, why the difference between the two runs? And if the engine analysis is going to change from one day to the next, how can we know for sure what the objectively 'best' move is in any given line of play?
Many expert chess engine users (such as correspondence chess masters) advocate using more than one engine to analyze a position, because each has strengths and weaknesses.
Generally, Stockfish is considered strongest in positions with tactical elements, while Komodo is biased toward positional / strategic strengths. Neither is a broad-spectrum solution.
As other responders have indicated, there's a lot of squishiness in the output of engines when there aren't any forcing lines, or transpositions are possible and undifferentiated. Engines do a fair amount of pruning, which saves computation but introduces problems with "horizon". The horizon is the depth of moves the engine will look at a variation that leads to a disadvantage. Such a variation may have a redeeming comeback move at the end, but may be just long enough that the engine gives up analyzing the line before it reaches the comeback move, because it's over the horizon.
On its way to a "final" evaluation, the engine is essentially approximating. That is, it evaluates the position, adds a few more moves and looks at the position, evaluates for the "best" move based on those, shifts to the next position, adds a few more hypothetical moves and evaluates, shifts, and so on.
At any one particular instant, the engine may be just about to shift from one evaluation of the position to another, even while the depth you're specifying is being reached. If you terminate the analysis manually (i.e. pick a move and make it, or just hit the Stop button), you may get a different "best" move recommendation in one millisecond, and another one a millisecond later, even at the so-called maximum depth.
The best way to ensure consistency is to run the engine by itself in analysis mode using software such as Fritz. The engine will evaluate the actual moves of a game (or an opening variation) offering improvements. The computation behind the improvements will be strictly limited by depth or time, as you specify. If you let the engine terminate the search at each position, you should get consistent (deterministic) results. Unfortunately, although it will annotate the improved variation at each position, this approach involves the engine resetting its analysis with each move/position of the move score that is analyzed. It won't move from improvement to improvement to improvement, leaving the game behind.
To get that kind of result, you need an engine tournament. Give two identical engines a starting position (such as the Berlin or Moscow Variations of the Ruy Lopez) that you want to improve from, set their limits as discussed, and let them duke it out. Play at least a dozen games, and see if anything shakes out. Two cautions:
- This is time-consuming (but at least it's not your time), and
- As you go further and further from known theory, the less likely that you'll ever see that position in an actual game played by anyone other than these engines, for the reasons discussed above.
BTW: As far as I know (and my research supports this), non-deterministic algorithms are not used in Stockfish or any other major engine. The reasons for this are self-evident - if you're looking for a solution to a deterministic problem, you use a deterministic approach. Stochastic approaches are only better in stochastic problem domains, or where a deterministic model is unavailable or problematic in itself.
As far as analysis depth goes, there's a point of diminishing returns that's determined by what you're trying to accomplish.
In different types of positions, the evaluation function of any engine will tend to stabilize at different points. For one type of position, there will be no noticeable difference in the evaluation or the recommended "best" move after about 20 ply. In another, you may need to hit 26 or 28 ply for the move to stop changing, and the evaluation function to stabilize at a terminal value to 2 significant digits (e.g. 1.87, instead of 1.86 or 1.88).
Clearly, if your goal is the perfect move / best evaluation accuracy, then if you can only choose one depth/time parameter limit, instead of a stability limit / sensitivity threshold, then you need one large enough to accommodate the most positions where the evaluation continues to be unstable to greater depth/for longer analysis time. You need to aim high.
But there's a tradeoff.
In an actual game, as the game proceeds, the probability increases exponentially that one or both (human) players will play a non-optimal move. Since the engine only calculates optimal moves, this means that in quiet positions (and in some complex tactical ones) the engine's choice of a move and the actual move played will almost always diverge, even if only slightly. It will also do so surprisingly frequently, often as many as a dozen times in a game even between GM's. This is, in fact, one of the indicators that TD's use to figure out whether a player at a tournament is getting outside help from an engine.
Because of this, if you're comparing a variation that an engine analyzes with a line that humans might actually play, the longer the variation, the more likely it is that the tail of the variation will only match the humans' moves when there is a forcing line. In fact, unless the line is forcing, a fair amount of the time not even the opponent's first reply will match the engine's expected optimal reply.
The more unclear or quiet the position, the shorter the useful tail of an analyzed variation will be, even if the opponent replies with the expected move.
So, if you're analyzing a murky or quiet position or opening, and you're curious to know whether an engine could possibly play a line better, then have at it. But if you want to know if it's possible to find a single winning line given the replies that the opponent would actually end up playing, the real odds start to look like a craps game as the variation gets longer.
That said, there are ways to optimize how you use the calculation time as you analyze a game or an opening variation.
As @GeorgeJempty indicated, you can get much better results at 35 ply (ply are half-moves; 12 ply is 6 moves for each side) than you will at 25. However, I use Stockfish on a Quad AMD at 2.9 GHz, and the positions where I need to go even 26 ply deep to find a hidden winning move that were missed at 25 ply are very few and far between (something on the order of 1 in 1,000). For me, that's simply not worth the extra compute time it takes to find it. What's more, the resulting improvement is almost certainly going to be negligible, because the probability that the opponent would have made the corresponding replies shrinks to zero, and the resulting end position would never appear.
In other words, the longer the move sequence, the greater the probability that any analysis will be overtaken by events. This is one reason that even Grandmasters rarely calculate beyond 12 ply (except in endgames), and often only calculate to 4 or 6, relying on positional intuition instead.
As for how much of a difference ply depth makes at extreme depths, I have some background in the problem. When I'm screening games for analysis targets (by this I mean trawling through large sets of them to find ones that had interesting highlights suggesting they're worth deeper analysis), I use just 23 ply. My configuration can get through about 10 games an hour at that clip, so I can process about 750 every night. Once I find these, I then reset the depth to 25, and rerun the analysis on those selected games.
Obviously this approach would only make sense if I'd tested it, and I have. I've run a few experiments to test the merits of different depths, and the settings I use turn out to be optimal for the compute time I'm willing to allocate. Only about 1 in 50 games turns out to have an interesting feature that shows up at 25 ply but gets missed at 23. Clearly, that suggests that some of the games I screened out using 23 ply would also have shown such elusive features if they'd screened in instead, and subsequently been processed at 25 ply. That's just the opportunity cost of the rate at which I choose to process games, and for my purposes, there's so much low-hanging fruit I don't really need to go climbing trees.
I would definitely take advantage of every CPU on your PC's chip, though. Most of the world's PC's computational power is incredibly underutilized. On my configuration, at 1 CPU Stockfish does about 1K positions / sec, while at 4 CPU's, it runs over 4K positions / sec. That quadrupling of the rate really tells when you're data mining, as I am.
To reiterate, I would also turn to Komodo for analyzing openings and quiet/murky positions as a comparative tool, and you should find that with one of the two engines the evaluations stabilize tolerably soon, at around 22-23 ply for most positions.
Chess engines are not necessarily deterministic due to multi-threading and heavy pruning.
In many positions, there is no such thing as objective "best" move. Many possibilities are possible and sound. Stockfish would not be able to give you a consistent answer in this case. Chess engines are simply not powerful enough to solve an opening for us.
The next time you analyze the same position, Stockfish might have hashing to guide the search. This will likely give you different line.
A chess engine's algorithm is "non-deterministic", meaning, given the same input, it will not necessarily provide the same output; see: https://en.wikipedia.org/wiki/Nondeterministic_algorithm. I especially like the following quote: "a nondeterministic algorithm represents a single path stemming into many paths, some of which may arrive at the same output and some of which may arrive at unique outputs." The single path stemming into many paths rather aptly describes the choice of moves in a chess game.
I'm guessing you were not looking at multiple pv's (primary variations) but rather just one at a time? I highly recommend always looking at at least two pv's at a time; if their evaluation is within 0.05 they are basically equal. Furthermore you will have much better luck finding definitive best moves if you let the search depth to closer to 35 rather than 25. If you have a multi-core machine (most are quad cores these days, so 4) you could increase Stockfish's settings to use 2 or even 3 cores (if you don't think you'll be doing other intense computing in the meantime) and it will get to depth 35 a lot quicker than using 1 core.