User talk:Kilgore T

Welcome!

Hello, Kilgore T, and welcome to Wikipedia! Thank you for your contributions. I hope you like the place and decide to stay. Here are a few links to pages you might find helpful:

You may also want to complete the Wikipedia Adventure, an interactive tour that will help you learn the basics of editing Wikipedia. You can visit the Teahouse to ask questions or seek help.

Please remember to sign your messages on talk pages by typing four tildes (~~~~); this will automatically insert your username and the date. If you need help, check out Wikipedia:Questions, ask me on my talk page, or ask for help on your talk page, and a volunteer should respond shortly. Again, welcome! RJFJR (talk) 15:01, 20 July 2018 (UTC)[reply]

Monte Carlo tree search

Kilgore T, in answer to your question, I think convergence is guaranteed for any finite game because after an infinite number of simulations the score of every possible move is "estimated" exactly, and matches the minimax value. Of course, this may not mean very much in practice for games like Go that have astronomical numbers of possible games. Servalo (talk) 16:05, 30 October 2018 (UTC)[reply]

Thank you for your answer. Like you said, and after studying a bit more the field I figured that the true minimax value is guaranteed to be reached only after an exponential amount of time. It is always possible to simulate UCB on completely known minimax trees, and in principle still get all the problems associated with minimax search, only worse since you need to hold all explored nodes in memory and you don't get the speedup of alpha-beta pruning. However, since many games have some underlying "structure" (correlation between moves and results), MCTS / UCB does actually perform better than the provable bound in practice. ̣Kilgore T (talk) 23:35, 9 November 2018 (UTC)[reply]