Probability theory and measuring the true strength of chessplayers

Question

If you wanted to measure the strength of, say, a chess player, the best way would involve knowing the true value of each position: then you could compute the frequency $W$ with which the player finds a winning move in a won position, and $D$ of finding a drawing move in a drawn position.

Even without a perfect evaluation algorithm, perhaps mathematics offers the possibility of saying something about a player's $W$ and $D$? So I ask, do there exists tools in probability theory, if not for chess then at least for some class of idealized games (only the morphology of the game tree would matter) that would would allow prediction of one player's winning percentage over another given just the two players' $W$ and $D$ frequencies?

If yes, then the distribution of winning percentages in a population of players might serve as data for an inverse problem allowing the statistical estimation of $W$ and $D$ frequencies (or at least associated derived quantities, or relative quantities).

Also welcome: thoughts about refining the model in the second paragraph to get results more realistic for real world games like chess (e.g., separate frequencies for opening, middle game and ending).

---

Edit: While I appreciate critiques of my model, I hope the weakness of the model doesn't distract from the purely mathematical question of the 2nd paragraph: for suitable idealized games, can one compute dominance in the game globally from the players' $W$ and $D$ frequencies? If that probability question turns out intractable then my whole project sinks; if it has a positive answer, I can hope to refine the models.

I'm not attached to $W$ and $D$ as the ultimate measure of game playing strength. I am interested in the mathematical challenge of estimating these frequencies in the absence of an evaluation oracle.

Also, is it enough merely to point out the naivete of my model? Shouldn't the critic argue that my distortion has significant numerical effect on the dominance calculation?

Answer 1

Your question makes assumptions with which I disagree.

I do not think that strength means choosing winning moves more frequently in theoretically won positions. The positions encountered in chess are not uniformly random, and the positions you encounter depend on previous moves. You might find someone who reliably executes a nontrivial endgame, but who performs poorly in related positions someone else sets up.

Part of chess is giving an imperfect opponent opportunities to make mistakes. Your measure assumes there is no skill involved in playing theoretically lost positions, but in practice there is.

Although it is popular to call chess mathematical, I think many other games such as backgammon allow much deeper mathematical analysis than chess, in part because positions have equities which are not restricted to $\{0,1/2,1\}$, and there are MonteCarlo methods for estimating the values of positions. Serious backgammon players commonly measure skill in error rates expressed as normalized millipoints per move. In my November 2006 column for GammonVillage, I looked at the correspondence between backgammon error rates and Elo rating differences on one backgammon server, concluding, for example, "100 rating points roughly corresponds to 1.8 millipoints per move."

Answer 2

David, your question makes the assumption that players will stochastically pick a move in the current possible set of branches, and does not say anything about the current depth of the tree. I believe that for certain states, particularly those labeled "end-games", it is possible for an astute player (or an experienced player) (the set of astute and experienced players are not equal) to have a higher $W$ percentage against an equally skilled or worse opponent.

Thus I believe that $W$ and $D$ are not just functions of one player $P_1$, but also of - the opponent $P_2$ and of - the current-depth of the game tree (= the number of moves played thus far), and - the current-state (global and local) of the game board.

$P_1$'s $W$ may change for a different opponent and for certain opening sequences or end-games with which they are familiar.

Now if you allow the assumption that you do not have an oracle evaluation function, but do have the win and draw percentages for two players, $P_1=(W_1, D_1)$ and $P_2=(W_2,D_2)$, your question in the second paragraph asks if that is sufficient to allow for calculating the probabilities of one player dominating over the other. I do not believe that there is a way to calculate this, as the $W$ and $D$ ratios are going to have to be calculated as a measure over all possible game board states, and the finite sampling of win and draw ratios for a finite number of games and board positions will not be sufficient to allow for such an extrapolation to be made.

Back to my first ruminations: the $W$ and $D$ will depend on the depth of the game tree and the relative experience of the players. If a player picks a bad move but has better experience, she could still recover and win at a later point in the game. If a player picks a bad move but does not have much experience, they are less likely to be able to recover and get to a position of advantage.

An experienced player recognizing classic openings may play by rote for a few moves, or may in fact feint and play slightly askew to see how her opponent responds. This type of psychological repertoire and skill cannot be encoded and captured in a two parameter model, and is also why I think $W$ and $D$ ratios are not just a function of the player $P_1$ but also of the opponent.

Answer 3

Even if we accept your proposal to model a player with numbers $W$ and $D$, it seems unlikely to me that we can get very far without further assumptions.

Focus on drawn positions for a moment. Say that a position is a "tightrope" if only a tiny fraction of the legal moves save the draw, and say that a position is an "easy street" if almost all legal moves maintain the draw. Now notice that an easy street could have the property that most drawing moves give the opponent an easy street, but exactly one drawing move (let's call it a tesuji) confronts the opponent with a tightrope. Clearly, your chances of winning depend not only on your probability of picking a drawing move, but on your probability of picking the tesuji.

Perhaps you want to wave away this difficulty by assuming that out of all drawing moves, players pick one uniformly at random, and out of all losing moves, players pick one uniformly at random. But there remains a difficulty, which is that tightropes and easy streets could be distributed in some complicated and asymmetric manner throughout the game tree. If Alice has a higher probability of picking a drawing move than Bob does, then Alice might still be at a disadvantage, if the game tree is such that Alice is confronted with more tightropes than Bob is. In any case, assuming away the probability that a player can find a tesuji would seem to be assuming away much of what we think of as skill.