4
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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! :) $\endgroup$ Dec 20, 2010 at 1:29
  • $\begingroup$ 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? $\endgroup$ Dec 20, 2010 at 2:36
  • $\begingroup$ 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. $\endgroup$ Dec 20, 2010 at 2:37
  • $\begingroup$ 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 $\endgroup$ Dec 20, 2010 at 21:23
  • $\begingroup$ The link to research.microsoft.com in the previous comment no longer works, but the article is now available here: microsoft.com/en-us/research/publication/… $\endgroup$ Jan 27 at 11:15

3 Answers 3

12
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 21, 2010 at 22:03
3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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! $\endgroup$ Dec 19, 2010 at 9:36
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I guess I'm tacitly assuming that the probability that Alice picks a drawing move in position is proportional not just to $D$, but to the fraction of legal moves that lead to a draw. Is that what you intended? Or do you intend that, if $D=1/2$, then Alice's probability of picking a drawing move in a given position is always $1/2$ regardless of whether 99% of moves draw or 1% of moves draw? That seems unlikely (for example, what if every move draws?). $\endgroup$ Nov 14, 2021 at 19:01

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