Some Experiments and Questions on lc3-style Stream MCTS

[zyk17]

Hi,

I’ve learned a lot of interesting things about chess-engine design from your project, so first of all, thank you for sharing it.

Recently, based on ideas from lc3 and this project, I built an MCTS + NN Chinese chess engine called X7:

https://github.com/zyk17/x7

During the implementation, I made a few choices that are slightly different from lc3, and I also ran into some interesting behaviors that I wanted to share and ask about.

lc3 / concurrency architecture

For node storage, I did not use the flat_map approach you mentioned. Instead, I use an arena, mainly to make node access/allocation cheaper.

For the NN pipeline, I use:

• one persistent NN worker
• a dynamic number of Gather workers
• a dynamic number of Eval workers
• a dynamic number of Backprop workers

So the whole search behaves like a continuously running Stream MCTS pipeline.

Skipping terminal nodes

I also handle terminal nodes a little differently.

When select/gather reaches a node that has already been confirmed as terminal, I do not keep treating it like a normal searchable leaf and repeatedly backpropagate through it. Instead, I skip it and continue looking for a non-terminal sibling.

There are mainly two reasons for this.

First, I do not want already-known win/loss results to keep interfering with normal PUCT selection.

Once a terminal result is known, repeatedly selecting that same branch and accumulating more visits/backprops would allow a solved branch to keep affecting the competition between sibling edges. I prefer to treat the terminal result as already-known information rather than something that should continue consuming search budget.

Second, this does not risk missing terminal branches.

Once a terminal node is discovered, it is permanently marked as terminal. Future selections can identify it immediately and skip it. As more terminal children become marked, search naturally moves toward the remaining non-terminal siblings. If eventually all relevant children are terminal, then the parent can also become resolved.

So conceptually, terminal nodes are removed from ordinary MCTS sampling once their result is known.

MCTS

Because the implementation is based on lc3-style Stream MCTS, I currently do not use Multi-Visit.

Collision and virtual loss

For collisions / virtual loss, I currently use a relatively mild form of mean virtual loss.

The virtual Q is:

q_virtual =
    (q * n_complete
     + VirtualMeanFpuScale * fpu * n_inflight)
    / n_started

with:

n_started = n_complete + n_inflight

The intuition is that, as more inflight visits accumulate on the same edge, q_virtual gradually moves from the current q_mean toward FPU, instead of applying a fixed negative virtual loss.

This reduces the attractiveness of the edge in PUCT relatively smoothly and encourages other workers to spread out.

So far this has worked reasonably well for me, so I have not implemented cache-only prefetch.

An interesting effect of nn_window

One thing I found especially interesting in lc3-style Stream MCTS is nn_window.

My understanding is that its primary purpose is to control when Gather should stop running ahead of NN/backprop, but it also seems to have a side effect: it can change the shape of the search tree.

Roughly:

larger nn_window
    -> easier to accumulate larger NN batches
    -> but selection uses older statistics

smaller nn_window
    -> selection sees fresher backprop results
    -> but batching becomes harder

There is another detail here that I found interesting.

In my implementation, completed virtual loss / virtual visits are removed after backprop.

So inside a larger nn_window:

• visits that have already completed NN + backprop no longer carry virtual loss
• visits that are still waiting for NN evaluation still carry virtual loss

This means that visits inside the same pipeline window are effectively in different search states.

Because of that, nn_window seems to influence more than batching efficiency. Through the lifetime of virtual loss, it can also change later PUCT decisions and therefore the resulting tree shape.

Have you observed something similar in lc3?

Variance bonus

I have also been experimenting with a simple variance bonus:

PUCT = Q_mean + U + B_var

where:

B_var = lambda * SE

SE = sqrt(variance / n_complete)

I intentionally use the standard error here rather than the standard deviation.

Therefore, as:

n_complete -> infinity

we get:

B_var -> 0

So this term does not permanently change the value of an edge. It only gives temporary extra search budget to nodes whose value samples currently disagree significantly while the sample count is still relatively small.

I think of it as a kind of temporary verification bonus:

if the evidence collected for an edge is still inconsistent, then its current Q may not be reliable enough, so it may deserve some additional verification. As visits increase, that bonus naturally disappears.

I am still testing how much this actually helps the search tree and Elo.

Neural network

On the NN side, I also made a few changes compared with a more standard AlphaZero-style target setup.

I train:

Final WDL
Root/Search WDL

separately.

The current setup is roughly:

Inference heads:
- Policy
- Final WDL

Auxiliary training heads:
- Root/Search WDL
- Soft Policy

I also added an Auxiliary Soft Policy target.

The idea is to let these auxiliary targets improve the shared representation using additional search information, while keeping the final inference interface relatively simple.

One more question: Loop / Recurrent Transformers

Recently I have also been interested in Loop / Recurrent Transformers.

The basic idea of using a relatively small model repeatedly, trading additional compute for parameter count, looks quite interesting to me.

Some recent work suggests that this kind of iterative computation can work especially well for mathematical or logical reasoning tasks.

So I am curious how you think this might translate to chess-like games.

For example:

larger one-pass Transformer

versus:

smaller Transformer
+ recurrent / loop computation

Do you think the latter could be especially suitable for board games, where local tactical relationships, exchanges, threats, and defensive interactions may benefit from iterative refinement?

Or, from your experience, do you think recurrent computation is unlikely to outperform simply making the Transformer wider/deeper for this type of NN?

Thanks again for the project and for sharing your work.