Author: Bob Durrett
Date: 12:40:32 01/30/04
Go up one level in this thread
On January 30, 2004 at 14:28:05, Robert Hyatt wrote: >On January 30, 2004 at 13:36:57, Bob Durrett wrote: > >>On January 30, 2004 at 13:20:47, Robert Hyatt wrote: >> >>>On January 30, 2004 at 12:05:30, Bob Durrett wrote: >>> >>>> >>>>A friend is playing games against his chess-playing program on his PC and asked >>>>this question. I do not know the answer. >>>> >>>>Suppose the user sets the ply depth to 5 ply. There are several things the >>>>engine could do in that case, assuming in the middlegame. >>>> >>>>If sufficient time were available: >>>> >>>>The entire tree could be exhaustively analyzed. >>> >>>I am not sure what that means... >> >>I guess I was not too clear. Sorry about that. >> >>I envisioned "un-pruning." In the beginning the engine does not know how much >>time the user will allow. Perhaps the programmer can decide this, but surely >>the engine must consider the possibility that the user will issue a "move now" >>command. Hence, I would expect pruning so that the engine would have a move >>available almost immediately. Then, as more time were made available, the >>engine could go back and consider previously pruned portions of the tree. > >Wouldn't help. Alpha/Beta only prunes stuff that it can _prove_ is not useful >to search. IE if you went back and did a full minmax search to the same depth, >which would take _much_ longer, you would still get the same best move, best >score, and PV. That's why alpha/beta is so important... You seem to be highly impressed by that alpha/beta algorithm. [People used to worship Newton's three laws, too, until Einstein came along. Not to mention the flat Earth theory, etc.] My impression, however, is that alpha/beta is not the whole story. If it were, ANYBODY could create a chess-playing program "overnight." : ) I keep reading about other exotic ideas here at CCC. What about them? Surely alpha/beta is not the whole story! One example: When an engine is in a position, a decision must be made [by the engine] as to whether to stop looking deeper into that line or just treating the position as a leaf node. If it decides to stop looking deeper into the line, then the position evaluation used would [presumably] be the "leaf node evaluation" code [as opposed to "internal node" evaluation code]. The messy part, it seems to me, is in the deciding whether or not to stop in that line. Based on what I've read here at CCC, the criteria used for that decision depends heavily on the individual programmer. If the engine were limited to a maximum depth of n half-moves, and if n were small, like ten or fewer, then it would likely happen that many leaf nodes were not of the desired type. In other words, they may be in the middle of a tactical combination or the positions may atleast not be "quiet." This suggests, at the very least, that leaf node evaluation code for this application would have to be able to handle such positions. Bob D. > >> >>> >>>> >>>>The position evaluation could be done more extensively/thoroughly. >>> >>> >>>Nor that since the normal Evaluation() stuff is done at appropriate points >>>inside the tree already. There's no other places where it could be done.. >> >>Again, I did not make myself clear. Sorry again! >> >>My thought was that the programmer will give the position evaluation a limited >>amount of time to do it's work. This might be accomplished simply by making the >>position evaluation code be "fast." >> >>If more time became available, however, maybe the position evaluations could be >>revisited and a more time-consuming [hence, presumably, better] evaluation be >>done. > >I don't know of a program that has two separate evaluations, however. Some do a >"quick" eval for ordering or pruning decisions, and a complete eval as needed, >but the quick eval is only used to determine if it is worthwhile to do the full >evaluation... or if it would be a waste of time to do so. > > > >> >>> >>> >>>> >>>>Do any engines to the above? Or, do they just stop prematurely? >> >> >>>> >>>>Bob D. >>> >>> >>>If "prematurely" means "when you said to stop" then I guess the answer is they >>>stop "prematurely". If you say "5 plies" they do 5 plies and that's all... >> >> >>My choice of the word "prematurely" may have been premature. : ) >> >>The idea was that "haste makes waste" in real life as well as in software. >>Software designed to reach an answer, or result, in a very short time may be >>compromised in some way. That does not mean that the number of positions >>evaluated be reduced [although that could happen with a "move now" command] but >>rather that position evaluations would have to be done quicker than what would >>be ideal. >> >>Bob D. > >I think that all I could do would be to search another ply deeper, but then that >would violate your depth limit... Alternatively you could eliminate your depth >limit and give it a time limit instead, which lets the program decide how to use >the time.
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.