Мого и алгоритм UCT для игры в го
Мого и алгоритм UCT впервые обыграли человека-противника уровня Мастера в Го 22 марта 2008 года в турнире, организованном Французской федерацией го.
The Game of Go
Это игра китайского происхождения, в которую играют на доске, называемой гобан, размером 19 х 19 квадратов, но часто уменьшенной до 13 х 13 или 9 х 9 квадратов.
Игроки размещают белые или черные камни на пересечениях линий доски, Игра проходит по очереди, цель состоит в том, чтобы окружить камни противника, чтобы набрать очки.
В этом историческом поединке против компьютера использовалась уменьшенная доска размером 9 на 9 квадратов.
Игра в го похожа на Отелло, в которую играют на квадратной доске 8 х 8. В Отелло окружённые фигуры принимают цвет окружающих их фигур и поэтому меняют владение. Реверси - вариант Отелло.
Программное обеспечение Отелло-Реверси с компьютером в качестве оппонента существует давно и использует простые алгоритмы вроде альфа-бета для замены игрока-человека.
Го не имеет никакого отношения к Гомоку, который является производным от игры Tic-Tac-Toe. Это имеет 3х3 поля и целью является создание линии или диагонали из трёх пешек одного цвета.
Мого и алгоритм ЦП
В 1998 году программа Deeper Blue на IBM впервые обыграла шахматного мастера Гари Каспарова. Однако игру в го сложнее программировать, поскольку количество предсказываемых ходов практически не ограничено.
Лучшей из доступных на данный момент программ для игроков в го является Mogo, разработанная компаниями INRIA, CNRS и Paris-Sud.
Эта программа использует алгоритм UCT для обхода дерева возможных ходов.
UCT, Upper Bound Confidence for Tree, выводится из UCB, Upper Confidence Bounds, и включает использование Monte Carlo в качестве оценочной функции.
Дерево проходит, начиная с корня, текущей позиции пешки, и проходит, используя алгоритм UTC, пока не будет достигнут конечный узел. В этот момент применяется вычислительная функция, называемая Монте-Карло. UCT несколько раз проходит через одни и те же ветки, но каждый раз их оценивают, и поэтому он будет стремиться пробежаться по наиболее перспективным веткам.
Улучшенная версия алгоритма UCT использует симуляцию Монте-Карло, которая заключается в заполнении игры счётчиками не просчитанным способом и подсчёте очков каждого игрока для присвоения значения этому терминальному узлу.
Название Монте-Карло относится к казино княжества и, следовательно, к азартной игре, которая является основой используемого метода.
Справки: Мого, мастер игры? Объяснение алгоритма и UCT и Monte Carlo, презентация программы Mogo. (PDF)