2
$\begingroup$

Let's say we have a card game, like poker. Inputs are board cards and an array of cards strength(that is calculated based on the board cards and game rules).

For example for 3 ranks(A, K, Q) /2 suits(h,s) simplified poker(Leduc) with Qs on board as input we will have a strength array [2, 2, 1, 1, -1, 3] indexes are [As, Ah, Ks, Kh, Qs, Qh]. The highest strength has Qh because pair wins, then aces and kings. -1 means that Qs is impossible because it is on board already.

We need to sample vectors of player ranges - probabilities that player holds each possible hand. We are using this vectors to train some machine learning algorithm to play with this cards.

On the average for the example above we should sample Qh with the same probability as As + Ah and Ks + Kh. So we need to split input array onto the strength "clusters" and split probability between them and then divide each cluster probability by the number of elements in that cluster. But how to define such clusters? What approach or algorithm can you suggest for this task?


Update: Here the procedure that is used by Alberta University for the "generating pseudo-random ranges that attempt to cover the space of possible ranges"

We used a recursive procedure R(S, p), that assigns probabilities to the hands in the set S that sum to probability p, according to the following procedure.

  1. If |S| = 1, then Pr(s) = p.
  2. Otherwise,

(a) Choose p1 uniformly at random from the interval (0, p), and let p2 = p − p1.

(b) Let S1 ⊂ S and S2 = S \ S1 such that |S1| = |S|/2 and all of the hands in S1 have a hand strength no greater than hands in S2. Hand strength is the probability of a hand beating a uniformly selected random hand from the current public state.

(c) Use R(S1, p1) and R(S2, p2) to assign probabilities to hands in S = S1 ∪ S2.

Also, I have looked at their implementation one note is that if we have an odd number of cards middle card goes to randomly to the left or right subsets.

But the real results of this algorithm looks strange: For the example above average cars sampling probability: [0.185,0.189,0.185,0.220,0, 0.219]

For the empty board: [0.19,0.12,0.19,0.19,0.12, 0.19] = [3/8, 1/8, 3/8, 3/8, 1/8, 3/8]. Not uniform because of an odd number of cards(6/2 = 3) on the second iteration. The results look not very good and accurate. Is this a best that we can achieve?

$\endgroup$
3
  • $\begingroup$ Assuming that cards are drawn with uniform probability, the probability for each possible hand is just 1/(hand size choose number of possible cards). I'm guessing you're interested in the distribution of hand strength instead. This can be computed directly using a recursive approach. For a 52 card deck with hands of 7 or so, this should only take a fraction of a second. If you're interested I have an implementation in julia for a related problem I'd be happy to put up on github. If this isn't fast enough, there should be some simplifications due to discrete card strength levels. $\endgroup$ – combo Aug 29 '17 at 22:43
  • $\begingroup$ @combo Please see the update. Is this a recursive approach you are talking about? $\endgroup$ – Brans Ds Aug 30 '17 at 9:27
  • $\begingroup$ I was more referring to computing each possible hand - this seems like a reasonable heuristic. If I find some time I'll see if I can throw together an implementation and time it $\endgroup$ – combo Aug 30 '17 at 23:28

Your Answer

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

Browse other questions tagged or ask your own question.