Fruit fly races on steroids?

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Rebel, chrisw

User avatar
towforce
Posts: 11678
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK

Re: Fruit fly races on steroids?

Post by towforce »

IN YOUR FACE AI!

Don't you be insulting me on my planet!

Image
The simple reveals itself after the complex has been exhausted.
User avatar
hgm
Posts: 27879
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Fruit fly races on steroids?

Post by 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. ;)
User avatar
towforce
Posts: 11678
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK

Re: Fruit fly races on steroids?

Post by towforce »

towforce wrote: Mon Jan 29, 2024 8:07 pmI 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! :twisted:

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.
Jouni
Posts: 3320
Joined: Wed Mar 08, 2006 8:15 pm

Re: Fruit fly races on steroids?

Post by Jouni »

Hmm. This paper has been removed from SSRN at the request of the author, SSRN, or the rights holder.
Jouni
User avatar
towforce
Posts: 11678
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK

Re: Fruit fly races on steroids?

Post by towforce »

Jouni wrote: Tue Apr 16, 2024 5:11 pm 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
The simple reveals itself after the complex has been exhausted.
petero2
Posts: 697
Joined: Mon Apr 19, 2010 7:07 pm
Location: Sweden
Full name: Peter Osterlund

Re: Fruit fly races on steroids?

Post by petero2 »

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.
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.
User avatar
towforce
Posts: 11678
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK

Re: Fruit fly races on steroids?

Post by towforce »

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 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).
The simple reveals itself after the complex has been exhausted.
petero2
Posts: 697
Joined: Mon Apr 19, 2010 7:07 pm
Location: Sweden
Full name: Peter Osterlund

Re: Fruit fly races on steroids?

Post by petero2 »

towforce wrote: Tue Apr 16, 2024 11:46 pm
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 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.
towforce wrote: Mon Apr 08, 2024 3:21 pm
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.
Agreed.
So the main problem is still the following:
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) 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.
User avatar
towforce
Posts: 11678
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK

Re: Fruit fly races on steroids?

Post by towforce »

petero2 wrote: Wed Apr 17, 2024 6:45 am
towforce wrote: Tue Apr 16, 2024 11:46 pm
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 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.
towforce wrote: Mon Apr 08, 2024 3:21 pm
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.
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.
The simple reveals itself after the complex has been exhausted.
User avatar
towforce
Posts: 11678
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK

Re: Fruit fly races on steroids?

Post by towforce »

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 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.
The simple reveals itself after the complex has been exhausted.