Author: Bruce Moreland
Date: 10:23:12 11/27/00
Go up one level in this thread
On November 27, 2000 at 13:01:04, Scott Gasch wrote: >Hi all, > >I have a standard AB search in my engine right now. It works fine and I am >reasonably happy with the tree sizes it is searching. > >However I am trying to convert it to a PVS -- a search with a minimal window for >all moves after the first followed, if needed, by a research with the full >alpha-beta window if this minimal window search returns a score in the original >a-b range. > >As a test I ran the original A-B search from d2d4 d7d5 e2e4 e7e5 to 8 ply and >compared the number of nodes searched to the new PVS search. I am pretty sure I >have the PVS implemented correctly and can only assume that the great difference >in tree size comes from a poor move ordering on my part: > > AB PVS >1. 45 83 I think you might have a bug, and if you dump out the first-ply tree it might be exposed. Why does PVS cause you to search twice as many nodes in a one-ply search? What you are supposed to do is search the first move with a full alpha-beta window. If the first move fails high, fine you are done. If the first move is between alpha and beta, or below alpha, you can do something with the rest of the moves. Rather than searching with a full window, search with alpha equals the score the first move returned, and beta equals that score plus one. Of course you have to negatize and reverse these, since you are passing them to search at the next ply, and everything is backwards. You are gambling that this search is going to fail low, because your move ordering is good enough that you'll search a fail-high move first if there is one. If you fail low on the first move, you *should* fail low on everything else. If your gamble fails, you open the window again and re-search the move that caused the failure. It is possible that your move ordering is bad, but you should rule out a bug first. It's easy to make a mistake. bruce >2. 525 646 >3. 3004 4975 >4. 14061 23048 >5. 43460 147922 >6. 183094 633827 >7. 486054 4727636 >8. 1129783 11029952 > >The strange thing is that I am using the same move ordering in both cases: hash >move (with PV stuffed), winning captures (MVV/LVA), losing captures (MVV, LVA), >killers (beta cutoffs at same ply), rest sorted on history heuristic (depth^2). > >I've read that some people who use a SEE put losing captures at the end of the >list. I do not want to do this for two reasons: 1. I generate all captures >before any of the moves to maybe get a cutoff with less work done and 2. Because >I do not use a SEE I am not entirely certain that a MVV/LVA capture is indeed >"losing"... the opponent's piece may be hung and no recapture occur. > >Is this move ordering scheme sane? > >Thanks, >Scott
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.