Another quick simple visualization of search trees

[j.t.]

I made some visualizations for Nalwalds search. All of them are depth 4 searches of the following random position (using iterative deepening information and check extensions).

[fen]r4rk1/1p1n1qpb/p1p1pbnp/P2p4/R1PP4/1N1BBN2/1PQ2PPP/4R1K1 b - - 5 17[/fen]


Thought it might be interesting.

Pure Minimax:

Alpha-Beta + move ordering (using SEE, history heuristics, hash table, killers):

Normal search (Nalwald):

[phhnguyen]

Very creative!!!

I have been managing to display some trees (in Banksia GUI) and know how hard it (displaying) is for correctness and beautifulness. Look like you can do both

[dangi12012]

Awesome!

Can you change the color of a line according to the score of the node?
So bad = red, good = green

[lithander]

Is the fanning out of moves in any specific order? It could be cool to have that sorted in the way the engine would play the moves so that you can see how late-move reductions is reducing the later (e.g. more clockwise) branches.

Also if you have more branches than pixels sometimes using alpha-blending looks pretty cool so that you can actually see how much overdraw there is!

...I love that kind of stuff.

[j.t.]

To be honest, this was all just a pretty hacky attempt to visualize this stuff. I only chose this radial style, because otherwise Graphviz (the tool I used, I don't really know how to do these kinds of graphics myself) would insist on leaving a non-zero amount of space (more than 0.02 of some unit) between nodes, such that a normal tree visualization would look very, very wide at the bottom with the amount of nodes we're talking about here.

So unfortunately I don't have much control over how this looks.

[dangi12012]

To be honest, this was all just a pretty hacky attempt to visualize this stuff.

You know the biggest projects ever were started that way - Javascript was a quick 10 day hack to get stuff done. And now the web practically runs off it.

I really like your idea - it looks so cool! I kind of want a UCI adapter that can output that graph for any uci engine from the Multi-PV score now

[j.t.]

I kind of want a UCI adapter that can output that graph for any uci engine from the Multi-PV score now

I don't think that's possible beyond depth 1, because UCI doesn't provide any introspective into the engine's search.

But I'll share what I did, because it should be quite simple to do this for any other engine if you have access to the source code.

What you need to do first is to add a line to the search of the engine, that prints out the height of each node that gets entered (I only did regular search, but could probably also work with quiesce). So like this:

Code: Select all

int alphaBeta(int alpha, const int beta, const int depth, const int height) {
   std::cout << height << std::endl; // <----- print out height
   if (depth <= 0) return quiesce(alpha, beta);
   for (all moves)  {
      // important, height must be increased by exactly one with each recursive call
      score = -alphaBeta(-beta, -alpha, depth - 1, height + 1);
      ...
   }
   ...
}

Then when you run your engine to a fixed depth, you should probably get output like this:

Code: Select all

0
1
...
1
info depth 1 time 0 nodes 19 nps 19000 hashfull 0 score cp 0 pv c2c3 
0
1
2
...
1
1
info depth 2 time 0 nodes 41 nps 41000 hashfull 0 score cp 21 pv c2c3 c7c6
0 // copy this bit
1 // copy this bit
2 // copy this bit
3 // copy this bit
3 // copy this bit
... // copy this bit
1 // copy this bit
1 // copy this bit
1 // copy this bit
1 // copy this bit
1 // copy this bit
info depth 3 time 2 nodes 263 nps 87000 hashfull 0 score cp 11 pv c2c3 d7d5 d2d4 
bestmove c2c3

The part I labeled with "copy this bit" (i.e. the height numbers from the last iterative search) should be copied to a new text file called "myTreeNumbers.txt".

Then you run this python script, which creates a .dot file:

Code: Select all

from treelib import Node, Tree

filename = "myTreeNumbers.txt"
    
with open(filename, 'r') as f:
    data = f.read()
    myNumbers = [int(i) for i in data.split()]

tree = Tree()
root = tree.create_node(tag = 0)

index = 1

def addNode(height, parent):
    global index
    assert myNumbers[index] == height

    while myNumbers[index] >= height:
        if myNumbers[index] == height:
            if index % 100000 == 0:
                print(index)
            current = tree.create_node(tag=height, parent=parent)
            index += 1
        if index >= len(myNumbers):
            return
        if myNumbers[index] > height:
            addNode(height + 1, current)
        if index >= len(myNumbers):
            return
    
    assert myNumbers[index] < height

addNode(1, root)

tree.to_graphviz(filename="myTree.dot", shape="point", graph="graph")

You need to install treelib for that ("pip install treelib") and also fix a bug in the function "to_graphviz" (it's in the file "/home/username/.local/lib/python3.10/site-packages/treelib/tree.py" at least on my machine).

You need to replace line 999 like this:

Code: Select all

// from this:
connections.append('"{0}" -> "{1}"'.format(nid, cid))

// to this:
edgeop = '->' if graph == 'digraph' else '--'
connections.append(('"{0}" ' + edgeop + ' "{1}"').format(nid, cid))

The last function "to_graphviz" takes ages when many nodes are involved. For the pure minimax example, roughly ~2 Million nodes had to be handled, and it took 12 hours. I even started writing my own tool, but the python script finished before I was done, so I didn't bother continuing it.

Anyway. The resulting file "myTree.dot" can be converted to an image using some tools from the Graphviz package.
For example to get this radial design, you need to run the command "twopi -Tpng myTree.dot -o myTree.png". If you want to have a traditional tree visualization (works only well for when having not more than a few hundred nodes), then you first should add "nodesep=0.02;" between the first and second line of the myTree.dot file, e.g.:

Code: Select all

// from this:
graph tree {
	"cb3be914-e8ab-11ec-b199-f859716de58e" [label="0", shape=point]
	"cb3beab8-e8ab-11ec-b199-f859716de58e" [label="1", shape=point]
	...
// to this:
graph tree {
	nodesep=0.02;
	"cb3be914-e8ab-11ec-b199-f859716de58e" [label="0", shape=point]
	"cb3beab8-e8ab-11ec-b199-f859716de58e" [label="1", shape=point]
	...

Then run the command "dot -Tpng myTree.dot -o myTree.png"

I believe, this way, the ordering how the moves were searched is from right to left. It would look roughly like this:

[RayLeeIsmay]

This says "another" - where did you find other things like this? I can't find them

[j.t.]

I didn't have something specific in mind, I just remembered that I saw something in this direction before, for example here. I also thought that I saw a similar post, this or last year here on the forums, but I'm not 100% sure now.

[j.t.]

Unfortunately, I found a bug in above python code. Here it is fixed:

Code: Select all

from treelib import Node, Tree

filename = "myTreeNumbers.txt"
    
with open(filename, 'r') as f:
    data = f.read()
    myNumbers = [int(i) for i in data.split()]

tree = Tree()
root = tree.create_node(tag = 0)

index = 0

print("myNumbers:", len(myNumbers))

def addNode(height, parent):
    global index
    assert myNumbers[index] == height

    while myNumbers[index] >= height:
        if myNumbers[index] == height:
            current = tree.create_node(tag=height, parent=parent)
            print("Created node:", index, height)
            index += 1
        if index >= len(myNumbers):
            print("Returning node:", index)
            return
        if myNumbers[index] > height:
            addNode(height + 1, current)
        if index >= len(myNumbers):
            print("Returning node:", index)
            return
    
    assert myNumbers[index] < height

addNode(0, root)

tree.to_graphviz(filename="myTree.dot", shape="point", graph="graph")

The current Nalwald version looks now like this:



And for Ataxx (a different game for which I have an engine too: Moonbird):


Here I went to depth 12, since the effective branching factor of the search is much lower (even though I think in the game, the number of moves per position is no much lower than in chess).