Author: Dan Homan
Date: 18:58:39 12/16/97
Go up one level in this thread
On December 16, 1997 at 17:53:25, Willie Wood wrote: >Dan, > >You say that, a few weeks ago, your program would have been crushed by >crafty, though you've been working on it a year. What did you do in >those few weeks to improve it? Perhaps I gave the wrong impression. My program is still regularly crushed by crafty clones, in fact - the game I posted was its first win against one. I don't pretend it is even close... it is just closer than it used to be. :) The gap used to be so large that playing any crafty clone (even one on much slower hardware) seemed hopeless. Most of the improvement has happened over the last couple months. I re-wrote the program entirely. This allowed me to dump a lot of unfortunate baggage that my program carried from it's one-ply evaluator stage. I had kludged a lot of code onto that old frame-work and it played a reasonable game (~1600 in blitz on FICS) but serious improvement required a re-write. The improvements in the last couple weeks have been incremental by comparision, but they seem to be the 'extra little bit' that have allowed it to play a few competitive games against other programs on FICS. For example... I improved the king safety - I noticed that some programs and 1900+ humans were crushing it by attacking the king. I also added capture extensions - this seems (so far with limited testing) to be a significant improvement. > >I would also be interested in hearing about the algorithms you use, what >worked the best, what didn't. For example, do you use bitboards, any >forward pruning, etc. > My time is limited so my goal in the re-write and adding new code is to keep it simple. I don't use bitboards - I think they are great, but I don't have the time to figure it out right now, maybe in a later re-write. I use a basic PVS algorithm, no frills. I tried adding aspiration on top of PVS, but that seemed to add significant complication for little gain. Move ordering is hash moves, followed by captures, followed by history moves. I tried adding killer moves but this didn't seem to add much improvement over history (perhaps I did something wrong). In the evaluation, I calculate piece-square tables at the root and evaluate pawn structure and king safety at the leaf nodes (these are hashed in a pawn hash table). I am incrementally adding other evaluation terms as I notice weaknesses, but I am a rather average player (~1600) so this is a slow process. The only forward pruning is by recursive null move. I recently understood something Bob Hyatt and Bruce Moreland had mentioned on occasion about allowing the null-move to collaspe straight into the capture search. I implemented this (it turned out to be a simplification over what I was doing before) and it was a big win. The capture search considers only captures that will bring the score above alpha - no checks are considered. As you can see, my program falls into the fast-dumb category - although it is not that fast (about 25000 nps on a P133, as much as 45000 nps in the endgame). My move generation might be a slow point. I don't use mailbox or a memory copy. I do lots of if...then and for...next loops - this reads very clearly but is probably slower than some of these other techniques. Tom Kerrigan's Simple Chess Program gave me several ideas for data structures that I have found quite valuable.... For example, the idea of carrying around the type of move (e.g. a capture, promotion, pawn push, etc.) with the move structure is very useful. Of course, there are many areas that need improvement; some need serious improvement, but that keeps the hobby going. :) - Dan p.s. I have aspirations of making my program into more than a fast-dumb searcher someday. I'd like to add a little personality. I have a few ideas of how to do this, but nothing I am close to being able to implement.
This page took 0.01 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.