Алгоритм подсчета покерной руки

[Vadikan]

Доброго времени суток!

Вот добрался я и до этого форума :) Сразу скажу, что программист я никакой, и весь мой опыт программирования сводится к нескольким заданиям в рамках курса VB.NET в универе. Курс предназначен для людей, не имеющих опыта программирования, и знакомит с элементарными понятиями. Поскольку курс преподается на англ. языке, я знаю только английскую терминологию. Предположу, что array - массив, a data structure - структура данных.

Финальный проект курса формулируется так. Надо сгенерировать колоду карт на 52 листа. Сначала нужно создать структуру данных, у которой два члена: face (номинал карты) и suit (масть). Затем нужно сформировать массив, который и будет наполнен 52 картами. Затем нужно сгенерировать 5 случайных уникальных номеров от 0 до 51 (или от 1 до 52) и на основе этих номеров сформировать покерную руку. Ну и самое главное - определить покерную комбиниацию, которая получится в рез-те. Покерные комбинации такие

Flush (все одной масти)
Четверка (четыре карды одного номинала)
Full house (3+2)
Тройка
Две пары
Пара
Ничего

Как видите, вариант упрощенный - straight (стрит) подсчитывать не нужно (курс-то для начинающих ;-) Ну и вывести надо 5 карт и название комбинации. Никаких картинок карточной колоды, все в текстовом виде.

Затрудненения у меня вызвали пять уникальных случайных кард и алгоритм подсчета покерной руки. С пятью уникальными картами я вроде разобрался относительно легко.

Прикрепленный файл (http://forum.oszone.net/attachment.php?attachmentid=528)

Если я что-то упустил, то буду признателен, если вы укажете на ошибки.

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

Основная идея: в руке не может быть более двух различных совпадающих номиналов карт. Т.е. если есть два туза и два короля, то пятой карте пары уже точно не будет. Значит надо подсчитать сколько раз совпали два различных номинала.

Прикрепленный файл (http://forum.oszone.net/attachment.php?attachmentid=529)

Ну а дальше уже детали. По порядку проверяем следующие условия:

Если все карты одной масти, то flush (масти берутся из массива на основе 5 уникальных чисел, сгенерированных ранее)
Если первый счетчик равен 4, то у нас четверка.
Если счетчики 3+2 или 2+3, то у нас full house.
Если первый счетчик равен 3, то тройка (причем, второй счетчик может быть равен 3 только в случае 2+3).
Если счетчики 2+2, то две пары.
Если первый счетчик равен 2, то пара (причем второй счетчик может быть равен 2 только в случае 3+2 или 2+2)
Ну а во всех остальных случаях нету даже пары.


Вот так я себе это представил, и вроде даже работает. Буду признателен, если вы проверите алгоритм на наличие ошибок или предложите более оптимальный вариант. Может где-то есть лишние шаги, которые можно убрать, упростив код.

Спасибо за внимание.

P.S. Полный код проекта прикреплен.

[hasherfrog]

Немного путанно или я старый уже, мозги усохли :] Можно уточнить условия?

>> Затем нужно сгенерировать 5 случайных уникальных номеров от 0 до 51 (или от 1 до 52) и на основе этих номеров сформировать покерную руку

Что такое "сформировать покерную руку"? Нужно просто рандомом (следя за неповторяющимися номерами) выбрать 5 чисел от 1 до 52? И всё? Так? Т.е. "сдать пять карт"?

>> Ну и самое главное - определить покерную комбиниацию, которая получится в рез-те.

Опять непонятно. Честно, я не очень понимаю. Нужно просто сказать, какая комбинация карт получилась из сданных пяти? Так? Т.е. никаких подсчётов вероятностей, никаких"взять ещё три" и "сколько сдать карт, чтобы получить флэш" и т.д.?

[hasherfrog]

Тасование колоды:
Алгоритм #4.

1. ячейки вектора инициализируются значениями своих индексов
2. R{ight} ← N {"текущая" длина вектора}
3. генерируется случайное число K из интервала 1..R
4. обмен содержимым между K-й и R-й ячейками
5. R ← R-1
6. if R = 1 then Exit
7. переход к шагу 3

Приведенный механизм известен под именем алгоритма "тасования колоды". Его легко переписать, используя уже знакомые нам процедуры, приходится лишь заменить интервал 0..N-1 на 1..N.

type
index = 1..N; {N>1}
massive1 = array [index] of index;

procedure RandomN(var Mas: massive1);
var i, K: index;
begin
for i := 1 to N do Mas[i] := i;
Randomize;
for i := N downto 2 do begin
K := Random(i) + 1;
Swap(Mas[K], Mas[i]);
end;
end;

Соответственно, получение 5 карт можно дать так:
1. Инициализируем массив, от 1 до 52, Перемешиваем массив - RandomN()
2. Берём его первые 5 элементов.

[hasherfrog]

Масть - номер карты (0-51) mod 4 (остаток от деления) 0 - пики... 3 - бубны
Номинал - номер карты (0-51) / 4 (целочисленное деление) 0 - двойка ... 12 - туз

[hasherfrog]

Проверку на флеш делаем очень быструю, без массивов.
Флеш - это когда K[0]%4 == k[1]%4 == k[2]%4 == k[3]%4 == k[4]%4
% - остаток от деления
== - равно
Сорри за мой С :-Р

Поверки по номиналам даём с использованием промежуточного массива.
1. Делаем пустой масив номиналов S размером от 0(двойка) до 12 (туз), итого 13 элементов.
2. Инициализируем его нулями - это счётчики встреч
3. Для каждой карты K из массива k[0..4](пять карт) увеличиваем счётчик номинала.

для i от 0 до 4
счётчик[K[i]/4] ++
/ - целочисленое деление
++ - увеличение на 1.

Далее сортируем массив S (счётчиков номинала по возрастанию) и проверяем результат:
1. если первый элемент стал 4 - "каре".
2. если первый элемент стал 3:
2а. если второй элемент равен 2 - "полный дом".
2б. если второй элемент равен 0 или 1 - "тройка"
3. если первый елемент равен 2:
3а. если второй элемент равен 2 - "две пары".
3б. если второй элемент равен 0 или 1 - "пара"

Комбинации "туз" и "стрит-флеш" тоже легко вычисляются.

Осталось только расписать "сортируем массив счётчиков" - это простая пузырьковая сортировка, например. Или чего-нибудь продвинутое :]

