Re: Chess solved?
Posted: Sun Sep 06, 2020 1:24 am
Are you planning to respond to Chris's Linear evaluations with tic-tac-toe, thread?duncan wrote: ↑Fri Sep 04, 2020 1:44 pmThanks for your explanation.towforce wrote: ↑Thu Sep 03, 2020 1:55 pm
I cannot give you a straight answer, so I'll answer in parts and try to keep those parts understandable:
* some chess positions (and in particular, my intuition tells me, relationships between pieces) and their evaluations will be mapped into multidimensional space
* I will use an algorithm I am building to fit a polynomial that is good in the machine learning sense (accuracy de-emphasised (hence ranges for evaluation scores rather than exact numbers), simplicity emphasised - lowest degree and smallest number of terms possible)
* hopefully, some of the positions will then be able to be discarded without lowering the standard of the resulting EF
* hopefully, the resulting EF will evaluate some positions well
* where it evaluates a position badly, new position/evaluation data will be added to strengthen it there
* repeat
IMO, there are two reasons to be hopeful:
1. my intuition tells me that the size of the polynomial will grow less quickly than the number of data rows (if the polynomial grows exponentially with extra data rows, that will be very disappointing)
2. my experience with CBR tells me that the number of data rows needed is likely to be lower than most people are expecting. In CBR, the number of cases needed to make a good system is almost always a lot lower than people expect, and my intuition tells me that there are similarities with what I am doing here
The ultimate achievement would be, to put it simply, to look at the polynomial, spot where it is converging to, and hence write an EF that evaluates all chess positions correctly. A way to go to get to that point!
Are you planning to respond to Chris's Linear evaluations with tic-tac-toe, thread?
What part of the paper are you basing this on?towforce wrote: ↑Thu Sep 03, 2020 10:54 am What the paper ACTUALLY proves is that, in worst case scenarios, the shortest path (minimum number of moves) from the current position to the end of the game, given an opponent who is trying their hardest to stop you, can grow exponentially in n on an n*n chessboard (I am not convinced that their case is watertight, but given that disproving it would take a lot of time, I'll grant that assertion as "maybe correct" for the purpose of this discussion).
One of towforce's problems with understanding the proof is that he obviously has no idea what a reduction is. Hence, he keeps repeating questions that make zero sense like where in the paper it shows there are no quick chess rules, etc.syzygy wrote: ↑Sun Sep 06, 2020 1:07 am What the paper proves is that any algorithm that solves NxN chess requires a number of computational steps that is asymptotically exponential in N. The paper proves this by showing that another game that is known to be EXPTIME-complete can be reduced to NxN chess. This means that NxN chess is EXPTIME-complete as well. A problem is EXPTIME-complete if any problem solvable in exponential time (or less) can be reduced to it with at most polynomial overhead.
towforce wrote: ↑Sun Sep 06, 2020 10:51 am The proof in the original paper is that chess has key mathematical transformations to boolean game G3, and that boolean game G3 has already been proven to be exponentially more difficult to resolve as its size increases. The original paper says nothing whatsoever about proving that G3 is EXPTIME complete, so actually the paper we need to be looking at is the one that claims to prove that G3 is EXPTIME complete. That would be this paper - link.
I will look at that paper and then come back with comments (I'm not promising how long I will take to respond).
I don't know why you would call them "key" (perhaps it sounds more interesting), and the transformation is from the boolean game G3 to Q = NxN chess, not the other way around. (From the fact that Q is in EXPTIME and G3 is EXPTIME-complete, it follows that a polynomial transformation from Q to G3 also exists, but the paper does not and need not describe one.)
Only if you have no trust whatsoever in long-standing results in theoretical computer science.The original paper says nothing whatsoever about proving that G3 is EXPTIME complete, so actually the paper we need to be looking at is the one that claims to prove that G3 is EXPTIME complete.
So you have no clue what this all is about. What a surprise!towforce wrote: ↑Sun Sep 06, 2020 1:23 pm [Page 2: it is clearly stated that the purpose of the report is to show that the games discussed are complete in exponential time with respect to EFFICIENT REDUCIBILTY. Using roughly the method the paper uses, off the top of my head, I would guess that Fermat's Last Theorem (FLT) has complexity of at least O(y * z^2) to prove to power integer y for by testing pairs of integers to z, and therefore cannot be solved to infinity. However, FLT HAS been proved - just not by reduction.
There are lots of mate-in-1 positions that even I can solve quickly.We know that many 8*8 chess positions can be resolved by heuristics: a strong player can often look at a board and quickly declare, correctly, that one side will win.
syzygy wrote: ↑Sun Sep 06, 2020 2:58 pmSo you have no clue what this all is about. What a surprise!towforce wrote: ↑Sun Sep 06, 2020 1:23 pm [Page 2: it is clearly stated that the purpose of the report is to show that the games discussed are complete in exponential time with respect to EFFICIENT REDUCIBILTY. Using roughly the method the paper uses, off the top of my head, I would guess that Fermat's Last Theorem (FLT) has complexity of at least O(y * z^2) to prove to power integer y for by testing pairs of integers to z, and therefore cannot be solved to infinity. However, FLT HAS been proved - just not by reduction.
Algorithmically, FLT is a single statement in an appropriately chosen axiomatic system. Proving that statement, if a proof exists (which we know to be the case), can obviously be done in constant time, since it is just a single instance.
But I see that you are now bowing out of your original position and are retreating to "it's enough for me that engines play really strong chess".