Set Selectors

I am writing a poker game, and I got mildly annoyed when I went to write the hand classification functions. There was a disparity between the specification and implementation of poker hands; I had to come up with an algorithm to match each type. I didn’t like this, I want the code to match the specification more directly.

This is quite a geeky post. The types of poker hands are very unlikely to change, and the amount of time I’ve spent thinking about this problem already is many times that of solving it directly in the first place. I.e. it would be stupid for someone to pay me by the hour to solve it this way. Still, it gives rise to an interesting generalization that could be very useful.

I decided that the way I would like to specify these things is with “set selectors” over logical expressions. That is, given a finite set U, find a subset R of U such that some logical expression holds in R (i.e. all quantifiers are bounded on R).

This has a straightforward exponential time solution. I’m trying to do better.

I started by classifying logical expressions. In the following, let P(…) be quantifier-free.

• $\exists x P(x)$ is straightforward $O(n)$.
• More generally, $\exists x_1 \exists x_2 \ldots \exists x_k P(x_1, x_2, \ldots x_k)$ is straightforward $O(n^k)$.
• $\forall x P(x)$ is also $O(n)$ to find the largest solution (because the empty set would satisfy it, but that’s not very interesting).
• $\exists x \forall y P(x,y)$ has an obvious solution, same as $\exists x. P(x,x)$. There is no unique largest solution, but there is a unique largest for each x which can be found in $O(n^2)$ time. It’s unclear what the library should do in this scenario.
• $\forall x \forall y P(x,y)$ is called the Clique problem and is NP-complete! Damn!

But the most interesting one so far is the case: $\forall x \exists y P(x,y)$. It turns out that there is a unique largest solution for this, and here is an algorithm that finds it:

Given a finite set U, find the largest subset R such that $\forall x \! \in \! R \, \exists y \! \in \! R \, P(x,y)$.

Let $r_0 = U, r_{n+1} = \{ x \in r_n | \exists y\!\in\!r_n \, P(x,y) \}$. That is, iteratively remove x’s from r that don’t have corresponding y’s. Then define the result $R = \bigcap_i r_i$.

Lemma. There is a natural number $n_f$ such that $r_{n_f} = R$.

Proof. Follows from finite U and $r_{n+1} \subseteq r_n$.

Theorem. $\forall x \! \in \! R \, \exists y \! \in \! R \, P(x,y)$.

Proof. Given $x \in R = r_{n_f} = r_{n_f + 1}.$ Thus there exists $y \in r_{n_f} = R$ such that P(x,y), by the definition of $r_{n_f+1}$.

Theorem. If $R^\prime \subseteq U$ and $\forall x \! \in \! R^\prime \, \exists y \! \in \! R^\prime \, P(x,y)$, then $R^\prime \subseteq R$.

Proof. Pick the least n such that $R^\prime \not\subseteq r_n$. There is an $x \in R^\prime$ with $x \not\in r_n$. The only way that could have happened is if there were no y in rn-1 with P(x,y). But there is a y in R’ with P(x,y), so $R^\prime \not\subseteq r_{n-1}$, contradicting n’s minimality.

The time complexity of this algorithm can be made at least as good as $O(n^2 \log n)$, maybe better.

While that was interesting, it doesn’t really help in solving the general problem (which, I remind myself, is related to poker, where all quantifiers will be existential anyway!). The above algorithm generalizes to statements of the form $\exists w_1 \exists w_2 \ldots \exists w_j \forall x \exists y_1 \exists y_2 \ldots \exists y_k \, P(w_1,w_2,\ldots w_j,x,y_1,y_2, \ldots y_k)$. Each existential before the universal adds an order of magnitude, and I think each one after does too, but I haven’t thought it through.

In fact, I think that, because of the clique problem, any statement with two universal quantifiers will take exponential time, which means I’m “done” (in a disappointing sort of way).

Back to the real world, I don’t like that finding a flush in a hand will take $O(n^5)$ time (16,807 checks for a 7-card hand, yikes), when my hand-written algorithm could do it in $O(n)$. I’m still open to ideas for specifying poker hands without the use of set selectors. Any ideas?