Decryption Might Work For Chess

[towforce]

In this model, a chess position is viewed as encrypted information, and the decrypt would be the number of moves to checkmate.

For this model to work, there needs to exist a function that is capable of taking a chess position as its input, and giving back the number of moves to checkmate as its output. Without going into a formal mathematical proof, it seems obvious to me that such a function must exist (though obviously not discovered yet). If we assume that such a function does exist, then two questions arise:

1. How big would that function need to be? My opinion is that the answer is, "very much smaller than most people would imagine", and, per previous discussions, I believe that the evidence supports this idea. However, if I am wrong, and the size of the function would have to be very large, then decryption techniques are probably not going to be useful.

2. Can we find the function (the "encrypting algorithm") using decryption techniques? Well, we're starting from a bad starting position, but we could certainly make progress on doing so. The history of chess has been that it takes longer than expected to master it with computers: in 1957, Herbert Simon famously said that a computer would be world chess champion within 10 years. It actually took a few more decades than that - but we did get there.

If this method of solving chess would work, then IMO it would be many orders of magnitude easier to crack than SHA-256, the encryption used by most blockchains (e.g. cryptocurrencies), and, based on the history of encryption, it seems likely to me that SHA-256 will be cracked sometime this century. However, in the case of SHA-256, we do actually know what the encryption algorithm is already, which obviously helps.

[smatovic]

I guess you search for an optimal solution for chess like one for the Rubik's Cube?

https://en.wikipedia.org/wiki/Optimal_s ... k%27s_Cube

https://en.wikipedia.org/wiki/God%27s_algorithm

--
Srdja

[towforce]

I guess you search for an optimal solution for chess like one for the Rubik's Cube?

https://en.wikipedia.org/wiki/Optimal_s ... k%27s_Cube

https://en.wikipedia.org/wiki/God%27s_algorithm

--
Srdja

From the second article (link to exact section):

Well-known puzzles fitting this description are mechanical puzzles like Rubik's Cube, Towers of Hanoi, and the 15 puzzle. The one-person game of peg solitaire is also covered, as well as many logic puzzles, such as the missionaries and cannibals problem. These have in common that they can be modeled mathematically as a directed graph, in which the configurations are the vertices, and the moves the arcs.

Well chess certainly meets that criteria!

I've always thought that a simpler proof in chess would be to prove that it's not possible to win material from the starting position - and hence that chess is drawn game, which, IMO, could be done as follows:

1. Create set 1: a list of simple conditions, one of which must exist, in order to win material (a pawn or a piece)

2. Create set 2: for each element of set 1, create a simple list of conditions that must exist the element from set 1 to be possible

Repeat this process until either

1) there are no more new conditions

or

2) all the new conditions have already been created in previous iterations of the process

If none of the generated conditions applies to the opening position, then chess is a draw.

If some conditions do apply, but not enough of the conditions in that condition's sub-conditions do, then chess is a draw.

Otherwise, it's possible to win material from the opening position, and you now know what conditions in the opening position enable that. Hopefully, after the win of material, conditions exist to win more material, and hopefully that would continue until you had enough material advantage to be able to force the win against any opponent (there are positions from which I could beat Magnus! ).

If chess is drawn, this would be "game over".

If chess is a win, this would be very far from a God algorithm per your link - but it would be a good step in the right direction!

[towforce]

1. How big would that function need to be? My opinion is that the answer is, "very much smaller than most people would imagine", and, per previous discussions, I believe that the evidence supports this idea.

Srdja's link to algorithms for the Rubik cube provides more "soft" support for this: in the early 80s, when the cube was the #1 toy worldwide, how many of you guessed that a cheap, hand held computer would be able to solve it optimally in 20 (or less) face turns with almost no thinking time? I didn't - but if you follow this link on your phone, two minutes from now you can be doing just that!

https://play.google.com/store/search?q= ... mal&c=apps

[expositor]

