Author: Russell Reagan
Date: 14:01:15 01/19/05
Go up one level in this thread
On January 19, 2005 at 09:09:25, S J J wrote: > Thank you, Andy. So then the alpha-beta is used to help select >(and reduce) the nodes for a follow up seach and extension will SEE, >quiescent search, etc. being the methods used to search those nodes? There are two separate issues. 1. Horizon problems. Horizon problems exist because minimax and alpha-beta search to a given depth, and then they quit searching regardless of the sitaution on the board. An example of a horizon problem is when you search to depth 6, and the last move was white capturing a black rook. Black may be able to capture a white rook on the very next move to restore material equality, but you are only searching to depth 6, so the search will think that this particiular sequence of moves loses a rook for black. If you search to depth 7, there will be horizon problems with some other position. So you have to use some other method like quiescence search to handle horizon problems. Horizon problems will exist regardless of whether you use minimax or alpha-beta. 2. Minimax vs. alpha-beta. Minimax will visit every node in the search tree to the given depth. Alpha-beta will not. Alpha-beta will prune a large percentage of those nodes, and it is completely safe. The alpha-beta algorithm *proves* that it can skip certain nodes. Think of a real life example. You are looking for a job. You call one company, fill out an application, send them your resume, go to an interview, and they offer you $50,000 per year. You call another company and they tell you on the phone that they can only pay you $30,000 per year to do a similar job. Now you can safely skip doing the extra work of filling out an application, submitting your resume, and going to an interview with the second company. They can't come close to paying you what the first company can pay you. In other words, you *proved* that you could skip that extra work. Alpha-beta does the same thing. It keeps track of the "worst case" for both sides. If something is worse than the worst case, then you can safely ignore that node and its entire subtree, and you will get the EXACT SAME SCORE that minimax would have produced, but in much less time.
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.