1
$\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. For this example, it is ideally to get [1/6, 1/6, 1/6, 1/6, 0, 1/8] as a result.

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 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.

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

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$
  • $\begingroup$ This seems like a pretty mundane programming exercise. Just to get it clear, in your example you want to output [1/8, 1/8, 1/8, 1/8, 1/4, 1/4]? $\endgroup$ – Yuval Filmus Aug 29 '17 at 21:59
  • $\begingroup$ [1/8, 1/8, 1/8, 1/8, 0, 1/4] because one card is on board.. this is not so simple see the update. $\endgroup$ – Brans Ds Aug 30 '17 at 9:29
  • $\begingroup$ I don't understand your problem. What is the input, and what is the required output? Try to explain without using the words "poker", "hand", "card". Abstract your problem. $\endgroup$ – Yuval Filmus Aug 30 '17 at 10:01
  • $\begingroup$ I think that problem is generic. We have a distribution of some value. (In our case distribution of cards strength.) And we need to take samples from the distribution to explore it in different cases(to use in ML). There can be a lot of samples with same or near the same value(for example 9000 can have value 1) and the tiny amount of extreme values( for example 1 sample with 1003 values 1 sample with 1010 and one sample with -2000, and one with -21000). If we will sample examples just randomly we will get samples with value 1 again and again and it will take very-very long to learn. $\endgroup$ – Brans Ds Aug 30 '17 at 10:21
  • $\begingroup$ Ok, so the input is a distribution. What is the desired output? $\endgroup$ – Yuval Filmus Aug 30 '17 at 10:49