Selection in Monte Carlo Alpha-Beta

[dangi12012]

HINT

Code: Select all

child_value/child_visits + sqrt(2log(parent_visits)/child_visits)

==

child_value/child_visits + C * inv_sqrt(child_visits/log2(parent_visits))

where C is the amalgation of adjusting the ln together with the free parameter of ucb1.

Also dont do the first term in integers. Cast to float before! Integer division is much slower than float and the + will cast it to float anyway.

Later advanced hint:

Code: Select all

(AVX1) _mm256_rsqrt_ps
(unfortunately avx512) _mm256_lzcnt_epi64 

To find the best UCB1 value you can use _mm256_cmpgt_epi64 + mask.

So you can calculate + compare 8 ucb1 values at once in a few instructions.
But keep the hardcore optimisation for when your search is good and everything works
No paper on the topic uses this as far as I have seen. Leaving performance on the table.

I am not built that way. When I see the optimum is not reached I will optimize more. Letting me take 2 years for a movegen alone... Not recommended.

[RedBedHed]

I recently switched to 2-ply Alpha-Beta searches. I am finding that the Alpha-Beta searches are much better at estimating win probabilities. The Alpha-Beta searches also help my MCTS pick up on subtle tactics that it missed before.

Apparently Kommodo Dragon's MCTS mode is doing it like that, too: https://youtu.be/JUQoSVqiavw?t=1689

This is so cool! Thank you for the link! I wish the code wasn't proprietary. *sigh*