Author: John Boyd
Date: 18:51:40 05/02/03
Go up one level in this thread
On May 02, 2003 at 17:09:07, Geoff wrote: >Hi > >I would appreciate some advice on how I should procede in improving the chess >program I am working on. > >Currently it is very similar to TSCP. I will explain what I have changed and the >results I have got. TSCP is a good place to start. >Mod1) >Changed the Alpha Beta search to use use an Aspiration Window >This did give an improvement, reducing the number of nodes searched to get to a >given depth in most positions. >I did read that this could give search instabilites and might even cause lock >ups or crashes, I have not noticed this yet however If you have conditional extensions in your search based on windows around dynamic values like the best root score so far or even alpha things can get a bit funky... because the search can return slightly different results. > >Mod2) >Added a simple mobility function to the Evaluation. >This took my nodes per sec down from 500k/s to about 350k/s as I recalculate >every move for every piece again in the eval function. The playing strength >marginally decreased, probably due to the severe hit on speed ;-( Maybe calculate mobility in your move generator? It won't be accurate though if you generate pseudo-legal moves only. > >Mod 3) >Added a save of 2 killer moves at each ply and re-sorted moves before searching >This made hardly any difference in reducing the nodes searched to get to a given >ply. I assumed this lack of effect was due to the fact that it has already got a >history[64][64] array built into the code I found killers to be effective but it depends a lot on your move ordering. I don't allow captures in my killer slots. And my killers get ordered between winning captures (eg PxQ PxR) and losing or equal captures (eg QxP QxQ). So, in the move ordering I try 1. PV move 2. bestmove from hash table 3. Winning Captures (PxQ,PxN etc) in mvv/lva order 4. Killer 1,2,3 (remember these are never captures) 5. Losing/equal captures (QxP QxQ etc) in mvv/lva order 6. All other non-captures are ordered by history scores Its probably not optimal but its better than nothing. > >I noticed that the good amateur programs get down to a depth of about 9 or 10 >where my program only manages 7 or 8 in a given time, so I guess I need to look >at things like Null moves and other complex search tricks ? I'm a beginner too and I was amazed how easy it is to implement nullmove. Just remember to clear the ep square and then restore it immediately after the null search. With TSCP I had to modify the makemove and takeback functions. Some debugging may be required but its really worth the trouble. Huge speedups. There are other caveats like not null moving twice in a row and not null moving when there are only a few pieces on the board (to avoid overlooking a zugzwang situation). >Any advice as to what further mods I could do to gain the most improvement ? >Simple mods preferred first ;-) 1. In TSCP you can write a dedicated root_search() function to handle ply 1. Then you can resort the root moves based on their actual scores after each iteration. This worked well for me. 2. If you are using TSCP's attack() function, rewrite it. Instead of looking for pieces which attack a certain square, work outward from the square and look for a potential attacker. Its heaps faster. 3. TSCP also benefits from keeping track of the two king's squares. The in_check() function scans the whole board looking for the relevant king's square before calling the attack()function. I created two global variables wksq and bksq and update them in makemove() and takeback() whenever the kings move. 4. TSCP can benefit from using piece lists so it doesn't have to loop 64 times in gen(), gen_caps() and eval(). It means makemove() and takeback() become a little messy but its a good speedup. 5. Converting TSCP to an 0x88 board representation is also worthwhile. That should keep you busy for a while... :-) Just adding hashtables and nullmove to TSCP (plus the above tweaks) will make TSCP search its built-in benchmark to 6 ply at least 25x faster. Good luck! Ross
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.