Are poker hands Ord or PartialOrd?

I really like that HandValue approach.

You can define Eq and Ord on a HandValue because it makes logical sense for two HandValue::TwoPair { Ace, Four } values to be compared or hashed without the "two sets of cards that are different but still compare equal" problem you have when representing cards directly.

It also gives you something you can print to the user, which is nice.

5 Likes

You could define several orders for poker hands. I assume we're talking about an order that reflects the "value" of the hand. Such an order where some items may be ranked equally is, mathematically speaking, a "total preorder" (see Wikipedia here and there).

But there are more ways to define orders for poker hands, for example you could lexicographically order them, etc.

That depends on definition of equality. Mathematically they are not the same objects (i.e. not "equal" in the mathematical sense), but they are in the same equivalence class, if you consider their value. Thus you could say they are "equivalent" in regard to their value (see also Wikipedia on Equality and Equivalence).

This is partially reflected in the documentation of std::ops::Eq where it says:

Trait for equality comparisons which are equivalence relations.

It says "equality comparison" but clarifies that actually equivalence relations are meant.

I started a longer thread a while ago on Traits in std::cmp and mathematical terminology, in which I wrote:

The important point here is: Whether Ord is a "total order" or a "total preorder" (the latter allows two different objects to be ranked equal, which you would need for poker hands) depends on how == is implemented in the particular case. When == is implementing mathematical equality, then Ord can't be a total preorder. However, if you implement == in a way that two different (mathematically non-identical) values may return true when compared with ==, then Ord is (mathematically speaking) not a total order but a total preorder, i.e. exactly what you need for the poker hands!


Theory aside, let's look at the return values of Ord::cmp and PartialOrd::partial_cmp:

  • fn cmp(&self, other: &Self) -> Ordering
  • fn partial_cmp(&self, other: &Rhs) -> Option<Ordering>

With Ordering being defined as:

#[repr(i8)]
pub enum Ordering {
    Less,
    Equal,
    Greater,
}

So Ord::cmp may return one of three values:

  • Less (poker hand is worse)
  • Equal (poker hand has equal value)
  • Greater (poker hand is better)

(which is what you need, IMHO).

