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

[gena_glot]

Почему вы не хотите сыграть на двух уровнях сразу? Или на трех. Вы же уже дерево «предварительное» имеете. Осталось сыграть. Вот и новый алгоритм-болгаритм.

[SeptiM]

Не пробовали к какой-нибудь пошаговой игрушке прикрутить?

[galvanom]

Если имеете в виду пошаговую игру типа Heroes of Might and Magic, то думаю, что не составит проблем использовать такой алгоритм в ней. Но я не пробовал =)

[SeptiM]

Я скорее про игрушки типа реверси, шашки, клоподавки и т.п. На самом деле может составить. У голых MCTS есть проблема с оценкой действий. Это дорого. Я пытался прикрутить их к войнам вирусов, и скажем так, они с большим трудом чуть-чуть отличались от рандома, при этом жрали секунды процессорного времени.

Я слышал, что в 2006 кто-то играл с ними в го и даже до какого-то дана дошел и все в режиме unsupervised learning. Но вот интересно, было ли у них обучение и какое? В голом MCTS его нет, значит, весь процесс принятия решений остается на момент обработки запроса. Т.е. интересно в первую очередь, что же там за эвристики сверху пилят.

[galvanom]

Вот ссылка на статью с описанием того как работает программа MoGo и собственно те эвристики, о которых вы интересуетесь. С нее в 2006-м и началось активное использование UCT в Го-программах. Про обучение там конечно ничего не сказано, но на эту тему есть наглядный пример — AlphaGo, информацию о том как эта программа устроена можно найти на хабре.

[BotCoder]

Перечитал с десяток раз и не понял один момент.

Третья фаза, симуляция. Из созданного на предыдущем этапе узла запускается игра со случайными или, в случае использования эвристик, не совсем случайными ходами. Игра идет до конца партии. Здесь важна только информация о победителе, оценка позиции не имеет значения.

Если это так, то единственное с чем мы оперируем, в дереве — количество побед в ветке и количество посещений а оценка позиции не рассматривается.

Далее вы говорите, что процесс создания новых узлов можно остановить в любой момент, что в моем понимании дает нам пустое дерево, так как до побед мы не добрались. Так как использовать дерево без информаций о победах и оценки позиции? Или под победой обозначается что-то иное, а не, собственно, конечный разгром противника?

Так же, на сколько я понимаю, вырастить дерево ходов на столько, чтобы оно доросло до побед не представляется возможным в большинстве игр. То есть пользуясь этим методом у меня будет постоянно пустое дерево без информации о победах?

[galvanom]

Нет, оценка позиции не рассматривается. Из каждой позиции проигрываются случайные ходы до конца партии. Эти ходы не запоминаются, дерево не дополняется новыми ходами после случайных партий. Важно только количество побед из данной позиции.

[BotCoder]

Спасибо! Это я как раз и не мог понять. Но теперь меня ужасает масштаб процессорного времени, требующегося под вычисление более или менее коррелирующего с реальностью дерева… И теперь понял, почему программа, победившая европейского чемпиона Го, во время игры «вертелась» на нехилом кластере в облаке