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.
- If |S| = 1, then Pr(s) = p.
(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?