The method PartialOrd::partial_cmp, in turn, would return one of four possible values:

  • Some(Less) (poker hand is worse)
  • Some(Equal) (poker hand has equal value)
  • Some(Greater) (poker hand is better)
  • None (we can't compare the poker hands, e.g. because perhaps one hand is invalid?)

Now the catch is that according to the documentation:

  • Implementations of Ord must be consistent with the PartialOrdimplementation.
  • The [method implementations of PartialOrd] must be consistent with each other and with those of PartialEq.

Thus if you allow Ord to return Ordering::Equal for some non-identical values (e.g. "3S 4S 5D 6H JH" and "3H 4H 5C 6C JD"), then you must also implement PartialOrd in such a way that the equality operator (==) will return true when comparing these two hands.

It's perfectly fine to do that! However, you will lose the ability to compare poker hands in a stricter sense (e.g. if you need to check whether two hands consist of the same cards in arbitrary order, or of the same cards in the same order).

Edit: And you will lose the abilitity to treat two "equivalent hands (in regard to their value)" as two separate items in a HashSet, for example, as pointed out by @Michael-F-Bryan previously. Hash and Eq must always be implemented consistently.

So it's ultimately your choice what to do. You could decide to make the == operator work on the equivalence relation regarding equal value of the hands (i.e. return true for different hands which have the same value), or you could follow @tczajka's approach of not using Ord (and instead writing your own compare_value_to method), or to use an enum HandValue.

Another option would be to use the newtype pattern, where you wrap a poker hand in another type and then implement Ord on that type.


I think that the Rust documentation still requires some overhaul in regard to precise terminology and giving some hints to avoid confusion. Maybe if I have some time, I will make a proposal on how to clean that up.

6 Likes

Technically this constraint only holds when you also implement Eq (in addition to PartialEq). Though I guess you should implement Eq.

Edit: I just noticed Eq is a supertrait of Ord, please disregard my comment.

1 Like

Yeah, that's a tricky one.

On one hand, the docs need to be unambiguous and tell people what they can/can't rely on. Especially when it has an effect on correctness or behaviour (e.g. keys in a HashMap).

On the other hand, if we made it precise (using proper mathematical concepts like total preorder and equivalence relations, etc.), it'll be like whenever you look up a physics or mathematics concept on Wikipedia and need a masters degree just to understand the words and a PhD for it to be useful.

Arguably, the second situation is just as bad because ambiguous documentation is just as useless as something that's confusing or requires knowledge that most readers won't have.

But perhaps I'm going off on a tangent here :sweat_smile:

3 Likes

The "value" of a hand imposes a weak order on the set H of all poker hands. That is, there exists a relation < in H that is transitive, irreflexive, and antisymmetric: for all a, b in H,

  • a < b && b < c => a < c
  • !(a < a)
  • a < b <=> !(b < a).

These conditions imply that there exists a relation Eqv(a, b) <=> !(a < b) && !(b < a) that partitions H into equivalence classes: hands that have the same value but are not necessarily equal. Furthermore, the weak order imposes an unambiguous total order on the set of equivalence classes (ie. hand values), as expected.

Unfortunately, Rust does not have a WeakOrd trait. Every weak order is also a partial order, but implementing PartialOrd is unsatisfactory and even misleading: hands with equal value are equivalent, not incomparable! On the other hand, implementing Ord would mean that Eq would have to regard equivalent hands as equal, which would be semantically wrong. (And Hash would naturally have to agree with Eq.)

Things being how they are, I would implement Eq but neither Ord nor PartialOrd on poker hands; rather I’d just have a value method that returns something that is Ord.

In general, the concept of a weak order is very useful; indeed most algorithms and data structures that depend on an ordering (sorting, partitioning, search trees, etc) work just fine with only a weak rather than a total order, which is why eg. in C++ they only require a weak order.

3 Likes

I don't think precise and intelligible are mutually exclusive here. The problem is that the documentation does already contain mathematical terms such as "partial ord(er)", "equivalence relation", "total order", etc. These terms must be used correctly and unambiguously.

In addition, things should be explained in a "down to earth" fashion such that it's possible for someone without mathematical background to understand usage properly. I.e. I don't want to make the documentation more precise at the cost of being more difficult to read, but I would like it to be

  • correct
  • unambigious
  • easy to understand for someone who doesn't know about the mathematical terms
  • easy to understand for someone being used to the mathematical terms

If I understand it right, then (non-strict) weak orders are essentially the same as total preorders (Wikipedia), but I'm not really an expert on that.

One could consider Ord to be a weak order, see:

That's where the documentation is a bit misleading.

If Eq describes an equivalence relation (and not equality), then Ord describes a weak order (i.e. a total preorder). Now one could argue whether Eq means equality or equivalence. Let's review the docs again:

Trait std::cmp::Eq

pub trait Eq: PartialEq<Self> { }

Trait for equality comparisons which are equivalence relations.

I'm not sure how to interpret that sentence. Maybe it means that it must only be used for equality comparisons and the second part of the sentence ("which are equivalence relations") is just redundant information. But that can't be. Let's look at PartialEq's docs:

Trait std::cmp::PartialEq

pub trait PartialEq<Rhs = Self>
where
   Rhs: ?Sized,
{
    fn eq(&self, other: &Rhs) -> bool;

    fn ne(&self, other: &Rhs) -> bool { ... }
}

Trait for equality comparisons which are partial equivalence relations.

If Eq really is to implement mathematical "equality" only, then the same would hold for PartialEq, but I don't think that "equality" here means equality in the mathematical sense.

In the wild, there will be implementations where using the equality operator on several different objects/values returns true (see Playground for an example in std). I would thus conclude that Eq can be used to describe any equivalence relation (and not just "equality"). The "equality operator" (==) will behave according to that equivalence relation (and not regarding true equality/identity).

I agree on that. But the situation is even more wicked: PartialOrd requires that:

The methods of this trait must be consistent with each other and with those of PartialEq. The following conditions must hold:

  1. a == b if and only if partial_cmp(a, b) == Some(Equal).
  2. […]

Thus hands with equal value would need to be

  • equivalent (i.e. partial_cmp(a, b) == Some(Equal)) when they are equal and
  • incomparable (i.e. partial_cmp(a, b) == None) when they are not equal but equivalent regarding their value.

I would thus concur that using PartialOrd here as a solution is a bad idea.

2 Likes

@AlwaysLearning I hope my comments on Rust's documentation didn't make things more confusing than before.

There are actually two different levels of the discussion:

  • Terminology (i.e. what is "equality" or "equivalence", etc.)
  • What to do best (i.e. how to solve the problem in Rust)

Let's forget about terminology, and focus on the second part.

Summarizing, one of the following approaches might be best:

  • Use two different types for poker hands (e.g. PokerHand) and their value (e.g. PokerHandValue), and provide a method (e.g. value), which returns the PokerHandValue for a given PokerHand. You can implement Ord for PokerHandValue. Now "3S 4S 5D 6H JH", and "3H 4H 5C 6C JD" could be non-equal hands, but having an equal value.
  • Do not use Ord and PartialOrd at all. Instead provide a method with a name of your choice (e.g. cmp_by_value, or compare_value_to as suggested by @tczajka), for example, which may return an Ordering.

Other, less preferred (and maybe non-idiomatic) options could be:

  • Make == return true when comparing two different hands with the same value. Like I said, I think this is possible, but it will make it impossible to store two different hands with the same value in certain data structures because they will compare as "equal" (even if they consist of different cards). Maybe it's not a good idea, but if you go that way, you can implement Ord.
  • Use the newtype pattern, where you wrap a poker hand in another type and then implement Ord on that type. Maybe this option is most confusing, especially if you are still learning.
4 Likes

Wow! Thank you all for the in-depth answers as expected by this community.

There is so much to say in regard to these traits that I dont know where to begin. I have read and re-read your comments. So, I'll just make statements in random order.

  • Eq and PartialEq tell whether two instances are same or not. That's it. They have nothing to do with < or >.
  • Eq: PartialEq means types are identically same (a == a) in addition to being symmetric (a == b implies b == a) and transitive (a == b and b == c implies a == c).
  • As for PartialEq, users decide when two instances have value equality. (Like clone() where we get to decide how to clone instances)
  • PartialOrd means two instances of a type may not be comparable. Hence, partial_cmp() returns Option<Ordering>.
  • Ord means all instances of a type are comparable. Hence, cmp() returns Ordering.

As to poker hands, they are Ord because all hands are comparable (win, lose or split/equal). What I find odd is, hands are Ord but because of Ord: Eq + PartialOrd, they are also PartialOrd. This trait bound confuses me. For two reasons:

  1. Why is my type supposed to impl both? Is it not enough for Ord to return a non-Option value ie Ordering?
  2. Also why Eq? cmp will return Ordering::Equal if they are same in value. What am I supposed to do in PartialEq that is brought in by Eq?

I will go ahead and what I have so far.

struct Hand {
    sorted: [Card, 5]
}

impl Hand {
    fn is_royal_flush(&self) -> bool {}
    fn is_straight_flush(&self) -> bool {},
    ...
}

impl PartialOrd for Hand {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Hand {
    fn cmp(&self, other: &Self) -> Ordering {
        // This is complicated. I handle hands on a case-by-case basis. 
        // For eg., I return Ordering::Equal if self and other are royal flushes.
        // For other hands, if they are same in value (like straight flush and flush), then I check for higher cards. 
        // For other hands, I return Ordering::Less if self is flush and other is royal flush.
        // And so on. 
    }
}

impl PartialEq for Hand {
    // Im hitting a brick wall here. What am I supposed to do here?
}

I felt I was close but then @jbe and @tczajka suggestions to create value() -> Ordering brought me back to square one. If Im being honest, I dont know why that suggestion is better than what I have.

My stance is that Eq and PartialEq denote an equivalence relation (or partial equivalence relation if Eq is not implemented), not necessary equality or "being the same" as in being identical. But there may be other opinions on that.

However, Eq and PartialEq are related to < and >, because if two values a and b compare as equivalent (i.e. if a == b), then a < b must be false. That is because the documentation of PartialOrd demands:

The methods of this trait must be consistent with each other and with those of PartialEq. The following conditions must hold:

  1. a == b if and only if partial_cmp(a, b) == Some(Equal).
  2. a < b if and only if partial_cmp(a, b) == Some(Less)
  3. […]

Thus, if a == b (due to an implementation in PartialEq), then it must not happen that a < b, because a == b implies that partial_cmp(a, b) == Some(Equal) which cannot be Some(Less) at the same time.

I would phrase it differently: Eq implies that a == a (reflexivity), i.e. that the == operator describes an equivalence relation (and not just a partial equivalence relation).

I would agree here.

Yes, and in that case a < b, a <= b, a == b, a >= b, a > b are all false! (But a != b is true!) (Playground).

Yes, but comparing two non-identical values (such as -0.0 and 0.0) using the == operator might still return true (Playground).

Yes, unless you have hands that are invalid, e.g. hands with a card missing.

This is to ensure that bounds which expect a type type PartialOrd can also accept all types that are Ord. It has to do with how Rust's type system work. PartialOrd needs to be a supertrait of Ord. Rust doesn't allow to automatically implement PartialOrd based on your Ord implementation, so you have to do it manually, unfortunately.

I don't understand what you mean. Can you rephrase the question or elaborate more?

You need to make a choice first. Do you want to implement Ord for Hand in such way that the ordering reflects the value of the hand? If yes, that corresponds to alternative 1 below; if no, then it corresponds to alternative 2 below.

Alternative 1

If yes, then this means a == b has to be true for two different hands a and b if their value is the same. (That's okay but may restrict you if you later want to use the == operator in a different fashion.) If you go this way, you can implement PartialEq::eq by just forwarding to Ord::cmp. See the following Playground:

use std::cmp::Ordering;

struct Card { /* … */ }

struct Hand {
    sorted: [Card; 5], // maybe use `Vec<Card>` here?
}

impl Hand {
    fn is_royal_flush(&self) -> bool { todo!() }
    fn is_straight_flush(&self) -> bool { todo!() }
    /* … */
}

impl PartialOrd for Hand {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Hand {
    fn cmp(&self, other: &Self) -> Ordering {
        todo!()
    }
}

impl PartialEq for Hand {
    fn eq(&self, other: &Self) -> bool {
        self.cmp(other) == Ordering::Equal
    }
}

impl Eq for Hand {} // we can implement this because `a == a`

(Playground)

Note that PartialEq::eq must behave according to your Ord::cmp implementation! By writing self.cmp(other) == Ordering::Equal in the body of the eq method (as in the above example), this is guaranteed.

Alternative 2

If you decide you want a different behavior of the == operator, then you cannot proceed like that, and instead you would need to pick one of the following choices:

1 Like

If it were me, I would rely on the behaviour of #[derive(PartialEq, Eq, PartialOrd, Ord, Hash)] instead of trying to implement the traits manually. That way you can make sure things will be ordered correctly just by looking at how their definitions are ordered.

First, I would define the basic types you need for representing a card. Note that there is no ordering between suits in poker, and therefore we don't derive Ord (and PartialOrd) for the Suit and Card types.

#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub struct Card {
    suit: Suit,
    rank: Rank,
}

#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub enum Suit {
    Hearts,
    Clubs,
    Diamonds,
    Spades,
}

#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Rank {
    Number(usize),
    Jack,
    Queen,
    King,
    Ace,
}

impl Rank {
    pub fn from_number(n: usize) -> Option<Self> {
        match n {
            1 => Some(Rank::Ace),
            2..=10 => Some(Rank::Number(n)),
            11 => Some(Rank::Jack),
            12 => Some(Rank::Queen),
            13 => Some(Rank::King),
            _ => None,
        }
    }
}

Next, I would define the different kinds of hand you can get (pair, straight, etc.). Note that the ordering of fields and the traits we derive are important here.

#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum HandValue {
    HighCard(Rank),
    Pair(Rank),
    TwoPair {
        high_card: Rank,
        other: Rank,
    },
    ThreeOfAKind(Rank),
    Straight {
        highest_value: Rank,
    },
    Flush {
        high_card: Rank,
        other_cards: [Rank; 4],
    },
    FullHouse {
        triple: Rank,
        pair: Rank,
    },
    FourOfAKind(Rank),
    StraightFlush {
        highest_rank: Rank,
        other_cards: [Rank; 4],
    },
}

