Покер, LINQ и конечные автоматы.

 

Архив с проектом, описанным в этой статье находится здесь
Pocker.rar

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

Немного поразмыслив, нашел решение. Набор из пяти карт можно рассматривать как множество(коллекцию) и применив некоторые операции с множествами можно получать разные результаты, в зависимости от того, с какой комбинацией мы имеем дело. Собственно LINQ-запросы я не использовал, однако методами класса System.Linq.Enumerable пользовался активно, отсюда слово LINQ в заголовке записи.

Итак, в чем суть подхода. Выполняя некую операцию над множеством, можно получить результат, свойственный одним комбинациям, но совершенно не свойственный другим и таким образом сузить круг поиска. Дальнейшие операции(уже другие) позволят уточнить результат и с каждым таким шагом круг поиска будет сужаться пока не придем к однозначному решению. Ветвление логики проще всего изобразить графически в виде набора состояний, при достижении каждого из которых можно будет точно сказать, что данная комбинация является одной из соответствующих этому состоянию и не может быть никакой другой. Финальные состояния соответствуют одной комбинации каждое.Поскольку графическое представление более наглядно и понятно, я использовал для решения задачи рабочие процессы (Workflow). В дизайнере рабочих процессов есть конечный автомат, который и позволит нам реализовать логику распознавания.

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

VB.Net

1. Public Class Card
2.     Public Sub New(rank As CardRank, flush As Flush)
3.         Me._rank = rank
4.         Me._flush = flush
5.     End Sub
6.  
7.     Private _rank As CardRank
8.     Public ReadOnly Property Rank() As CardRank
9.         Get
10.             Return _rank
11.         End Get
12.     End Property
13.  
14.     Private _flush As Flush
15.     Public ReadOnly Property Flush() As Flush
16.         Get
17.             Return _flush
18.         End Get
19.     End Property
20.  
21.     Property RandomOrder As Integer
22.  
23.     Public Overrides Function ToString() As String
24.         Return String.Format("{0} Of {1}", Me.Rank, Me.Flush)
25.     End Function
26. End Class
27.  
28. Public Enum Flush
29.     '
30.     Spades
31.     '
32.     Clubs
33.     '
34.     Diamonds
35.     '
36.     Hearts
37. End Enum
38.  
39. Public Enum CardRank
40.     Ace = 1
41.     C2
42.     C3
43.     C4
44.     C5
45.     C6
46.     C7
47.     C8
48.     C9
49.     C10
50.     Jack
51.     Queen
52.     King
53. End Enum
54.  
55. Public Enum Combination
56.     ' .
57.     HighCard
58.     Pair
59.     TwoPair
60.     [Set]
61.     Straight
62.     Flush
63.     FullHouse
64.     Quads
65.     StraightFlush
66.     RoyalFlush
67. End Enum

Далее добавляем в проект рабочий процесс( если изначально это не был выбран шаблон проекта, в котором он уже есть).  С панели элементов добавляем конечный автомат в дизайнер рабочего процесса (StateMachine) и можно начинать колдовать. Результатом моих усилий стала схема, имеющая следующий вид

Вначале мы попадаем в состояние Инициализация набора. Здесь инициируются исключения для случаев, когда набор не соответствует нормам. У нас есть один входной аргумент Hand, представляющий набор карт, в котором надо узнать комбинацию и если коллекция не существует (аргумент не передан), состоит не из пяти карт или все пять карт одного достоинства(в колоде их может быть только четыре) – создается исключение. Можно было бы еще предусмотреть варианты, когда встречаются совпадающие карты( в колоде обычно нет повторений), но это смысла в нашей задаче иметь не будет, в силу того, что на логику распознавания комбинаций не влияет, а вот вышеперечисленные условия должны выполняться, иначе иначе все будет работать со сбоями.

Щелкнув дважды по состоянию мы входим в его структуру. В поле Entry переносим действие If, в поле Condition которого вводим следующий код

