Neural network evaluation for a Monte Carlo Tree Search engine

[OWL]

I haven't tested it, so do take this with a grain of salt - but it instinctually feels like that storing children contiguously doesn't seem like a good idea - you need to find large-enough "gaps" in your array which might result in wasted memory and slow allocations.

Another idea would be to have each node in the array contain an index of its rightmost "sibling," as well as its' leftmost children. almost like a linked-list. That way you could follow the pointers to find all of the children of its node. Most of the time when you allocate the nodes it would be fairly close, I'd imagine, so it doesn't have that much extra overhead while searching, but allows for faster allocations and fewer unused slots in the table.

I'd imagine this approach would also work for edges. Again, I haven't tested this, so do take this with a grain of salt.

It is a neat idea to store the left and right most sibling. However I dont delete nodes so I wont create any holes. So when I expand a node the first free spot is at the back of the array, therefore I wont have any gaps.

[dangi12012]

It is a neat idea to store the left and right most sibling. However I dont delete nodes so I wont create any holes. So when I expand a node the first free spot is at the back of the array, therefore I wont have any gaps.

You will have to solve defragmentation when this is an actual engine - as on opponent move you will have to delete all not taken nodes from the tree (so you get a new root and forget all other paths). This is actually one of the biggest strengths of MCTS - as you can just continue searching from the new position and dont have to have the intermediate and very indirect Hashtable between your nodes and your scores.

One way to solve this is to do overprovision for most children and have only 8,16,32,64,128 nodes and pack them accordingly.
Also I have solved most memory related stuff and one cool side effect of continuous memory is that you can store your pointers as 32 or 48 bits and use the other bits for free which saves a lot of memory once you have billions of nodes.

But yeah the goal for MCTS is 1 Billion nps per core which is very doable when you do full playouts. (But since you want to have a smart agent at the leafes that supports noisy playouts there are a lot of open points that need solving)

[AAce3]

It is a neat idea to store the left and right most sibling. However I dont delete nodes so I wont create any holes. So when I expand a node the first free spot is at the back of the array, therefore I wont have any gaps.

You will have to solve defragmentation when this is an actual engine - as on opponent move you will have to delete all not taken nodes from the tree (so you get a new root and forget all other paths). This is actually one of the biggest strengths of MCTS - as you can just continue searching from the new position and dont have to have the intermediate and very indirect Hashtable between your nodes and your scores.

One way to solve this is to do overprovision for most children and have only 8,16,32,64,128 nodes and pack them accordingly.
Also I have solved most memory related stuff and one cool side effect of continuous memory is that you can store your pointers as 32 or 48 bits and use the other bits for free which saves a lot of memory once you have billions of nodes.

But yeah the goal for MCTS is 1 Billion nps per core which is very doable when you do full playouts. (But since you want to have a smart agent at the leafes that supports noisy playouts there are a lot of open points that need solving)

Wow, 1 billion nps is a lot . Are you counting playout positions as nodes?

Also, I'm really curious as to how overprovision would work. Have you run into issues with 'wasted' memory? Or is it so little that it hardly ever matters?

Definitely use 32-bit pointers. I did some calculations and there's really very few circumstances where you'd ever need more. (Unless you're running it on TCEC hardware).

I'm currently writing up an engine (it's in very early developmental phase) in rust but my current plan is to use MCTS with alpha-beta pruning instead of playouts. Maybe it'll produce good results (hopefully ).

Definitely you do want to keep the hash tree in memory, OWL. Most MCTS engines have a garbage collection thread that clears out useless nodes when moves are made, and this actually simplifies a lot of things.