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

Так вышло, что для получение автомата по программированию бедным первокурам задали одну интересную задачу: написать программу, которая ищет по дереву методом Монте-Карло.

Конечно, всё началось с поиска информации в интернете. На великом и могучем русском языке было всего-лишь пара статей с Хабра, словесно объясняющие суть алгоритма, и статья из Википедии, перенаправляющая на проблему игры Го и компьютера. По мне — уже неплохое начало. Гуглю на английском языке для полноты и натыкаюсь на английскую статью с Википедии, в которой алгоритм так же словесно объясняется.

Немного теории

Метод Монте-Карло для поиска по дереву достаточно давно применяется в играх для искусственного интеллекта. Задача алгоритма — выбрать наиболее выигрышный вариант развития событий. Дерево представляет из себя структуру, в которой помимо хода и указателей есть количество сыгранных и количество выигранных партий. На основе этих двух параметров метод выбирает следующий шаг. Следующее изображение наглядно продемонстрирует работу алгоритма: