Author: J. Wesley Cleveland
Date: 15:10:23 12/12/02
Go up one level in this thread
On December 12, 2002 at 17:24:11, Dann Corbit wrote: >On December 12, 2002 at 17:12:34, J. Wesley Cleveland wrote: > >>On December 12, 2002 at 15:51:48, Dann Corbit wrote: >> >>>On December 12, 2002 at 14:55:59, J. Wesley Cleveland 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. >>>> >>>>Do you not understand (or remember (or accept ;)) the concept of "proof by >>>>induction" ? My algorithm can find a move that will lead to mate from any >>>>starting position (with the side with the queen to move) with at most a 5 ply >>>>search (I am pretty sure that it could be done with no search, but hesitate to >>>>say I can prove it). I do not know of any such algorithm for chess ;), but >>>>cannot prove it does not exist. >>> >>>I understand proof by induction. Do you understand that when the induction >>>algorithm runs to termination >> ^^^^ ^^ ^^^^^^^^^^^ >> >>The induction algorithm does not "run to termination". You prove it is true for >>the starting condition. Then you prove that if is true for n, where n>= the >>starting condition, it is true for n+1. *Now* you are *done* QED, no "running to >>termination". >> >>it will implicitly construct the exact same tree >>>tree? >> >>Perhaps in the same sense that the proof by induction that there is no largest >>integer involves adding 1 to every integer and never terminates. >> >>> >>>Here is proof that chess is solved [in a mathematical sense]: >>>http://www.talkchess.com/forums/1/message.html?270359 >>> >>>Does not change anything else that I have said, of course. >> >>The difference is that your method can prove that chess is won for white (or >>drawn or lost) sometime after the stars have grown cold, while my method *does* >>prove that KQ v K is won for white on an arbitrarily large board. > >So would minimax. In fact, minimax is known to solve chess for any board that >is not infinite. There is no difference between your induction proof and my >minimax proof, as far as feasibility. Both form a certain solution. There is one difference. To write a full, formal proof by induction might take me a couple days, at which point you have a proof it is won. Your minimax algorithm would still be running when the universe ended and you would not know whether or not it is won until it finished.
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.