Я хочу начать со сценария, который заставил меня задуматься о том, насколько хорошо может работать MCTS: предположим, что есть движение, которое еще не добавлено в дерево поиска. Это несколько слоев / движется слишком глубоко. Но если мы сыграем этот ход, игра в основном выиграна. Однако давайте также предположим, что все ходы, которые можно сделать вместо этого в данном игровом состоянии, очень и очень плохие. В качестве аргумента, скажем, есть 1000 возможных ходов, и только один из них хорош (но очень хорош), а остальные очень плохи. Не MCTS не сможет признать это и нерасти дерево поиска к этому движению, а также очень плохо оценивать это поддерево? Я знаю, что MCTS в конечном итоге сходится к минимаксной (и в конечном итоге она построит целое дерево, если будет достаточно памяти). Тогда следует знать, что этот шаг хорош, хотя есть много плохих возможностей. Но я думаю, на практике это не то, на что можно положиться. Может быть, кто-то может сказать мне, если это правильная оценка с моей стороны.
Помимо этого специального сценария, я также хотел бы знать, есть ли другие подобные сценарии, где MCTS будет работать плохо (или необычайно хорошо).
Ответы:
Найден ли ход и насколько быстро он найден, зависит от нескольких вещей. Если я правильно понимаю, есть последовательность из многих «плохих» ходов, которые приводят к ходу «большой выигрыш», и вы боитесь, что алгоритм MCTS не доберется до хода «большой выигрыш», потому что он будет выбирать более многообещающие движется дальше вверх по дереву. Некоторые вещи, чтобы думать (прочитайте также статью MCTS Wikipedia ):
когда вы играете в плей-офф, вы можете играть в свою игру только на несколько дальнейших ходов или до конца игры. Играть на несколько ходов дальше, очевидно, быстрее, но в описанном выше крайнем случае это не лучший выбор. Если вы знаете о существовании таких сценариев, обязательно поиграйте в игру до конца в играх.
во время игр вы можете выбирать свои движения / действия случайным образом или на основе простой, жадной (быстрой) эвристики, приспособленной к вашей проблеме. Может быть, есть жадная эвристика, разработанная, чтобы найти или учесть такие сценарии для вашей игры / проблемы? Если да, реализуйте их. Это тогда называют "тяжелым playout". Сравните результаты с играми, используя случайные ходы.
Если вы выбираете действия, используя UCT (верхняя граница достоверности, применяемая к деревьям), то первая часть выражения отвечает за эксплуатацию. Ходы с высоким средним коэффициентом выигрыша являются предпочтительными. Вторая часть, хотя и соответствует разведке. Если параметр исследования установлен достаточно высоко (тестируйте эмпирически для вашей задачи), тогда предпочтительнее будет двигаться с небольшим количеством симуляций. Высокие исследования - это еще один способ найти свой золотой ход в ущерб эксплуатации (читайте о дилемме исследования / эксплуатации).
Если вы описываете реалистичную игру или проблемный сценарий, мы можем помочь вам найти подходящую стратегию.
источник