Author: Dan Homan
Date: 11:28:36 08/23/99
Go up one level in this thread
On August 23, 1999 at 12:01:59, Bas Hamstra wrote: >Hi Dan, > >>In each position (either regular or q-search), I have a loop that >>cycles through each avaiable move. At the top of that loop I do a >>Nodes++ or a QNodes++ to increment the count. This is the same as >>doing a node increment with every make-move. My qnode count is a >>little different than most because I count depth=0 nodes as nodes >>in the regular search. Q-search nodes (in my notation) are positions >>that result from captures after depth=0. > >Well it should total the same, yes. Also the same order of magnitude with NPS as >mine, but I have hardly any Eval, so it's too early to say. I do SEE however, >like you. A lot depends also on if you let nodes in the qsearch cut >by Eval > Beta *if* the king is in check. I used to do that (like Crafty and I >think also you) but I have the feeling it is not accurate. If I let this *not* >happen, I can solve wac141 at 9 ply without *any* extension. However your qrate >worsens. > >However nearly 300/300 WAC is impressive. Maybe I should ask you first how you >manage that. An earlier version of mine topped 272 on slow hardware. The new >(half baken) version does 260, for the time being, but again without any >extension. Is your source still available? I got on a few dead links here and >there, when I tried to down the source. > The web page is now at http://pc.astro.brandeis.edu/BRAG/people/dch/chess.html Version 2.51 (which is available at that web-page) solves something like 270/300 at 5 sec/move on a Cel 400. It gets like 290/300 at 60 seconds per move. The version I am currently working on gets 280/300 at 5 sec/move and 297/300 at 60 seconds per move. I get the remaining 3 problems if I extend the time to 180 seconds on those three problems, but I don't know if EXchess would change its' mind on any of the other 297. Surprisingly (or perhaps not so surprising), I solved more problems by removing some of the "clever" tricks I was using - such as futility pruning, extended futility pruning, and an extreme form of lazy eval. Part of this may be that I eliminated bugs that I didn't know I had. I used to think that tactical problems in my program could be solved by knowing the right tricks, but now I realize that my tactical problems were mostly caused by bugs. Stripping the program down and having it perform better (at least search-wise) has been an interesting learning experience. - Dan > >Regards, >Bas Hamstra. > > > >>> >>>However in fact I think it should me more appropriate to do Nodes-- in stead of >>>a QNodes--, because the overhead of that node is in the QSearch (movegeneration >>>for example). >>> >>>BTW I have tried nearly all possible datastructures and am still not sure what's >>>fastest. So far my expermiments indicate incremental (pseudo-) attacks (if you >>>do it efficienly) and bitboards are good. At the moment the bitboard version is >>>slightly faster than incremental attacks. Plain 0x88 is also ok. I would say >>>they are all competitive. >> >>I think there are a lot of good choices. My program currently uses the >>simplest minded data-structures I could come up with - a simple 64 element >>array. I have started carring around piece-lists, and these definitely >>speed things up for me. I'll probably go to a more advanced data structure >>in the future (if I stay interested that long), but right now I am >>trying to kill all the search bugs I can. (Actually, I think I've >>got most of my seach bugs killed... I just found another one and >>now I am pretty close to getting 300/300 in WAC at 3 min/move on >>a 400 MHz Cel.) Next step for me is fixing my evaluation.... > >>My "feeling" is this: if you want to do SEE, bitboard and incremental >>>pseudoattacks approaches are fastest. You pay overhead, but get capture >>>generation and SEE very cheap, and many eval advantages. On 64 bits machines >>>probably bitboards get the advantage. >> >>I've recently implemented a reasonable "swap" function in EXchess. I am >>sure it is much slower that bitboards will allow (it drops my nps on the >>WAC test from 200k to 155k), but it more than pays for itself >>by cutting off a large number of q-search nodes. > >Yep, I'm wrestled with this also. An option could be sorting MVV/LVA and >stripping losers at the latest possible moment, just before the move is played. >Tree size grows about 10% then, according to Bob. > > >>>(experiments based on full (-inf, inf) window plain a-b material recursive >>>nullmove R=2 search, with hash, one killer, no history sorting, without >>>extensions). >>> >>>(Question: any idea what Fritz uses? My guess is some extremely efficient form >>>of incremental attacks by which incremental movegeneration. *If* Fritz does >>>incremental movegeneration plain 0x88 would be too slow to get its NPS, I think) >>> >>> >>>Regards, >>>Bas Hamstra. >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>>On August 20, 1999 at 14:24:54, Dan Homan wrote: >>> >>>>On August 20, 1999 at 13:40:28, James Robertson wrote: >>>> >>>>>On August 20, 1999 at 12:24:44, Jon Dart wrote: >>>>> >>>>>>Actually, the first thing I'd look for is the logic you have for >>>>>>storing and retrieving hash values. If you do not always correctly >>>>>>identify the node type (fail-high, fail-low, or in bounds) or >>>>>>if you do not properly set the search bounds after a hash hit, >>>>>>you will have problems like you describe. Having "almost right" >>>>>>logic will appear to work for a while, but sooner or later you >>>>>>will pull a bad value out of the hash table and you will be >>>>>>hosed. >>>>>> >>>>>>Unlike many areas of computer chess, there is really only one >>>>>>right way to do this. Look at Arasan, Crafty, or Gnuchess source >>>>>>and do what they do (in Crafty, look at hash.c). >>>>>> >>>>>>--Jon >>>>> >>>>>I have tried to look at Arasan source several times and was always completely >>>>>confused. Crafty is confusing because the hash stuff is split between 2 files. >>>>>EXchess is of some help. The only program that is not confusing is JRCP, and it >>>>>has too many bugs. :( >>>> >>>>The currently released version of EXchess (2.51) has some small bugs >>>>in hash handling. I forget exactly what they are... it is basically >>>>right, but even small bugs can be a big problem in the right >>>>position. One bug that I can remember gives the same >>>>behavior as your program... i.e. the MATE score is not always >>>>properly adjusted to the ply depth. I can't remember the exact >>>>cause, but I think it had something to do with trying to return a >>>>MATE score when I only had a bound rather than an exact >>>>score in the table. >>>> >>>>The newer version (currently in progress) has some fixes/improvements >>>>in this area and many others. >>>> >>>> - Dan >>>> >>>>> >>>>>James
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.