The Complexity Of Chess

[towforce]

I'm still thinking about this topic, and I thought I'd move it away from the "fruit fly on steroids" thread to its own thread.

I'm not planning to continue the discussion on whether simple algorithms can solve exptime problems (I'm willing to, but the urge to do so is not strong).

However, the complexity of chess is an absolutely fundamental issue in seeing "the big picture" regarding chess.

There is very likely to be a negative correlation between the complexity of a game and the ease of creating a relatively simple algorithm for playing it well.

A game of chess can be up to a little under 6000 moves (the upper limit caused by the 50 move rule), but in reality the average game is probably in the 40-50 move range.

On average, IIRC, there are around 28 choices of move in each position - and here we can start to simplify (reduce the scale of the game): the better a player you are, the fewer of those moves will meet your quality threshold. These are just guesses, but I'm going to go for the following number of moves that meet the quality criteria in chess positions at different elo levels:

Code: Select all

+------+----------------------------------------------------+
| Elo  | Average Number Of Moves That Meet Quality Criteria |
+------+----------------------------------------------------+
| 1000 | 15                                                 |
+------+----------------------------------------------------+
| 1500 | 10                                                 |
+------+----------------------------------------------------+
| 2000 | 5                                                  |
+------+----------------------------------------------------+
| 2500 | 2                                                  |
+------+----------------------------------------------------+

Thus the game of chess is much smaller, and hence a lot simpler, for a novice than it is for a GM!

So... in terms of searching for deep patterns in chess, GM level is going to be a better place to look than novice level.

btw - as the number of moves gets close to one, the game becomes drawn - which is happening right now (especially at correspondence level chess).

[Chessqueen]

I'm still thinking about this topic, and I thought I'd move it away from the "fruit fly on steroids" thread to its own thread.

I'm not planning to continue the discussion on whether simple algorithms can solve exptime problems (I'm willing to, but the urge to do so is not strong).

However, the complexity of chess is an absolutely fundamental issue in seeing "the big picture" regarding chess.

There is very likely to be a negative correlation between the complexity of a game and the ease of creating a relatively simple algorithm for playing it well.

A game of chess can be up to a little under 6000 moves (the upper limit caused by the 50 move rule), but in reality the average game is probably in the 40-50 move range.

On average, IIRC, there are around 28 choices of move in each position - and here we can start to simplify (reduce the scale of the game): the better a player you are, the fewer of those moves will meet your quality threshold. These are just guesses, but I'm going to go for the following number of moves that meet the quality criteria in chess positions at different elo levels:

Code: Select all

+------+----------------------------------------------------+
| Elo  | Average Number Of Moves That Meet Quality Criteria |
+------+----------------------------------------------------+
| 1000 | 15                                                 |
+------+----------------------------------------------------+
| 1500 | 10                                                 |
+------+----------------------------------------------------+
| 2000 | 5                                                  |
+------+----------------------------------------------------+
| 2500 | 2                                                  |
+------+----------------------------------------------------+

Thus the game of chess is much smaller, and hence a lot simpler, for a novice than it is for a GM!

So... in terms of searching for deep patterns in chess, GM level is going to be a better place to look than novice level.

btw - as the number of moves gets close to one, the game becomes drawn - which is happening right now (especially at correspondence level chess).

I have to disagree with you that the chess game is much simpler for a novice like me than it is for a GM. Since Novice like me usually get lost during the Middlegame stage, whereas it is simple pattern recognition for any GM to know exactly what to do under these circumstances:

1st Most of us Novice do NOT know how to take advantage of Weeak Squares and outpost for the Knight
2nd When to do a pawn Breakthroughs
3rd Or how to best utilize the power of a pass pawn
4th How to best play a Minority Attack
5th Or How to and when to play for a Pawn Majority Attack
6th When it is convenient to trade pieces or NOT
7th When to Launch an Attack in the center of the board, Queen Side , or King side of the board
8th Best and fastest way to improve our pieces mobilities
9th When and How to best take advantage of backward pawn or isolated pawn
10th When to sacricife a Queen, or a Rook to force Checkmate.
1th How to best place our pawn structures with different chess Openings.
12th Finally most of us weak novice players do NOT know of the best way or when to use the Greek Gift sacrifice during the middlegame. These are just a few of many many ways that a game of chess is harder for us novice especially during the Middlegame than it is for any GM; since they recognize so may paterns that for most GM the game comes naturally whereas for us novice we simply do NOT know what to do during the middlegame and after thinking and thinking always select the worse plan and always manage to select a Blunder move than to create a masterpiece like GM.

NOTE: If somebody can recommend me a good Middlegame book that cover all these in simple to understand for Novice like me, probably I might increase my chess rating by at least 400 to 500 elo.

[towforce]

Thus the game of chess is much smaller, and hence a lot simpler, for a novice than it is for a GM!

Oops - that's the wrong way around!

[towforce]

SAT is NP-complete (link), but algorithms exist that can solve many instances quickly. NP-Complete gives the upper-bound for how long it will take to solve something - not how long a particular instance will take.

Chess has a simplification that SAT doesn't: dependency between the variables. This is a major reason why so many patterns occur in the game: a GM can often look at a position and understand it at a glance: I have actually witnessed this for myself. It's easy to see that this dependency between the variables reduces the complexity of chess by many, many orders of magnitude.

Human players start by encoding simple patterns, and over time the patterns become more sophisticated. If you ask a GM to explain a position, words will come out of their mouths - but they're not able to genuinely explain the encoded chess patterns that they have - at least not in a way that's meaningful to a lower ranking player. If they give a simple explanation that's easy to understand, that explanation probably won't hold in other positions with similarities to the current one.

There are no good reasons to think that either GMs or even NNs trained against billions of positions (more positions than any human will see in their lifetime) have found the best patterns for chess at this time.

[Henk]

So Pow(2, 50) is about Pow(1000, 5) = 10 * million * million. Chess will be solved within ten years. Unless number of good moves is not 2 but 5.

[Henk]

So Pow(2, 50) is about Pow(1000, 5) = 10 * million * million. Chess will be solved within ten years. Unless number of good moves is not 2 but 5.

O wait mistake Pow(1000,5) ~= 1000 * million * million of course.

[towforce]

So Pow(2, 50) is about Pow(1000, 5) = 10 * million * million. Chess will be solved within ten years. Unless number of good moves is not 2 but 5.

Good point!

In some cases, though, the GMs or strong chess engines might be mistaken in their choice.

Let's take a moment to ask how chess might be solved:

1. Practically: the engines become so good that nobody can find a way to beat them (top level correspondence chess is seeing this already).

2. Actual proven solution

Option (2) may require some mathematics that hasn't been devised yet - but here are a couple of ideas that might be possible with today's knowledge and technology:


Proof Method 1

(p1) Generate conditions that exist if, and only if, checkmate can be given

(p2) Generate conditions that exist if, and only if, a p1 position can be forced

(p3) Keep deepening this condition list. Each time a condition is added, check it doesn't already exist in the condition tree

(p4) When the list becomes exhausted (each new condition generated is already in the list) you will have a set of conditions for being able to mate the opponent


Proof Method 2

Because chess has so many symmetries and so much interconnectedness (mathematically, "dependence" - the opposite of "independent" variables) between the variables, there may exist a deep pattern that enables accurate evaluation of all positions. If it does exist, the proof of chess would then become:

(p1) Find the deep pattern

(p2) Reverse engineer this pattern to find out what it's really telling us about chess

(p3) Maths problems are always easier to solve when you already have the solution. Use this knowledge about the solution to work out what we've all missed about chess, and why it enables us to determine the outcome of a particular position