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.01 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.