Author: Dave Gomboc
Date: 10:44:22 01/25/00
Go up one level in this thread
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
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.