For this model to work, there needs to exist a function that is capable of taking a chess position as its input, and giving back the number of moves to checkmate as its output. Without going into a formal mathematical proof, it seems obvious to me that such a function must exist (though obviously not discovered yet).

You've described a map from the collection of chess positions to the integers, and it certainly exists [1]. However, this map is not a cipher or any encryption scheme – there's no key involved and it's highly non-injective (billions and billions of positions map to the same integers). In fact, it sometimes behaves somewhat like a (really poor) hash function.

However, there's another way of looking at the function you've described – it's incidentally just the 32-man tablebase. Generating the n-man tablebases has been the subject of a lot of work. There are a fair number of symmetries that are exploited, but even so, we've only finished the 7-man tablebase. Many of the lines simply defy explanation, which suggests that the structure of chess is so complicated (or in other words, chess is so unstructured) that there may not be any ways to simplify the problem.

Solving chess has also been a mathematical fascination for decades or perhaps even centuries, and I'm not aware of any progress being made on the problem (besides e.g. showing that generalized chess on an n×n board is EXPTIME-complete). Even checkers and antichess, which have been solved, have only been weakly solved, whereas you are asking about chess being strongly solved.

[1] Every line of play from any legal position either has an accessible forced mate or it doesn't; if you are concerned about repetitions, you can show that retrograde analysis is guaranteed to terminate because there are a finite number of legal positions.

[towforce]

Solving chess has also been a mathematical fascination for decades or perhaps even centuries, and I'm not aware of any progress being made on the problem (besides e.g. showing that generalized chess on an n×n board is EXPTIME-complete).

Being EXPTIME-complete just means it takes a lot more moves to achieve the same things than it would on a smaller board - not that it's impossible for simplifying algorithms to exist.

Even checkers and antichess, which have been solved, have only been weakly solved, whereas you are asking about chess being strongly solved.

Decryption doesn't have to be perfect to be worthwhile: we know a lot about decryption by both sides in WW2 - and even the best teams didn't manage much more than 50% of the encrypted messages they received. In one sense, it can already be done: I think it's likely that a strong human guessing the number of moves to mate would do a lot better than would be expected by chance.

When chess was devised 1500 years ago in India, it's doubtful that its makers designed the game to be resilient to attack by powerful computers and sophisticated algorithms. It is surprising how well chess has held out in the modern age. However, just because the ultimate simplifications haven't been found yet, it doesn't mean that they don't exist. If the motivation to do so exists, we can combine many more dimensions into the solution algorithm than the human brain can, and hence produce relatively simple algorithms (but not intuitive to humans) which can score a position accurately in a high proportion of cases.

Once we have a way to find/generate such algorithms, we can improve them, and increase the proportion of positions for which the results are accurate, like, say, a decryption algorithm.

[expositor]

Being EXPTIME-complete just means it takes a lot more moves to achieve the same things than it would on a smaller board - not that it's impossible for simplifying algorithms to exist.

I mentioned EXPTIME-completeness just to illustrate that the mathematical progress we've made studying chess is fairly abstract and removed from the problem you're interested in. That particular result is irrelevant to the situation at hand – for an 8×8 board specifically, the problem is technically solvable in constant time.

Decryption doesn't have to be perfect to be worthwhile: we know a lot about decryption by both sides in WW2 - and even the best teams didn't manage much more than 50% of the encrypted messages they received.

I'm not sure that you actually read what I wrote (if so, I must not have made my point very well). This isn't a decryption problem. There's nothing to decrypt. Encryption requires both a message and a key, not just a message. The message must be uniquely recoverable from the cyphertext (given the key). The map from chess positions to depth-to-mate scores does not meet any of these criteria.

When chess was devised 1500 years ago in India, it's doubtful that its makers designed the game to be resilient to attack by powerful computers and sophisticated algorithms. [...] However, just because the ultimate simplifications haven't been found yet, it doesn't mean that they don't exist.

Mathematicians and computer scientists have been trying to do this for decades now. And although it's quite likely there are better techniques waiting to be discovered, it's entirely possible (and very very probable, imo) that chess by its very nature cannot be simplified to the degree that strongly solving the game is computationally feasible.