[hasherfrog]

Сортировка (два-три метода)
http://www.relib.com/articles/article.asp?id=197

[Vadikan]

hasherfrog
LOL Т.е. "сдать пять карт"?Да, пять неповторяющихся карт. Нужно просто сказать, какая комбинация карт получилась из сданных пяти?Ок, можно и так сказать. Не вижу принципиальной разницы между этим и тем, что я сказал :) Наверное, твой вариант проще :) Спасибо за ответы.

Насчет тасования колоды я понял идею, но не слишком понял реализацию. Что делает следующий код?
for i := N downto 2 do begin
K := Random(i) + 1;
Swap(Mas[K], Mas[i]);
Конкретнее, downto2 do begin вообще непонятно, сорри.

А для подсчета совпадений номиналов твой вариант действительно проще. Общая идея, как я вижу, такая же: отталкиваемся от факта, что у нас не более двух различных совпадающих номиналов карт. Однако исполнение намного проще. Мне как-то в голову не пришло использовать целочисленое деление :confused:
Я сделал так. Допустим, у меня уже есть массив Hand(4), 5 элементов которого являются случайными числами от 0 до 51. Теперь создается массив HandFaces(12) для номиналов

Dim HandFaces(12) As Integer
For i = 0 To 12
HandFaces(i) = 0
Next
и все элементы наполняются нулями. Затем для каждого элемента из массива Hand выполняется целочисленное деление, получившееся число становится индексом массива HandFaces и значение данного элемента увеличивается на единицу.

For i = 0 To 4
HandFaces(Hand(i) \ 4) += 1
Next

Я правильно понял? Затем массив HandFaces сортируется. Я, честно говоря, не знаю как отсортировать в обратном порядке. Поэтому мне нужно смотреть на последний и предпоследний элементы. Правильно?

[hasherfrog]

>> Правильно?
Ну да :]

Кстати... Я только сейчас увидел, что дал кусок про тасовку карт на паскале... :-P
LOL, даже ROTFLMAO

По-русски :] это будет так:
Sub shuffle()
'массив карт
Dim L(0 To 51) As Integer

'инициализация колоды
For I = 0 To 51 Step 1
L(I) = I
Next I

'печать для екселя - надо же что-то узреть :)
For I = 0 To 51 Step 1
Worksheets(1).Cells(I + 1, 1).Value = L(I)
Next I

'тасовка
For I = 51 To 0 Step -1
R = Int(52 * Rnd)
If R <> I Then
T = L(R): L(R) = L(I): L(I) = T
End If
Next I

'снова печать - результат тасования
For I = 0 To 51 Step 1
Worksheets(1).Cells(I + 1, 2).Value = L(I)
Next I

