Author: KarinsDad
Date: 12:22:59 05/15/99
Go up one level in this thread
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.). 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. 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. > >> This is the MAIN reason that >>programs without opening books are so weak. The GMs have spent years analyzing >>to some depth various openings and have found moves such as 2. c4 which are >>strong, but a program would not find these moves in any reasonable amount of >>time since it prunes via alpha beta. >> >>So, in the example of exhaustive 6 ply search, there are many lines dropped via >>alpha beta at ply 1, 2, 3, 4, and 5 so that the evaluation routine does not even >>get to compare those nodes at ply 6. If a line is dropped at ply 4, how can you >>evaluate it's grandchildren at ply 6 or ply 9 or ply 12 and find that it is in >>fact actually stronger, not weaker? >> > >In alpha-beta you search from that node down to ply 6 and then evaluate, you >don't simply evaluate at that node and drop it if its score is too low. In >fact the nodes you drop are those that are too high...so high that your >opponent will choose some other path to avoid that node and thence the disaster >that likely lies ahead. So, you may as well not even finish searching it >because you've proven your opponent won't allow you to get there. This is done >recusively throughout the tree, and in this way lots of useless work is avoided. > >-Dan. Absolutely. KarinsDad :) > >>Do you still think that I do not understand Alpha Beta? Min Max and Alpha Beta >>are the reasons that other techniques such as null move and razoring, etc. have >>been developed. If we were doing exhaustive search to ply 14 and alpha beta >>search to ply 20 after that, no human in the world could beat the program and >>these other techniques would not be needed. >> >>KarinsDad :)
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.