Author: Robert Hyatt
Date: 09:49:41 07/06/98
Go up one level in this thread
On July 06, 1998 at 10:14:57, Don Dailey wrote: >On July 05, 1998 at 19:39:10, Peter Jacobi wrote: > >>Disclaimer: As I wasn't involved with chess programming >>for some years, so the topic presented below may have >>been resolved for some time. >> >> >>Having done some games with Comet A90 and Crafty 15.15, I am >>somewhat disturbed that I am able to win some games. Even >>running the programs on a Pentium 133 shouldn't allow my >>mediocre chess (German Rating Number about 1600) to win?! >>(15min + 15sec/move time controls) >> >>The same problem will apply to better humans against faster >>machines, I assume. >> >>The positions I am able to win, begin with this pattern: >>The programs assumes to have some advantage (0.5 ... 2.5), >>then following exactly the principal variation displayed, the >>program's evaluations goes down, for example because I am able >>to regain a "sacrified" piece. >> >>The point I want to raise: >>Isn't it possible for the computer to re-check the PV after it >>is established, using some (low) fraction of time of the main >>analysis. >> >>To elaborate, let the PV be 1.W1 B1, 2.W2 B2, 3.W3 B3, >>4.W4, B4 5... - where W1 stands for the first white (computer) >>move of the PV, B1 stands for the first black (opponent) >>move of the PV, and so on. >> >>Having searched for a level of N ply to get this PV, now the >>computer should check the position after 1.W1 B1, 2.W2 for >>a level of N-2 plys (or perhaps N-1). This will give one further >>ply lookahead. If this doesn't refute (giving a significant >>worse eval) the PV, the computer should check the position after >>1.W1 B1, 2.W2 B2, 3.W3 for a level of N-3 plys, giving two further >>plys lookahead. This can be continued for all or part of the moves >>of the PV. >> >>Using this approach, the computer can be somewhat safer against >>refutations of his PV, except for the case, that there is a better >>black move than 1...B1. For statistical reasons (is this argument >>really correct?), more often than not the refutation is not in the >>first black move but further down. >> >>And - I don't know yet, what the computer shall do, if it discovers >>a refutation. >> >> >>Thanks for your patience reading this message, >>Peter > >This is a perfect example of tradeoffs in computer chess. For >any good idea you come up with, there will be tradeoffs. Hopefully >you come up with a good tradeoff and improve your program. > >Unfortunately, your idea is not as powerful as it might intuitively >seem to be. The PV is actually an extremely minor part of the tree >and it is far from clear in any given position how relevant it >actually is. Sometimes the most minor change in the evaluation >of the PV could change even the first move choice. In many (maybe even >most) cases there are hundreds of possible PV's possible that will >score within 4 or 5 points of the score the PV returned. You cannot >easily check them all out. Even if you did you might miss a more >important line that does not score well. > >I experimented once on extending the PV from the previous iteration. >I chose the line at some fixed point (such as the 3rd move of the >PV) and always extended this. Picking an early point like this >increases the chances your extension will be relevant but also >increases the extra nodes you must search. My experiments >occasionsally would help but this was not very common and it's hard >to measure how much damage the extra nodes caused, it was a small >slowdown but it slows down every single position in principle. >Ocassionally of course (in very forced move sequences mainly) you >will get dramatic improvements (which is the point of extensions.) > >I still think PV moves are especially relevant (in the grand scheme of >things) and this should suggest some interesting workable algorithms. > >- Don If you go back to Richard Greenblatt's original paper on Mac Hack, you will find this idea explained in detail. What he did was simple, and might be ok although I tried it way back and didn't like it. He simply noted that at any time a new best score/PV was to be backed up to ply=1, he stopped, went to the position at the end of the soon-to-be-new-PV, and did a 2 ply search. If the score was better, he ignored it and backed up the new PV/score as-is. If the score was *worse*, he tested this new score and PV to see if it can *still* be backed up (> alpha). This was a pessimistic way to avoid some horizon-effects, but works in a limited way... you can certainly try it, but it's interesting to see how many ideas were actually tried back in the 1960's... :)
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.