Author: Dann Corbit
Date: 14:17:04 12/12/02
Go up one level in this thread
On December 12, 2002 at 14:37:01, Uri Blass wrote: >On December 12, 2002 at 14:08:22, Dann Corbit wrote: > >>On December 12, 2002 at 12:47:20, J. Wesley Cleveland wrote: >>[snip] >>>You are the one that said you could prove that chess was not currently solvable, >>>which means others can speculate and you have to prove them wrong. >> >>I was wrong. See some other message I wrote elsewhere in this thread in answer >>to Heiner. >>[snip] >>>The proof takes only a few steps. Define king confined in a rectangle n,m as >>>queen on square n+1,m+1, king in the rectangle not adjacent to the queen, and >>>opposing king outside the rectangle n+1,m+1. Prove if the king is confined in a >>>rectangle of 3,1 or 3,2, it is checkmate. Prove if the king is confined in a >>>rectangle of n,1, you can force it to be confined in a rectangle of n-1,1. Prove >>>if the king is confined in a rectangle of n,m, you can force it to be confined >>>in a rectangle of n-1,m or n,m-1. Prove that you can confine the king in a >>>rectangle. QED. >> >>This proof will take exactly the same number of steps to complete as the tree >>search. Hence it is an implicit tree. >> >>I could just post a ten line minimax algorithm and say: >>"Chess is solved." >> >>We can easily show that the algorithm terminates. > >I can give you a simple example when it is possible to prove things without a >tree. > >[D]k7/P2ppp2/K7/8/8/8/7P/8 w - - 0 1 > >I can see mate in 5 without calculating all the tree > >1.h4,2.h5 3.h6,4.h7,5.h8R# > >a stupid computer program(and I believe that all of the available programs are) >need to calculate a lot of lines(1.h4 f5,1.h4 f6,....) You have to calculate the square root of the nodes of the tree. Not the full tree. >Humans do not need to calculate them because they can see that the white pawn >promotes before the black pawns and they can see that the place of the black >pawns is not relevant when they cannot promote. > >It is simple to prove it by a tree of classes of positions and not a tree of >positions. > >Another simple example >[D]7k/8/1p1p1p1p/pPpPpPpP/P1P1P1P1/8/8/6KR w - - 0 1 > >It is simple to prove that it is a draw without tree or tablebases. This is a terminal game condition. It could be added via a recognizer. We could say at this point that the game is concluded, but it might be necessary via the rules to either repeat 3-fold or 50 move rule. We could include a "wall + insufficient material to break the wall" recognizer. I suspect that it will slow down the search, rather than speed it up. It is (of course) possible that the real tree is small (as discussed in other messages) and that a solution is nearby. I have retracted the "solution is technically infeasible" claim. I change it to "incredibly unlikely".
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.