ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

DTS Structure
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Onno Garms



Joined: 12 Mar 2007
Posts: 224
Location: Bonn, Germany

PostPost subject: Re: DTS Structure    Posted: Fri May 28, 2010 10:27 pm Reply to topic Reply with quote

Edmund wrote:
A main difference moving to the Dynamic Tree Splitting Algorithm is that the whole search has to be laid out iterative instead of recursive. Now my question is, how can this be achieved best?


Iterative search is also useful for YBW. Also, it helps profiling because you don't have cycles in the call tree.

I personally don't like the macro based solutions for iterative search from other programs.

EDIT: because I dislike macros in general and try to minimize their use. I also dislike a huge case switch. The latter was fine for qsearch, but as a case switch cannot jump into the middle of loops, it requires ugly adaptions of the code.

I thought quite a long time, how to write a readable iterative search. I found a macro free solution. The price are - gotos. I hadn't used goto since my youth with C64 BASIC (not counting jumping out of nested loops) but for an iterative search I found gotos really useful.

Search looks like this:

Code:


namespace Label
{
  enum _ {after_scout, after_research, ...};
}

class Node
{
  int alpha, beta;
  Move move;
  MoveList moves;
  int value;
  Label::_ ret_addr;
}; 

search ()
{
  Node* node = &d_nodes[0];
  Node* child = node+1;

recurse:
  node->moves.init();
  while ((node->move = node->moves.next()))
  {
    child->alpha = ...
    child->beta = ...
    child->ret_addr = Label::after_scout;
    ++node;
    ++child;
    goto recurse;
    // when we return here, node and child have their original values
    // and child is evaluated   
after_scout:
    if (child->value < -node->alpha)
    {
      child->alpha = ...
      child->beta = ...
      child->ret_addr = Label::after_research;
      ++node
      ++child;
      goto recurse;
    after_research:
      ...
    }
    if (cutoff)
    {
      node->value = ...
      goto node_done;
    }
  }
node_done:
  --node;
  --child;
  switch (node->ret_addr)
  {
    case Label after_research:
      goto after_research;
    ...
  }
}


Using gcc enhancements of C++ or using inline assembly in msvc, it is possible to store the address of the lables rather then the enum. This saves the switch at the end, one can directly jump to the label. However I found the inline assembly based solution in msvc slower then with the case switch. Also I could not find a way to port to 64 bit in msvc. So I decided to stay in the C++ standard and have the case switch.
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
DTS Structure Edmund Moshammer Fri May 28, 2010 8:29 am
      Re: DTS Structure liuzy Fri May 28, 2010 11:30 am
            Re: DTS Structure Edmund Moshammer Fri May 28, 2010 7:21 pm
      Re: DTS Structure Zach Wegner Fri May 28, 2010 2:44 pm
            Re: DTS Structure Edmund Moshammer Fri May 28, 2010 7:27 pm
      Re: DTS Structure Onno Garms Fri May 28, 2010 10:27 pm
            Re: DTS Structure Onno Garms Fri May 28, 2010 10:49 pm
            Re: DTS Structure Edmund Moshammer Fri May 28, 2010 11:05 pm
                  Re: DTS Structure Dann Corbit Sat May 29, 2010 12:17 am
            Re: DTS Structure Zach Wegner Sat May 29, 2010 1:49 am
                  Re: DTS Structure Onno Garms Sat May 29, 2010 7:48 am
      Re: DTS Structure Lance Perkins Sat May 29, 2010 4:26 am
            Re: DTS Structure Robert Hyatt Sat May 29, 2010 5:11 am
                  Re: DTS Structure Onno Garms Sat May 29, 2010 7:33 am
                        Re: DTS Structure Robert Hyatt Sat May 29, 2010 4:36 pm
                              Re: DTS Structure Onno Garms Sun May 30, 2010 8:35 am
                                    Re: DTS Structure Robert Hyatt Sun May 30, 2010 4:57 pm
                                          Re: DTS Structure Joona Kiiski Sun May 30, 2010 7:08 pm
                                                Re: DTS Structure Robert Hyatt Sun May 30, 2010 8:28 pm
                                                      Re: DTS Structure Edmund Moshammer Sun May 30, 2010 9:39 pm
                                                            Re: DTS Structure Robert Hyatt Mon May 31, 2010 12:25 am
                                                                  Re: DTS Structure Edmund Moshammer Mon May 31, 2010 8:17 am
                                                                        Re: DTS Structure Robert Hyatt Mon May 31, 2010 2:47 pm
                                                                              Re: DTS Structure Edmund Moshammer Mon May 31, 2010 2:56 pm
                                                                                    Re: DTS Structure Robert Hyatt Mon May 31, 2010 9:24 pm
                                                      Re: DTS Structure Onno Garms Mon May 31, 2010 5:00 pm
                                                            Re: DTS Structure Robert Hyatt Mon May 31, 2010 9:25 pm
                                                      Re: DTS Structure Marco Costalba Mon May 31, 2010 5:10 pm
                                                            Re: DTS Structure Nils Magnusson Mon May 31, 2010 6:07 pm
                                                                  Re: DTS Structure Gregory Strong Mon May 31, 2010 7:41 pm
                                                            Re: DTS Structure Robert Hyatt Mon May 31, 2010 9:28 pm
                                                                  Re: DTS Structure Marco Costalba Tue Jun 01, 2010 4:57 am
                                                                        Re: DTS Structure Robert Hyatt Tue Jun 01, 2010 2:01 pm
                                                                              Re: DTS Structure Robert Hyatt Tue Jun 01, 2010 2:40 pm
                                                                              Re: DTS Structure Sam Hamilton Tue Jun 01, 2010 2:52 pm
                                                                                    Re: DTS Structure Robert Hyatt Tue Jun 01, 2010 3:02 pm
                                          Re: DTS Structure Onno Garms Mon May 31, 2010 4:47 pm
                                                Re: DTS Structure Robert Hyatt Mon May 31, 2010 9:30 pm
            Re: DTS Structure Edmund Moshammer Sat May 29, 2010 7:43 am
                  Re: DTS Structure Onno Garms Sat May 29, 2010 8:09 am
                        Re: DTS Structure Edmund Moshammer Sat May 29, 2010 8:20 am
                              Re: DTS Structure Robert Hyatt Sat May 29, 2010 4:40 pm
                        Re: DTS Structure Robert Hyatt Sat May 29, 2010 4:39 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads