В 2006 году Левенте Кочиш и Чаба Сепешвари представили UCT — способ направлять поиск по дереву с помощью статистического выбора действий. Алгоритм балансировал между повторной проверкой обещающих вариантов и изучением тех, о которых пока мало данных.
В том же исследовательском периоде команда MoGo применила эту схему к го. В объяснении участников проекта на портале Inria Interstices описано сочетание двух частей: дерево чаще исследует перспективные ходы, а позиция на его границе оценивается серией доигрываний до конца. Итоги возвращаются в посещённые узлы и влияют на следующий поиск.
Для самих доигрываний MoGo использовала небольшие локальные образцы, создававшие более правдоподобные последовательности. Авторы подчёркивали разницу между бессистемным заполнением доски и статистикой таких продолжений.
Это изменило практическое устройство компьютерного го: вычислительный ресурс можно было сосредоточивать на наиболее полезных ветвях. Тогдашние успехи на малых досках ещё не означали равенства с лучшими профессионалами на 19×19.
Основание материала
Источники и проверка
- Исследование
Кочиш и Сепешвари: Bandit Based Monte-Carlo Planning
Авторская копия ECML 2006; PDF с. 1–5: выбор действий, exploration/exploitation, UCT; с. 1 проверена визуально.
Проверен:
- Исследование
Inria Interstices: MoGo, maître du jeu de Go?
Объяснение команды MoGo: разделы об UCT, оценке Монте-Карло, локальных последовательностях и ограничениях.
Проверен:
Раскрытие связи
Материал входит в общий проект сайтов о го.
История продолжается.
Другие события в хронике →