Author: Stuart Cracraft
Date: 13:35:27 12/15/05
Go up one level in this thread
On December 15, 2005 at 16:13:12, Andrew Wagner wrote: >On December 15, 2005 at 16:04:58, Stuart Cracraft wrote: > >>On December 15, 2005 at 15:55:03, Andrew Wagner wrote: >> >>>Let your imaginations roll for a moment. >>> >>>First, imagine that a perfect SEE algorithm existed. That is, given any >>>position, and a side to move, you could decide which piece to move without doing >>>any searching, and get it right 100% of the time. Now your search tree is down >>>to a branch with an ammortized size of about 12 branches per position (maximum >>>of 27 moves for the queen, 14 for rook, 13 for bishop, 8 for knight, 8 for king, >>>3 for pawn) with an average case in the middle game much lower. You still have >>>to search those 12 branches or whatever, but you're always only searching moves >>>for a single piece per node. >>> >>>Now, take a typical modern engine, with or without a typical SEE algorithm, and >>>fitted it with this new, perfect SEE. How much improvement would you see, if >>>any? >> >>There's a problem here. SEE stands for Static Exchange Evaluator. It is >>called to determine whether to do the quiescence capture search. It is not >>for other kinds of moves. >> >>I spent some time working on SEE and finally just asked for this board to do it. >>Someone contributed a nice code fragment (no, it wasn't Bob), and it is now >>a permament part of my program. I noticed a substantial improvement in the >>program's search capability. >> >>SEE eliminates the ostensibly losing captures, permitting search of the winning >>and even captures. It is more often far more right than wrong because the bad >>captures are by far the preponderance of the events in the capture tree. >> >>What YOU are talking about is not SEE. You are talking about the perfect >>Evaluation function. I've thought about that point in the past and just >>don't see it worth thinking too much about because the game is far more >>easily approached tactically than non-tactically. The former is the >>majority of skill. The lack of it, at any reasonable player strength, is >>often fatal. >> >>It has been noticed, by many, that a better evaluation function than they >>had before, up to a point, can actually improve (i.e. reduce) the size >>of the tree and actually speed up the search. >> >>I can't cite a specific paper that investigates this as its goal but think >>it would be a useful piece of research and rather convincing at that. I >>suspect you'd find a bell-curve where at a certain point of additional >>knowledge, the tree search is better but much further away from that point >>would give much poorer results. >> >>Too much knowledge and too little knowledge are not the place to be. >> >>Unless, of course, you can do it all in hardware and in parallel. :-) >> >>Stuart > >Stuart, >It's been a while since I've done any twiddling with an engine, so I'm still >trying to remember how some of these algorithms work. I actually went and found >GCP's SEE code from Sjeng in 2001 (I suspect this is the fragment you're >referring to), and looked at that briefly. You're right, I forgot that SEE was >for captures only. But I don't think what I'm referring to is quite the same as >static eval, either. The question I want this algorithm to answer is not "Who is >better in this (static) position, and by how much?" (eval), nor "How good of an >idea is this particular capture?" (SEE), but "Which piece should I move?" (or, >in the follow-up, "Which move should I make?"). It's the ultimate move-ordering >question, which is not eval. But it applies to all moves, not just captures, >which is not SEE. It's the same thing as perfect eval because the routine would return a number, you'd apply it to each immediate successor position, and the highest would be the position you'd move to. I don't see the issue. It would be fun to have a tournament where only one-ply search without any form of quiescence would be used. SEE would be permissible in that one-play evaluation. Now match all the programs with each other in 2-game round-robin, do your eliminations, and the result, should be, the best evaluation function in the lot for that domain. Stuart
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.