Проектирование алгоритма игры 'Покер'
Содержание
Определения
Введение
. Краткие сведения из теории вероятности
. Обзор имеющихся разработок и алгоритмов
.1 Метод 1
.2 Метод 2
.3 Метод 3
.4 Метод 4
. Проектирование алгоритма
.1 Задачи
.2 Решения
. Код
. Тесты
Заключение
Список использованных источников
Определения
Ауты - карты, которые помогут игроку
улучшить свою руку. Например, для дро-рук аутами будут карты, которые дополнят
её и сделают готовой комбинацией. Количество аутов используется при расчёте
оддсов - вероятности улучшить свою руку. Существуют также дисконтированные аусы
- это более продвинутая система, в которой в аутах не учитываются карты,
которые помогут игроку, но могут дать его оппоненту выигрышную руку.
Термин "рука" может иметь
два значения:
. Конкретная раздача.
. Комбинация карт игрока, которая
составляет его руку.
Флоп - это три первых общих карты в
разновидностях покера, где есть общие карты.
Ривер - это последняя (пятая) общая
карта.
Терн - это четвёртая общая карта,
которую выкладывают после флопа.
Шансы (англ. odds) - термин,
использующийся игроками в покер для определения математического ожидания хода в
игре. Шансы обычно указываются в форме отношения ожидаемого количества побед
(совершившихся событий) к количеству поражений (несвершившихся событий),
например, 1:4, именно таким форматом будем пользоваться далее (возможно
написание 1/4). Иногда также используется обратная пропорция - шансы против
улучшения, то есть отношение поражений к победам - 4:1. Шансы можно перевести в
вероятность наступления события по формуле: кол-во побед/(кол-во побед + кол-во
поражений). Таким образом, шансам 1:4 соответствует вероятность 1/(1+4)=1/5.
Введение
Техасский холдэм (иногда просто
называемый холдэм) - самая популярная на сегодня разновидность покера.
Популярность, возможно, связана с тем фактом, что основные турниры по покеру
проводятся именно в этой разновидности игры. Техасский холдэм - пример покерной
игры с общими картами, в которой существуют карты, которые используются всеми
игроками при составлении комбинаций.
Особенно интенсивно сейчас
развивается покер в сети: существует огромное количество покер-румов, где есть
возможность сыграть партию в покер с любым человеком из любой точки мира.
Для успешной игры часто используются
различные программы-помощники. Однако, на данный момент это программа либо
платная, либо оснащена не всеми необходимыми функциями. Именно поэтому, тема
моего курсового проекта является актуальной на данный момент.
1. Краткие сведения из теории
вероятности
Вероятность (вероятностная мера) -
мера достоверности случайного события. Оценкой вероятности события может
служить частота его наступления в длительной серии независимых повторений
случайного эксперимента. Согласно определению П. Лапласа мерой вероятности
называется дробь, числитель которой есть число всех благоприятных случаев, а
знаменатель - число всех возможных случаев.
Случайная величина - это величина,
которая принимает в результате опыта одно из множества значений, причем
появление того или иного значения этой величины представляет собой случайное
событие.
Наряду со случайными событиями, как
фактами в схеме испытаний, характеризующими её качественно, результаты опытов
можно описать количественно. Это и ведёт к понятию случайной величины в теории
вероятностей. Фактически, всегда результаты опытов со схемой можно представить
количественно с помощью одной или нескольких числовых величин. Так, в конечных
схемах описаний вместо самих элементарных исходов можно рассматривать их
номиналы (идентификаторы). Например, при бросании монеты «решка» - это 0, а «орел»
- это 1; при бросании игральной кости результаты - суть номера граней от 1 до 6
и т.д.
Математическое ожидание - понятие
среднего значения случайной величины в теории вероятностей.
2. Обзор имеющихся разработок и
алгоритмов
Вычисление точных вероятностей в
покере для каждой игры, которую вы играете, может оказаться сложной
математической операцией, а времени для вычислений при игре в сети не так уж
много, особенно, если вы играете сразу на нескольких столах. Игроки имеют
различные подходы к решению этой задачи. Кто-то из них использует специальные
программы, которые вычисляют значения вероятности и шансы непосредственно во
время игры, другие запоминают вероятности для большого количества ситуаций,
третьи не считают точных вероятностей, а опираются на собственный опыт и
интуицию.
Зная свои ауты несложно подсчитать
вероятность выигрыша, для этого необходимо просто разделить их число, на
количество неизвестных карт в колоде. Например, если у вас есть 15 аутов,
вероятность на терне будет рассчитываться как P(терн) = 15 / 47 (47 = 52 карты
в колоде - 2 карманные карты - 3 карты флопа) и составит ~ 32%. Если на терне
придет карта, которая не улучшит вашу руку и не поможет сопернику, то
вероятность на ривере будет 15/46 - около 33%.
Подсчет вероятности того, что ваша
карта придет на терне или ривере несколько сложнее, чем простое суммирование
вероятностей, поскольку эти события не являются независимыми, например если туз
пик придет на терне, то уж на ривере вы его точно не дождетесь. Существует
несколько методов вычисления вероятности прихода нужного аута.
.1 Метод 1
Существует три возможных варианта,
что вы получите один из необходимых вам аутов: он придет на терне, на ривере,
или обе карты после флопа улучшат вашу руку.
(терн, не ривер) = (15/47) × (46 - 14)/46 = 0.222(не
терн, ривер) = (47 - 15)/47 × 15/46 = 0.222(терн и ривер) = 15/47 × 14/46 = 0.097
Сумма этих трех величин даст искомую
вероятность, которая для данного примера составит 0.54.
.2 Метод 2
Вероятность того, что вы получите
один из необходимых 15 аутов можно вычислить, через вероятность обратного
события - т. е. нужной карты не будет ни на терние, ни на ривере.
(терн или ривер) = 1 - (47-15)/47 × (46 - 15)/46 = 0,54
Оба предложенных метода несколько
сложны, для того, чтобы производить их на лету, да еще во время игры сразу за
несколькими столами, а потому для оценки вероятностей можно использовать
следующий метод
Быстрый метод оценки вероятности в
покере
(терн или ривер) = (4 × количество аутов -
1)%(терн) = P(ривер) = (2 × количество аутов + 1)%
Для приведенного выше примера
(терн или ривер) = (4 × 15 - 1) = 59%(терн) =
P(ривер) = (2 ×
15 + 1) = 31%
Такой точности в большинстве случаев
вполне достаточно, а вычисления настолько просты, что с ними справится даже
школьник. Осталось лишь подсчитать количество аутов и провести несложные
вычисления.
.3 Метод 3
Можно воспользоваться уже
составленной ранее таблицей шансов на улучшение:
Таблица имеет 20 строк и 3 главных
столбца с данными. По вертикали расположено количество карт, которые улучшат
руку до выигрышной, по горизонтали в ячейках - вероятности этих событий
соответственно с флопа на тёрн (открытие 1 карты), с флопа на ривер (открытие
двух карт) и с тёрна на ривер (открытие 1 карты).
Вероятности записаны в двух видах.
Первое значение в виде процента - собственно вероятность, второе значение в
виде отношения единицы к числу - шансы.
2.4 Метод 4:
Воспользоваться специальной
программой для расчета вероятности, например, pokerstove
(http://www.pokerstove.com). В этой программе, могут задаваться любые значения
комбинации рук и флопа (в том числе и произвольные у соперников), далее
программа, используя генератор случайных чисел, разыгрывает несколько миллионов
вариантов игр. Выдаёт полученные опытным путём результаты, с точностью до
тысячной процента.
Эта программа с открытым исходным
кодом, именно поэтому я выбрал её для примера. В своем курсовом проекте, по
написанию калькулятора для покера, я планирую использовать приёмы, применённые
в этой программе.
3. Проектирование алгоритма
.1 Задачи
Необходимо спроектировать алгоритм
нахождения вероятности выигрыша для нескольких игроков в том случае, если
известно, какие карты вышли, какие на столе и какие карты у каждого из игроков.
Эту основную задачу можно разбить на несколько подзадач:
Представление карт
Необходимо создать удобный формат
для того чтобы хранить информацию о картах (номер и масть).
Перебор возможных комбинаций
Реализовать грамотный перебор всех
возможных комбинаций.
Нахождение победителя
Придумать и реализовать алгоритм,
который будет правильно находить игрока с выигрышной комбинацией карт.
Расчет вероятности выигрыша
Составить функцию, которая будет
каждый раз отслеживать победителя в зависимости от карт, которые появляются на
флопе, тёрне и ривере.
Карты
Я решил использовать 16-битные
переменные:
Первые двенадцать битов отвечают за
наминал карты, последние четыре за масть (cdhs AKQJT9876543) Если все первые
двенадцать битов имеют значение «0», то это двойка.
Вот так, например, будет выглядеть
четвёрка буби 0100000000000010;
валет крести 000100010000000; двойка
черви 0010000000000000;
В программе я буду обращаться к этим
переменным по битам. Я принял решение использовать такое представление данных,
потому что оно намного удобнее, чем использование упорядоченной нумерации для
каждой из карт.
Перебор
Перебирать все возможные комбинации
карт я буду пятью вложенными друг в друга циклами (так как всего пять карт на
доске). Причём, у каждого вышестоящего цикла, число итераций будет на единицу
меньше предыдущего, это связано с тем, что с каждой картой, появившейся на
доске, число возможных выпавших карт будет уменьшаться на один.
Победитель
Для того чтобы определить победителя
я решил использовать приоритеты для каждой комбинации (от роял флеша до
обычного кикера). Каждой покерной комбинации будет соответствовать некоторое
число, причем будет учитываться и наминал карты, будь это второй кикер для сета
или первая карта у комбинации стритфлеш.
Также я буду проверять все карты на
наличие какой-либо комбинации. Каждую комбинация будет проверяться отдельной
функцией. После чего по сумме приоритетов получившихся комбинаций и будет
определён победитель текущей игры.
Расчет вероятностей
Расчет вероятности выигрыша для
каждого игрока в моей программе будет происходить по следующей схеме:
После того, как модуль нахождения
победителя определил результат это доски, он будет инкрементировать число побед
победившего игрока, в случае ничейного исхода доски будет инкрементироваться
счетчик ничьих. В конечно итоге, программа выводит процентное соотношение побед
и ничьих для каждого игрока от количества всех сыгранных рук.
4. Код
Здесь представлены фрагменты
основных функций.
.1 Перебор
Таким образом я реализовал перебор
всех возможных комбинаций.a, b, c, d, e //идентификатор карты
// перебираем все возможные варианты
доски, 5 карт
(a=0;a<48;a++) {[0] =
deck[a];(b=a+1;b<49;b++) {[1] = deck[b];(c=b+1;c<50;c++) {[2] =
deck[c];(d=c+1;d<51;d++) {[3] = deck[d];(e=d+1;e<52;e++) {[4] = deck[e];
.2 Победитель
Проверять будем по комбинациям.
Небольшой фрагмент кода
, j, ranks,= hand0lo,= hand1lo,= hand2lo,=
hand3lo;(nbrOfRanks[ranks = c | d | h | s]) {2: /* каре или фул хаус */= c
& d; /* любые две другие карты*/(!(i
& h & s)) { /* нету общего бита для всех карт*/= c ^ d ^ h ^ s; /* сет
*/Value(FULL_HOUSE) | hiBotRank[i] with(i ^ ranks); }Value(FOUR_OF_A_KIND) |
hiBotRank[i] with(i ^ ranks);3: /* сет и два кикера или две пары и кикер */((i
= c ^ d ^ h ^ s) == ranks) {
/* сет и два кикера */((i = c & d)!= 0)Value(THREE_OF_A_KIND)
| hiBotRank[i] with(i ^ ranks);((i = c & h)!= 0)Value(THREE_OF_A_KIND) |
hiBotRank[i] with(i ^ ranks);= d & h;Value(THREE_OF_A_KIND) |
hiBotRank[i](i ^ ranks); }
/* две пары и кикер; в i бит кикера */= i ^ ranks; /* в j биты
пар*/hiTopRankTWO_PAIR[j] | hiBotRank[j ^ hiRankMask[j]] | i;4: /* пара и три
кикера */= c ^ d ^ h ^ s; /* биты кикеров */Value(PAIR) | hiBotRank[ranks ^ i]
| i;5: /* нету пар */ranks;
}
4.3 Расчет вероятностей
deckIx0, deckIx1, deckIx2, deckIx3, deckIx4;_T handValue0,
handValue1;wins0 = 0, splits0 = 0, pots = 0;(deckIx0 = 0; deckIx0 <=
limitIx0; ++deckIx0) {[0] = deck[deckIx0];(deckIx1 = deckIx0 + 1; deckIx1 <=
limitIx1; ++deckIx1) {[1] = board[0] | deck[deckIx1];(deckIx2 = deckIx1 + 1;
deckIx2 <= limitIx2; ++deckIx2) {[2] = board[1] | deck[deckIx2];(deckIx3 =
deckIx2 + 1; deckIx3 <= limitIx3; ++deckIx3) {[3] = board[2] |
deck[deckIx3];(deckIx4 = deckIx3 + 1; deckIx4 <= limitIx4; ++deckIx4) {[4] =
board[3] | deck[deckIx4];= Hand_7_Eval(board[4] | holeHand[0]);=
Hand_7_Eval(board[4] | holeHand[1]);
++pots;(handValue0 > handValue1)
++wins0;(handValue0 == handValue1)
++splits0; } } } } }[0] = wins0;[1] = pots - wins0 - splits0;[0] =
splits[1] = splits0;[0] = partialPots[1] = splits0 / 2.0;
5. Тесты
покер вероятность алгоритм программный
Для тестирования программы я использовал другой калькулятор
нахождения вероятности в покере с сайта
http://ru.pokernews.com/poker-tools/poker-odds-calculator.htm.
Моя программа выдавала такие же результаты с погрешность в сотые
доли процента.
Примеры:
Моя программа при руке Qs Js против руки оппонента Ts Th выдаёт
шансы на победу 46.663618% и 47.114706% на победу или ничью. На сайте 46.66%
победа и 0.45% на ничью.
При руках 2c7d Ah As и флопе 8с 9с Kh 5s шансы совпадают
точь-в-точь с сайтом 9.090909.
Если известна только собственная рука Ts 9S и неизвестном флопе
моя программа выдаёт 52.376873% на победу, на ничью и победу 55.671884%, в то
время как на сайте шансы на победу 52.33% а на ничью 3.31%. Единственным
минусом было, то что на сайте данный подсчет велся меньше одной секунды, а моя
программа ~846 секунд.
Я считаю, что это вполне приемлемые результаты для тестирования,
но все же необходимо оптимизировать и упростить алгоритм вычисления
вероятностей в тех случаях, когда неизвестны руки соперников.
Заключение
В процессе написания моей курсовой работы я ознакомился с
различными алгоритмами подсчета вероятности в покере, а также с их
достоинствами и недостатками. Во время кодирования я столкнулся с различными
проблемами, самой сложной из них оказалось проблема определения победителя по
его комбинации. Но благодаря советам из интернета решение было найдено. Так же
была проблема с представлением карт, в ходе изучения материалов на эту тему я
принял решение об использовании именно такой системе представления карт. Еще
одной проблемой является длительное время расчета вероятностей при большом
количестве игроков, если их руки не известны. В дальнейшем планируется
оптимизировать этот алгоритм для сокращения времени расчетов.
По итогам проведенных мной тестов программа показывает очень
хорошую точность вычислений, что на данном этапе является одним из самых важных
критериев.
Сейчас программа запускается только из-под консоли, визуализация
планируется в ближайшем будущем. В перспективе моей курсовой работы реализовать
многопользовательскую сетевую игру с возможностью вывода информации о
вероятности выигрыша с той или иной комбинацией на руках.
Список использованных источников
[1] [Электронный ресурс]. URL:
://kingpokerclub.com/articles/426-raschet-veroyatnostej-v-pokere.html
[2] [Электронный ресурс]. URL:
://profitpoker.ru/articles/49-articles/120-tablica-shansov.html
[3] [Электронный ресурс]. URL:
://www.pokerstove.com/analysis/zealots.html
[4] [Электронный ресурс]. URL:
://www.safdar.net/shabbircombinatorics-texas-holdem-limit-poker.html
[5] [Электронный ресурс]. URL: ://www.betpoker.ru/holdem.html
[6] [Электронный ресурс]. URL:
://ru.wikipedia.org/wiki/Теория_вероятности
[7] [Электронный ресурс]. URL: ://pokersource.sourceforge.net/
[8] [Электронный ресурс]. URL:
://www.codingthewheel.com/archives/poker-hand-evaluator-roundup
[9] [Электронный ресурс]. URL:
://webdocs.cs.ualberta.ca/~games/poker/
[10] [Электронный ресурс]. URL: ://ru.pokernews.com/poker-tools/poker-odds-calculator.htm