Author: Don Dailey
Date: 15:17:29 01/18/99
Go up one level in this thread
On January 18, 1999 at 17:18:12, Pauli Misikangas wrote: >Hi all! > >I'm trying to optimize the size of the alpha-beta window for my shogi program. I >understand that if I use a small window, the search terminates faster but >re-searches (with full window) are needed more often. On the other hand, >re-search is not so bad because I should get some useful values from the >transposition table, right? So, what would be a good hit/re-search balance? > >Do you use always the same window size or change it during the game? I've been >thinking that when nothing crucial is happening in the game (maybe during the >opening and early middlegame) one might get some advantage by using a very >narrow window. When the fight really begins, one could then start using a wider >window. Do you think that this might be worth of trying? Is anybody using >techniques like this? Is there some cases when it is better not to use >AB-window? > >All the best, > >Pauli Misikangas > >Pauli.Misikangas@cs.helsinki.fi >http://www.cs.helsinki.fi/~pmturune/index_e.html ----------------------------------------------------------- First of all, I would like to dedicate this post to Enrique Irazoqui who really enjoys these discussion of Alpha beta pruning. This one is for you buddy! ----------------------------------------------------------- Hi Pauli, You might consider just using PVS search. The basic idea is that you search the very first move with the current alpha beta margin (which is infinite of course at the root.) Then ALL the sibling moves are searched with a zero width window, really to test the premise that you chose the best move first. Of course this is a recursive excercise, you would do this at every node unless of course the window was already zero width which it will be in many cases. When (if) the zero width search fails, you simply research with the new score returned as alpha and whatever beta would have been (or you could make the same assumption and go zero width on the remaining siblings) experimentation will tell you what works best. Some programmers combine this pure PVS thing with an additional window wrapped around the whole search! This is probably a slight improvement but then you are starting to look more and more like mtd which most people have a manifest hatred for! mtd is just aspiration search taken ALL THE WAY and my program Cilkchess uses it. There are a lot of issues concerning lazy evaluation and hash tables and selectivity that make a lot of this stuff kind of weird and fuzzy if you are not very careful. If you do lazy evaluation, and I think most programs do, your re-searches in PVS may exhibit flaky behavior. Some programmers do not use very strict re-search windows because of this. They may for instance simply do the re-search after a fail hi using (alpha, beta) to be safe, instead of the squeaky clean and technically correct (score_returned_from_fail_hi, beta). - Don
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.