Author: Steven Edwards
Date: 19:15:16 03/25/04
Go up one level in this thread
On March 25, 2004 at 16:28:03, Robert Hyatt wrote: >On March 25, 2004 at 13:20:22, Duncan Roberts wrote: >>Could you commment on this project and its likelihood for success. >Yes, I did a _way_ selective chess engine in the early 70's. > >And yes, I abandoned that after chess 4.0 showed that brute-force should not be >dismissed "just because it is exponential". Prior to Chess 4.x, including Chess 3.x which I'd played on the operator's console on a CDC 6500, just about all programs were Shannon type B. They were selective in the sense that they had a significant reliance on a plausibility function that selected the moves for consideration at any node instead of a reliance on move ordering techniques that potentially allowed consideration of all the moves at a node. But some Shannon type B programs were also exponential, at least the later ones that did not have an arbitrary (and relatively low) fixed search depth. The attractiveness of Shannon type B is from two factors: potentially better results on limited hardware, and a hopeful chance of mimicking human behavior. Chess 4.x pretty much discredited the first factor, and the second one turned out to be not that much of an imitation of how humans actually performed move selection. The real challenge in designing a Shannon type B program is coming up with a fast and reliable plausibility function that, overall, can out-perform the move ordering techniques of a Shannon type A full width searcher. While it is true that a type A program may be better at spotting tactical shots, a sufficiently smart type B program could, with its greater average search depth, prevent such shots against it from appearing on the board. Symbolic is selective, but is not a Shannon tye B prgram. Instead of having a plausible *move* generator, it's designed to have a plausible *plan* generator. The main idea for avoiding the exponential demon of combinatorial explosion is to use its plans to avoid (i.e., "play around") regions of the search where further expansion is unlikely to affect the ultimate move selection given the resources available. The thought here is intended to be similar to a human player who might think "I will not consider the move M in position P because the opponent could play response R and then the successor position S is just too complicated for me to evaluate accurately". >I have no idea whether Steven's ideas will work or not. There's certainly >nothing wrong with experimenting... It is certainly possible that Symbolic might not work. If this turns out to be the case, I would suggest that perhaps another researcher with superior capabilities could try the approach and do better. Of course, if I knew for sure that it it work, then I wouldn't bother actually writing the program. Also, I've got a backup development plan that also uses Lisp and a low NPS, whole tree approach. This alternative doesn't rely much on patterns and planning, but on a market simulation (!) idea. Here, each node has an instance of an interpreter running a program in a Lisp-ish language called NodeScript and these instances compete for resource allocation (i.e., greater proportion of interpreter step cycles). All the NodeScript interpreter instances run at the same time, communicate via messaging plus blackboards, and together perform a planless search where the final move selection is reached by consensus. My NodeScript idea is certainly not like any other chess program known to me, and it's also rather unlike the reasoning process of a human player. But it does have some similarities to human group behavior, perhaps like a team of investment analysts, where economic projections and results guide resource allocation and target areas of market expansion.
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.