Author: Dave Gomboc
Date: 12:38:18 05/15/99
Go up one level in this thread
On May 15, 1999 at 15:22:59, KarinsDad wrote: >On May 14, 1999 at 17:35:00, Dan Newman wrote: > >>On May 14, 1999 at 15:09:35, KarinsDad wrote: >> >>>On May 14, 1999 at 14:25:05, J. Wesley Cleveland wrote: >>> >>>>On May 14, 1999 at 13:14:36, KarinsDad wrote: >>>> >>>>> >>>> >>>>You seem to misunderstand alpha-beta. Alpha-beta *always* finds the same "best" >>>>move as exhaustive search does at any depth. What it does not tell you is how >>>>much better the "best" move is. >>> >>>Alpha Beta finds the best move "under the same depth and constraints", but does >>>not find the best move. That is why chess programs are not perfect at this point >>>in development (since they are restricted from performing exhaustive searches). >>> >> >>Well, yes, chess programs aren't perfect because they can't perform exhaustive >>searches depthwise. But I think there must be a misunderstanding of some sort, >>perhaps in terminology? The alpha-beta algorithm effectively does the same >>search that pure minimax does. Pure minimax is exhausive (widthwise): every >>node above a certain depth is examined. Alpha-beta gets the same result but >>only examines approximately the square root of the number of nodes in the >>tree that's searched. This is an enormous win when the depths are large. In >>chess it reduces the branching factor from approx 36 to approx 5 or 6. When >>people speak of "full-width, exhustive, brute-force" search it's alpha-beta >>that they are generally speaking of since the result is (more or less) identical >>to that achieved by pure minimax. The pruning done by alpha-beta is of an >>entirely different nature than the lossy pruning done in the quiescence search >>or by the null move heuristic. > >Agreed. I totally understand what you are saying and you are correct, based on >the limitations that you stated (i.e. using Alpha Beta to a given depth). > >I think that I will have a very difficult time explaining my point of view here >(you touched on it when you agreed that programs cannot search exhaustively >depthwise). > >Lets say that you have a position that you are searching. At each ply below the >position, you will decrease the number of searched nodes by about a factor of 5 >(in a normal position) using Alpha Beta. So, if you search down 10 ply, you will >find about 10 million nodes. At 250k nps, this comes out to be about 40 seconds. >Very doable with today's hardware and software. And, of course, chess programs >use other techniques in order to search any PV further and some of the other >less desirable positions even less. > >However, you used iterative deepening to get to that 10 ply and you pruned out >the tree at each level due to alpha beta cutoffs found while searching at lower >ply. So, you have a "perfect" score on your PV and a range of scores everywhere >else. This range of scores were calculated using very limited data. Originally, >they are calculated using the evaluation routine at the leaf node of the depth >below the one being searched, but eventually, those ranges start to improve as >the depth increases. Fair enough. > >However, since MinMax is a widthwise search (as is Alpha Beta), it drops >depthwise nodes on the floor as well. And these nodes will very rarely be >re-searched unless they move over to (or towards) the PV. > >So, effectively, what MinMax and Alpha Beta both do is a kind of controlled >shotgun effect where you are aiming in the general area of your target and you >will probably partially hit it, but there are no guarantees. > >Say, for example, that you had a program with "nearly perfect" move ordering. >Then, Alpha Beta would work wonderfully. It would quickly dispatch lesser moves >and you would in the majority of cases, find either the best move in a position >or the second best move in a position (I'm using these terms loosely here). > >But, how do you acquire a nearly perfect move ordering. It's tough since it is >based on the position (yes, a lot of programs use various techniques based on >similar positions and positions at a similar depth, etc.). It isn't actually that tough. The way to acquire nearly perfect move ordering is to use iterative deepening. This is an extremely important technique, and its power should not be underestimated. >So, you are either stuck with trying to come up with a nearly perfect move >ordering algorithm, improving your search techniques, and improving your >evaluation routine. Simple Alpha Beta no longer cuts it alone (you will be >killed by every other program out there). > >Most programs rely on pruning the tree even further with null move, razoring, or >other techniques. The theory is that if you can search deeper, you will search >better. In some positions (leading to mate or whatever), this may be true. But >for a majority of positions, I believe this postulate seems to hold BECAUSE >people are strickly following Alpha Beta (or some Alpha Beta derivative). > >My program is relying on some of these techniques as well (including a modified >version of Alpha Beta). However, my program also is attempting to pick up some >of the more interesting depth nodes dropped on the floor due to Alpha Beta. The >idea is to not miss some of those hidden resources that normally get pruned (and >to only find them if positions start heading towards PV). That's all. Pruning and extending are all about focusing on the "important" parts of the tree. This is a totally legitimate endeavor. It is not at all incompatible with iterative deepening. >Without going into detail on how I am doing this, I hope this made some sense. > >> >>>If after a quiescence alpha beta search, you determine that you have lost a >>>knight for a pawn, most programs do not search much beyond that to find the >>>forced checkmate 4 moves later and hence do not find the sacrifice. The GM, on >>>the other hand, may find this. >>> >>>What this effectively means is that the alpha beta routines "prune" out lines >>>which do not look promising, but in actuality are very promising. >>> >> >>That's true, but pure minimax won't see that these lines are promising either. >>And it won't see as deeply (in the same period of time) because it's uselessly >>examining huge numbers of nodes that can't affect the result. > >Correct. I am not disputing that Alpha Beta is superior to Min Max. It obviously >is. > >> >>>For example, let's take the opening. 1. d4 d5 2. c4 c6 3. Nc3 >>> >>>Most alpha beta programs would prune out the move c4 at ply 3 since there >>>appears (via the evaluation routine) for there to be a lot of other moves at >>>that point which develop pieces and are stronger. This does not mean that a >>>program may not find this on a re-search or something, however, you have to get >>>to ply 11 or so to start to appreciate the advantages of c4 and you will never >>>get there with a standard alpha beta search. >> >>You'll never get there with simple minimax, but you will get there with alpha- >>beta at 120 Mnps in 8 seconds or so. > >Yes, I was refering to today's max speeds of 500k nps (single processor) where >it would take somewhere around 30 minutes. Fine for analysis, but lousy for a >game. I have heard someone describe a program on here that finds c4 just about immediately. (They were testing it, as I recall.) In any case, all it really depends upon is how you are assessing positions. If the program likes QGA and QGD positions for White more than the London System stuff, it may well pick 2. c4. [snip] >KarinsDad :) 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.