2
$\begingroup$

I am trying to find the best poker hand in a connected grid, where order matters. An illustration is the best way of explaining the situation.

3x4 connected grid of playing cards

This grid has 12 random cards, in random positions. Each card is connected to the vertically, horizontally and diagonally adjacent cards.

The hands are standard poker hands but no extra cards are allowed – only the cards which constitute the hand. So, a pair is only two cards connected, four of a kind is just four cards connected, etc.

The best hand for this grid highlighted: The best hand in this case, a two pair: 10s and Aces

Order matters, so a straight must be in the correct order (e.g. 10, J, Q, K, A is valid but 10, A, J, Q K is not). There is no straight in this particular grid, the 10s are not connected to the Jack directly.

An invalid straight, the cards must be connected in the correct order

I am looking for an algorithm that finds the best hand for a random grid. The grid isn’t ever going to be much larger than this grid of 12.

I am also looking for an algorithm that finds out if there are no moves at all – this would alert the player to this fact to save them searching for too long…

$\endgroup$
0
$\begingroup$

I recommend you use breadth-first search (BFS) through the state space.

Start by trying to find (partial) straights that are ascending. For each possible starting position (there are 12 possibilities), use BFS to search for a path that starts at that position and makes an ascending straight (i.e., the numbers increment by one each time you move forward). This will find you the longest ascending straight.

Next search for descending (partial) straights in the same way. This will find you the longest descending straight.

You can also search for straight flushes in this way, too.

Next for x-of-a-kinds in the same way. This will find you the longest sequence that are all of the same rank (e.g., two-of-a-kind, three-of-a-kind, four-of-a-kind, five-of-a-kind).

Next search for flushes in the same way. This will find you the longest sequence that are all of the same suit.

You can look for two-pair and full-house separately, with a different method tailored to that problem. Enumerate all pairs (i.e., all pairs of adjacent positions where the two cards have the same rank). Now check whether any two of those pairs are adjacent; if so, you have found a two-pair. Similarly, enumerate all three-of-a-kinds (i.e., paths of length 3 where the three cards have the same rank). Now check whether any pair is adjacent to any three-of-a-kind; if so, you have found a full-house.

In this way you can find the best poker hand in the grid. I expect that this will be very efficient.

$\endgroup$
  • $\begingroup$ Thanks D.W. BFS ended up being very fast in finding all possible hands from the grid $\endgroup$ – Matt Aitken Jan 27 '18 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.