Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Crafty and NUMA

Author: Anthony Cozzie

Date: 06:53:06 09/04/03

Go up one level in this thread


On September 03, 2003 at 19:55:08, Robert Hyatt wrote:

>On September 03, 2003 at 19:23:46, Anthony Cozzie wrote:
>
>>On September 03, 2003 at 11:53:58, Robert Hyatt wrote:
>>
>>>On September 03, 2003 at 08:12:55, Uri Blass wrote:
>>>
>>>>On September 03, 2003 at 02:24:00, Gian-Carlo Pascutto wrote:
>>>>
>>>>>On September 02, 2003 at 22:34:49, Robert Hyatt wrote:
>>>>>
>>>>>>>Been working a year fulltime now :)
>>>>>>>
>>>>>>
>>>>>>So?  It took you over a year to get your parallel search working.  It took
>>>>>>me weeks.
>>>>>>
>>>>>>:)
>>>>>
>>>>>In all fairness, he did a full DTS implementation, including rewriting the
>>>>>program to a nonrecursive search, while you took an easy way out.
>>>>
>>>>I do not understand the need for non recursive search.
>>>>
>>>>I think that non recursive search simply limit your possibilities for future
>>>>developement because the code is ugly and you need to write almost the same
>>>>function again and again.
>>>
>>>
>>>
>>>You don't do recursive calls, instead you have a loop that increments ply
>>>and goes back to the top for the next level of the tree.  The reason this is
>>>needed is that you want to be able to see the _entire_ tree, and tell a
>>>processor to start work _there_ (at some specific ply where you are pretty
>>>certain all moves need to be searched.)  WIth a recursive search, this is
>>>very difficult to do.  It is easy to split the tree at the current ply, but
>>>it is _very_ difficult to split somewhere else.
>>>
>>>
>>>>
>>>>If you want to change something in the search rules then you need to change your
>>>>program in a lot of places.
>>>
>>>No.  rather than recursive calls, you execute the same loop over and over, once
>>>for each ply of the search...
>>>
>>>
>>>>
>>>>I guess that you need to write code for every possible depth that you get and in
>>>>order to let your self to do extensions you need to write code for
>>>>depth 10,depth 10 after one extension,depth 10 after 2 extensions, and you also
>>>>need to limit the number of extensions at specific depth.
>>>>
>>>>You also limit your possibilities to extend because
>>>>you cannot decide to extend more than one ply without modifying your code.
>>>>
>>>><snipped>
>>>>>
>>>>>Diep's parallel performance does seem to be better than what you and I are
>>>>>getting.
>>>>
>>>>I have no idea about Diep's parallel performance.
>>>>I do not know about a single game of Diep on the new machine and I guess that we
>>>>need to wait for november to see its performance.
>>>>
>>>>Uri
>>
>>
>>wouldn't it be easier to simply put all your recursive variables into some huge
>>struct and essentially manage the stack yourself (while still traversing it with
>>a recursive function over a loop) ?
>
>
>It isn't so easy.  When I return from the "split point" I need to do special
>things, but there is no way to go back and modify the call stack so that the
>old call will now return to a different place...  I could do that, but not in
>any way that would be remotely portable, in fact it would be specific to each
>compiler and/or O/S used, which would be horribly ugly to support...
>
>IE I am at ply 12, but I want to split with an idle processor at ply=6.  I
>can't go back to my stack and modify things so that ply=6 returns to a different
>point, to "unsplit" the tree...

what I am saying, is to put all the data that would normally be on the stack in
your own structure, e.g:

struct RecursionBlock
{
  int alpha, beta, ply, depth, cur_move, move_list, ......
};

then traverse with

Push(alpha, beta, ply, depth, ....);
Search(RecursionBlock *rb)
Pop();

which is what the compiler is doing anyway, and now you can go back and modify
things appropriately.

to me this seems conceptually easier than an iterative search.

anthony



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.