Программирование игрового бота общего назначения -> Форум на Исходниках.RU [Powered by Invision Power Board]

Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум на Исходниках.RU > Алгоритмы > Программирование игрового бота общего назначения

Автор: JoeUser 22.05.18, 17:40

Буэнос диас, амигос!

Вопрос просто ради "самообразования". В последнее время время мы видим то тут, то там, что "программа" обыгрывает человека то в шахматы, то в го ... Вот, собственно, это и заинтересовало.

Простой вариант - тупо полный перебор. Как применение - игра в "крестики-нолики". Вариантов там достаточно ограниченное количество, решение можно свести к полному перебору. Но, когда берем, шахматы, а тем паче, ту же игру го - количество развитий игры стремиться к необозримо большому числу вариантов. Такое количество вариантов современному компьютеру рассчитать в реальном масштабе времени просто не реально.

Но! ... Программы все-таки выигрывают...

Собственно вопросы:

1) Каким образом программируются стратегии выигрыша?
2) Есть ли какие-то общие методики программирования игровых стратегий, безотносительно игры и правил?

Автор: FasterHarder 22.05.18, 18:19

на шахматном сайте (личез, где я поигрываю иногда) их главный проггер пишет шахматных ботов!
самый совершенный этот: БОТ ЛИИЛА!
вроде код у них открытый, хотя хз
Гроссов этот бот крошит в пух и прах!

Автор: JoeUser 22.05.18, 18:34

FasterHarder, спасибо за линк ... но вопросы остались открытыми.
Меня не алгоритмы интересуют, а методология

Автор: OpenGL 22.05.18, 19:45

Цитата JoeUser @ 22.05.18, 17:40

1) Каким образом программируются стратегии выигрыша?

Никаким - стратегии выводятся самим ботом в виде набора весов нейросети

Вообще, боты вроде alpha zero или leela, способные самообучаться без человека, работают относительно несложно (если не углубляться в нюансы, конечно). Есть некая нейронка, она для позиции выдаёт список "разумных" ходов (применительно к го, например - матрицу 19*19, которая, грубо говоря, интерпретируется как вероятность сходить в то поле) и вероятность выигрыша. Далее, имея эту нейронку, мы запускаем Монте-Карло, в котором ищем ноду, дающую максимальную вероятность выигрыша с т.з. этой нашей нейронки. Ну а когда игра закончилась - сдвигаем веса нейросети так, чтобы она данную игру предсказывала правильней, а так же правильней оценивала разумность ходов (выигрышная сторона делала более разумные ходы, проигравшая - менее).
Можешь глянуть реализацию бота для го, работающего как раз по вышеописанному алгоритму и обучающегося исключительно на партиях самим с собой - leela zero. Играет этот бот на данный момент хуже, чем топовые профи, но большинство игроков ему не могут противопоставить ничего - проверено лично :crazy:

Цитата JoeUser @ 22.05.18, 17:40

2) Есть ли какие-то общие методики программирования игровых стратегий, безотносительно игры и правил?

Ну для настольных игр, где передвигаются фишки, видимо, такую стратегию сделали. Для карточных игр, стратежек или какого-нибудь The Talos Principle, видимо, что-то другое надо - алгоритмы для настольных игр подходят не очень в этом случае.

Цитата FasterHarder @ 22.05.18, 18:19

на шахматном сайте (личез, где я поигрываю иногда) их главный проггер пишет шахматных ботов!
самый совершенный этот: БОТ ЛИИЛА!

leela? Она разве не проигрывает топовым ботам вроде Стокфиша?

Автор: Pavia 22.05.18, 20:07

Цитата JoeUser @ 22.05.18, 17:40

Такое количество вариантов современному компьютеру рассчитать в реальном масштабе времени просто не реально.

По этому поводу вспоминается журнал GoWord для того что-бы установить какое начало игры приводит к выигрышной стратегии простой китайский клуб сыграл один миллион партий. 8-)

Цитата JoeUser @ 22.05.18, 17:40

Есть ли какие-то общие методики программирования игровых стратегий, безотносительно игры и правил?

Для первичного обучения используют кластеры/суперкомпьютеры. Так что там бот в паролели играет кучу игр сам с собой. Во-вторых команд код пишут команды. Как бы команда соревнуется одним игроком пусть и лучшим профи в мире, но всё равно это не честно. :tong:

Шутки шутками. А теперь серьёзно.
Обучение с подкреплением. Если выиграл то стратегия верная. Если проиграл стратегия не верная.
Самое важно это три вещи определить цену игры, делай самый большой ход и не теряй темпа. Есть ещё немало важных правил: к примеру известных как 10 правил Го. Они универсальны и их можно принимать и к другим играм.

Цитата JoeUser @ 22.05.18, 17:40

Есть ли какие-то общие методики программирования игровых стратегий, безотносительно игры и правил?

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

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

К ответу а как же полный перебор? Полный перебор можно свернуть в короткое правило. Сейчас популярны рекурсивные нейронные сети. У них очень хорошо получается играть в Го и читать тексты. :jokingly:

Сами по себе такие сети плохо поддаются обучению по методу обратному распространению ошибки. Поэтому их обучают через структурные методы. К структурным относятся генетические алгоритмы (ГА). По мимо ГА есть такая вещь как автокодировщик и стековые алгоритмы.

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

Большинство из этого уже закодировано в фреймворках таких как TenserFlow.

Ещё про структурные методы. Структурные методы хороши, но теория разработана недоконца. Поэтому в большинстве задач выигрывают вероятностные деревья классификаций. Если их удаться совместить, то должен получится довольно сильный общий метод.