End Sub

[Vadikan]

hasherfrog
Да я уже разобрался как отсортировать массив в обратном порядке. На самом деле мне это не нужно, без разницы какой элемент использовать для подсчета сопвадений.
Кстати, хорошая идея с Масть - номер карты (0-51) mod 4 (остаток от деления) 0 - пики... 3 - бубны
Номинал - номер карты (0-51) / 4 (целочисленное деление) 0 - двойка ... 12 - тузЯ "подсократил" колоду сразу. В задании сказано создать структуру, состоящую из мастей и номиналов. Вот я "заполнял" мастями все 52 карты. На самом деле достаточно 13 по числу номиналов, и четыре масти обозначить. А потом уже из них по твоему методу все брать.

Спасибо за пояснения по тасовке колоды. Я понял теперь :) Ты с VB на Си, a потом на паскаль прыгаешь, совсем меня запутал. Я же сказал, что я начинающий ;) На самом деле, я вижу преимущества такого метода вообще, т.к. если надо сдать две руки, то берутся просто следующие пять элементов массива. В моем же случае с одной единственной рукой я, пожалуй, оставлю свой код. Нет нужды в создании массива на 52 элемента, если нужно всего 5. Логично?

Признателен за ответы :up:

[hasherfrog]

У-ё.
Неправильно я расписал тасовку. Так тужился, вспоминая васик... :] Переупростил код и потерял смысл использования -1. Надо так:
'тасовка
For I = 51 To 1 Step -1
R = Int((I + 1) * Rnd)
If R <> I Then
T = L(R): L(R) = L(I): L(I) = T
End If
Next I

>> Я же сказал, что я начинающий
Стоит только начать... ;]
Удачи при сдаче.

[Vadikan]

hasherfrog
В общем, преподаватель сказал, что все очень хорошо и добавлять ничего не надо. Конечно, оговорился, что при финальной проверке может что-то и всплывет :)

Ладно, я тут подумал как подсчитывать straight на основе массива, который содержит счетчики номиналов. Пусть он будет массив S. Не сортируя его я могу задать поиск первого элемента, содержащего единицу
i=Array.IndexOf(S,1)
a затем рассматривать следующие варианты
i<0
элементов содержащих единицу нет, значит неповторяющихся номиналов нет. Это возможно только в случае 3+2 - значит Full House
i=0
Самый первый элемент массива имеет значение 1. Значит у нас в руке один Ace. Проверяем на наличие straight
Если А2345, что выражается как S(0)=S(1)=S(2)=S(3)=S(4) или 10JQKA, что выражается как S(0)=S(9)=S(10)=S(11)=S(12), то у нас straght, в противном случае сортируем массив и проверяем совпадение номиналов (на full house уже проверять не надо).
i<=8
Проверяем на наличие straight снова таким образом. Если S(i)=S(i+1)=S(i+2)=S(i+3)=S(i+4), то у нас straight. В противном случае сортируем массив и проверяем совпадение номиналов.
i>8
В этом случае straight уже быть не может, т.к. 9й элемент массива - десятка. Просто сортируем массив и проверяем совпадение номиналов.

Единственное, что три раза один и тот же код сортировки и сравнения номиналов вставлять не хочется, надо как-то это иначе оформить. Но идея такая.

[hasherfrog]

Vadikan
Эммм. Я бы исходил из того, что стрит (правильно я интерпретирую straight?) - это пять _разных(1) по номиналу, но _последовательных(2) карт.
1. Т.о. предварительную проверку на стрит можно делать уже после определения всех остальных комбинаций. Стрит получится, только если нет даже пары. Ведь все карты должны быть _разные по номиналу. Единственное, что нельзя учитывать - это флеш. Поэтому проверку на флеш стоит делать уже _после проверки на стрит (и до проверки на стрит-флеш aka флеш-рояль, емнип).
2. "Последовательность" можно определить двумя способами.
2а. Сданные карты должны дать в массиве счётчиков единицы в пяти последовательных ячейках (до сортировки по номиналу - то есть проверку на стрит надо делать самой-самой первой). Проверка такая: для i=0 to (12 - 5) если S[i]==S[i+1]==S[i+2]==S[i+3]==S[i+4] (и, кстати, == 1), то стрит.
2б. Можно опираться на номинал. Взять промежуточный массив из 5 элементов, заполнить его номиналами карт (K/4). Отсортировать по увеличению. И проверить, если будет T[0]==T[1]+1==T[2]+2==T[3]+3==T[4]+4, то стрит.