Edit: an addendum: I think we have attacked the problem by powerful computers and sophisticated algorithms with a fair amount of success. Ronald de Man's work on the Syzygy tables, John Tromp's work on position ranking, mate solvers like Chest, and community efforts like Stockfish and Elsie are all good demonstrations of this.

Edit: I don't mean to sound harsh ^_^' I appreciate you bringing up the topic, because it's an interesting one! and I enjoy the excitement and positivity.

[smatovic]

I think I agree, I do not see how to use asymmetric key (RSA), symmetric key (AES) or in-key (SHA) en/decryption for chess as described in the OP, but that does not mean that some kind of function as described by towforce does not exist, God's Algorithm for chess. That being said, would be fun if someone could make use of SHA-256 hashing for computer chess, there is a lot of beef out there in this regard, or alike.

--
Srdja

[towforce]

This isn't a decryption problem. There's nothing to decrypt. Encryption requires both a message and a key, not just a message. The message must be uniquely recoverable from the cyphertext (given the key). The map from chess positions to depth-to-mate scores does not meet any of these criteria.

I accept I've made a mistake there: you are correct. What I intended to convey was the usage of decryption techniques to find the patterns. For example: mapping the data into multidimensional space to uncover hidden patterns (which is how Bill Tutte famously worked out the wheel patterns of the Lorenz cipher - link).

When chess was devised 1500 years ago in India, it's doubtful that its makers designed the game to be resilient to attack by powerful computers and sophisticated algorithms. [...] However, just because the ultimate simplifications haven't been found yet, it doesn't mean that they don't exist.

Mathematicians and computer scientists have been trying to do this for decades now. And although it's quite likely there are better techniques waiting to be discovered, it's entirely possible (and very very probable, imo) that chess by its very nature cannot be simplified to the degree that strongly solving the game is computationally feasible.

Apart from the word "strongly", I profoundly disagree. Obviously I cannot yet prove it, but I've taken a good high-level look at chess, and to me it looks very likely that chess has relatively simple underlying patterns which will enable quick and "reasonably accurate" evaluation (I'm not yet willing to say "completely accurate", but I'm VERY far from convinced that this would be impossible).

If we could get a quickly computable algorithm requiring no recursion (or even iteration), it would only be a small step from there to "decompile" it to make an easily understandable explanation of what determines whether a position is a win or not.

Think about how you would classify problems according to whether they can be resolved with a relatively simple algorithm: you soon realise that problems that seem more complicated, or which have a larger search space, HAVE been resolved with relatively simple algorithms.

Chess is a simple game compared to some activities that some people do, and we have many dimensions (if you want a large number, maybe start with a dimension for every piece and every square), for each subset of dimensions you could apply arithmetic, then you could make new layers of derived functions by applying functions between these derived functions (effectively creating a complicated polynomial function). I have in mind a way to do this. At the moment, NNs are the best known "universal approximators", but they have horrible weaknesses which IMO makes them unsuitable for resolving chess, which is why I have in mind layers of directly built functions.

For the purpose of building the function, table bases are too big, so you run into the same "training" problem you find with nets. I see myself having to expend a lot of computer time working out which previously-used TB positions can be dropped from the training data in order to keep the size of it usable.

I appreciate you bringing up the topic, because it's an interesting one! and I enjoy the excitement and positivity.

Maybe too much excitement: I could probably do with a "dopamine detox" to get more productive and build a proof-of-concept for my idea.

[jtwright]

Obviously I cannot yet prove it, but I've taken a good high-level look at chess, and to me it looks very likely that chess has relatively simple underlying patterns which will enable quick and "reasonably accurate" evaluation (I'm not yet willing to say "completely accurate", but I'm VERY far from convinced that this would be impossible).

Even in the existing tablebases there are some mate sequences that are just incomprehensible to human and (non-TB) engine alike. I feel it's pretty plausible that the more "men" you add to the TB the stranger such sequences will get, although that's just conjecture.