Author: Harald Lüßen
Date: 02:19:12 01/01/06
Go up one level in this thread
Sometimes ideas are in the air and many people try to use them. In this postings I find some of my own ideas or in other words I can imagine what was intended or meant with Vasik's descriptions. My problem is, there are people who can implement them and others who cannot (me). On December 31, 2005 at 19:24:30, Mike Byrne wrote: >Vasik Rajlich , chess programming superstar in the making, has offered many of >his ideas on chess programming here on CCC - prior to his release of Rybka. > >What follws are his words extracted from the CCC archives. Interesting stuff as >it provides clues into how he programmed Rybka. > >========================================================================= >"Interesting. You could also prepare some data structures in the positional >search and use them in the tactical search, a sort of root-node pre-processing >repeated in mid-search. ... >Vas >" I have heard of pre-processing piece square tables in the root position depending on the opening or the position of (center) pawns. My idea is to expand this to the middlegame. I don't know whether it works. When I hat a few minutes look at a Rybka.exe dump and saw lots of tables I wondered, whether Vas had done what I just dreamt about. My idea is an idea database or midgame database: Get the information of pawn structure, king position and raw material for both sides in very few bits as a key to further information. 2 x king pos = 2 x 5 bit = 10 bit (a1b1, c1d1, ..., g1h1, ..., g8h8) 2 x pawn pos = 2 x 24 bit = 48 bit (a2a3, a4a5, a6a7, ..., h6h7) 2 x material = 2 x 3 bit = 6 bit (0=pawns only, 1=B/N, ..., 7=all) These 64 key bits can be used with an additional hash value in a big const table. Of course you can improve this coding. The entries in the table can be a kind of piece square tables coded in very few bits: 3 bit piece type, 5 bit coding pattern (like king and pawns above) to be filled with the individual 0-1-pattern or just fixed patterns, and 8 bit for the bonus value of pieces placed on the 1-fields of the pattern. Or you can store a list of typical moves (piece (from) to) with reduce/expand-values for the key. Or you can store some evaluation switches for special evaluation terms. You can give an additional evaluation bonus for pieces on the right place or sort the moves to the front in your move ordering. It would be good to reduce or expand the moves found in the table if they are possible in the real current position or expand the moves that hit some stored (pattern-)criteria. Off course you have to test your current position at each node in the search tree, at least near the root. Just like we do with the normal hash table. How to get and collect the information of the database? Scan through a big pgn database of good players, build the keys and patterns of each position and da a statistic of the pieces at positions and frequent moves. Reduce this data collection to a usable size and store it with or in your engine. I have no own chess knowledge and have to rely on others. In this case the whole chess history. Just think: every made move was good in that position. I don't know whether it is possible to build this database. Some pictures I have seen in Scid or other visualisation tools are very impressing and seem to hold some chess knowledge. They are like trained neural nets or just valuable heuristics. I don't know whether it is possible to use this information for an improved evaluation and search, but I would very much like someone to test it and tell us his results. I would do it myself but I have not enough time and patience to do it. What do you think? ... >====================================================================== > >"True, an evaluation which is both accurate and fast is ideal I can tune my engine (Elephant) to win against Gnuchess or Tscp, but not both. I will be crashed positionally or tactically. And when I find a good compromise it will loose badly to gerbil. Now you see my engines' level. :-) >It would be interesting to know the exact profile of the time spent in eval of >the top programs. As I rememember Amir said that Junior spends "less than 10% in >most positions". Does this mean a lot of lazy evals and some very big evals? Or >a truly small evaluation which pinpoints the most important features of the >position and ignores the rest. > >In many cases, you arrive in eval needing only to show that the non-material >factors can't add up to more than X. (ie X = material score - alpha, or beta - >material score.) As X gets higher and higher, more and more things could be >ignored. Maybe some sort of a pinpointed lazy eval is the answer. > >It seems to me that the areas where an engine can get the most benefit are: > >A) Guiding search (ie reducing/extending): very very high >B) Quality of eval: very high >C) Overall speed, including speed of eval: medium/low, unless very big factors >are involved, such as building specialized hardware or getting a chance to run >on a big mp machine > >On the other hand, "A" and "B" are quite vague, you never really know if what >you did was an improvement, while "C" is very easy to measure. > >Vas >" I did something similar in the last months. I replaced some lazy evaluation with a new one that gives an evaluation and possible estimated margins to the real score. I use these raw values and margins in my qsearch. The values are just the big material and evaluation terms without any fine detection. The margins depend on special threats and unsecurities like king safety and passed pawns. There could even be some search hints besides these two return values of this function. And the function could (should) be used in the whole search. I have not finished it yet. To be honest, the result was not worse than before. >============================================================== >" >Hello, > >It seems to me that there is a way to deal with this. > >Let's say you're at node A going to node B. You can statically evaluate node A, >statically evaluate the move (A->B) in the context of node A, apply the >appropriate reduction/extension, and enter node B with the already >extended/reduced search depth. In this case, node B will go into the hash table >with that new remaining search depth. > >If I understand the issue correctly, you'd also like to statically evaluate node >B before deciding on the reduction/extension for move (A->B). However, I am not >sure that that is necessary. > >Let's consider the typical node which is a candidate for reduction. It should >have one of two qualities: A) it is extremely static B) it looks unpromising, ie >score somewhat below alpha. > >In the case of very static nodes, it's pretty clear that you shouldn't need to >also look at the next move/node. In the case of an unpromising node, I was >thinking that you could do something like identify the few factors which could >change the evaluation. For example, if you're down two pawns but there are some >vague attacking prospects, then king safety would be that factor, and moves that >attack the king would be extended/not reduced, while moves which attack pawns on >the queenside are reduced. If you have an advanced passed pawn, then pushing >that pawn or supporting its advance would be the one way to bring the score >back, and moves which support that would be extended/not reduced. In all of >these cases, it seems to me to be enough to only consider the original node >(node A) and the moves themselves. The static evaluation of the next node can >then be done already knowing the new depth. > >Unfortunately I haven't started to implement this, so there might be some issues >here. > >At any rate, any reports on your experience in implementing this are welcome. >There appears to be almost nothing in the chess literature about this. The best >I found was Ed Schroeder's description of the pruning in Rebel, but he >concentrates on pruning positions with very bad scores rather than on pruning >irrelevant moves. > >It does also seem to me that this is "the key" to a good program, or at least >that it could be "a key". > >Vas >" Does this follow from my ideas above or is there something else to? ... >===================================================================== > >There's much more there too -- I just selected teh more interesting (for me) >tidbits. > >Best, > >Michael I also find these ideas interesting. I just cut some out for a shorter posting. I would like a further discussion of these ideas but I can not answer for 1 or 2 days. Harald
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.