Scaling up

[arr28]

How can we make Sancho scale better?

(For post-IGGP15)

Multi-core performance

Having a single game searcher thread causes a bottleneck and caps performance in most games.

• How do we measure our scalability? (Probably by enhancing the game searcher variant of the performance test to ramp up the number of cores in use, taking a measurement at each setting, and then plotting the results.)

• 315 pushes some work from the game searcher to rollout threads. Fairly safe and likely to have good bang for buck.

• 178 asks the general question of "What keeps the game searcher busy?". That's a good vehicle for finding more things like #315.

More generally though, would we benefit from moving to a symmetric threading model? Obviously, it would require careful locking consideration. Would the consequent locking kill us? Either from a performance perspective or from a maintainability perspective?

Distributed computation

If we could co-opt several machines, how might we take advantage of them?

Organisation

Obviously, we'd need a single p.o.c. for the Tiltyard/Gamemaster to connect to. But that could potentially farm out work to other machines.

(Since the p.o.c. would need to be accessible to the internet anyway, the other machines could connect to it. That would also allow us to use horsepower from NAT'd systems. I could well imagine getting permission to borrow some big iron for competitions.)

Task splitting

How do we split the work? I definitely need to re-read the various papers on distributed MCTS. But even if we can't sensibly leverage distributed MCTS, what other tasks could be distributed?

• Local search
• Latch re-analysis (as the game progresses) - e.g. once you've taken a corner in Reversi, the adjacent cells are positive latches
• Propnet pruning? Should significantly reduce propnet size in games w/ Pie.
• Fast depth-first minimax search w/ alpha-beta pruning - i.e. attempt to brute force the current position. Wouldn't need to do any node allocation.
• ...?

  Safety

To avoid issues if we lost connectivity to other machines in the cluster, the p.o.c. node would also need run "as normal", so that it could use its own local data to submit results if it didn't get the necessary responses.

[SteveDraper]

Unless we were trying to go for massively scalable distribution I wouldn't necessary try to distribute MCTS search symmetrically. I would probably enhance local search and distribute THAT, using its results (which only require low bandwidth and low latency comms) to modify selection probabilities in the master MCTS expansion. For MODEST distributed scaling (up to O(10s) machines I think this would probably work better than trying to distribute the MCTS tree itself.