Research Notes + Reading List

I figure I might as well share some of the things I'm reading or watching that are relevant to the Puyo problem.

My "current reading list" has changed dramatically. A few months ago, I focused my research on OpenCL, but I am now focusing on a CPU-based agent.

APIs

* Extendable Storage Engine: https://msdn.microsoft.com/en-us/library/gg269259(v=exchg.10).aspx

* Reserving and Committing Memory: https://msdn.microsoft.com/en-us/library/windows/desktop/aa366803(v=vs.85).aspx

* YieldProcessor: https://msdn.microsoft.com/en-us/library/windows/desktop/ms687419(v=vs.85).aspx

For maximum reach, I am writing my bot in Win32, targeting Win7 and above. The ESE will provide me a concurrent file-format. I've written a custom memory management routine for my code (mostly because MCTS doesn't "delete" data until the end, at which point I can just "free" ALL the memory at once, or even just overwrite it with a new MCTS iteration).  

YieldProcessor / "Pause" Assembly instruction is important for spinlocks on SMT / Hyperthreaded systems. I wrote and tested my own spinlock, but I haven't quite gotten to use it yet. Mutexes are too slow for synchronization, Spinlock + Atomics ftw.

SPSA

* http://www.jhuapl.edu/spsa/

I'm slowly building up a number of parameters that I'll eventually need to optimize. Stochastic search is the study of optimizing these sorts of parameters. It seems like Stockfish uses SPSA to self-optimize itself.

I'll still need to build some kind of official testing framework and suite of benchmarks. For now, something like a 10,000 step single-player Puyo game is going to be the benchmark for the AI.

Multithreaded / Atomics 

* Every CPPCon talk by Pikus: https://www.youtube.com/watch?v=ZQFzMfHIxng

Pikus is an amazing speaker and explains "Atomics" exceptionally well. Above is a link to one of his 2017 talks, but I've watched all of them and understand multithreaded synchronization much better because of it.

* Another Pikus talk: https://www.youtube.com/watch?v=lVBvHbJsg5Y

* Herb Sutter's Atomic Weapons: https://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-1-of-2

MCTS

* https://arxiv.org/abs/1204.5721

The Multi-Armed Bandit Problem is the cornerstone of the UCT algorithm, a piece of the MCTS algorithm overall.

Optimization

* Agner Fog: http://www.agner.org/optimize/

* Intel Optimization guide: https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

Low-level optimization guides for optimizing L1 cache and CPU cycles. I've of course got some profiling tools (Visual Studio's profiler) which is guiding me primarily, but a solid theory on how modern CPUs work is necessary to optimize. I'm staying mostly higher-level.

* Chess Programming Wiki: https://chessprogramming.wikispaces.com/

The Chess Programming Wiki has a huge number of low-level bit-twiddling tricks

Offline Reading / Books

* The Art of Computer Programming -- Knuth's signature book. I've read through it before, but Chapter 2 has a very good review of tree representations and tree-algorithms. I've reread this section, since there's a lot of tree stuff in in MCTS... trees.