Author: Andreas Herrmann
Date: 19:52:16 06/15/04
Go up one level in this thread
On June 15, 2004 at 20:21:01, Andrew Wagner wrote: >On June 15, 2004 at 20:09:48, Dann Corbit wrote: > >>On June 15, 2004 at 19:28:36, Andrew Wagner wrote: >> >>>I've heard it said before that it's not good to compare node counts between >>>engines, and that node counts aren't a good indication of strength. So, I've >>>been staying away from that a lot. >>> >>>The other day, I was chatting with my good friend Jaime Benito de Valle Ruiz. We >>>see each other a lot on ICC and compare notes on our engines. We decided to play >>>a fixed-depth game between our engines, to test eval strength. In the process of >>>the game, he noticed that my node count was ridiculously higher than his. For >>>example, in one position, where I was getting 277k nodes, he was getting like >>>11k. Other engines varied, but no more than about 50k nodes. >>> >>>So we started doing some tests. For him, he got a huge node reduction by using >>>some sophisticated aspiration windows. So, my question is three-fold: >>> >>>1.) Do most engines get a similarly large reduction in nodes by using aspiration >>>windows? >> >>It will depend on what other things you are using to trim the tree. >> >>>2.) What other techniques reduce node counts at a fixed depth? >> >>A. Move ordering is the most important thing. So a good hash table is a must. >>B. After that, null move reduction will be a stupendous node reducer. >>C. PVS search does fewer nodes than ordinary Alpha-Beta >>D. SEE is worth a lot for reduction >>E. Razoring will reduce nodes, but you have to be careful not to shave the skin >>off with the hair >>F. IID will help, especially in deep searches >>G. Aspiration window (mentioned above) reduces nodes. >>H. Easy move cutoff >> >>Here are things that will cost you nodes, but are a good idea anyway: >>A. Check extensions >>B. Increasing quiescense depth (if you don't allow infinite quiescence) >>C. Single reply extensions >>D. Pawn race extensions >>E. Recapture extensions >> >>Also, adding king safety and pawn structure to your evaluation will slow down >>the NPS greatly, but make the program play better. >> >> >> >>>3.) To what extent are node counts reliable for determining engine strength? >> >>Not generally useful, except to compare against yourself. Goliath will be >>around one million NPS on a machine where Yace will get 300K NPS. But they are >>about the same strength. > > >I should have been clearer. I didn't mean NPS, but number of nodes searched. Dann has listed most of these technics above. Most of these technics will more or less reduce your NPS, because of additional code, but are helpful to search a smaller tree, and so less nodes: Most important to reduce nodes is the moveordering. The following technics are helpful for better moveordering: a) Iterative deepening b) HashTables - helps very much c) ordering moves by type of moves (cheching moves, winning captures, ...) d) History heuristic e) Killer heuristic f) Internal Iterative Deepening (IID) in the case where there is no best move in the hash table ... Then all kinds of forward pruning and reduction technics like: a) Nullmove b) Razozing c) Futility pruning d) SEE with according pruning e) all kinds of reductions like FHR ... Also helpful to reduce the tree, are the following: a) Using better search algorytms than normal AlphaBeta like PVS or NegaScout. This search alpgorythms are producing a bit smaller trees than normal AlphaBeta. b) Perhaps MTD(f) search produces also a smaller tree than AlphaBeta, but i don't know, because i have never tryd it. c) Aspiration window technic d) Using table bases in the endgame, but this slows down the NPS a lot e) Interior node recognition ... best wishes Andreas
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.