IN YOUR FACE AI!
Don't you be insulting me on my planet!
Fruit fly races on steroids?
Moderators: hgm, Rebel, chrisw

 Posts: 11678
 Joined: Thu Mar 09, 2006 12:57 am
 Location: Birmingham UK
Re: Fruit fly races on steroids?
The simple reveals itself after the complex has been exhausted.

 Posts: 27879
 Joined: Fri Mar 10, 2006 10:06 am
 Location: Amsterdam
 Full name: H G Muller
Re: Fruit fly races on steroids?
Yeah, but you cheat, as the Bat cannot fly to n9 with a noncapture. 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.

 Posts: 11678
 Joined: Thu Mar 09, 2006 12:57 am
 Location: Birmingham UK
Re: Fruit fly races on steroids?
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.
The simple reveals itself after the complex has been exhausted.

 Posts: 3320
 Joined: Wed Mar 08, 2006 8:15 pm
Re: Fruit fly races on steroids?
Hmm. This paper has been removed from SSRN at the request of the author, SSRN, or the rights holder.
Jouni

 Posts: 11678
 Joined: Thu Mar 09, 2006 12:57 am
 Location: Birmingham UK
Re: Fruit fly races on steroids?
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
The simple reveals itself after the complex has been exhausted.

 Posts: 697
 Joined: Mon Apr 19, 2010 7:07 pm
 Location: Sweden
 Full name: Peter Osterlund
Re: Fruit fly races on steroids?
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 EXPTIMEcomplete and therefore there cannot exist "simple" patterns that can decide the gametheoretic value of all positions in generalized chess.towforce wrote: ↑Tue Apr 16, 2024 5:07 pm 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.

 Posts: 11678
 Joined: Thu Mar 09, 2006 12:57 am
 Location: Birmingham UK
Re: Fruit fly races on steroids?
petero2 wrote: ↑Tue Apr 16, 2024 10:35 pmDoes 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 EXPTIMEcomplete and therefore there cannot exist "simple" patterns that can decide the gametheoretic value of all positions in generalized chess.
Asked and answered (link).
The simple reveals itself after the complex has been exhausted.

 Posts: 697
 Joined: Mon Apr 19, 2010 7:07 pm
 Location: Sweden
 Full name: Peter Osterlund
Re: Fruit fly races on steroids?
Yes, but you later admitted that your answer was wrong.towforce wrote: ↑Tue Apr 16, 2024 11:46 pmAsked and answered (link).petero2 wrote: ↑Tue Apr 16, 2024 10:35 pmDoes 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 EXPTIMEcomplete and therefore there cannot exist "simple" patterns that can decide the gametheoretic value of all positions in generalized chess.
So the main problem is still the following:towforce wrote: ↑Mon Apr 08, 2024 3:21 pmAgreed.chesskobra wrote: ↑Mon Apr 08, 2024 11:15 amI 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.
petero2 wrote: ↑Sun Apr 07, 2024 10:32 pm 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) timesteps 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 Pspacehard.

 Posts: 11678
 Joined: Thu Mar 09, 2006 12:57 am
 Location: Birmingham UK
Re: Fruit fly races on steroids?
petero2 wrote: ↑Wed Apr 17, 2024 6:45 amYes, but you later admitted that your answer was wrong.towforce wrote: ↑Tue Apr 16, 2024 11:46 pmAsked and answered (link).petero2 wrote: ↑Tue Apr 16, 2024 10:35 pmDoes 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 EXPTIMEcomplete and therefore there cannot exist "simple" patterns that can decide the gametheoretic value of all positions in generalized chess.
towforce wrote: ↑Mon Apr 08, 2024 3:21 pmAgreed.chesskobra wrote: ↑Mon Apr 08, 2024 11:15 amI 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.
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.
The simple reveals itself after the complex has been exhausted.

 Posts: 11678
 Joined: Thu Mar 09, 2006 12:57 am
 Location: Birmingham UK
Re: Fruit fly races on steroids?
towforce wrote: ↑Sun Apr 07, 2024 11:50 pmTo 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 50move 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) timesteps 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 counterexample 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.
The simple reveals itself after the complex has been exhausted.