I think this is actually based on subjective measures. An annotated game[0] will have ?!, ?, and ?? added by human commentators to indicate varying levels of mistakes. A computer analysis can make use of these subjective move evaluations within an annotated game to easily measure which players cause their opponents to make mistakes at a significantly greater frequency than their normal rate of mistakes.
The computer program Fritz actually has algorithms to imitate a human's analysis. It's one of my favorite tools to improve my game, since it searches databases of master-level games to find games that progressed in the same way and also gives "human-like" annotations. Here's an example PGN[1] from one of my games (NAG[2] has been converted to Unicode for the sake of clarity)
Since computers play chess (better than humans) by looking at moves and ranking them as advantageous or disadvantageous, I would think it would be relatively straightforward to use a computer to decide whether a move is a mistake or not.
You can't definitively say that a computer's move is best, the branching factor of chess means that searching the game tree until finding a checkmate is nearly impossible. It leads to the horizon effect:
but recent advances in AI like in Deep Blue have introduced branch extension, where branches of the game tree with statistically similar rankings are searched further until one can be definitively regarded as the best one.
To summarize, chess engines can't give definitive answers on how good a move is because, like humans, they can't search the whole game tree.
This applies in the earlier stages of the game. In the endgame, when there are fewer pieces, computers can find the best move. There are many instances where say, you reach and endgame with some nine pieces, and the computer will find a mate in 18 moves.
One of the reasons computers are so much stronger than humans, especially in the endgame, is because they have incredibly large pre-calculated tablebases[1] of 3, 4, 5 and 6 piece positions. So, if a computer calculates ahead 15 moves, and reaches a 6 piece ending, it already knows the exact evaluation of this position. And in some of these cases, the number of moves from that position to the final position (forced draw or checkmate) can be 10-100 moves [2]. But it is already calculated, the computer doesn't have to go any further. So in effect, the computer calculating 15 or 20 moves ahead in a late stage position can actually be calculating 50 or 100 moves ahead.
This is why the second part of Carlsen's quote is so important:
"Sometimes 15 to 20 moves ahead. But the trick is evaluating the position at the end of those calculations."
A human sees a late game position and has to actually calculate it all the way to its conclusion or at least a key position where they are confident of the evaluation [3]. A computer doesn't have to, and believe me, some of those 6 piece endgame positions are really weird. You move a piece just one innocuous looking square and it can alter the outcome from a win to a draw. There in fact were many endgame positions throughout chess history which were considered solved, only for the evaluation to change after a brute force calculation.
I'm not particularly good at chess [4], but in slow games I will routinely calculate 10 moves ahead in some sharp positions. Now, I'm not comparing my calculating ability to a GM, which is obviously better in every way, but the fact that a GM calculates 15-20 moves ahead is not why they are good. It is that at every step of that calculation they are evaluating the position incredibly accurately and are deciding the right moves to calculate.
In fact, due to the horizon effect, the reason computers got a lot better than humans wasn't due to raw calculation speed, it was due to massive improvements in their evaluation ability (like endgame tablebases) allowing them to put that massive calculation advantage to good use.
2: All of which are already in the tablebase by definition, because you can't add to the number of pieces on the chess board
3: For example, if I can calculate a position to where I have a rook and a king and you only have a king, I don't have to think any further, I know this is a win for me.
It would be able to tell if the move was a mistake if playing against a computer. A move that would be bad against a computer opponent might throw a human opponent off balance through surprise, or take the game into a type of board state which was unfamiliar and disorienting to the opponent.
[0] http://en.wikipedia.org/wiki/Chess_annotation_symbols#Move_e...