Fruit fly races on steroids?

[towforce]

IN YOUR FACE AI!

Don't you be insulting me on my planet!

[hgm]

Yeah, but you cheat, as the Bat cannot fly to n9 with a non-capture. If you play 1.i5 to make that possible it would see the threat, and play 1... m10, even at 2.5 ply. It just tries to be polite.

[towforce]

I want chess solved and fully explained. In contrast to most other people, I think that this is achievable with today's technology...

Looks as though a God algorithm has been found for prime numbers - link.

IIRC, a lot of public/private key encryption is based on the difficulty of factorising large numbers: the above report tells me that this type of encryption will soon be futile!

For anyone with blockchain products (e.g. cryptocurrency), you're OK for now - these mostly use elliptical encryption - but the mathematicians will be coming for you in the fullness of time!

The trend is that relatively simple underlying patterns are being found in all sorts of places where you wouldn't expect them, and as a person who has looked into this, it seems "obvious" to me that the chess set is going to have them. See previous threads on this subject for more explanation on why I think that.

[Jouni]

Hmm. This paper has been removed from SSRN at the request of the author, SSRN, or the rights holder.

[towforce]

Hmm. This paper has been removed from SSRN at the request of the author, SSRN, or the rights holder.

Yes - It was a draft paper, and it looked flawed. It looked as though they had discovered a filter for finding some primes - but such filters already exist.

Some possibilities:

1. I've been caught out by hype again

2. They have got what's claimed, but the paper needs to be improved

3. They have got what's claimed, but the secret services pulled it to keep it secret

[petero2]

The trend is that relatively simple underlying patterns are being found in all sorts of places where you wouldn't expect them, and as a person who has looked into this, it seems "obvious" to me that the chess set is going to have them. See previous threads on this subject for more explanation on why I think that.

Does your explanation fail for generalized chess? If it does not fail, we can conclude that your explanation is wrong or incomplete, since it is already known that generalized chess is EXPTIME-complete and therefore there cannot exist "simple" patterns that can decide the game-theoretic value of all positions in generalized chess.

[towforce]

Does your explanation fail for generalized chess? If it does not fail, we can conclude that your explanation is wrong or incomplete, since it is already known that generalized chess is EXPTIME-complete and therefore there cannot exist "simple" patterns that can decide the game-theoretic value of all positions in generalized chess.

Asked and answered (link).

[petero2]

Does your explanation fail for generalized chess? If it does not fail, we can conclude that your explanation is wrong or incomplete, since it is already known that generalized chess is EXPTIME-complete and therefore there cannot exist "simple" patterns that can decide the game-theoretic value of all positions in generalized chess.

Asked and answered (link).

Yes, but you later admitted that your answer was wrong.

I have not read the paper, but petero2 quoted "there exist infinitely positions for which deciding ... requires ... steps to compute". This does not mean there are no simple positions where the win can be proved easily. There could also be infinitely many simple positions as in your example.

Agreed.

So the main problem is still the following:

A direct quote from the article:

This implies that there exists d > 0 and infinitely many positions p such that an algorithm for deciding whether White (Black) can win from that position requires at least c^(|p|^d) time-steps to compute, where c > 1 is a constant and |p| is the size of p. Generalized chess is thus provably intractable, which is a stronger result than the complexity results for board games such as Checkers, Go, Gobang and Hex which were shown to be Pspace-hard.

[towforce]

Does your explanation fail for generalized chess? If it does not fail, we can conclude that your explanation is wrong or incomplete, since it is already known that generalized chess is EXPTIME-complete and therefore there cannot exist "simple" patterns that can decide the game-theoretic value of all positions in generalized chess.

Asked and answered (link).

Yes, but you later admitted that your answer was wrong.

I have not read the paper, but petero2 quoted "there exist infinitely positions for which deciding ... requires ... steps to compute". This does not mean there are no simple positions where the win can be proved easily. There could also be infinitely many simple positions as in your example.

Agreed.

That was not me "admitting my answer was wrong" at all. Not even to a small degree. That was me conceding the particular point that Chess Kobra was making.

[towforce]

To help anyone who's interested, here's a direct link to the paper PDF - link.

Assuming that the paper is, in general, correct, then the part of the paper that REALLY MATTERS is the section called "POLYNOMIALITY OF TRANSFORMATION", which is a little over half a page long, and is on page 213 of the paper.

This proves that in the given position, the number of moves (more accurately, the complexity of the game tree) it would take to get from that position to the win rises exponentially with the size of the board. I have no argument whatsoever with this proof - it looks entirely correct to me.

However, their proof assumes that there is no other way to prove the win other than to play out all the possible ways the game could go.

It is utterly trivial to show that this is wrong. Take another look at this position:

[d]8/8/8/8/3k4/8/8/4KR2 w - - 0 1

This position is won for white, with 29 moves to mate (see my previous post about this position for the EGTB link). I am going to prove it's won another way, without reference to the EGTB, as follows:

IT'S CONSPICUOUSLY OBVIOUS THAT WHITE IS WON IN THIS POSITION

What I mean by that is:

1. The position has a pattern which is known to be won

2. All chess players who are not beginners know this pattern

Now imagine a similar position on a 100x100 chess board. The kind of proof discussed in that paper would now be intractably large (as would a game tree of all possible games from that position - assuming that the 50-move rule becomes the "5000 move rule"). Using the mechanism described in the paper, you could reasonably say that it couldn't be proven to be a win in a reasonable amount of time on a cheap computer.

However, using my proof above ("it's obvious"), you can say it's won. It will take hundreds of moves to win rather than the 29 moves it takes on an 8x8 board, but its still a provable win.

Continuing the theme of "obvious statements", there are going to be many positions on a 100x100 board (and even on an 8x8 board) where there are not known patterns to quickly tell you whether white can win. But the point is that I have disproven the assertion that the paper proves that "This implies that there exists d > 0 and infinitely many positions p such that an algorithm for deciding whether White (Black) can win from that position requires at least c^(|p|^d) time-steps to compute...". The paper only proves that, in similar positions*, the distance to the win can rise exponentially with the board size. It has nothing whatsoever to say about patterns and heuristics.

*a simplification for clarity

Allow me to restate what I said above in a (hopefully) clear and concise way:

(1) What the paper demonstrates:

(1a) Chess can be transformed into a game described at length in the paper

(1b) This game can be shown to have polynomiality (their choice of word) with regard to the size of the board

(1c) My conclusion (not stated in the paper, but it seems to follow): the size of the chess game tree will therefore increase with polynomiality with the size of the board

(2) From the above, people are concluding that generalised solutions to chess are intractable with increasing board size

(3) It's very easy to show that point (2) is mistaken

(3a) I offered a simple position in which white is obviously won

(3b) I showed that for a similar position on a 100x100 board (and assuming the 50 move rule gets expanded), it would not be possible to show that white was won using exhaustive tree search on a cheap computer in a reasonable timescale

(3c) However, using patterns and heuristics ("It's obvious!"), it's clear that white is won

(4) Providing a counter-example demonstrates that point (2) can be wrong

The key point is that the paper demonstrates that the size of the chess game tree expands with polynomiality with board size, but it says ABSOLUTELY NOTHING WHATSOEVER about patterns and heuristics.