Author: Slater Wold
Date: 11:43:08 02/05/04
Go up one level in this thread
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?
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.