Emulating an arbitrarily difficult gametree

[dangi12012]

Simple question:
I dont want to explore a tree of games or chess position with known good moves - but I am looking for an algorithm that can generate hard trees on its own.
Search algos deal with imperfect eval() data at so I would like to have a mocked eval() value that can simulate these things:

Random trees that skew towards losing or winning generally
Distributed in that tree should be moves that look good (high eval()) but turn out to be bad in the long run
Distributed in that tree should be moves that look neutral (not the highest eval) but turn out to be the best in the long run.
Forced wins that are N plies deep.
Horizon effect: Alphabeta(8) clearly winning - Alphabeta(9) clearly losing

In summary an algorithm that can generate a gametree of arbitrary difficulty and arbitrary depth and arbitrary branching factor (within memory limits)
For example a tree where the first 6 plies are more or less neutral - but after 6 plies there are 20 ply poisoned moves that need to be avoided and 1 forcing win in there somewhere.

How would one achieve this?

[Mike Sherwin]

A material search only that keeps track of statistics for each side for each root move.

1. number of moves for each side
2. number of checkmates for each side
3. number of beta cutoffs
4. number of failed null moves

And whatever else that can be thought of. I'd start with just checkmates. Create two ratios w#cm/w#m - b#cm/b#m and then convert that to some amount of material value to add or subtract from the root move.

[dangi12012]

The answer will be an algorithm that spits out a tree:

Code: Select all

struct Node
{
    Node* Parent;
    Node* Children;
    int NChildren;
    int eval;
}

Where eval is filled in such a way to fullfil above requirements when searched. A poisoned position would look good with negamax(8) and bad with (12).

[hgm]

For a given depth you can start with a PV, and assign it the score you want in the end leaf. You can then built a refutation tree (of alternating cut-nodes and all nodes) by generating only a single move in the cut-nodes (the cut-move), and assign all the leaves a score better (for the side playing the cut-moves) than the PV score. You can then go back to the cut-nodes, and generate trees from them through their other moves with totally random leaf evaluation.

If you want a tree with a poisoned move, that looks best on d=N, and is bad on d=N+1, you first generate the d=N tree according to the above recipe, and from the former leaf add moves that lead to new leaves with the bad score. Since you will be extending all branches by one ply, all leaves will be new. You can just randomly designate one of the (extended) other branches as the new PV, and repeat the procedure.

[dangi12012]

For a given depth you can start with a PV, and assign it the score you want in the end leaf. You can then built a refutation tree (of alternating cut-nodes and all nodes) by generating only a single move in the cut-nodes (the cut-move), and assign all the leaves a score better (for the side playing the cut-moves) than the PV score. You can then go back to the cut-nodes, and generate trees from them through their other moves with totally random leaf evaluation.

I have literally no idea what any of this means.
Could you post you idea in pseudocode? (english leaves too much for interpretation imho)

[hgm]

It is somewhat hard to express this in something as exact as pseudo-code. Because hwat you request is rather vague. A game tree can be characterized by many parameters. Even for just the topology (i.e. not looking at scores) you can have any distribution of the number of daughters. And such a distribution can be homogeneous throughout the tree, or slowly varying through some 'inheritance with mutation' scheme. (E.g. in chess you can start with 30 moves/position in the root, which drops to 10 in subtrees where one converts to a pawn ending, and within some nodes of the latter jumps back up to 40 after a promotion.)

Code: Select all

Tree(depth, score, bound)
{
  if(depth == 0) {
    switch(bound) {
      case EXACT: return score;
      case UPPER: return score - 1;
      case LOWER: return score + 1;
      case ANY: return randomScore();
    }
  } else {
    n = N; // desired number of children
    switch(bound) {
      case EXACT: // PV node
        Tree(depth-1, -score, EXACT); n--; // one PV child
        children = LOWER; // other moves are refuted, i.e. lead to cut-nodes
        break;
      case LOWER: // cut-node
        Tree(dept-1, -score, UPPER); n--; // one cut-move
        children = ANY; // the other children are irrelevant
        break;
      case UPPER: // all-node
        children = LOWER; // all children are cut-nodes
        break;
      case ANY: // unspecified node type
        children = ANY;
    }
    while(n-- > 0) {
      Tree(depth-1, -score, children);
    }
    
  }
}

The above routine would walk a tree of fixed depth with fixed branching ratio, and a non-degenerate PV where any deviation at least scores 1 point worse.