Единственное, что я не помню... Туз-король-дама-валет-десять - это стрит. А вот считается ли туз-двойка-тройка-4-5 за стрит??? Ентих покеров, афаик, штук десять разновидностей. В какой ваш перпод играет???

P.S. Ну а стрит-флеш, это когда есть стрит и есть флеш :]

OOOPS. Заметил несуразность. Надо делать проверку до сортировки. И тут же - надо делать проверку после сортировки :] Выходит так, что придётся делать не сильно оптимизированную программу. Либо немного запутанную по логике.

[hasherfrog]

Т.е. вариант в п. 2а. подходит без учёта п 1. - заполняем массив номиналов, прогоняем 2а, сортируем, дальше проверяем остальные комбинации.

Либо заполняем массив номиналов, сортируем, проверяем остальные комбинации, затем, если ничего нет, прогоняем 2б.

[Vadikan]

hasherfrog
Надо делать проверку до сортировки. И тут же - надо делать проверку после сортировки :] Вот-вот :)
По пункту 2а. Да вроде я таки делаю. (и, кстати, == 1)ну я же сказал, что ищу первый элемент, который равен единице, с ним же и остальные сравниваю.
По пункту 2б. Еще один промежуточный массив не очень хочется делать. Это уже третий получается...
Туз-король-дама-валет-десять - это стрит. А вот считается ли туз-двойка-тройка-4-5 за стрит???
Я вроде учел оба варианта :) Для этого i=0 выделено в отдельный пункт.

[hasherfrog]

Vadikan
Спешил я, невнимательно прочёл :] У тебя же всё и расписано по полочкам, LOL.
Меня сбило с толку IndexOf, я сразу полез делать своё самостийное решение :]
Таки да, всё правильно, так и делай.

[Vadikan]

hasherfrog
Да, мне тоже показалось, что ты не столько мое решение проверял, сколько свое продвигал ;) Я уже сделал: алгоритм сравнения повторющихся номиналов запихал в subroutine, и все работает как надо. Со straight-flush я не стал заморачиваться, и так уже сделано больше, чем требовалось в проекте. Бонусных очков все равно не предусмотрено...

[Vadikan]

Зашел сейчас на страничку курса почитать письма сокурсников. В день сдачи проекта сразу несколько человек писали письма с вопросами о том, как им оценить покерную руку. Учитывая то, что как сгенерировать колоду фактически об'яснялось в лекциях, то непонятно чем люди занимались раньше :) Но речь не об этом. Преподаватель ответил сразу всем студентам, а не только тем, кто задавал вопрос. Он об'яснил, что надо считать совпадения номиналов, и сказал, что обычно студенты пишут очень болшие блоки IF/ELSE (бедные преподы потом в них разбираются ;-), но поскольку для вычисления "Пары" понадобится проверка десяти условий, то проблему подсчета совпадений номиналов он бы решил так:

For i = 0 to 4
For j = 0 to 4
If hand(i).face = hand(j).face AndAlso i <> j
matches += 1
End If
Next j
Next i
hand(i).face - берется из структуры данных (колоды) созданной раннее. Весьма компактно, и мне такое в голову не пришло. Тем не менее решение с массивом позволяет также просчитать и straight. Но по условиям проекта straight считать не надо было...

[aESThete]

Vadikan
имхо этот кусок кода определит только то, что на руке есть что-то "не меньше пары", а вот что именно... тут подумать надо
а с преподом согласен, циклы всегда лучше/универсальнее (вдруг кому-то в голову придет сделать 6-карточный покер :))

[Vadikan]

aESThete
Мда... я вот сейчас посмотрел внимательнее... Не удивительно, что мне такое в голову не пришло :) Как ни крути, но придется работать с двумя числами, представляющимии совпадения номиналов. Я-то изначально два счетчика делал (второй прикрепленный файл), хотя там наверное можно было упростить как-то.

[aESThete]

Vadikan
счетчиков д.б. не два, а массив счетчиков (можно плавающий, можно по кол-ву номиналов...)
тогда достигаем нужной гибкости:
For i = 0 to 4
For j = 0 to 4
If hand(i).face = hand(j).face And i <> j then
matches(face) += 1
End If
Next j
Next i
соответственно затем:
For i = 0 to maxfaces
if matches(i) = 2
pairs += 1
elseif matches(i) = 3
threes += 1
elseif matches(i) = 4
kare += 1
endif
Next i
это и красиво, и будет работать при любом кол-ве карт в руке, т.е. покажет все пары, тройки и каре... :)