Author: Vincent Diepeveen
Date: 10:43:50 04/15/03
Go up one level in this thread
On April 15, 2003 at 12:48:06, Uri Blass wrote: >On April 15, 2003 at 10:13:07, Vincent Diepeveen wrote: > >>On April 14, 2003 at 04:47:44, Andreas Rueckert wrote: >> >>>Hi! >>> >>>I'm thinking about a incremental movegenerator for our little project. The idea >>>is to store the moves for the pieces in a array and then check the last moved >>>pieces, if they intersect with the potential moves of the piece on the square. >>>If not, the moves that were computed before the piece was moved, could be >>>reused. Has this been done before? (I guess so, since almost everything has been >>>tried in this field, as it seems to me). Are there any numbers, how much >>>performance gain is too expect from such a solution? >> >>for a beancounter that is psq only i assume is your question as in diep move >>generation including generating all moves at every qsearch node is < 0.6% system >>time. >> >>it is trivial that incremental generation is fastest. you just pick 1 piece and >>generate all moves for it. if first move generates cutoff then you had a cheap >>cutoff. >> >>Yet search efficiency is poor of course as perhaps some other move was better to >>try first. >> >>Let's skip that. >> >>We all know fritz 5 and older than that must have used incremental move >>generators. >> >>Perhaps you can get to 10 million nps speed at a fast K7 with incremental move >>generator (of course pseudo legal, not legal). > >I think that the only right way to count is to count legal move as a node. No. >If my target is to have more nps than I can get more than 10 million legal moves >per second on p1000 by the following steps that I do when movei >calculates perft. perft has nothing to do with this. >1)Search to a fixed depth(no pruning and no extensions and no qsearch so I can >know the last ply in order to avoid making and unmaking that node). >2)Use bad order of moves(no hash tables and no killer moves and no history >tables). >3)Use no evaluation. >4)Do not use alphabeta. A small program i created for fun to see whether it could run within 4KB ram and 64KB rom, i later extended that to be using hashtables. It had nullmove with alfabeta with hashtables with primitive qsearch about 200k nps at a P5-100Mhz. When i tried to search deeper by tricks like killermoves and doing captures first, then it dropped to 150k. When i added 2 things to evaluation it dropped to 100k nps, but searched considerable deeper. 133Mhz P5 was 1.33 times faster. Pro200 is 3 times faster than P5-133Mhz. and P3 scales well against Pro200. So P3 at 2Ghz would be 10 times faster than pro200. Then K7-MP/XP is 25% faster than that machine again at 2Ghz. So multiplication factor is about: 3 x 1.33 x 1.25 x 10 = 50 times. 50 x 200k nps = 10MLN nps That is without incremental move generator by the way. Fritz3-5 were at < 1000 clocks a node at P5. That thing just could do like 2 instructions a clock. So nowadays that would be more like 750 clocks a node at maximum. Note that this had a very primitive evaluation. primitive but it had one. It was a commercial product that fritz. So an optimized version for 2Ghz K7 will easily hit 3 MLN nodes a second. No problem. Vaste majority of system time goes to just evaluation and searching deeper. Not to move generator. >Note that I do not use incremental move generator and I suspect that incremental >legal move generator can do the task of calculating perft even faster. >Uri
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.