Author: Frank Phillips
Date: 00:50:59 04/18/99
Go up one level in this thread
On April 17, 1999 at 14:07:28, Bruce Moreland wrote: > >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 Bruce Thanks. A most helpful list for one unfamiliar with the well trodden path. The single response extension was a quick hit, solving another 10 of WAC in the same time as before. As far unique……… maybe later - much later. I take your point, but my aim is lower. I was happy enough a while ago when the thing stopped making illegal moves. There was one phase where it had the occasional habit of producing an extra piece out of thin air. Unfortunately WinBoard tended to notice, otherwise it could have been a useful extension to its abilities. Frank
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.