Author: Bob Durrett
Date: 12:01:13 02/05/04
Go up one level in this thread
On February 05, 2004 at 14:53:56, Robert Hyatt wrote: >On February 05, 2004 at 14:43:08, Slater Wold wrote: > >>On February 05, 2004 at 14:30:52, Robert Hyatt wrote: >> >>>On February 05, 2004 at 13:43:26, Bob Durrett wrote: >>> >>>>On February 05, 2004 at 12:41:02, Robert Hyatt wrote: >>>> >>>>>On February 05, 2004 at 12:22:44, Bob Durrett wrote: >>>>> >>>>>> >>>>>>Bob Hyatt: >>>>>> >>>>>>I was going through the older CCC bulletins to make sure I didn't miss anything >>>>>>important and noticed the thread begun by Russell, >>>>>>http://www.talkchess.com/forums/1/message.html?345569. After checking Russell's >>>>>>reference, I saw something you wrote cited below. This made me really curious >>>>>>about how the alpha/beta algorithm might be impacted by improvements in the >>>>>>position evaluation code. It seems to me, intuitively, that accurate assessment >>>>>>of positional [and other non-material] factors in a position, along with the >>>>>>correct assessment of material factors, would give >>>>>>values which would change the interpretations of failing alpha or beta tests. >>>>>>It seems that this would significantly alter the way searching would proceed. >>>>>> >>>>>>If this is unclear, I can try to be more detailed if you wish. [I never claimed >>>>>>to be a Pulitzer Prize winning author.] >>>>>> >>>>>>Bob D. >>>>> >>>>>The point is this: First we start with a pure minimax framework. And that >>>>>search is going to search a tree of a given size, when given a specific depth >>>>>limit. It is going to find the path to the "optimal" endpoint as defined by the >>>>>min/max strategies, using the evaluation function you write. It doesn't matter >>>>>how good or bad the evaluation function is, either, because pure minimax simply >>>>>finds the path to the optimal position as defined by the eval. If you use >>>>>material only, or the most sophisticated positional evaluator in the world, you >>>>>search the same number of nodes and find the optimal path. >>>>> >>>>>Alpha/beta does the _same_ thing, but by ordering things carefully, and proving >>>>>that some branches are irrelevant by the alpha/beta test, we reach the _same_ >>>>>optimal position, but after searching far fewer nodes. But the "same" score is >>>>>a critical point. >>>>> >>>>>All this means is that your eval can be as gross as you want, but it should not >>>>>affect the size of the tree, so long as your move ordering fits your evaluation >>>>>function. IE if your eval maximizes material, but your move ordering is >>>>>ordering for give-away chess, then it isn't going to work well because you won't >>>>>be searching the minimal alpha/beta tree with that backward ordering. >>>>> >>>>>But if you do them right, the evaluation won't change the size of the tree in >>>>>general, although obviously any scoring change can change the size of the tree >>>>>if the move ordering code doesn't factor that in at all. Chess is dominated by >>>>>material, and our move ordering takes this into consideration when ordering >>>>>moves. If your eval produces huge positional scores that frequently add up to >>>>>way more than a pawn's value, then the move ordering is not working with the >>>>>evaluation very well, and the resulting tree will not be optimally sized. >>>>> >>>>>In the below excerpt, hopefully now you see what it means. >>>>> >>>>>Think about a different example: >>>>> >>>>>There are three holes in a wall. I give you the following assignment: >>>>> >>>>> "go to each hole, stick your hand in for one minute, and then when >>>>> you have finished, report back and tell me which hole was the least >>>>> unpleasant experience." >>>>> >>>>>You stick your hand in the first hole, and for 60 seconds all you get is a >>>>>stream of warm water running over your hand. You stick your hand in the second >>>>>hole, and are met with almost frozen saltwater at around zero degrees Celsius. >>>>>Do you stick around in that hole to see if something even worse happens, or is >>>>>the freezing water enough to convince you that is is _already_ worse than the >>>>>first hole (warm water) you tried? And, of course, if you wait around any >>>>>longer, something even _worse_ might happen. >>>>> >>>>>That is the alpha/beta algorithm. I only prove that B is worse than A. I don't >>>>>need to know exactly how much worse, that is irrelevant to the task of simply >>>>>choosing the best move, overall. >>>> >>>>I see you are trying to simplify the alpha/beta algorithm for my sake and I >>>>truly appreciate that. However, in spite of that effort, you are still a mile >>>>over my head. Anyway, I would never have been dumb enough to stick my hand in >>>>the first hole! : ) >>>> >>>>What I'm getting from all this is that you seem to be saying that the quality >>>>and nature of the position evaluation simply are irrelevant when it comes to >>>>shaping the tree [by pruning, etc.]. It sounds like the same branches will be >>>>evaluated NO MATTER WHAT happens in the position evaluation. That's what I'm >>>>reading, anyway. It also sounds like the main objective is to minimize the >>>>amount of computer time consumed by the position evaluation code. Why have any >>>>at all? >>>> >>>>What am I missing? >>> >>>Two different topics. To find the best "chess" position, requires specific >>>chess knowledge. IE positional stuff. To find the best "tactical" position in >>>the tree only requires piece values that are correct. >>> >>>In computer chess, sometimes material is enough to show you the right move, but >>>in other positions there is nothing you can win (material-wise) but you still >>>have to play a move, and it needs to be a good one. >>> >>>My point was that the search is going to have to search to find the best move, >>>based on some criterion. Whether that be pure material, complex positional >>>analysis, or something else really doesn't make any difference. Alpha/beta will >>>reduce the size of the minimax tree by the same amount no matter which >>>evaluation type you use, so long as your move ordering capability is up to the >>>task. >> >>Obviously with bad move ordering, Alpha/Beta resorts back to M-M, which is >>exactly what A/B is trying to avoid. >> >>But what I think Bob D. is wondering, is that Alpha/Beta seems to be tailored >>simple material returns. I think he is worried that a huge positional eval >>would be hindered by bad returns from A/B. >> >>A/B works from your search, not your eval. >> >>I think his questions is, can they get in the way of each other? > > >as I mentioned, alpha/beta is order dependent. Get the order wrong and the tree >size blows up. So the correct question to ask is "can your move order code >accurately predict moves that lead to the best evaluation score?" For example, >in a material-only search, looking at winning (SEE) captures first tends to do >exactly what you want... So, in modern engines, what are the determining factors which set the move ordering? What does choice of move ordering depend on and what does it not depend on? Bob D.
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.