Just found some interesting ideas about how to go about this on the old Yahoo Poki group (see
this thread and it's replies). Ignoring the idea of creating a huge sparse look-up table mentioned in that thread, I've so far come up with these methods, but none of them really seem ideal:
Input : WeightMatrix[10][52][52]
Output: PlayerHand[10]
<u>Method 1: Full re-sampling on collision</u>
<font class="small">Code:</font><hr /><pre>init CardNotUsedYet[52]
finished=false
while finished=false
for each player, I
PlayerHand[I]=ChooseHand(WeightMatrix[I]) { O(1) if we use gsl_ran_discrete() and O(n) to init at start }
finished=true
for each player, I
if either card in PlayerHand[I] set in CardNotUsedYet
finished=false
else
update CardNotUsedYet with PlayerHand[I]
</pre><hr />
NOTES: Very quick if collisions rare, else could be bad and might even not terminate if very constrained distributions are passed in. Not biased in any way.
<u>Method 2: Partial re-sampling on collision</u>
<font class="small">Code:</font><hr /><pre>init CardNotUsedYet[52]
for each player, I { using a random permutation of player ordering [ie: not 0..9]}
do
PlayerHand[I]=ChooseHand(WeightMatrix[I]) { O(1) if we use gsl_ran_discrete() and O(n) to init at start }
while either card in PlayerHand[I] set in CardNotUsedYet
update CardNotUsedYet with PlayerHand[I]
</pre><hr />
NOTES: Very quick if collisions rare, else could be bad and might even not terminate if very constrained distributions are passed in. Might still be badly biased?
<u>Method 3: Re-adjust WeightMatrix after each assignment</u>
<font class="small">Code:</font><hr /><pre>for each player, I { using a random permutation of player ordering [ie: not 0..9]}
PlayerHand[I]=ChooseHand(WeightMatrix[I]) { O(log2n) at best, using cumulative sum method }
for each remaining player, J
for each hand in weight matrix, K
if hand contains either card in PlayerHand[I], set WeightMatrix[J][][]=0
</pre><hr />
NOTES: Very slow [(10x9)/2x(1326/2) + (10x9)/2x1326 = 89505 opps per selection!], but will always terminate. Might still be biased though?
<u>Method 4: Weighting of results using uniform distribution (thanks to Mogobu for this idea!):</u>
<font class="small">Code:</font><hr /><pre>1. Use Knuth shuffle to assign each player a hand uniformly randomly.
2. Run the Monte-Carlo simulation using the uniform distribution but bias the result summation based on WeightMatrix[][][] entry for the hand the player was assigned.</pre><hr />
NOTES: Might require alot more simulation runs for the results to converge (but only on similar distributions to what would cause (1) and (2) to not terminate or run very slowly...), but very quick to initialize the player's holdings and shouldn't be biased because of the uniform distributions.
Does using a permutation of player orderings in (2) and (3) produce the same results as (1) or is it still biased? Can anybody think of any alternative/better algorithms to do this? Any ideas/help would be greatly appreciated! [img]/images/graemlins/smile.gif[/img]
Juk [img]/images/graemlins/smile.gif[/img]
PS: Alastair J. Walker's distribution selection method used in the GSL is outlined here.