Author: Dann Corbit
Date: 10:11:35 05/17/01
Go up one level in this thread
On May 17, 2001 at 08:39:35, Alberto Rezza wrote: >On May 16, 2001 at 19:12:23, Dann Corbit wrote: > >>Chess is finite. TSP is finite. Matrix multiplication is finite. All >>algorithms are finite. Otherwise, they AREN'T algorithms. > >Come on, Dann. Termination of algorithms and finiteness of a game are >two totally unrelated matters. Is that so difficult to understand? I think I understand it perfectly. You have algorithms, and you can give them an instance of data. >If chess is too much, try with tic-tac-toe. A few hundred nodes, and >you cannot increase the depth anymore: all leaves are won, lost or >drawn, there is nothing left to expand. It is finite, so it is O(1) >time. And chess is the same, for the same reason. The algorithm for tic-tac-toe can be a table lookup, a brute force search, alpha-beta, etc. Since the problem is so small (there are only 9^3 states, and many of them are thrown out as illegal) the exponential nature of even brute force search is unimportant. That's because n=9, and it is not insufferable. You could easily create a table of all possible correct moves. Then tic-tac-toe game is O(1). Once again, this is an example of how to decide what is computable. Since 'noughts and crosses' has a tiny n for input, it *is* computable no matter how you do it. The ALGORITHM of how you solve tic-tac-toe can have many different kinds of behavior, depending on what algorithm you choose. I truly fear for the future of corporate computation, because nobody understands the practical importance of complexity. >With matrix multiplication, after multiplying two nxn matrixes, you >can always find two (n+1)x(n+1) matrixes to try. The algorithm WILL >terminate, but it will take longer: for any time duration T, you can >find an input large enough that it takes more than T to compute, so it >is not O(1). I have said all that I will say to you on this matter. If you wish to discuss it further, you will have to send me an email.
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.