Искусственный интеллект и Холдем

Предлагаем вашему вниманию перевод серии статей Николая Яковенко об искусственном интеллекте в покере.

Это был хороший год для изучения автоматики и искусственного интеллекта. И нет, я сейчас не просто ссылаюсь на российского ученого, который утверждает, что его робот-повар может приготовить идеальную миску крабового супа.

Более непосредственное отношение к миру покера имело место в том году, когда исследователи из Университета Альберты заявили, что «решили» хедз-ап в LHE, вычислив стратегию для всех возможных случаев в пределах 1% неэксплуатируемого равновесия Нэша. Между тем, группа из Университета Карнеги-Меллона в Питтсбурге, специализирующаяся на покере, протестировала систему хедз-ап NLHE против одних из лучших хедз-ап игроков онлайн-покера, в этом поединке победили люди, но только со статистически недоказанной маржей.

Эти результаты ранее уже освещались. Поэтому сегодня мы погрузимся в алгоритм с интригующим названием «минимизация гипотетической ситуации сожаления» (сокращенно CFR), имеющий отношение к тому, как работает покерный AI. Помимо красивого названия, CFR имеет важное значение – эта математика проделывает титаническую работу, чтобы найти практически идеальное решение для LHE и конкурентоспособного NLHE AI.

Представление CFR

Если смотреть отдаленно, то CFR довольно прост, особенно для тех, кто знаком с равновесием Нэша.

Теоретически равновесие Нэша – это неэксплуатируемая вероятностная стратегия. «Вероятностная» означает, что в некоторых ситуациях вы будете бетить 50% времени и столько же чекать в зависимости от случая. «Неэксплуатируемая» означает, что ни один оппонент не сможет получить долгосрочное преимущество – во внимание приняты все возможные в игре действия (то есть все комбинации карт и ставок), даже если оппонент знает вашу стратегию, но не знает ваших карт или какое из решений 50 на 50 вы будете использовать.

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

Если в хедз-ап LHE мы запишем каждую комбинацию карт и последовательность ставок как отдельное событие, то получится около 320 триллионов «наборов информации». Это число кажется огромным, но оно не столь велико, как количество атомов в галактике или что-то вроде этого. В своей книге «Краткая история времени» Стивен Хокинг сделал хорошее замечание, что каждое уравнение, которое появляется в книге, сокращает читательскую аудиторию вдвое, поэтому мы обойдемся без уравнений. Нам придется говорить на математическом языке, но я попытаюсь избежать чисел там, где в них нет острой необходимости.

MacBook Air, на котором я пишу, имеет процессор Intel на 2.13 GHz. Умножение 320 триллионов возможных наборов информации для LHE на 2.13 GHz занимает 1.74 дня вычислительной работы. Конечно, цикл по всем возможным рукам не так прост, но его можно провести, даже на вашем ноутбуке.

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

Продолжение следует

Оценить материал:
- отличный материал
- хороший материал
- неплохой материал
- плохой материал
- материал ужасный
Добавить коментарий
Редактировать коментарий
Комментарии отсутствуют
Вы будете первым, кто оставит свой комментарий