Author: Robert Hyatt
Date: 11:47:53 01/25/00
Go up one level in this thread
On January 25, 2000 at 13:44:22, Dave Gomboc wrote:
>On January 24, 2000 at 09:50:32, Shep wrote:
>
>>On January 21, 2000 at 20:41:27, Dann Corbit wrote:
>>
>>>On January 21, 2000 at 19:28:38, walter irvin wrote:
>>>
>>>>which is more important ?????? is it posible that a program written on a 286
>>>>25mhz 4mg ram could be stronger than deep blue ????? is it posible that a
>>>>program like sargon ran on a machine that produced 2,000,000,000,000,000 nps
>>>>could reach 2900 elo ?? perhaps there are great untried methods that will
>>>>produce major elo jumps ????
>>>
>>>My 286 program would look like this:
>>>
>>>#include <stdio.h>
>>>#include <stdlib.h>
>>>static char str[4096];
>>>main()
>>>{
>>> char *err;
>>>getmove:
>>> puts("Tell me, Kasparov, what move should I make?");
>>> err = fgets(str, sizeof str, stdin);
>>> if (err == 0) goto getmove;
>>> if (strcmp(str, "quit\n") == 0) exit(0);
>>> printf("I choose: %s", str);
>>> goto getmove;
>>>
>>> return 0;
>>>}
>>>
>>>But it needs a special operator to be effective (His name is in the code).
>>>
>>>Actually, you raise a good question, which is this:
>>>Is chess O(exp(n))? {where n is the depth in plies}
>>>
>>>If we could discover an algorithm linear in n [stop laughing all you chess
>>>programmers] then a 286 could pound the stuffings out of Deep Blue.
>>>
>>>Conversely, can it be proven that the search in chess cannot be made in
>>>polynomial time as a function of plies of lookahead? How about a subset search
>>>that produces "good enough" answers?
>>>
>>>In other words, a fundamentally better algorithm for searching chess positions
>>>could render all chess programs obsolete. Don't hold your breath, though. A
>>>lot of smart people have been looking and nobody has found one yet.
>>
>>Still that doesn't mean it's going to be a matter of centuries like Fermat's
>>Theorem. There are several important problems in computer science for which the
>>answer is surprisingly simple (at least in relation to the effort put into it).
>>
>>I remember the famous "LBA problem" which was unsolved for a decade or so, was
>>found by a Czech student (and independently, an American prof), and the proof is
>>about 1.5 pages in a pocket-size book; and many computer science students can
>>understand it (though they wouldn't be able to find it themselves).
>>
>>Bottom line is, there might be some rather simple "new method" that can advance
>>computer chess by 100 or 200 ELO.
>>
>>OTOH, it may just as well be a "P=NP" problem... :)
>>
>>---
>>Shep
>
>Exactly what is the "LBA" problem?
>
>Dave
LBA usually means "Linear-Bounded Automaton"... Which is one of several sub-
classes of automatons discussed in CS theory courses. There are always clever
questions that can be inductively answered as "yes" or "no" but not proven. I
assume that this is one of those. No idea which one, although it doubt it is
involved with trying to prove that P=NP or NP=NPH or some such...
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.