(Note: As @KSwanson's comment points out, this could be simplified by making Flush hold a [Rank; 5] and skipping the high_card/other_cards business)

Finally, we can define Hand and a way to compare two hands. Note that I've derived PartialEq and Eq for Hand because we can always check whether two hands have the same cards in them.

The value() method is where you would look at the hand and figure out whether it's got a pair or straight flush or whatever.

#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub struct Hand([Card; 5]);

impl Hand {
    pub fn value(&self) -> HandValue {
        todo!("Figure out what type of hand the player has");
    }
}

For convenience, I'd throw in a FromStr impl which lets you parse something like "3H 4H 5C 6C JD" into a Hand.

impl FromStr for Hand {
    type Err = InvalidFormat;
    
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        todo!("Parse a string like '3H 4H 5C 6C JD' into its 5 cards");
    }
}

#[derive(Debug)]
struct InvalidFormat;

Finally, we can start checking which hand is better.

fn main() {
    let person_1: Hand = "3H 4H 5C 6C 7D".parse().unwrap();
    let person_2: Hand = "4S 5D 6H 7H 8C".parse().unwrap();
    
    // the two hands have different cards
    assert_ne!(person_1, person_2);
    
    // checking ordering directly is a compile error
    // assert!(person_1 < person_2); // uncomment me
    
    // however, we can check whether they have the same 
    assert!(person_1.value() < person_2.value());
}

