Метод Монте-Карло для поиска в дереве

Метод Монте-Карло это алгоритм принятия решений, часто используемый в играх в качестве основы искусственного интеллекта. Сильное влияние он оказал на программы для игры в Го, хотя находит свое применение и в других играх, как настольных, так и обычных компьютерных (например Total War: Rome II). Так же, стоит отметить, что метод Монте-Карло используется в нашумевшей программе AlphaGo, победившей го-профессионала 9-го дана Ли Седоля в серии из 5 игр.

В данной статье хотелось бы рассказать про версию алгоритма Монте-Карло под названием Upper Confidence bound applied to Trees (UCT). Именно после публикации этого алгоритма в 2006-м году, программы для игры в Го сильно усилили свои позиции и достигли значительных успехов в игре против человека.