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):
Another quick simple visualization of search trees
Moderators: hgm, Rebel, chrisw
-
- Posts: 252
- Joined: Wed Jun 16, 2021 2:08 am
- Location: Berlin
- Full name: Jost Triller
-
- Posts: 1499
- Joined: Wed Apr 21, 2010 4:58 am
- Location: Australia
- Full name: Nguyen Hong Pham
Re: Another quick simple visualization of search trees
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
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
https://banksiagui.com
The most features chess GUI, based on opensource Banksia - the chess tournament manager
The most features chess GUI, based on opensource Banksia - the chess tournament manager
-
- Posts: 1062
- Joined: Tue Apr 28, 2020 10:03 pm
- Full name: Daniel Infuehr
Re: Another quick simple visualization of search trees
Awesome!
Can you change the color of a line according to the score of the node?
So bad = red, good = green
Can you change the color of a line according to the score of the node?
So bad = red, good = green
Worlds-fastest-Bitboard-Chess-Movegenerator
Daniel Inführ - Software Developer
Daniel Inführ - Software Developer
-
- Posts: 881
- Joined: Sun Dec 27, 2020 2:40 am
- Location: Bremen, Germany
- Full name: Thomas Jahn
Re: Another quick simple visualization of search trees
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.
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.
-
- Posts: 252
- Joined: Wed Jun 16, 2021 2:08 am
- Location: Berlin
- Full name: Jost Triller
Re: Another quick simple visualization of search trees
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.
So unfortunately I don't have much control over how this looks.
-
- Posts: 1062
- Joined: Tue Apr 28, 2020 10:03 pm
- Full name: Daniel Infuehr
Re: Another quick simple visualization of search trees
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
Worlds-fastest-Bitboard-Chess-Movegenerator
Daniel Inführ - Software Developer
Daniel Inführ - Software Developer
-
- Posts: 252
- Joined: Wed Jun 16, 2021 2:08 am
- Location: Berlin
- Full name: Jost Triller
Re: Another quick simple visualization of search trees
I don't think that's possible beyond depth 1, because UCI doesn't provide any introspective into the engine's search.dangi12012 wrote: ↑Wed Jun 08, 2022 8:59 pm I kind of want a UCI adapter that can output that graph for any uci engine from the Multi-PV score now
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);
...
}
...
}
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
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 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))
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]
...
I believe, this way, the ordering how the moves were searched is from right to left. It would look roughly like this:
-
- Posts: 7
- Joined: Sun Jul 03, 2022 10:39 pm
- Full name: Rayleigh Langhoff
Re: Another quick simple visualization of search trees
This says "another" - where did you find other things like this? I can't find them
-
- Posts: 252
- Joined: Wed Jun 16, 2021 2:08 am
- Location: Berlin
- Full name: Jost Triller
Re: Another quick simple visualization of search trees
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.
-
- Posts: 252
- Joined: Wed Jun 16, 2021 2:08 am
- Location: Berlin
- Full name: Jost Triller
Re: Another quick simple visualization of search trees
Unfortunately, I found a bug in above python code. Here it is fixed:
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).
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")
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).