Компьютер научился беспроигрышной стратегии карточной игры

Канадским ученым удалось написать компьютерную программу, способную на слабое решение самой популярной разновидности покера — техасского холдема (с лимитированными ставками). Иными словами, компьютер смог создать стратегию игры, настолько близкую к оптимальной, что никакой человек не способен обыграть его (со статистическим уровнем значимости) за всю свою жизнь. О программе, получившей название Cepheus («Цефей») сообщается в журнале Science.

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

Метод Майкла Боулинга (Michael Bowling) и его коллег основывается на принципе counterfactual regret minimization. Алгоритм реализуется на распределенных вычислительных узлах за счет того, что игра разбивается на отдельные фрагменты (около 110 тысяч), согласно доступной информации (знанию об открытых картах и прошлых ходах игроков). Кроме того, специальные техники сжатия данных обеспечивали хранение фрагментов партии на локальных дисках и возврат их в память системы для расчетов. Всего использовалось 200 вычислительных узлов (в каждом 2,1-гигагерцовые процессоры AMD, всего 24 процессорных ядра в узле, 32 гигабайта оперативной памяти, 1-терабайтный жесткий диск в каждом), а вычисления заняли в общей сложности 68 с половиной суток. За это время Cepheus провел сам с собой несколько миллиардов партий, таким образом набрав необходимый опыт игры.

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

Узнать больше о Cepheus и сыграть с ним партию можно на сайте Университета Альберты.

Обсудить
Моя семья
Легендарный маньяк и его культ кровавых убийц держали в страхе всю Америку
Чарльз МэнсонКонец маньяка: Чарльз Мэнсон умер в тюрьме
Легендарный убийца не дождался великой межрасовой войны
Порошок, приходи
Жадные мексиканцы потеряли доход от марихуаны и завалили Америку героином
Кровавая ривьера
Франция отстреливает врагов по всему миру, пока никто не видит
Абсолютное возмездие
Россия, США и Китай готовятся к третьей мировой войне
Пробила дно
Планета-пришелец расколола Землю и сдвинула континенты
Голодающие дети в Бузулуке (Самарская губерния), 1921-1922 гг.«Обезумевшие родители отбирали еду у детей»
Советская власть бросила миллионы умирать от голода, но их спасли американцы
«Девочку из России тут никто не ждет»
История сибирячки, перебравшейся в Нидерланды
Во всем виноват буй
Она мечтала о круизе с секс-рабынями, но потерялась в море с боевой подругой
«Не надо меня спасать»
Звездный путешественник нашел тайное племя головорезов, ввязался в войну и выжил
Эмилио Эстевес в роли Билли КидаМалыш на миллион
Легендарный головорез Дикого Запада передал привет из прошлого
Самые большие шины в мире
Огромные покрышки, которые подойдут даже машине Годзиллы
5 причин, почему мы ненавидим кроссоверы
Объясняем в картинках, почему самые популярные машины в мире никуда не годятся
Audi Q5 против SQ5
Пять причин купить Audi SQ5 вместо обычной Q5 (и одна против)
Кто делает самые эпатажные британские машины
«Рэйнджи», «Астоны» и «Роллс-Ройсы»: лучшие творения ателье Kahn Design
Ловушка для планктона
Тест: Какой офис идеально вам подходит
«Моя бывшая живет на помойке»
Москвич сделал из жены бомжа, и ему не стыдно
Белый друг
Самые необычные туалеты мира
Это Англия, детка!
Идеальный дом можно выиграть за две тысячи рублей
Берите две
Пять стран, где ипотеку дают под смешной процент