Author: Don Dailey
Date: 09:11:42 07/14/98
Go up one level in this thread
On July 14, 1998 at 08:53:21, frank phillips wrote: >I have managed to write my first chess program with help from articles found on >the Web and individuals in CCC (how to do the pv). Its a bit clunky (a lot >clunky) but works, which was original aim. However it is disappointingly slow, >managing only 4 to 5 ply (plus up to a 12 ply quiescent extension) in about >10-30 seconds or so in the opening on my K6-233, compared to Crafty, Exachess >and GNU that manage 8-10ply or more easily in the same position with much more >evaluation of leaf nodes. > >Any hints on how to make it go deeper, faster (on the same machine) would be >most welcome ie the big areas to tackle. Reference to appropriate articles >would also be welcome since I am new to programming, not just chess programming. > The disparity in speeds is so great that it makes me think I could implement a >technique or two to speed things up greatly (I hope) or have completely >messed-up, which I doubt becuase it plays legal chess games (weakly) and solves >a few WAC positions. > >The program does Negamax with capture extensions in the quiescent search, >generates moves using the mailbox[] approach in Tom Kerrigan s simple chess >program, is based on integer arrays (not bitboard), stores moves for each node >in a local array (of structures) in each incarnation of Negamax/Quiescent(), >searches the pv move and captures first, does not have hash tables, does not do >null-move, dose not do killer moves nor all the other things I have heard about >but have no idea what they are. > >Frank > >BTW My thanks to Tom Kerrigan for his simple chess program without which I >would not have even got this far. >Bob, if you ever write that chess computer programming book............... A lot of your problem is in the last paragraph. You will see at least 2 or 3 ply if you do: 1. Hash tables 2. Null move prunning 3. Killer moves A lot of the speed of good programs is lot's of engineering. A lot of "2 percenters" together make a lot of difference. Are you sorting your moves efficiently, do you test for legal castling during the move generation or only when you are about to make the move? Check testing can be made very efficient if you take advantage of what is known, for instance if you are in check, it has to be a result of the last move your opponent made, either by that piece or a result of discovery. There are dozens of little things that will combine to make your program much faster. You have to cover them one at a time. - Don P.S. Profile your program with a good profiler. How much time does evaluation take? Which routines are taking the most time? Can you speed them up? I measure some of my routines by using this trick: I will call the routine twice instead of once (if this is possible without changing the results.) Time the normal version and the version with 2 calls. The difference is an estimate of how much time that routine takes. This won't be perfect since calling a routine twice has the effect of making it more likely to be in the instruction cache, but you can probably view it as a lower bound on how much time the routine takes. For instance, to measure check testing, call this routine twice instead of once everywhere in the program. Compare how much longer it takes the program to run and you will know how much time the check tester takes. If you have nice high resolution timming tools use them instead. Use the profiler. - 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.