Комп’ютер навчився безпрограшної стратегії карткової гри

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

Покер, як і інші карткові ігри, відноситься до ігор з неповною інформацією — де учасники мають прихованим від інших знанням про своїх картах, а також можуть використовувати це знання в свою користь (наприклад, блефувати). Якщо в іграх з повною інформацією (наприклад, шахах, де обидва гравці бачать положення всіх фігур на дошці) штучний інтелект або обігрує людини, або як мінімум досяг паритету з ним, над покером програмісти безуспішно билися з 2006 року (коли пройшов перший щорічний чемпіонат по цій грі серед комп’ютерів).

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

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

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