All the above code is on the playground.

Note that besides the todo!() bits, that was all I needed to do. By ordering my enums so that the lowest ranked variant comes first and variants like HandValue::TwoPair have fields ordered so the tie-breaker is compared first (e.g. if multiple people have two pairs, we'll first compare their high_card field before the other) I was able to let the compiler generate the tricky implementations.

Also, regarding your is_royal_flush()-like methods, there is a really nice blog post which explains why the value() way of doing things is superior... "Parse, don't validate".

8 Likes

I like your approach. It just doesn't teach how to implement Ord yourself (which might come in handy in other scenarios).

You can really go either way. The only downside of implementing Ord directly for the hand is that you will be restricted in how you can use the == operator and in how you can store hands in certain data structures such as hash tables.

In general, I prefer to use derives because humans are bad at writing repetitive code. Plus, whenever readers see a #[derive(PartialOrd)] they just need to look at the definition to understand how things are ordered.

To me, the presence of a #[derive(Ord)] just indicate that comparisons are well behaved and obvious, with no NaN-like funny business. You can use the same "funny business" rule of thumb when deciding whether Eq is appropriate.

Sorry to jump in here, I was just confused about something:

#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum HandValue {
    HighCard(Rank),
    Pair(Rank),
    TwoPair {
        high_card: Rank,
        other: Rank,
    },
    ThreeOfAKind(Rank),
    Straight {
        highest_value: Rank,
    },
    Flush {
        high_card: Rank,
        other_cards: [Rank; 4],
    },
    FullHouse {
        triple: Rank,
        pair: Rank,
    },
    FourOfAKind(Rank),
    StraightFlush {
        highest_rank: Rank,
        other_cards: [Rank; 4],
    },
}

