6.2.3.6 Игры с неполной информацией: карточные игры - История изменений

Andrey Fedichkin в 21:50, 8 мая 2025

2025-05-08T21:50:19Z

← Предыдущая версия		Версия от 21:50, 8 мая 2025
Строка 28:		Строка 28:

	Наследником Libratus стала Pluribus — система, которая в 2019 г. смогла одержать победу при игре в HUNL с шестью игроками, играя против пяти игроков, входящих в состав мировой покерной элиты<ref>Rodriguez J. (2019). Inside Pluribus: Facebook’s New AI That Just Mastered the World’s Most Difficult Poker Game / KDnuggets // https://www.kdnuggets.com/2019/08/inside-pluribus-facebooks-new-ai-poker.html</ref><sup>,</sup> <ref>Blair A., Saffidine A. (2019). AI surpasses humans at six-player poker / Science, Vol. 365, Iss. 6456, pp. 864–865 // https://doi.org/10.1126/science.aay7774</ref>. Pluribus была создана совместными усилиями учёных из Университета Карнеги — Меллона и исследователей ИИ из компании Facebook. Обе системы, Libratus и Pluribus, обучались при помощи методов обучения с подкреплением. Прежде чем соревноваться с людьми, Pluribus разыграла триллионы раздач в покер против самой себя. Хотя ни Libratus, ни Pluribus не использовали нейронные сети для оценки (вместо этого применялась более простая модель, основанная на методе ''k''-средних для кластеризации признаков), последние публикации<ref>Brown N., Lerer A., Gross S., Sandholm T. (2019). Deep Counterfactual Regret Minimization / Proceedings of the 36th International Conference on Machine Learning, PMLR 97:793-802 // http://proceedings.mlr.press/v97/brown19b.html</ref> создателей Pluribus посвящены возможности использования глубоких нейронных сетей для замены текущей модели оценки.		Наследником Libratus стала Pluribus — система, которая в 2019 г. смогла одержать победу при игре в HUNL с шестью игроками, играя против пяти игроков, входящих в состав мировой покерной элиты<ref>Rodriguez J. (2019). Inside Pluribus: Facebook’s New AI That Just Mastered the World’s Most Difficult Poker Game / KDnuggets // https://www.kdnuggets.com/2019/08/inside-pluribus-facebooks-new-ai-poker.html</ref><sup>,</sup> <ref>Blair A., Saffidine A. (2019). AI surpasses humans at six-player poker / Science, Vol. 365, Iss. 6456, pp. 864–865 // https://doi.org/10.1126/science.aay7774</ref>. Pluribus была создана совместными усилиями учёных из Университета Карнеги — Меллона и исследователей ИИ из компании Facebook. Обе системы, Libratus и Pluribus, обучались при помощи методов обучения с подкреплением. Прежде чем соревноваться с людьми, Pluribus разыграла триллионы раздач в покер против самой себя. Хотя ни Libratus, ни Pluribus не использовали нейронные сети для оценки (вместо этого применялась более простая модель, основанная на методе ''k''-средних для кластеризации признаков), последние публикации<ref>Brown N., Lerer A., Gross S., Sandholm T. (2019). Deep Counterfactual Regret Minimization / Proceedings of the 36th International Conference on Machine Learning, PMLR 97:793-802 // http://proceedings.mlr.press/v97/brown19b.html</ref> создателей Pluribus посвящены возможности использования глубоких нейронных сетей для замены текущей модели оценки.
			<references />
	<comments />		<comments />

Andrey Fedichkin в 20:34, 8 мая 2025

2025-05-08T20:34:30Z

← Предыдущая версия		Версия от 20:34, 8 мая 2025
Строка 28:		Строка 28:

	Наследником Libratus стала Pluribus — система, которая в 2019 г. смогла одержать победу при игре в HUNL с шестью игроками, играя против пяти игроков, входящих в состав мировой покерной элиты<ref>Rodriguez J. (2019). Inside Pluribus: Facebook’s New AI That Just Mastered the World’s Most Difficult Poker Game / KDnuggets // https://www.kdnuggets.com/2019/08/inside-pluribus-facebooks-new-ai-poker.html</ref><sup>,</sup> <ref>Blair A., Saffidine A. (2019). AI surpasses humans at six-player poker / Science, Vol. 365, Iss. 6456, pp. 864–865 // https://doi.org/10.1126/science.aay7774</ref>. Pluribus была создана совместными усилиями учёных из Университета Карнеги — Меллона и исследователей ИИ из компании Facebook. Обе системы, Libratus и Pluribus, обучались при помощи методов обучения с подкреплением. Прежде чем соревноваться с людьми, Pluribus разыграла триллионы раздач в покер против самой себя. Хотя ни Libratus, ни Pluribus не использовали нейронные сети для оценки (вместо этого применялась более простая модель, основанная на методе ''k''-средних для кластеризации признаков), последние публикации<ref>Brown N., Lerer A., Gross S., Sandholm T. (2019). Deep Counterfactual Regret Minimization / Proceedings of the 36th International Conference on Machine Learning, PMLR 97:793-802 // http://proceedings.mlr.press/v97/brown19b.html</ref> создателей Pluribus посвящены возможности использования глубоких нейронных сетей для замены текущей модели оценки.		Наследником Libratus стала Pluribus — система, которая в 2019 г. смогла одержать победу при игре в HUNL с шестью игроками, играя против пяти игроков, входящих в состав мировой покерной элиты<ref>Rodriguez J. (2019). Inside Pluribus: Facebook’s New AI That Just Mastered the World’s Most Difficult Poker Game / KDnuggets // https://www.kdnuggets.com/2019/08/inside-pluribus-facebooks-new-ai-poker.html</ref><sup>,</sup> <ref>Blair A., Saffidine A. (2019). AI surpasses humans at six-player poker / Science, Vol. 365, Iss. 6456, pp. 864–865 // https://doi.org/10.1126/science.aay7774</ref>. Pluribus была создана совместными усилиями учёных из Университета Карнеги — Меллона и исследователей ИИ из компании Facebook. Обе системы, Libratus и Pluribus, обучались при помощи методов обучения с подкреплением. Прежде чем соревноваться с людьми, Pluribus разыграла триллионы раздач в покер против самой себя. Хотя ни Libratus, ни Pluribus не использовали нейронные сети для оценки (вместо этого применялась более простая модель, основанная на методе ''k''-средних для кластеризации признаков), последние публикации<ref>Brown N., Lerer A., Gross S., Sandholm T. (2019). Deep Counterfactual Regret Minimization / Proceedings of the 36th International Conference on Machine Learning, PMLR 97:793-802 // http://proceedings.mlr.press/v97/brown19b.html</ref> создателей Pluribus посвящены возможности использования глубоких нейронных сетей для замены текущей модели оценки.
			<comments />

Andrey Fedichkin: Новая страница: « 642x481px Прогресс в игровом ИИ, наметившийся благодаря успехам в области глубокого обучения, затронул не только настольные игры. Фокус исследований постепенно стал смещаться в сторону иг...»

2025-04-06T11:12:56Z

Новая страница: « 642x481px Прогресс в игровом ИИ, наметившийся благодаря успехам в области глубокого обучения, затронул не только настольные игры. Фокус исследований постепенно стал смещаться в сторону иг...»

Новая страница

[[File:image229.jpeg|642x481px]]

Прогресс в игровом ИИ, наметившийся благодаря успехам в области глубокого обучения, затронул не только настольные игры. Фокус исследований постепенно стал смещаться в сторону игр с большими размерами поисковых пространств. Отдельной непростой задачей всегда было создание систем ИИ для игр с неполной информацией. В этих играх размер поискового пространства растёт за счёт того, что количество способов разрешения неопределённости может быть достаточно большим. В карточных играх вам почти всегда неизвестны карты противника, а значит, при полном переборе вы должны включить в рассмотрение все потенциальные сочетания карт, которые могут быть у него на руках. Поверье о том, что машины никогда не научатся блефовать, было, возможно, даже более распространено, чем поверье о том, что машинам никогда не удастся одолеть человека в го. Например, в телесериале «Звёздный путь: Следующее поколение» андроид лейтенант-коммандер Дейта, познакомившись с игрой в покер, изначально полагает, что игра достаточно проста и может быть освоена при помощи простой математической стратегии, однако сталкивается с большими трудностями, пытаясь постичь искусство блефа.

В 1920-е гг., когда фон Нейман впервые занялся вопросами теории игр, именно покер стал для него первым объектом исследования. Почему покер, а не шахматы, которые всегда считались стратегической игрой? Британский математик, биолог и историк науки Джейкоб Броновски приводит ответ фон Неймана на этот вопрос: «''Нет‑нет, шахматы — это не игра. Шахматы — это хорошо определённая форма вычислений. Возможно, вы не сможете найти все ответы, но в теории должно быть решение, правильная процедура для любой позиции. Реальные игры совсем не такие. Реальная жизнь не такая. Реальная жизнь состоит из блефа, из маленьких тактик обмана, из вопросов себе о том, что другой человек думает о том, как я собираюсь поступить. И это как раз то, чем являются игры в моей теории''»<ref>Poundstone W. (2011). Prisoner's Dilemma. Knopf Doubleday Publishing Group // https://books.google.ru/books?id=twNXXfYVB1UC</ref>.

Количество точек принятия решений в такой разновидности покера, как безлимитный техасский холдем один на один (Heads-up no-limit Texas hold’em, HUNL), превышает 10160 (для сравнения: количество игровых состояний в го составляет примерно 2,08 × 10170, а в шахматах — около 1047). Хотя HUNL и отстаёт от го по этому показателю на целых десять порядков, но на логарифмической шкале эти игры расположены фактически по соседству и на огромном расстоянии от шахмат.

В 2015 г. исследователи из канадского Альбертского университета в Эдмонтоне представили систему «Цефей» (Cepheus), предназначенную для игры в более простой вариант покера — лимитированный холдем один на один (Heads-up limit hold’em, HULHE). Вычислительно HULHE гораздо проще HUNL: в этой игре «всего» примерно 3,19 × 1014 точек принятия решений (1,38 × 1013, если убрать симметричные случаи).

Стратегия «Цефея» очень близка к равновесию Нэша для HULHE, поскольку математическое ожидание выигрыша оптимальной контрстратегии составляет только 0,000986 единицы ставки (так называемого большого блайнда, big-blind) за игру. Этот результат позволил создателям «Цефея» заявить<ref>Bowling M., Burch N., Johanson M., Tammelin O. (2015). Heads-up Limit Hold’em Poker is Solved / Science, Vol. 347, Iss. 6218, pp. 145—149 // https://doi.org/10.1126/science.1259433</ref> на страницах журнала ''Science'', что HULHE «по существу» решён (для того чтобы преодолеть дистанцию от решения «по существу» до полного решения, нужно уменьшить математическое ожидание проигрыша до нуля больших блайндов за игру).

Создатели «Цефея» так определили понятие игры, «решённой по существу» [essentially solved]: «Если игра в течение всей жизни не позволяет статистически достоверно отличить её от решённой с 95%-ной достоверностью». Под «игрой в течение всей жизни» в данном случае понимается игра со скоростью 200 игр в час по 12 часов в день без выходных на протяжении 70 лет.

«Цефей» стал детищем Исследовательской группы по компьютерному покеру (Computer Poker Research Group, CPRG), созданной в 1991 г., участником (до 2004 г. — руководителем) которой является хорошо знакомый нам создатель шашечной программы Chinook Джонатан Шеффер.

За время своего существования группа создала несколько сильных компьютерных программ для игры в техасский холдем. Первой из них стала программа Poki, в основу которой была положена симуляция игр методом Монте-Карло. В 2007 г. новая программа группы, Polaris, на конференции AAAI сыграла с двумя профессионалами-людьми: Филом Лааком и Али Эслами. Из четырёх матчей Polaris выиграл один, один свёл вничью и проиграл дважды; то есть в целом люди выиграли соревнование с небольшим отрывом. В 2008 г. обновлённая версия Polaris одержала победу над командой людей-профессионалов во втором соревновании по покеру между людьми и машинами.

