Chess as a game of chance.

Chess is touted as a game of pure skill, there being no explicit elements of randomness in its structure. As I am learning to play better chess using various robotic opponents, I am starting to realize that there is a large amount of randomness, in the Chaitin/Kolmogorov sense, involved in the game. The depth of analysis a player chooses to use is a function of that players estimate of the opponent's depth of analysis, the computing/thinking resources available to the player and the time available for analysis. At any finite level of examination, there is always a risk that at deeper levels, significant pitfalls or opportunities exist that will be missed. Playing out the game will eventually reveal these pitfalls/opportunites for the gain or detriment of the player. You can imagine a probability distribution of gain/loss for moves over the horizon, with small gains or losses being of much higher probability than large ones. This uncertainty as a function of the level of analysis introduces an element of chance into an otherwise pure game of skill. A valid theoretical framework around this concept would allow statements such as: if player A can evaluate postions 6 ply ahead and player B can evaluate positions 8 ply ahead, what is the probability that B can win as white? Or

This isn't an element of chance, but merely a method of attributing a skill rating. There is no uncertaintly, just an unknown - which are different

I agree with Kevin's view that this isn't a manifestation of luck, but simply a measure of how skillful the players are. However, I think it's still an interesting question. I took a swing at it in my 1978 PhD thesis at Carnegie-Mellon, 'Performance Analysis of the Technology Chess Program', relating 2-ply increases in search depth to corresponding USCF rating increases. Down in the area of my program (class D) the correspondence was linear, which I found surprising. I don't remember the number (and don't have a copy of my thesis with me), but when asked during my oral defense to extrapolate how many ply would be required to get to world champion level if it remained linear, I came up with about 13 ply. I seasoned that with massive caveats about having no reason to believe the curve would stay linear, since I was measuring from (I think) about 3 ply through 7 ply. Nonetheless, this number did eventually turn out to be about right, even if it was by... chance.

Nope. The Chaitin/Kolmogorov senses permit unbounded computing power. The game is almost devoid of information.

I've heard that rating goes more or less lineraly with ply, I don't buy it because I don't think 'ply' by itself is a particularly good measure of chess skill. Unless you can actually see until checkmate, being able to accurately evaluate a position without looking in advance matters more than being able to see a lot of moves in advance.

Computers are much more consistent than humans. I suspect that a human using a computer as a blunder checker could be a much stronger player than either the computer or the human alone.

The 'linearly' may or not be true, or may be only an approximation, but it should be undeniable that if you have a program that searches to 11 ply, it will be stronger if it can search to 13 ply in the same amount of time (e.g. by giving it a processor that's 25 times faster, or 25 times as many processors). At the end it does its same kind of evaluation (whatever that may be), but in the extra two ply it has discovered combinations that win a piece or do anything else that its evaluation function takes into account. You may argue about how much of an improvement this gives, but it *is* an improvement.

At some point deeper and deeper tactics become indistinguishable from strategy. Some have argued that this number may be as high as 30 ply, and some as low as 13 ply... but there *is* such a number for any fixed evaluation function.

Very likely (unless the program is really good and the human is really bad and any of the human's overrides damage the position). I've read that professionals used programs during their adjournments, though that's old information

George Weinberg schrieb:

But doesn't that come down to the same thing? If you can evaluate positions better, you can prune the search tree more aggressively and go deeper.

If you mean forward pruning (i.e. ignoring whole branches of the tree without investigating them further than your static evaluation function), it's tough to make that work because of the baby+bathwater problem. You can lose opportunities when it turns out the position has a surprise for you. So far this always seems to have happened

SPOILER (JUST KIDDING)

Gedanken: We set up two identical, non-randomizing chess programs, P_m and P_n, opposing each other. Designate the ply depths to which these programs examine prospective moves as m and n respectively. Let m = n. Play them against each other. If P_m (white) wins the game, increase n and replay the game. Repeat until P_n wins. Now repeat this process, but increasing m until P_m wins. Continue with this procedure, alternating the increasing index, m or n on each repetition.

Conjecture: For all chess programs P, after reaching some index value k, no increase of the opposing program's index value will produce a win. Proving that k is the maximum useful index value for any given chess program is equivalent to solving the halting problem for this special case. In general, the value of k for an arbitrary chess program can only be determined by exhaustive evaluation of the move tree to the limit of the number of allowed game final positions.(~10^10)

If this conjecture is true, even a player using a good estimate of k cannot be certain that their choice of moves will be optimum since the (theoretical) opponent may use a larger ply that dominates estimated k. Thus, the outcome is random (less than certain) in the Chaitin sense, ignoring the possibility of evaluations beyond current limits of computing. John Bailey

<snip>

A cross-post to rec.games.chess might be worthwhile.

mnkhjyiuytrewqsadxfcgvghbhnjnkmfxdseawq123353bmnnnmjkil o098766544321wqsaxzdvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv