Author: Bruce Moreland
Date: 09:01:17 10/11/05
Go up one level in this thread
On October 11, 2005 at 05:35:57, chandler yergin wrote: >On October 11, 2005 at 05:11:57, Uri Blass wrote: > >>On October 11, 2005 at 04:39:01, chandler yergin wrote: >> >>>On October 11, 2005 at 04:08:58, Bruce Moreland wrote: >>> >>>>On October 10, 2005 at 23:37:41, chandler yergin wrote: >>>> >>>>>http://chess.verhelst.org/1997/03/10/search/ >>>>> >>>>>"Tree search is one of the central algorithms of any game playing program. The >>>>>term is based on looking at all possible game positions as a tree, with the >>>>>legal game moves forming the branches of this tree. The leaves of the tree are >>>>>all final positions, where the outcome of the game is known. The problem for >>>>>most interesting games is that the size of this tree is tremendously huge, >>>>>something like W^D, where W is the average number of moves per position and D is >>>>>the depth of the tree, Searching the whole tree is impossible, mainly due to >>>>>lack of time, even on the fastest computers. All practical search algorithms are >>>>>approximations of doing such a full tree search." >>>> >>>>It's true for chess. Some aspects are not true for tic-tac-toe, and some others >>>>are not true for other games that aren't like chess. >>>> >>>>I don't know where you are going with this. It's possible to make a lot of >>>>assertions about chess programs that people will agree with unless they don't >>>>understand the assertion. That the chess tree is too big to search to its >>>>limits with any sane hardware is obvious. Someone might mention quantum >>>>computers here, but that doesn't fall into the category of sane. >>>> >>>>bruce >>> >>> Thanks Bruce for your response... >>>Where am I going? I'm trying to get a consensus of opinion before I embarrass >>>myself.. But on the other hand I'm used to that. >>>No, this is strictly about chess.. not Tic tac toe or other games. >>>I expected a negative response from Uri, and he has Posted that Programs do not >>>evaluate every move in a position. >> >>programs do not evaluate every move in a position that they search >>and it does not contradict your post. >> >>programs have pruning rules. >>It is written also in your post that >>"Searching the whole tree is impossible, mainly due to >>lack of time, even on the fastest computers." >> >>>Well, you know that is not true. >>>Rather than have a long thread and dialog with him, I was hoping that other >>>Programmers would agree about the Tree ..search function analysis mode etc. >>>I think that is a given, so we'll start from here. >>>It should be obvious that he who runs the fastest wins the race. >>>The Program/Engine that searches the deepest & faster in the alloted time, >>>finds the 'best' moves. >>>Would you agree? >> >>No >> >>A program may search deeper but still lose because of inferior evaluation. > >No, We disagree 100% The Program truly does evaluate 'every' possible move in >any position! It ranks them in order of the highest return from the Alpha Beta >& Mini/Max algorithim. The centipawn eval is based only on the static positional >factors programmed in. The program that searches the deepest in the >alloted time will find the better moves. >I don't understand why you don't understand this! They use forward pruning. What forward pruning means is that they are *not* guaranteed to find everything in an N-ply search that an N-ply min-max search will find. bruce
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.