Отправляет email-рассылки с помощью сервиса Sendsay

Алготрейдинг

Подписаться Бесплатная новостная рассылка Подписчиков 1 RSS
  Январь 2015   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://r-trader.ru
Открыта: 12-01-2015

Автор
Андрей Антонов

Статистика

1 подписчиков
0 за неделю
←   Все выпуски   →

Алготрейдинг: Компьютер обыграет вас в покер


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

“Мы не говорим, что гарантирован выигрыш на каждой руке, – говорит Майкл Боулинг, ученый из Университета Альберты и соавтор исследования. – Мы хотим сказать, что в долгосрочной перспективе, при игре на все руки, компьютер должен сыграть либо без убытка, либо выиграть”.

Решение для игры в покер является огромным достижением в области разработки алгоритмов. Простые игры, такие как tic-tac-toe, легко решить. Большинство людей понимает как выиграть в эту игру, сыграв пару раз. Но есть и более сложные игры. Например, шахматы и шашки являются достаточно трудными и предлагают тысячи возможных сценариев того, как компьютеры должны реагировать. Тем не менее, даже для этих игр не так сложно найти решение, как для игры в покер, потому что в покере у вас нет полной информации – вы не знаете, какие карты держит ваш оппонент.

“Совершенные информационные игры, такие как шахматы или шашки, являются играми, где вся информация, которая вам необходима для принятия решений, хранится на виду, – говорит Боулинг. – Но в покере все не так, это несовершенная информационная игра, и этот факт делает разработку стратегии намного сложнее”.

Метод работы программы, на самом деле, довольно прост: все, что делается во время игры – это создается собственная база данных, предварительно вычисленных игровых ситуаций для нахождения наиболее оптимального хода в любой момент игры. Создание этой базы данных было далеко не тривиальной задачей. “У нас была фаза обучения, где программа начала играть против самой себя, это означает, что она не имела ни малейшего представления, что делает, кроме соблюдения правил игры”, – говорит Майкл Йохансон, ученый из Университета Альберты и один из разработчиков. Но по мере игры, программа работала все лучше и лучше и обновляла свою стратегию.

“Это означает, что нужно думать о всех возможных точках принятия решений и принимать всевозможные меры,- объясняет Боулинг.- Например, программа может подумать: что, если я подниму здесь, вместо того, чтобы играть в случайном порядке, больше или меньше денег я смогу выиграть?” Если она решает играть в случайном порядке и теряет деньги, то она возвращается и вычисляет, сколько денег она могла бы заработать, если бы все-таки подняла. Эта сумма затем хранится в виде значения сожаления. Так, программа вычисляет количество сожалений для каждого действия, чтобы затем принять решение. Таким образом, каждый раз, когда она играет руку, программа корректирует свою стратегию и начинает выполнять действия, о которых она пожалела, что не предприняла их в предыдущих играх. И так себя обновляя, программа приблизилась к тому, что по словам Боулинга является “совершенной стратегией”.

Период обучения составлял 70 дней на 200 компьютерах, каждый из которых был оснащен 32 Гб оперативной памяти и 24-мя ядрами. По прошествии этих 70-ти дней программа играла практически идеально. “Мы могли бы продолжить обучение, и программа могла бы стать еще лучше,- говорит Боулинг.- Но мы остановились на этом этапе, потому что мы все равно не сможем сделать ее совершенной. И даже если программа будет обучаться всю жизнь, становясь все более и более совершенной, это все равно не будет иметь большого значения, кроме научной новизны”. Короче говоря, дальнейшее обучение Цефей не приведет к каким-либо существенным изменениям.

Программа также продемонстрировала, что игрок, который раздает карты, и следовательно, играет вторым имеет крошечное преимущество над другим игроком. “На самом деле, мы можем доказать, что дилер имеет преимущество, которое мы называем 88 милиблайндов за игру, – говорит Йохансон.- Это 0,88 большого блайнда в игре”.

Это крупнейшая несовершенная информационная игра, которая решена на сегодняшний день.

11 лет покера

Майкл Боулинг входит в группу исследователей, которые приступили к созданию программы в 2003 году. Тогда они были далеки от понимания, и вряд ли кто-то действительно верил в то, что удастся решить эту проблему. Они работали над разработкой программы, которая смогла бы обыграть лучших игроков в heads-up лимитированном покере, самой простой игре в покер один на один. И в 2008 году они ее реализовали. Эта программа называется Polaris, ее улучшенная версия выиграла три из шести игр. Она пыталась воспользоваться преимуществом человеческих слабостей. Цефей этого не делает, новая программа пытается играть совершенно и не адаптироваться к своим противникам.

После Polaris Боулингу и его команде пришлось принять решение о том, что делать дальше. Они решили создать программу для более сложной покерной игры – лимитированного техасского холдема. После предварительных расчетов выяснилось, что нужно около 4-х петабайт дискового пространства (1 млн. гигабайт) просто для того, чтобы записать решение. Майкл Боулинг колебался, но другие исследователи настаивали, в конце концов, покупка петабайта дискового пространства была возможна. Но столько не понадобилось, и они обошлись 520 терабайтами. Они научились сжимать данные, и программа стала работать намного быстрее.

Теперь, когда решение для лимитированного техасского холдема в версии с двумя игроками найдено, разработчиков интересуют другие виды покера, в частности, безлимитный heads-up. Они, вероятно, не смогут решить проблему целиком, но смогут написать программу, которая сможет обыграть лучших в мире игроков. То же самое касается игры лимитированного техасского холдема с тремя игроками. Там нет никакой конкретной стратегии, так как нет гарантий избежать потерь, потому что два игрока могут объединиться против третьего. Сговор является незаконным, но это трудно определить. Некоторые люди могут делать это, даже не осознавая. Тем не менее, когда испытывали Цефей против двух других компьютеров, программа выдала неплохие стратегии. Но пока рано говорить, насколько они оптимальны.

В конечном счете, Цефей может быть использован не только для игры в покер. Программа может помочь правительству или компаниям оптимизировать свои стратегии для служб безопасности, создать график для патрульного катера или оптимизировать работу контрольно-пропускных пунктов, чтобы сбить с толку противника, который попытается использовать стратегию защиты. Программа также может быть использована для назначения лечения для больных сахарным диабетом. Если их рацион или уровень активности изменяется, то программа может найти оптимальное решение с учетом любого количества неопределенностей.

“Я заинтригован всем этим, – говорит Боулинг. – И очень хочу увидеть применение этой программы за пределами покерного пространства. У меня не хватает терпения, чтобы играть в покер. Я нахожу это занятие скучным”. Ученый только один раз играл в покер за последний год. “Единственный раз, когда я играл в покер в течение последних 12 месяцев, это когда я проверял интерфейс текущей версии программы. Я играл около 100 рук”.

Попробовать свои силы в игре в покер против Цефей можно на сайте Университета Альберты 
В избранное