Author: Gerd Isenberg
Date: 12:44:42 10/27/05
Go up one level in this thread
On October 27, 2005 at 07:38:05, Rick Hagen wrote: >On October 26, 2005 at 16:13:00, Gerd Isenberg wrote: > >>On October 26, 2005 at 07:01:10, Rick Hagen wrote: > >[...] > >>>First number is from the starting postition, second from 8-pawn position: >>> >>> KN/s >>>Junior 9 1460 1415 >>>Hiarcs 9 218 430 >>>Shredder 9 365 620 >>>CT 15 435 580 >>>Toga II 1.0 760 1355 >>>Fritz 7 1000 645 >>>Fritz 9 930 540 >>>Crafty 19.15 865 855 >>>Pro Deo 1.1 735 1100 >>> >>>P4(.) 3Ghz >>>HT 128 MB >>>TBs off (Not installed atm...) >>> >>>So, my question: who are the "odd" ones out, and why? >>> > >> >>A few aspects on your interesting nps-compare: > >Hi Gerd, Thanks for calling it intersting; remember I'm not a chess-programmer >so have patience with me, I might loose track somewhere.. > > >> >>The ratio of the number of expensive nodes versus cheap nodes during a search >>and the (average) ratio of the implementation depending duration of expensive >>nodes (full eval, all-nodes) versus cheap nodes (repetition detection, lazy eval >>cuts at leaves, etc.) might be the main factor to explain the nps behaviour. > >Okay, so far so good (only minor headache now..) > > >> >>The ratio of expensive nodes versus cheap nodes is depending on the position and >>of course on the implementation of the engine. If we use forward pruning to cut >>futile subtrees, we have relative more expensive nodes. If we, probably >>depending on the state of the game, don't use futility pruning (but probably >>lazy eval), we will have relative more cheap nodes. >> >>More hashhits, better move-ordering favours expensive nodes and therefor lower >>nps. Also some extension (and reduction) effects may cause the engine to have >>more cheap or lazy eval-cuts at the leaves. >> >>There are a lot of other things of course, pawn-hashing, eval-hashing, >>move-generation, incremental verus on the fly attack or move-generation, legal >>versus pseudolegal movegen and whatever else... >> >>Movegen and attack generation is usually faster in endings with no sliding >>pieces also due to less pieces to generate moves for. >> >>More sophisticated search statistics would be interesting. >>Eg. about the number of fullsearch-, [pre[pre]...]-frontier-, horizon- and >>qsearch-nodes, differentiated by foreward cuts (hashhit-cuts, nullmove-cuts, >>(lazy)eval-cuts, etc.) and beta cuts and beta cuts after first move. > >Well Gerd, that seems a very comprehensive explanation to this "mystery". >You've just wrote a Hitchhikers Guide to Chess Programming for me. >Somehow you've got me persuaded to read articles on chess-programming, just to >understand what makes them tick. (and to comprehend what you're trying to >explain to me.) > >Running this tournament it seems that there are more ways to Rome, concerning >this type of position, or any pawn-endgame for that matter. > >How does Isichess 2.5 compare to the engines listed? >And is this kind of position (including running a tournament) of any relevance >to a chess-programmer at all? > >Thanks again for your time. >Really appreciate it. > >Cheers, >Rick > Hi Rick, thanks for your appreciation - but "Hitchhikers Guide to Chess Programming" - please no ;-) Some aspects and vague explanations of the nps-behaviour. I suggest to have a look at Bruce Moreland's site: http://www.seanet.com/~brucemo/topics/topics.htm To make the node-duration aspect more concrete: A typical recursive alpha-beta (or enhancements like pvs and others) search/qsearch-routine usually has several exits - or loop breaks. Most nodes we count are leaf-nodes at the horizon or below in qsearch. Here the cycles per node are likely to be more or less volatile. Some possible leaf-node scenarios (as always depending on the implementation): 1. If at the very beginning of the search routine a repetition got detected, we can return a draw score. These are the cheapest nodes, they usually occur rarely - but there are pathological cases... Some don't implement it, if depthleft < 0 or even <= 0. 2. Next, after probing transposition table, there might be a hit with score >= beta, we return score or beta. Probing hashtable(s) may already take a lot of cycles. Cache-misses are likely with "huge" memory access latency. Therefor not all programs probe/store hashtable at the horizon or in quiescence. 3. Possible early returns from interior node recognizers, if they recognize a final game theoretical result for some endgames, for instance K-K. 4. At or below the horizon our material balance + some lazy evaluation (incremental updated) - maxPositionalScore(probably also depending on (grand)parents eval and threat detection) may be greater or equal to beta. Programs may return without further search. 5. At or below the horizon our material balance + some lazy evaluation (incremental updated) + someMargin is less alpha. Programs may skip expensive full evaluation. goto 7. 6. Otherwise nodes become more expensive - full evaluation is done. Eval is of course very implementation depending - caching, incremental attack generation, tiny versus huge eval, lot of conditional cases and pattern, etc.. The greater the possible positional eval score, the less is the chanche of lazy cuts or full eval skips. If full eval score is greater or equal beta, we can return, if at or below the horizon. But this i would usually call an (medium) expensive node. 7. Now we look for captures to improve our alpha. Because this is considered a leaf node, we don't find a capture - or at least an appropriate one, where material gain reaches alpha at least. But there is some effort to generate attacks and to look for captures or promotions, probably with SEE (Static exchange evaluator) involved. Some do it on the fly - some do it incrementally. On the fly is usually slower per node, but due to the earlier returns it is not always needed, while an incremental attack-/movelist update in doMove/undoMove must be done always. Incremental update time is depending on the number of changed (direct + discovered) square controls after a move... This was all about cycles per node, but not about the aspect how often the different degrees of cheapness occur or not. In search we have odd-even effects. Sometimes cheap cut-nodes dominate at the leaves, because the predecessor is an "expensive" all-node. Sometimes the opposite... ------------------------------------------------------------------------ I am not particularly interested in the 8-pawn position, but found the nps issue quite interesting. Dos IsiChess 2.5 was last century - no idea ;-) IsiChess XMM on AMD64 3400+ 2.2GHz: 380KN/s 500KN/s Cheers, Gerd
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.