Проектирование алгоритма игры "Покер"

 

Содержание

Определения

Введение

. Краткие сведения из теории вероятности

. Обзор имеющихся разработок и алгоритмов

.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 (#"justify">Эта программа с открытым исходным кодом, именно поэтому я выбрал её для примера. В своем курсовом проекте, по написанию калькулятора для покера, я планирую использовать приёмы, применённые в этой программе.

3. Проектирование алгоритма

.1 Задачи

Необходимо спроектировать алгоритм нахождения вероятности выигрыша для нескольких игроков в том случае, если известно, какие карты вышли, какие на столе и какие карты у каждого из игроков. Эту основную задачу можно разбить на несколько подзадач:

Представление карт

Необходимо создать удобный формат для того чтобы хранить информацию о картах (номер и масть).

Перебор возможных комбинаций

Реализовать грамотный перебор всех возможных комбинаций.

Нахождение победителя

Придумать и реализовать алгоритм, который будет правильно находить игрока с выигрышной комбинацией карт.

Расчет вероятности выигрыша

Составить функцию, которая будет каждый раз отслеживать победителя в зависимости от карт, которые появляются на флопе, тёрне и ривере.

.2 Решения

Карты

Я решил использовать 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;_ThandValue0, 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. Тесты

покер вероятность алгоритм программный

Для тестирования программы я использовал другой калькулятор нахождения вероятности в покере с сайта #"justify">[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

Содержание Определения Введение . Краткие сведения из теории вероятности . Обзор имеющихся разработок и алгоритмов .1 Метод 1 .2 Метод 2

Больше работ по теме: