Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[54.224.52.210] |
|
Сообщ.
#1
,
|
|
|
Буэнос диас, амигос!
Вопрос просто ради "самообразования". В последнее время время мы видим то тут, то там, что "программа" обыгрывает человека то в шахматы, то в го ... Вот, собственно, это и заинтересовало. Простой вариант - тупо полный перебор. Как применение - игра в "крестики-нолики". Вариантов там достаточно ограниченное количество, решение можно свести к полному перебору. Но, когда берем, шахматы, а тем паче, ту же игру го - количество развитий игры стремиться к необозримо большому числу вариантов. Такое количество вариантов современному компьютеру рассчитать в реальном масштабе времени просто не реально. Но! ... Программы все-таки выигрывают... Собственно вопросы: 1) Каким образом программируются стратегии выигрыша? 2) Есть ли какие-то общие методики программирования игровых стратегий, безотносительно игры и правил? |
Сообщ.
#2
,
|
|
|
на шахматном сайте (личез, где я поигрываю иногда) их главный проггер пишет шахматных ботов!
самый совершенный этот: БОТ ЛИИЛА! вроде код у них открытый, хотя хз Гроссов этот бот крошит в пух и прах! |
Сообщ.
#3
,
|
|
|
FasterHarder, спасибо за линк ... но вопросы остались открытыми.
Меня не алгоритмы интересуют, а методология |
Сообщ.
#4
,
|
|
|
Цитата JoeUser @ 1) Каким образом программируются стратегии выигрыша? Никаким - стратегии выводятся самим ботом в виде набора весов нейросети Вообще, боты вроде alpha zero или leela, способные самообучаться без человека, работают относительно несложно (если не углубляться в нюансы, конечно). Есть некая нейронка, она для позиции выдаёт список "разумных" ходов (применительно к го, например - матрицу 19*19, которая, грубо говоря, интерпретируется как вероятность сходить в то поле) и вероятность выигрыша. Далее, имея эту нейронку, мы запускаем Монте-Карло, в котором ищем ноду, дающую максимальную вероятность выигрыша с т.з. этой нашей нейронки. Ну а когда игра закончилась - сдвигаем веса нейросети так, чтобы она данную игру предсказывала правильней, а так же правильней оценивала разумность ходов (выигрышная сторона делала более разумные ходы, проигравшая - менее). Можешь глянуть реализацию бота для го, работающего как раз по вышеописанному алгоритму и обучающегося исключительно на партиях самим с собой - leela zero. Играет этот бот на данный момент хуже, чем топовые профи, но большинство игроков ему не могут противопоставить ничего - проверено лично Цитата JoeUser @ 2) Есть ли какие-то общие методики программирования игровых стратегий, безотносительно игры и правил? Ну для настольных игр, где передвигаются фишки, видимо, такую стратегию сделали. Для карточных игр, стратежек или какого-нибудь The Talos Principle, видимо, что-то другое надо - алгоритмы для настольных игр подходят не очень в этом случае. Цитата FasterHarder @ на шахматном сайте (личез, где я поигрываю иногда) их главный проггер пишет шахматных ботов! самый совершенный этот: БОТ ЛИИЛА! leela? Она разве не проигрывает топовым ботам вроде Стокфиша? |
Сообщ.
#5
,
|
|
|
Цитата JoeUser @ Такое количество вариантов современному компьютеру рассчитать в реальном масштабе времени просто не реально. По этому поводу вспоминается журнал GoWord для того что-бы установить какое начало игры приводит к выигрышной стратегии простой китайский клуб сыграл один миллион партий. Цитата JoeUser @ Есть ли какие-то общие методики программирования игровых стратегий, безотносительно игры и правил? Для первичного обучения используют кластеры/суперкомпьютеры. Так что там бот в паролели играет кучу игр сам с собой. Во-вторых команд код пишут команды. Как бы команда соревнуется одним игроком пусть и лучшим профи в мире, но всё равно это не честно. Шутки шутками. А теперь серьёзно. Обучение с подкреплением. Если выиграл то стратегия верная. Если проиграл стратегия не верная. Самое важно это три вещи определить цену игры, делай самый большой ход и не теряй темпа. Есть ещё немало важных правил: к примеру известных как 10 правил Го. Они универсальны и их можно принимать и к другим играм. Цитата JoeUser @ Есть ли какие-то общие методики программирования игровых стратегий, безотносительно игры и правил? Как тебе сказать и да и нет. Вот к примеру есть такое правило "разделяй и властвуй". А есть его брат блезнец "в единстве мы сила". Их вполне можно закодировать безотносительно. Но все равно под каждую игру придётся писать свою метрику. Вся теория обучения построена как безотносительная. Но с другой стороны эти алгоритмы точно не работают по одиночке и даже есть самомнения что будут работать в системе. В одних играх работают одни стратегии в других другие. К ответу а как же полный перебор? Полный перебор можно свернуть в короткое правило. Сейчас популярны рекурсивные нейронные сети. У них очень хорошо получается играть в Го и читать тексты. Сами по себе такие сети плохо поддаются обучению по методу обратному распространению ошибки. Поэтому их обучают через структурные методы. К структурным относятся генетические алгоритмы (ГА). По мимо ГА есть такая вещь как автокодировщик и стековые алгоритмы. Тут стратегия простая основана она на сжатие информации. Чем меньше нейронов тет лучше НС. Из сети пробуют удалять нейроны или связи так что-бы количество информации сохранялось на выходе. Большинство из этого уже закодировано в фреймворках таких как TenserFlow. Ещё про структурные методы. Структурные методы хороши, но теория разработана недоконца. Поэтому в большинстве задач выигрывают вероятностные деревья классификаций. Если их удаться совместить, то должен получится довольно сильный общий метод. |