Author: Robert Hyatt
Date: 07:38:35 11/13/03
Go up one level in this thread
On November 13, 2003 at 09:38:49, Daniel Clausen wrote:
>On November 12, 2003 at 13:40:24, Robert Hyatt wrote:
>
>>On November 11, 2003 at 22:30:39, John Stanback wrote:
>>
>>>On November 11, 2003 at 10:24:30, José Carlos wrote:
>>>
>>>>On November 11, 2003 at 09:38:59, Robert Hyatt wrote:
>>>>
>>>>>On November 11, 2003 at 02:45:28, José Carlos wrote:
>>>>>
>>>>>>On November 11, 2003 at 01:00:14, John Stanback wrote:
>>>>>>
>>>>>>>As others have noted, this is an interesting position since the tree
>>>>>>>becomes so much smaller after the capture such that it's easy
>>>>>>>to enough search depth to see the impact of Qxf3.
>>>>>>>I made a simple modification that lets Zarkov find Qxf3 in
>>>>>>>under a minute (or less depending on the threshold). This also helps
>>>>>>>on lots of other sacrifice positions, but I don't know
>>>>>>>if overall it helps more than it hurts since I just implemented
>>>>>>>it 15 minutes ago.
>>>>>>>The extra code is only applied at the root and looks like this:
>>>>>>>
>>>>>>>MakeMove();
>>>>>>>d = depth;
>>>>>>>while (1)
>>>>>>> {
>>>>>>> score = -Search(side,ply,d,-beta,-alpha);
>>>>>>> if (!capture || nodes_just_searched > threshold)) break;
>>>>>>> ++d;
>>>>>>> }
>>>>>>>UnmakeMove();
>>>>>>>
>>>>>>>Where threshold is some fraction of the total nodes searched
>>>>>>>during the previous iteration, say nodes/32 or nodes/16.
>>>>>>>
>>>>>>>This allows the program to search captures at the root to
>>>>>>>arbitrary depth. In this position for example, it searches
>>>>>>>Qxf3 to more than 20 ply during iteration 11!
>>>>>>>
>>>>>>>It doesn't seem to cause much slowdown on about 20 other positions
>>>>>>>I tried. I think this might cause some strangeness with the hashtable.
>>>>>>>It may make sense to try some variant of this at ply=2 also.
>>>>>>>
>>>>>>>
>>>>>>>John
>>>>>>
>>>>>>
>>>>>> Interesting idea. What about real games? In games, I don't clear the hash
>>>>>>table between moves, so if I did this (haven't tried 'cause I'm at work now) I
>>>>>>guess I'd have extrange behaviour when I'd cuoff by hash hit in the first
>>>>>>iterations. I mean, if I search up to depth 12, in the next move I go to depth
>>>>>>10 almost instantly due to hash hits in ply 2.
>>>>>> Do you preserve the hash table between moves? Have you tried games to see how
>>>>>>your idea affects?
>>>>>>
>>>>>> José C.
>>>>>>
>>>>>
>>>>>I don't see where this should hurt hashing at all. You are only searching
>>>>>the positions below the capture with extra depth. Certainly storing the
>>>>>depth you are using when you do the search can't hurt later lookups no matter
>>>>>where they occur...
>>>>
>>>> I'm not sure if what I say makes sense because I haven't come back home yet to
>>>>try it, but the idea is: I have made a search before; then my oponent moves and
>>>>I start searching again, depth = 1; and I do
>>>>
>>>>MakeMove();
>>>>d = 1;
>>>>while (1)
>>>> {
>>>> score = -Search(side,ply,d,-beta,-alpha);
>>>> if (!capture || nodes_just_searched > threshold)) break;
>>>> ++d;
>>>> }
>>>>UnmakeMove();
>>>>
>>>> I will hit the hash table in ply 2 with draft, lets say, 10, so I'll return
>>>>with a very small number of nodes searched; then I ++d and try again; at some
>>>>point, I won't be able to cutoff from the hash table and I'll start searching at
>>>>a high depth; if time runs out, I will have only searched on move.
>>>>
>>>> José C.
>>>
>>>
>>>I guess Bob's right that technique I described shouldn't cause any
>>>unusual problems with the hash table, other than the related issue
>>>that you point out where the search can reach a depth where the
>>>hash table "gives out" and the current move will use most or all of the
>>>allotted time. I guess I'll have to come up with a workaround for
>>>this problem.
>>>
>>>
>>
>>
>>
>>Try my idea. Set a much-reduced time-out while doing that "quasi-search"
>>so that you don't get stuck there. Once you time out, set the time limit
>>back to normal and on to the next root move...
>>
>>There are probably hidden piles of doo-doo to avoid, of course, once you
>>start implementing such a fix. :)
>
>Well, when/if I try the idea in my chess program I will definitely try to solve
>it more general.
>
>What I'd like my engine to think is something like this: Ok, material-wise I'm
>no a win here. After the queen-sacrifice my positional evaluator tells me there
>are good chances to win this simplified endgame. So let me invest some time (but
>not very much) in the position after Qxf3 gxf (NOT just after Qxf3!) and check
>whether I can find a win. If yes, I like the move Qxf3.
>
>Of course my engine should think this on each ply, not just in the root-node.
>
>Imagine a position where white can exchange rooks and reach the famous FINE-70
>position. With HTs it's quickly possible to see the win. I'd like me engine to
>see the win before the exchange though, not afterwards. (since then, I maybe
>never reach the position in the first place)
>
>Yeah, I know these are just words. I mean, at least John tried something _for
>real_ and it worked. :) But maybe one day... :)
>
>Sargon
This just opens a huge can of worms that has been discussed thousands of
times in the past. Here is the question:
"what makes it reasonable to search one root move deeper than another?"
sub-questions include "if you search two moves to different depths, how can
you possibly compare the scores?" Answer: "you can't." Of course, if you
search two moves to different depths and the deeper search proves a win,
then you can safely take that even if the other move also wins quicker if you
search it to the same depth. But if it isn't winning, then comparing the two
scores is _very_ risky.
John's idea is certainly interesting. however, it isn't really new. Even
Greenblatt's program added some fuzz by re-searching a move anytime it replaces
the PV move as best. The idea was that if you get a new PV, just before you
accept it as better, you go to the end of that PV, and tack on a two-ply
search. If the score is better, you use the score before the 2-ply add-on. If
the score is worse, you use the score after the two-ply add-on and decide if
_that_ score is good enough to still make this a new PV. The intent was to
drive off horizon effect moves to a deeper level. The result was search
inconsistencies. I did this in the 1974-1975 version of my chess program, but
eventually took it out just before the 1978 ACM as I decided that the idea
was interesting, but not "sound".
Of course, we search root moves to different depths anyway, due to search
extensions, and this already causes interesting "issues" to crop up. It
seems that everybody is happy with the result. So going a few plies deeper
after a capture that removes the last piece might be worth-while. Or it might
be too expensive. Time will tell.
Meanwhile the various problems have to be solved, such as wasting too much
time on that move and walking into a trap after playing another move.
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.