Author: Bruce Moreland
Date: 11:07:28 04/17/99
Go up one level in this thread
On April 17, 1999 at 10:38:25, Frank Phillips wrote: >There are times when I think my chess program is actually working. This is one >such moment. It is hardly a killer, but manages around 260 on WAC300 at 10 >seconds a move and is about on a par with GNUChess4 in matches under WinBoard - >which, as I recall, according to at least one authority here puts it firmly in >the pansy class. (Come to think of it I need to name it.). Against LambChop >and Gromit, for example, however it often falls to tactics even though, at least >in the case of LambChop according to its readme files, these programs are not >necessarily faster searches. So my question is, how do you make a program a >better tactician? Currently mine is the usual mix of full-width alpha-beta >(PVS) search with extensions for check, recapture and pawn-push in the endgame >in the endgame, and simple quiescent alpha-beta with futility pruning. The next steps along this very well trodden road, and in no particular order, are: 1) Null-move forward pruning. This will increase depth searched, which will cause it to find a lot of things, but will cause it to miss a few things. 2) Improved move ordering. Do experiments to improve move ordering, this will improve search depth. History heuristic and killer moves. 3) Hash table. Done almost solely with step 1 in mind, since hash tables improve move ordering. 4) Single-response extension. Normally you extend on checking moves. But if you also extend when *in* check if there is only one legal way out of check, you can resolve some common king hunts extremely quickly. This extension must be constrained or you'll blow all of your data structures (meaning that you can't extend a full ply on average for this one). Your WAC scores will increase if you do this one. 5) Prune quiescent search. Experiment with reducing the number of nodes you evaluate in your quiescent search. If you can prune out dumb cases earlier, you can get more general depth. 6) General performance improvements. Get in there with a profiler and figure out which of your functions is slow, and fix them. 7) Improve testing procedures. When you make a change that is meant to increase speed without changing the tree that is searched, make sure you have a tool that can determine if the number of nodes take to finish any given ply changes. That is usually indicative of a tree-shape change. A tree-shape change when you are merely trying to make the same system go faster is always a bug, or at least an unintended consequence that needs to be explained. When you get a tree shape change, you need to aggressively debug it. This will result in less time spent dealing with bugs, and more time spent making the silly thing go faster. As a side-issue, these debugging tools can be used to determine if a performance change really did make you go faster, it is amazing how often a change that you'd think is a fantastic improvement really makes you go slower. Another thing is that WAC kind of sucks. After a while you get almost all of them and it's hard to tell if you are getting better. ECM is a better suite, there are 879 positions, and although some of them are broken or cooked, there are many that are sound and challenging, so if you increase speed or efficiency you will get more right, but you won't run out (at least I haven't). None of what I said will make your program in any way unique, which is something you may wish to consider. bruce
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.