В 2017 г. группа представила<ref>Moravčík M., Schmid M., Burch N., Lisý V., Morrill D., Bard N., Davis T., Waugh K., Johanson M., Bowling M. (2017). DeepStack: Expert-level artificial intelligence in heads-up no-limit poker / Science, Vol. 356, Iss. 6337, pp. 508—513 // https://doi.org/10.1126/science.aam6960</ref> систему DeepStack, предназначенную для игры в HUNL. В качестве оценочной функции в этой программе используется глубокая нейронная сеть (семь слоёв по 500 нейронов, функция активации — PReLU — одна из модификаций ReLU с обучаемыми параметрами). Обучающая выборка для этой сети формировалась путём псевдослучайной генерации множества состояний игры (наборы карт, размер банка) с последующим их разрешением. Фактически нейронная сеть в DeepStack используется для аппроксимации результатов Монте-Карло-симуляций, что позволяет существенно сократить вычислительные затраты.

Для оценки силы игры DeepStack авторы программы использовали пул профессиональных игроков в покер, привлечённых для этой цели Международной федерацией покера. В пул вошли 33 добровольца из 17 стран. В общей сложности было сыграно 44 852 игры, при этом 11 игроков смогли выполнить просьбу организаторов и провести по 3000 игр. Итоговый выигрыш DeepStack составил 492 миллиблайнда (почти половина минимальной ставки) за игру, что составило более четырёх стандартных отклонений от нуля. Это означает, что можно с очень высокой степенью уверенности говорить о превосходстве DeepStack над противостоящим ему пулом игроков.

Если рассчитать результат только по тем игрокам, которые совершили по 3000 игр (11 человек), то DeepStack выиграл у них всех в среднем 429 миллиблайндов за игру, а если сделать поправку на фактор удачи, то победы над десятью игроками из одиннадцати были одержаны со статистически значимым преимуществом и лишь над одним — со статистически незначимым (70 миллиблайндов за игру).

В том же году система Libratus, созданная в Университете Карнеги — Меллона, уверенно одолела четырёх ведущих мировых игроков в HUNL<ref>Mets C. (2017). Inside Libratus, the Poker AI That Out-Bluffed the Best Humans / Wired, 02.01.17 // https://www.wired.com/2017/02/libratus/</ref>. Матчи проходили в реальном времени в ходе 20-дневного турнира, а расчёты во время игры производились на новом суперкомпьютере Bridges в Питтсбургском суперкомпьютерном центре.

Наследником Libratus стала Pluribus — система, которая в 2019 г. смогла одержать победу при игре в HUNL с шестью игроками, играя против пяти игроков, входящих в состав мировой покерной элиты<ref>Rodriguez J. (2019). Inside Pluribus: Facebook’s New AI That Just Mastered the World’s Most Difficult Poker Game / KDnuggets // https://www.kdnuggets.com/2019/08/inside-pluribus-facebooks-new-ai-poker.html</ref>, <ref>Blair A., Saffidine A. (2019). AI surpasses humans at six-player poker / Science, Vol. 365, Iss. 6456, pp. 864–865 // https://doi.org/10.1126/science.aay7774</ref>. Pluribus была создана совместными усилиями учёных из Университета Карнеги — Меллона и исследователей ИИ из компании Facebook. Обе системы, Libratus и Pluribus, обучались при помощи методов обучения с подкреплением. Прежде чем соревноваться с людьми, Pluribus разыграла триллионы раздач в покер против самой себя. Хотя ни Libratus, ни Pluribus не использовали нейронные сети для оценки (вместо этого применялась более простая модель, основанная на методе ''k''-средних для кластеризации признаков), последние публикации<ref>Brown N., Lerer A., Gross S., Sandholm T. (2019). Deep Counterfactual Regret Minimization / Proceedings of the 36th International Conference on Machine Learning, PMLR 97:793-802 // http://proceedings.mlr.press/v97/brown19b.html</ref> создателей Pluribus посвящены возможности использования глубоких нейронных сетей для замены текущей модели оценки.