Author: Andrew Williams
Date: 04:05:09 08/10/01
Go up one level in this thread
On August 10, 2001 at 05:55:08, José Carlos wrote:
>On August 10, 2001 at 05:23:19, Andrew Williams wrote:
>
>>On August 10, 2001 at 02:51:15, José Carlos wrote:
>>
>>>On August 09, 2001 at 12:44:40, Andrew Williams wrote:
>>>
>>>>On August 09, 2001 at 11:17:56, Dieter Buerssner wrote:
>>>>
>>>>>On August 09, 2001 at 11:02:38, Andrew Williams wrote:
>>>>>
>>>>>>On August 09, 2001 at 10:48:18, Dieter Buerssner wrote:
>>>>>>
>>>>>>>On August 09, 2001 at 10:05:42, Andrew Williams wrote:
>>>>>>>
>>>>>>>>Here's my implementation of this in PostModernist:
>>>>>>>>
>>>>>>>>if(ply < (DEPTH-3)) {
>>>>>>>> int m;
>>>>>>>>
>>>>>>>> for(m=plystart[ply]; m < plystart[ply+1]; m++) {
>>>>>>>> make_move(tree[m].mv);
>>>>>>>> if(in_check(OTHERSIDE(whoseTurn))) {
>>>>>>>> unmake_move();
>>>>>>>> continue;
>>>>>>>> }
>>>>>>>> // Probe the TT. If found, react appropriately!
>>>>>>>> ttr = tt_probe();
>>>>>>>> if(ttr != NULL) {
>>>>>>>> if(beta <= -ttr->beta && ttr->betaDraft >= (draft-1)) {
>>>>>>>> unmake_move();
>>>>>>>> return -ttr->beta;
>>>>>>>> }
>>>>>>>> }
>>>>>>>> unmake_move();
>>>>>>>> }
>>>>>>>>}
>>>>>>>
>>>>>>>Perhaps, I don't understand this correctly. Don't you ignore all possible search
>>>>>>>extensions, that might be triggered by the move here.
>>>>>>>
>>>>>>>Or is the "if(in_check(OTHERSIDE(whoseTurn)))" taking care of the check
>>>>>>>extension. (I am not totally sure, whose turn it is ...) It could also mean,
>>>>>>>that this is just the legality check. Or do you generate only legal moves?
>>>>>
>>>>>>I'm not completely sure I understand what you're asking.
>>>>>>The if(in_check(OTHERSIDE(whoseTurn))) test is checking
>>>>>>for an illegal position (ie if the move leaves the side
>>>>>>moving in check).
>>>>>
>>>>>Actually, this is how I understood it first, but then I got unsure ...
>>>>>
>>>>>I assume you extend checking moves normally in search. So what can happen?
>>>>>Assume you have depth 5. Now you try all the legal moves. You check the hash for
>>>>>a cutoff (draft 4 is enough). But what if one move is a checking move? In a
>>>>>normal search, you will probably extend one ply, and then search again for the
>>>>>other side with depth 5 again. So, in the "normal" search, you also need draft 5
>>>>>or better for a cutoff from the hash.
>>>>>
>>>>>So, it looks to me, that all search extensions are ignored by this approach.
>>>>>Especially, I would think, that very often the ETC is successful in typical game
>>>>>situations where the normal search wouldn't be. Earlier you quite likely will
>>>>>have searched the same line in the above example with depth 4. And stored it
>>>>>with draft 4 in the HT. You made the checking move. And searched again with
>>>>>depth 4, and stored with depth 4. No, the next time you visit the position, the
>>>>>first HT probe will fail to yield a cutoff (5 needed, 4 available), in the probe
>>>>>code above, you will have enough draft (4 is enough). But I think, this works
>>>>>against the idea of search extension. This is also the reason, why I did not
>>>>>experiment with ETC yet. To take search extensions into account will almost
>>>>>yield in a full fledged search loop.
>>>>>
>>>>>I must admit, that I had some problems to express myself clearly here :-(
>>>>>If it is still too confusing, please complain, and I will try again.
>>>>>
>>>>>Regards,
>>>>>Dieter
>>>>
>>>>Actually, after I pressed Submit, I understood what you were asking :-)
>>>>
>>>>When I enter a node, I do this (ignoring some stuff that's not relevant):
>>>>
>>>>1. Calculate draft, which is (depth-ply).
>>>>
>>>>2. Probe the hash table, looking for the current position. If I find
>>>> it with appropriate scores and drafts etc, I return. Note that I'm
>>>> checking *before* applying extensions for this node.
>>>>
>>>>3. Work out what extensions are required at this position (eg check, recapture
>>>> etc).
>>>>
>>>>4. Check to see if (given the extensions applied) I should enter qsearch.
>>>>
>>>>5. Try a null move.
>>>>
>>>>6. Try the hash move, if one was found in step 2.
>>>>
>>>>7. Generate the moves
>>>>
>>>>8. Do the ETTC loop shown above.
>>>>
>>>>9. Enter the main loop. Here, I make moves, then recursively
>>>> call alphabeta() with ply+1 and (depth+extensionsAtCurrentPly).
>>>>
>>>>
>>>>I think I do have an error, as you say. What I should be doing is
>>>>incorporating the extension for the current node in the test for
>>>>"sufficient draft" in my ETTC loop. I have a feeling that other
>>>>people do the extensions in a different place (after each make_move
>>>>in the main loop?) and for them this would look different again.
>>>>
>>>>Thanks a lot for spotting this, Dieter.
>>>>
>>>>My apologies for the rambling nature of this message; as much as
>>>>anything, I'm "thinking aloud" to help myself understand what I
>>>>am doing wrong.
>>>>
>>>>
>>>>Andrew
>>>
>>> I think you don't have any error, as long as you store the hash stuff (after
>>>the search is completed for that node) with draft=depth_before_extensions. This
>>>was, your probes and your search is consistent. Right?
>>>
>>> José C.
>>
>>I think what ETTC is trying to answer is, "if I make this move and then
>>search recursively (as I normally would), would I get a cut-off at the
>>top of the new search?". So I need to be sure that the cut-off condition
>>I apply is the same for both the test and the recursive call; this is what
>>the (draft-1) is supposed to achieve in my original version. However, my
>>recursive call uses (depth+extensionsAtCurrentPly) as the target depth, so
>>to be consistent, I should incorporate the extensions into the ETTC test
>>as well.
>>
>>Andrew
>
> I think I didn't express correctly, or maybe I'm missing something now... Let
>me try again:
> At the top of your search function, you check the hash table _before aplying
>extensions_ (this is what I understood in a previous post). If you don't cut
>from the HT, you aply extensions and do the rest of the search stuff.
> Finally, you store the result of the search in the HT.
> What I meant is: if you save the depth-before-extensions as the draft of the
>hash position
> a) your search is consistent because your stores and your probes use the same
>depth for the same node, no matter if you extend or not.
> b) ETC will work just fine, because the hash probe is _before extensions_ so
>it will work exactly the same as in your normal search.
>
> Am I right?
>
> José C.
Hmmmm..
Here's the premise I'm working from: Suppose we forget about ETTC. I'm
reasonably confident that the relationship between my hash table and
my recursive use of it is correct. So when I probe and I get a hit and
the scores and drafts are OK, I'm happy that my program is correct to
take the cut-off etc. So I'm assuming that whatever I put in the HT is
correct, with respect to what I'm going to do when I probe it.
So now I introduce ETTC. I'm happy with what is going on before, so my
implementation is focussed on mimicking that, but hopefully with less
work. I think that to accurately reflect what I'd do if I got to the
main search loop (the one which makes recursive calls), I need to include
the extension in the depth that I'll check, because if I made the recursive
call I would be including the extension in the depth I would pass in to
the next level.
I think this is correct, but this is a very useful discussion :-)
Andrew
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.