Author: Bob Durrett
Date: 11:47:06 02/05/04
Go up one level in this thread
On February 05, 2004 at 14:41:16, Uri Blass 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 is simply wrong impression. > >It is clear that evaluation influence the tree that the program searches. > >if I evaluate only material and search the opening position to depth 2 >I may get a line like 1.a4 a5 in the tree when I may never search that line if I >use a better evaluation(even only piece square table) because 1.e4 may be the >best move at ply 1 and 1.a4 may be refuted by 1...e5 when 1...e5 may be >searched first based on killer moves. > >evaluation can also influence pruning because of different threats and different >moves that you prune by null move pruning. > >Uri Thanks, Uri. Maybe I was not so far off after all. Now, what remains is to quantify the impacts of evaluation types on the tree/pruning. My main interest is in determining how much difference positional evaluation would make over just tactical. Bob D.
This page took 0.01 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.