Какие алгоритмы ИИ можно использовать для игры в вероятностные игры с возможно неполной информацией?

Question

Минимаксный алгоритм и поиск по дереву Монте-Карло (MCTS) можно использовать для реализации агентов, которые играют в детерминированные (то есть не вероятностные) игры, такие как шахматы или крестики-нолики, которые имеют полную информацию об игре.

Существуют ли общие методы для игр с неполной информацией и / или игр с вероятностным компонентом (например, покер или бридж)?

Answer 1

Да. Вы задаете несколько вопросов одновременно.

Самая простая возможность - игра типа нарды, которая включает в себя вероятность, но полную информацию. Расширение до минимакса является простым и называется expectiminimax.

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

Карточные игры обычно бывают одновременно и требуют обеих техник.

Обратите внимание, что эти простые расширения только поцарапать поверхность. Точно так же, как шахматы и гоу требуют не только простых деревьев поиска, так и частично наблюдаемые случайные игры требуют не только расширений. Когда действия имеют вероятностные результаты (то есть вероятность неудачи), вы попадаете в область глубоких академических исследований.