Hand IsNot Nothing AndAlso Hand.Count <> 5 AndAlso DistinctCount > 4

В поле Then переносим действие Throw, а в его свойстве Exception пишем

New ArgumentException("Входной аргумент Hand должен быть массивом, содержащим 5 карт.")

На этом первичная инициализация завершена и можно приступать к реализации логики.

Первым критерием, который можно применить к набору, может быть проверка масти. Есть комбинации, в которых все карты состоят из одной карт масти, а есть такие, в которых масти различны. Таким образом, проверив все ли карты одной масти мы сразу разобьем все возможные комбинации на две группы, в одной будут Flush, Straight Flush и Royal Flush; а в другой – все остальные.Для каждой из этих групп мы добавим по состоянию(Онда масть и Разные масти) и соединим их с уже существующим (Инициализация набора). Чтобы проверить все ли карты одной масти, надо проверить масть любой(например первой) карты, после чего посчитать сколько карт в наборе имеют такую же масть. Посчитать можно с помощью функции Count класса Enumerable, расширяющую все коллекции. Поскольку проверку эту придется проводить для обоих переходов в следующее состояние, лучше результат сохранить в переменной(переменную можно создать, кликнув слово “Переменные” в нижнем левом углу дизайнера). Я назвал ее FlushCardCount и инициировал выражением

Hand.Count(Function(c) c.Flush = Hand(0).Flush)

То есть подсчитываются те карты, у которых свойство Flush имеет то же значение, что и это же свойство у первой карты.

Теперь выделяем переход от состояния Инициализация набора к состоянию Одна масть и в свойствах пишем

DisplayName = “5 карт одной масти”
Condition = “FlushCardCount = 5”

С переходом к состоянию Разные масти надо сделать то же, только там переменная не должна равняться 5, ну и текст перехода тоже должен быть соответствующим.

Если у нас одна масть, то возможны три варианта комбинаций: Flush, FlushStright или RoyalFlush.

Начнем с RoyalFlush. Эта комбинация возникает, когда мы имеем карты: туз, десятка валет дама и король. При этом замечаем, что карты с 2 по 9 отсутствуют. Кроме того, учитывая, что мы разбираем вариант игры с одной колодой, можно сказать точно, что если в наборе из пяти карт одной масти отсутствуют карты с двойки по девятку, то это RoyalFlush, поскольку в колоде 13 карт одной масти и если 8 из них отсутствуют, а остальные не повторяются( это условие выполняется благодаря тому, что мы имеем одну колоду, стало быть быть двух карт одной масти и одного достоинства быть не может), значит эти пять карт и есть остальные 5 карт данной масти. Таким образом нам нужно проверить, что карты с 2 до 9 отсутствуют. Результат проверки наличия карт этого диапазона мы сохраним в переменную, поскольку аналогичную проверку придется проводить и для комбинации Straight и нет смысла делать это дважды.

Создаем переменную NonBetween1And10 и инициируем ее выражением

NonBetween1And10

1. Hand.Count(Function(c) c.Rank > CardRank.Ace AndAlso c.Rank < 10) = 0

Теперь добавляем элемент FinalState, соединяем его с состоянием Одна масть, в условии перехода указываем NonBetween1And10. Меняем DisplayName на RoyalFlush.

Теперь нам нужно создать выходной параметр Result, который будет выводить найденную комбинацию. Открываем раздел с параметрами, указываем имя Result, направление – выходной, тип – Combination. После этого раздел с параметрами можно закрыть.

Дважды щелкнув по состоянию RoyalFlush перетащим в поле Entry действие Assign. В левом поле укажем Result, в правом – Combination.RoyalFlush. Таким образом, если наш процесс дойдет до этого состояния, то завершившись он возвратит именно это значение.

