On internal iterative deeping

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 6:31 pm
Location: Bonn, Germany

Re: On internal iterative deeping

Post by Onno Garms » Thu Mar 17, 2011 8:02 pm

UncombedCoconut wrote:A little off-topic: I've never seen this Label:: syntax before. Is this a local struct you defined at the start of the function and populated with the GCC (or ICC) && operator? Or is it an actual language extension (or pseudocode)?
This is actual ISO-C++-code from the Onno sources, my personal enum syntax.

I couldn't find an equivalent for the && operator in MSVC for 64 bit. In MSVC for 32 bit you can use inline assembly to implement your && operator, but it seemed that the compiler could not optimize that well. As I wrote, there is a case switch at the end.

Code: Select all

class Label
{
public:
  enum _
  {
    after_bad_pruning,
    after_null_search,
  };
}
namespace instead of class might be cleaner. Some labes skipped.

Code: Select all

node_done:
  // return to parent node
  --node;
  --child;
  switch (child->ret_addr)
  {
  case Label::after_bad_pruning:
    goto after_bad_pruning;
  case Label::after_null_search:
    goto after_null_search;
  }

User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 6:31 pm
Location: Bonn, Germany

Re: On internal iterative deeping

Post by Onno Garms » Thu Mar 17, 2011 8:46 pm

Don wrote: It's unclear to me what these "known" schemes are, as there is ambiguity about how to define these node types.
I know that there are slight differences in the node type schemes. Actually I never formalized my scheme. I have to go through my sources to extract an exact definition. I will do so later.

I did not address the node scheme in optimization of my engine. I would not assume that the details matter too much, but you never know.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: On internal iterative deeping

Post by Don » Thu Mar 17, 2011 9:15 pm

Onno Garms wrote:
Don wrote: It's unclear to me what these "known" schemes are, as there is ambiguity about how to define these node types.
I know that there are slight differences in the node type schemes. Actually I never formalized my scheme. I have to go through my sources to extract an exact definition. I will do so later.

I did not address the node scheme in optimization of my engine. I would not assume that the details matter too much, but you never know.
There is some common sense stuff, such as promoting a cut node to an all node if the first N moves does not produce a cutoff. N might be 1 or 2 or be based more on the type of moves near the front of the list.

Don

User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 6:31 pm
Location: Bonn, Germany

Re: On internal iterative deeping

Post by Onno Garms » Thu Mar 17, 2011 9:20 pm

Don wrote: So what is your exact definition? What are others using?
Don't know what exactly others use. Some seem to change the type of a node, e.g. the rules quoted by you or Fruit. I never change the type of a node once it is assigned.

Basically, CUT nodes are those where I expect a failhigh, so that I need not search all children. ALL nodes are nodes where I expect to have to search all children.

When talking of node types, a node is defined by a jump to recurse, even if no move is made. In this case, I have Move::none which differs from Move::null. (However, for nps, I count do_move()). This means that when you do iid or bad pruning, you create a child without brothers.

The root node is a PV node.
The first child of a PV node is a PV node.
The further children are searched by a scout search as CUT nodes.
Research is done as PV nodes.

The first node of bad pruning is a CUT node.
The node after a null move is a CUT node.
The first node of null move verification is a CUT node
Internal iterative deeping does not change the node type.
The first child of a CUT node is an ALL node.
Further children of a CUT node are CUT nodes.
Children of ALL nodes are CUT nodes.

Hope I have found all node type assignments.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: On internal iterative deeping

Post by Don » Thu Mar 17, 2011 9:29 pm

Onno Garms wrote:
Don wrote: So what is your exact definition? What are others using?
Don't know what exactly others use. Some seem to change the type of a node, e.g. the rules quoted by you or Fruit. I never change the type of a node once it is assigned.

Basically, CUT nodes are those where I expect a failhigh, so that I need not search all children. ALL nodes are nodes where I expect to have to search all children.

When talking of node types, a node is defined by a jump to recurse, even if no move is made. In this case, I have Move::none which differs from Move::null. (However, for nps, I count do_move()). This means that when you do iid or bad pruning, you create a child without brothers.

The root node is a PV node.
The first child of a PV node is a PV node.
The further children are searched by a scout search as CUT nodes.
Research is done as PV nodes.

The first node of bad pruning is a CUT node.
The node after a null move is a CUT node.
The first node of null move verification is a CUT node
Internal iterative deeping does not change the node type.
The first child of a CUT node is an ALL node.
Further children of a CUT node are CUT nodes.
Children of ALL nodes are CUT nodes.

Hope I have found all node type assignments.
Thanks for the information - gives me something ponder!

Don

Post Reply