Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
David, I believe I didn't merely point out some weak assumptions but also pointed out an experimental technique for comparing multiple algorithms by pitting them against each other, or having them make evaluations of static board positions. Per my moniker "sleepless", I'll need some more cogitation and perhaps some rest before I return and modify my answer. I believe my attempt at an answer pointed out that your $W$ and $D$ measures would be different at different depths/plies of the tree, and that assigning a single numerical value does distort the nature of these "grades". Back later! :) –  sleepless in beantown Dec 20 '10 at 1:29
    
Sleep sweetly, sleepless. I'm thinking over your suggestions. In particular I'm considering effect of the tradition of resigning lopsided positions - doesn't truncating play obviate the unwarranted oscillation of the winning advantage that my stochastic assumption might otherwise entail? –  David Feldman Dec 20 '10 at 2:36
    
Anyway my personal interest lies in estimating the hidden parameters $W$ and $D$ rather than finding better measures of playing strength. I do understand $W$ and $D$ as averages that may vary by changing the sample space. Available data will reflect how players perform in practical positions. The meanings of $W$ and $D$ should be conditioned on the same (fuzzily defined) sample space. –  David Feldman Dec 20 '10 at 2:37
    
Not directly related, but maybe interesting anyway, how a machine learning based system for chess ranking works research.microsoft.com/pubs/74417/NIPS2007_0931.pdf –  Yaroslav Bulatov Dec 20 '10 at 21:23
add comment

3 Answers

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 20006 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."

share|improve this answer
    
Here is a situation where choosing many winning moves may not indicate strength, and might be a sign of weakness: Suppose the position is a forced win in 3 moves, but instead I take 30 moves to win. This will bloat the number of winning moves I make, and it will decrease my percentage of blunders, but it suggests that I overlooked the faster way to win. –  Douglas Zare Dec 21 '10 at 22:03
add comment

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.

share|improve this answer
1  
also, the human chess player is neither a deterministic nor probabilistic "small number of states" finite-state-machine. It might be interesting to test your theory/concept out on two (or more) chess-playing algorithms, as that would allow for both algorithmic-players to be tested out on identical board positions for comparison. This type of comparison would be doable as the majority of playing algorithms are not "learning algorithms" which change based upon the new games which they play, thus the order in which board positions are tested would not matter. I sense an experimental approach! –  sleepless in beantown Dec 19 '10 at 9:36
add comment

Let us suppose that the initial position of chess is a drawn position. In this case, why not just assign someone a rating based on how often they win/lose/draw this particular position? I.e. how often they a game?

share|improve this answer
    
There's a word missing here. Can't make sense of what you wrote. –  David Feldman Dec 19 '10 at 21:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.