Для комбинаций FlushStraight и Flush рассмотрим конкретный пример, ну скажем (2,3,4,5,6). В данном случае, если мы вычтем из максимального числа минимальное, то получится 4. Учитывая, что карты не повторяются(одна масть одной колоды), можно точно сказать, что если эта величина равна 4-м, то это FlushStraight, в ином случае – просто Flush. Таким образом нам надо ввести переменную RankRange и инициировать ее выражением

RankRange

1. Hand.Select(Function(c) c.Rank).Max - Hand.Select(Function(c) c.Rank).Min

Далее добавляем еще два финальных состояния, соединяем их с “Одной мастью”, в условиях проверяем значения RankRange на равенство четырем, меняем названия и добавляем присвоение значение параметру Result, аналогично тому, как это было сделано для комбинации RoyalFlush.

Теперь перейдем к состоянию Разные масти. Если в наборе разные масти, то все такие комбинации можно разделить на две группы: комбинации, в которых присутствуют карты одного достоинства и те, в которых достоинства не повторяются. То есть следующим шагом будет добавление еще двух состояний, соответствующих указанным случаям. Проверить повторяемость достоинств мы можем с помощью функции Distinct, которая удаляет повторяющиеся элементы из коллекции, стало быть применив эту функцию можем просто проверить изменилось ли количество элементов, если да – значит есть повторы.

Создадим переменную RankCount и инициируем ее выражением

RankCount

1. Hand.Select(Function(c) c.Rank).Distinct().Count

Эта переменная показывает количество достоинств в наборе. Ну то есть, если весь набор состоит из двоек пятерок и королей, то эта переменная будет иметь значение – 3.

Ну и соответственно для перехода к состоянию Есть повторы эта переменная должна быть меньше 5, а для перехода к состоянию Нет повторов – равняться 5.

Если повторов нет, значит это либо Straight, либо HighCard (проигрышная комбинация).Таким образом к состоянию Нет повторов добавляем два финальных состояния с именами соответствующих комбинаций, каждое из которых будет инициировать параметр Result соответствующим значением. Для определения условий перехода в эти состояния у нас уже есть готовые переменные (RankRange и NonBetween1And10), так что нам нужно только проверить их значения. В условии перехода к Straight пишем

Straight

1. RankRange = 4 OrElse NonBetween1And10

Ну и соответственно в условии перехода к HighCard пишем

HighCard

1. RankRange <> 4 AndAlso Not NonBetween1And10

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

Pair

1. RankCount = 4

То есть, если количество достоинств в коллекции равно 4, это значит, что мы имеем дело с одним повтором, то есть присутствует одна пара карт одного достоинства, все остальные разные.

Создадим еще одну переменную и назовем ее MaxRankCount. Эта переменная будет отображать наибольшее количество карт одного достоинства. То есть для каре ее значение будет равно 4, а для фуллхауса – 3. Выражение, которым мы инициируем эту переменную будет иметь следующий вид.

MaxRankCount

1. Aggregate c As Card In Hand Select Hand.Count(Function(x) x.Rank = c.Rank) Into Max()

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

Нетрудно понять, что Quads – единственная комбинация, для которой эта величина будет равна 4. По этой причине сразу можно добавить финальное состояние и в условии перехода к нему выполнить проверку

Quads

1. MaxRankCount = 4

Для двух пар эта переменная будет иметь такое же значение как и для пары, но зато переменная RankCount здесь будет иметь значение 3, а не 4.

TwoPair

1. MaxRankCount = 2 AndAlso RankCount = 3

А вот для FullHause и Set можно создать еще одно промежуточное состояние с условием

FullHouse или Set

1. MaxRankCount = 3

Однако RankCount для FullHouse будет равно 2, а для Set – 3, что и следует отобразить в условиях перехода к финальным состояниям. В каждом финальном состоянии выходной параметр Result инициируется соответствующим состоянию значением. И на этом построение рабочего процесса завершено и можно переходить к коду.

Для того, чтобы можно было работать с этим рабочим процессом в коде, его вызов надо обернуть в функцию. В моем проекте класс рабочего процесса называется CombinamionTester и код выглядит следующим образом.