For Flush and StraightFlush, why do you separate highest_rank from other_cards? Is it just a convenience?

And separately (or maybe not), will the derivation of Ord Do The Right Thing when highest_value are the same? I.E., will "QS 9S 7S 3S 2S" "QS 9S 7S 4S 3S" be considered greater than "QD 9D 7D 3D 1D" "QD 9D 7D 4D 2D" automatically? And if so, why not just have a single 5-length Rank array?

Note: edited to fix my sample poker hands because I forgot that aces are high in poker :man_facepalming:

That's a good point!

In retrospect, I probably should have used a [Rank; 5] for both and then just require Hand::value() to make sure the array is sorted in descending order. The two versions are identical as far as the comparisons are concerned, and splitting the highest card out like that was probably unnecessary.

In theory, I could have also created a SortedRanks type which contains a [Rank; 5] which is always in descending order (thanks to its constructor) and has helper methods like high_card() to make printing "ace high flush" to the screen.

2 Likes

I forgot to add the kicker for TwoPair. You have to add kickers for HighCard, Pair, TwoPair. On the other hand, StraightFlush doesn't need other_cards. So it should be more like:

#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum HandValue {
    HighCard {
        ranks: [Rank; 5],
    },
    Pair {
        pair: Rank,
        kickers: [Rank; 3],
    },
    TwoPair {
        high_pair: Rank,
        low_pair: Rank,
        kicker: Rank,
    },
    ThreeOfAKind(Rank),
    Straight {
        highest: Rank,
    },
    Flush {
        ranks: [Rank; 5],
    },
    FullHouse {
        triple: Rank,
        pair: Rank,
    },
    FourOfAKind(Rank),
    StraightFlush {
        highest: Rank,
    },
}
1 Like

ThreeOfAKind and FourOfAKind should also have kickers. In community card games like texas hold 'em multiple people can have those hands.

4 Likes

I created PR #103046 for that matter.

I came here to understand the theory (and there is so much) behind Ord, PartialOrd, Eq and PartialEq. But I ended up getting a solution to my exercise. Not bad.

I love the HandValue approach mostly because how enum variants are ordered in Rust. :exploding_head:

Im mostly exploring these concepts (also watching the PR by @jbe) and I have nothing more to add here. All comments were very insightful so I dont know which one to mark as the solution.

I'll just let this topic die a slow death. Unless someone thinks otherwise.

5 Likes

Wait...not sure why I was surprised by this. This is valid even for Java.

When I used enums, I never felt the need to compare invariants variants. The order of invariants variants matters only when you want enum instances to be ordered.

Going forward Im going to be cognizant of this fact. It'll save me some refactoring (and weird bugs) in case there is a future requirement to make my enum ordered.

@scottmcm Thanks for pointing out the nit.