Author: Peter McKenzie
Date: 23:27:56 07/18/99
Go up one level in this thread
On July 18, 1999 at 03:17:02, Scott Gasch wrote: >What are the typical ways people use to improve the speed of the searching >algorithm? Here's what I have done: move ordering / history, memory pool for >moves so I am not calling malloc/free, optimized my C as much as I can, save a >pointer to the kings on a board representation so I do not have to search for >them when looking for checks. > >And still the program is sluggish; it gets a little over 20,000 nodes/sec on my >AMD K6-3 400. For comparison I clocked TSCP on the same machine and it is >getting about 15,000 nodes/sec. > >How can I speed this up more? What is a good speed on this kind of hardware? It all depends, of course :-) LambChop has what I would consider to be a slow NPS rate, and would do about 25,000 NPS on that machine. This is partly because I try to have a smart evaluation, and partly because I've never been totally hung up on speed. Fast programs are approximately 10 times faster I think. There are zillions of ways to speed up a chess program - but some involve a complete rewrite! First thing to do is see if there is any major bottleneck. Do you have a complex eval? Try replacing it with a material only eval, and see if the NPS speeds up much. If so, look at how you can optimise your evaluation function. Some ideas: - hash the pawn structure evaluation in a separate hash table - compute more stuff incrementally (update piece square scores in make/unmake function etc) Maybe move ordering is slowing you down - take it out and see how the NPS increases (although this can be deceptive since less cutoffs will occur and your NPS will automatically increase). Don't sort the moves, just choose the best few (5-10) - if you don't have a cutoff by then odds are you have to search all the moves anyway. Doing a full sort is pretty slow You could give lazy evaluation a try. A basic thing: do you have a list of pieces (as well as the basic board representation)? In LambChop I have 4 lists: white pieces (excludes pawns, the king is always the first in the list), black pieces, white pawns, black pawns. I find these data structures handy for alot of things. What is your basic board representation? 0x88 is nice, although I use Board[120]. There are different tricks for each type of representation... cheers, Peter > >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.