GetCombination

1. Public Function GetCombination(hand As Card()) As Combination


2.     Dim tester = New CombinationTester()


3.     Dim res = WorkflowInvoker.Invoke(tester, New Dictionary(Of String, Object)() From {{"Hand", hand}})


4.     Return res("Result")


5. End Function

Функция принимает массив из пяти карт и возвращает элемент перечисления Combination.

Для проверки работы функции создадим модульные тесты. Добавляем в решение проект тестов, добавляем в этот проект ссылку на тестируемый проект, импортируем в код класса теста пространство имен, в котором определена тестируемая функция( у меня рабочий процесс создан в консольном приложении и функцию я определил прямо в главном модуле, только ему надо присвоить модификатор Public).

Для начала определим пару вспомогательных методов для теста, чтобы сам тест не разросся.

CreateHand

1. Function CreateHand(ParamArray intvalues() As Integer) As Card()


2.     Return New Card() {


3.          New Card(intvalues(0), intvalues(1)),


4.          New Card(intvalues(2), intvalues(3)),


5.          New Card(intvalues(4), intvalues(5)),


6.          New Card(intvalues(6), intvalues(7)),


7.          New Card(intvalues(8), intvalues(9))


8.          }


9. End Function

Данная функция создает массив из пяти карт и для этого ей надо передать набор из десяти чисел, каждое из которых соответствует элементам перечислений Flush и Rank. В аргументах они идут попарно, то есть если я хочу, чтобы первой картой был туз пик, я передаю первые два аргумента – 1 и 0, так как 1 соответствует тузу в перечислении Rank, а ноль – пикам в перечислении Flush. Следующие восемь чисел следуют тому же принципу.

TestCombination

1. Sub TestCombination(comb As Combination, ParamArray ints() As Integer)


2.     Dim hand = CreateHand(ints)


3.     Dim testedcomb = GetCombination(hand)


4.     Assert.AreEqual(comb, testedcomb, String.Format("{0}   {1}.", comb.ToString, testedcomb.ToString))


5. End Sub

Метод TestCombination тестирует одну комбинацию. Первый аргумент задает ожидаемый результат, а второй – набор чисел, передаваемый функции CreateHand и следующий той же логике. В этом наборе карты должны составлять ту же комбинацию, что описывает первый аргумент метода.

Ну и собственно сам код теста

TestGetCombinationMethod

1. <TestMethod()> Public Sub TestGetCombinationMethod()


2.      TestCombination(Combination.HighCard, 1, 0, 3, 1, 5, 0, 7, 2, 9, 3)


3.      TestCombination(Combination.Pair, 1, 0, 1, 1, 5, 0, 7, 2, 9, 3)


4.      TestCombination(Combination.TwoPair, 1, 0, 1, 1, 5, 2, 5, 3, 9, 3)


5.      TestCombination(Combination.Set, 1, 0, 1, 1, 1, 2, 5, 3, 9, 3)


6.      TestCombination(Combination.Set, 5, 3, 9, 3, 1, 0, 1, 1, 1, 2)


7.      TestCombination(Combination.FullHouse, 1, 0, 1, 1, 1, 2, 5, 3, 5, 2)


8.      TestCombination(Combination.Quads, 1, 0, 1, 1, 1, 2, 1, 3, 9, 3)


9.      TestCombination(Combination.Flush, 1, 0, 3, 0, 4, 0, 7, 0, 10, 0)


10.      TestCombination(Combination.StraightFlush, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0)


11.      TestCombination(Combination.RoyalFlush, 1, 1, 10, 1, 11, 1, 12, 1, 13, 1)


12.      TestCombination(Combination.Straight, 7, 0, 8, 2, 9, 3, 10, 1, 11, 1)


13.      TestCombination(Combination.Straight, 1, 3, 10, 0, 11, 2, 12, 3, 13, 1)


14.  


15.  End Sub

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