SET simulation de cotes de jeu (MATLAB)

Question

J'ai récemment trouvé la grande carte est venu - SET. En bref, il y a 81 cartes avec les quatre caractéristiques: symbole (ovale, gribouillis ou diamant), couleur (rouge, violet ou vert), nombre (un, deux ou trois) et ombrage (solide, rayé ou ouvert). La tâche consiste à localiser (parmi les 12 cartes choisies) un jeu de 3 cartes, dans lequel chacune des quatre caractéristiques est soit la même sur chaque carte, soit toutes différentes sur chaque carte (pas de combinaison 2 + 1). Je l'ai codé dans MATLAB pour trouver une solution et estimer les chances d'avoir un ensemble dans des cartes choisies au hasard.

Voici mon code pour estimer les cotes relatives:

%% initialization 
K = 12; % cards to draw 
NF = 4; % number of features (usually 3 or 4) 
setallcards = unique(nchoosek(repmat(1:3,1,NF),NF),'rows'); % all cards: rows - cards, columns - features 
setallcomb = nchoosek(1:K,3); % index of all combinations of K cards by 3 

%% test 
tic 
NIter=1e2; % number of test iterations 
setexists = 0; % test results holder 
% C = progress('init'); % if you have progress function from FileExchange 
for d = 1:NIter 
% C = progress(C,d/NIter);  

% cards for current test 
setdrawncardidx = randi(size(setallcards,1),K,1); 
setdrawncards = setallcards(setdrawncardidx,:); 

% find all sets in current test iteration 
for setcombidx = 1:size(setallcomb,1) 
    setcomb = setdrawncards(setallcomb(setcombidx,:),:); 
    if all(arrayfun(@(x) numel(unique(setcomb(:,x))), 1:NF)~=2) % test one combination 
     setexists = setexists + 1; 
     break % to find only the first set 
    end 
end 
end 
fprintf('Set:NoSet = %g:%g = %g:1\n', setexists, NIter-setexists, setexists/(NIter-setexists)) 
toc 

100-1000 itérations sont rapides, mais soyez prudent avec plus. Un million d'itérations prend environ 15 heures sur mon ordinateur personnel. Quoi qu'il en soit, avec 12 cartes et 4 caractéristiques, j'ai environ 13: 1 d'avoir un ensemble. C'est en fait un problème. Le livre d'instructions a indiqué que ce nombre devrait être 33: 1. Et il a été récemment confirmé par Peter Norvig. Il fournit le code Python, mais je ne l'ai pas encore testé.

Donc, pouvez-vous trouver une erreur? Tous les commentaires sur l'amélioration des performances sont les bienvenus.

Answer 1

J'abordé le problème par écrit ma propre mise en œuvre avant de regarder votre code.Ma première tentative était très semblable à ce que vous avez déjà eu :)

%# some parameters 
NUM_ITER = 100000; %# number of simulations to run 
DRAW_SZ = 12;  %# number of cards we are dealing 
SET_SZ = 3;   %# number of cards in a set 
FEAT_NUM = 4;  %# number of features (symbol,color,number,shading) 
FEAT_SZ = 3;  %# number of values per feature (eg: red/purple/green, ...) 

%# cards features 
features = { 
    'oval' 'squiggle' 'diamond' ; %# symbol 
    'red' 'purple' 'green' ;   %# color 
    'one' 'two' 'three' ;   %# number 
    'solid' 'striped' 'open'   %# shading 
}; 
fIdx = arrayfun(@(k) grp2idx(features(k,:)), 1:FEAT_NUM, 'UniformOutput',0); 

%# list of all cards. Each card: [symbol,color,number,shading] 
[W X Y Z] = ndgrid(fIdx{:}); 
cards = [W(:) X(:) Y(:) Z(:)]; 

%# all possible sets: choose 3 from 12 
setsInd = nchoosek(1:DRAW_SZ,SET_SZ); 

%# count number of valid sets in random draws of 12 cards 
counterValidSet = 0; 
for i=1:NUM_ITER 
    %# pick 12 cards 
    ord = randperm(size(cards,1)); 
    cardsDrawn = cards(ord(1:DRAW_SZ),:); 

    %# check for valid sets: features are all the same or all different 
    for s=1:size(setsInd,1) 
     %# set of 3 cards 
     set = cardsDrawn(setsInd(s,:),:); 

     %# check if set is valid 
     count = arrayfun(@(k) numel(unique(set(:,k))), 1:FEAT_NUM); 
     isValid = (count==1|count==3); 

     %# increment counter 
     if isValid 
      counterValidSet = counterValidSet + 1; 
      break   %# break early if found valid set among candidates 
     end 
    end 
end 

%# ratio of found-to-notfound 
fprintf('Size=%d, Set=%d, NoSet=%d, Set:NoSet=%g\n', ... 
    DRAW_SZ, counterValidSet, (NUM_ITER-counterValidSet), ... 
    counterValidSet/(NUM_ITER-counterValidSet)) 

Après avoir utilisé le profileur pour découvrir les points chauds, une certaine amélioration peut être principalement au début de-break'ing de boucles lorsque cela est possible. Le principal goulot d'étranglement est l'appel à la fonction UNIQUE. Ces deux lignes ci-dessus où nous vérifions des ensembles valides peuvent être réécrites:

%# check if set is valid 
isValid = true; 
for k=1:FEAT_NUM 
    count = numel(unique(set(:,k))); 
    if count~=1 && count~=3 
     isValid = false; 
     break %# break early if one of the features doesnt meet conditions 
    end 
end 

Malheureusement, la simulation est encore lent pour la simulation plus grande. Ainsi ma prochaine solution est une version vectorisée, où pour chaque itération, nous construisons une matrice unique de tous les ensembles possibles de 3 cartes de la main de 12 cartes tirées. Pour tous ces ensembles candidats, nous utilisons des vecteurs logiques pour indiquer quelle fonction est présente, évitant ainsi les appels à UNIQUE/NUMEL (nous voulons des caractéristiques toutes identiques ou toutes différentes sur chaque carte de l'ensemble). Je reconnais que le code est maintenant moins lisible et plus difficile à suivre (j'ai donc posté les deux versions pour comparaison). La raison en est que j'ai essayé d'optimiser le code autant que possible, de sorte que chaque boucle d'itération soit entièrement vectorisée. Voici le code final:

%# some parameters 
NUM_ITER = 100000; %# number of simulations to run 
DRAW_SZ = 12;  %# number of cards we are dealing 
SET_SZ = 3;   %# number of cards in a set 
FEAT_NUM = 4;  %# number of features (symbol,color,number,shading) 
FEAT_SZ = 3;  %# number of values per feature (eg: red/purple/green, ...) 

%# cards features 
features = { 
    'oval' 'squiggle' 'diamond' ; %# symbol 
    'red' 'purple' 'green' ;   %# color 
    'one' 'two' 'three' ;   %# number 
    'solid' 'striped' 'open'   %# shading 
}; 
fIdx = arrayfun(@(k) grp2idx(features(k,:)), 1:FEAT_NUM, 'UniformOutput',0); 

%# list of all cards. Each card: [symbol,color,number,shading] 
[W X Y Z] = ndgrid(fIdx{:}); 
cards = [W(:) X(:) Y(:) Z(:)]; 

%# all possible sets: choose 3 from 12 
setsInd = nchoosek(1:DRAW_SZ,SET_SZ); 

%# optimizations: some calculations taken out of the loop 
ss = setsInd(:); 
set_sz2 = numel(ss)*FEAT_NUM/SET_SZ; 
col = repmat(1:set_sz2,SET_SZ,1); 
col = FEAT_SZ.*(col(:)-1); 
M = false(FEAT_SZ,set_sz2); 

%# progress indication 
%#hWait = waitbar(0./NUM_ITER, 'Simulation...'); 

%# count number of valid sets in random draws of 12 cards 
counterValidSet = 0; 
for i=1:NUM_ITER 
    %# update progress 
    %#waitbar(i./NUM_ITER, hWait); 

    %# pick 12 cards 
    ord = randperm(size(cards,1)); 
    cardsDrawn = cards(ord(1:DRAW_SZ),:); 

    %# put all possible sets of 3 cards next to each other 
    set = reshape(cardsDrawn(ss,:)',[],SET_SZ)'; 
    set = set(:); 

    %# check for valid sets: features are all the same or all different 
    M(:) = false;   %# if using PARFOR, it will complain about this 
    M(set+col) = true; 
    isValid = all(reshape(sum(M)~=2,FEAT_NUM,[])); 

    %# increment counter if there is at least one valid set in all candidates 
    if any(isValid) 
     counterValidSet = counterValidSet + 1; 
    end 
end 

%# ratio of found-to-notfound 
fprintf('Size=%d, Set=%d, NoSet=%d, Set:NoSet=%g\n', ... 
    DRAW_SZ, counterValidSet, (NUM_ITER-counterValidSet), ... 
    counterValidSet/(NUM_ITER-counterValidSet)) 

%# close progress bar 
%#close(hWait) 

Si vous avez la boîte à outils de traitement parallèle, vous pouvez facilement remplacer la plaine boucle FOR avec un parfor parallèle (vous pouvez déplacer l'initialisation de la matrice M dans la boucle à nouveau : remplacer M(:) = false; avec M = false(FEAT_SZ,set_sz2);)

Voici quelques exemples de sorties (simulations parfor 50000 utilisées avec un pool de 2 instances locales):

» tic, SET_game2, toc 
Size=12, Set=48376, NoSet=1624, Set:NoSet=29.7882 
Elapsed time is 5.653933 seconds. 

» tic, SET_game2, toc 
Size=15, Set=49981, NoSet=19, Set:NoSet=2630.58 
Elapsed time is 9.414917 seconds. 

Et avec un million d'itérations (parfor 12, no-parfor 15):

» tic, SET_game2, toc 
Size=12, Set=967516, NoSet=32484, Set:NoSet=29.7844 
Elapsed time is 110.719903 seconds. 

» tic, SET_game2, toc 
Size=15, Set=999630, NoSet=370, Set:NoSet=2701.7 
Elapsed time is 372.110412 seconds. 

Le odds ratio d'accord avec les résultats rapportés par Peter Norvig.

Answer 2

Voici une version vectorisée, où les mains 1M peuvent être calculées en environ une minute. J'en ai à peu près 28: 1, donc il se peut qu'il y ait toujours quelque chose de moins à trouver des ensembles «tous différents». Je suppose que c'est aussi ce que votre solution a des problèmes.

%# initialization 
K = 12; %# cards to draw 
NF = 4; %# number of features (this is hard-coded to 4) 
nIter = 100000; %# number of iterations 

%# each card has four features. This means that a card can be represented 
%# by a coordinate in 4D space. A set is a full row, column, etc in 4D 
%# space. We can even parallelize the iterations, at least as long as we 
%# have RAM (each hand costs 81 bytes) 
%# make card space - one dimension per feature, plus one for the iterations 
cardSpace = false(3,3,3,3,nIter); 

%# To draw cards, we put K trues into each cardSpace. I can't think of a 
%# good, fast way to draw exactly K cards that doesn't involve calling 
%# unique 
for i=1:nIter 
    shuffle = randperm(81) + (i-1) * 81; 
    cardSpace(shuffle(1:K)) = true; 
end 

%# to test, all we have to do is check whether there is any row, column, 
%# with all 1's 
isEqual = squeeze(any(any(any(all(cardSpace,1),2),3),4) | ... 
    any(any(any(all(cardSpace,2),1),3),4) | ... 
    any(any(any(all(cardSpace,3),2),1),4) | ... 
    any(any(any(all(cardSpace,4),2),3),1)); 
%# to get a set of 3 cards where all symbols are different, we require that 
%# no 'sub-volume' is completely empty - there may be something wrong with this 
%# but since my test looked ok, I'm not going to investigate on Friday night 
isDifferent = squeeze(~any(all(all(all(~cardSpace,1),2),3),4) & ... 
    ~any(all(all(all(~cardSpace,1),2),4),3) & ... 
    ~any(all(all(all(~cardSpace,1),3),4),2) & ... 
    ~any(all(all(all(~cardSpace,4),2),3),1)); 

isSet = isEqual | isDifferent; 

%# find the odds 
fprintf('odds are %5.2f:1\n',sum(isSet)/(nIter-sum(isSet))) 

Answer 3

J'ai trouvé mon erreur. Merci Jonas pour l'indice avec RANDPERM.

J'ai utilisé RANDI pour tirer des cartes K au hasard, mais il y a environ 50% de chances d'obtenir des répétitions même dans 12 cartes. Quand j'ai substitué cette ligne avec randperm, j'ai 33.8: 1 avec 10000 itérations, très proche du nombre dans le livre d'instructions.

setdrawncardidx = randperm(81); 
setdrawncardidx = setdrawncardidx(1:K); 

Quoi qu'il en soit, il serait intéressant de voir d'autres approches du problème.

Answer 4

Je suis sûr qu'il y a quelque chose de mal dans mon calcul de ces cotes, puisque plusieurs autres ont confirmé avec des simulations qu'il est proche de 33: 1 comme dans les instructions, mais quel est le problème avec la logique suivante?

Pour 12 cartes aléatoires, il y a 220 combinaisons possibles de trois cartes (12!/(9! 3!) = 220). Chaque combinaison de trois cartes a 1/79 chances d'être un ensemble, donc il y a une chance 78/79 que trois cartes arbitraires ne soient pas un ensemble. Donc, si vous avez examiné toutes les 220 combinaisons et qu'il y avait 78/79 chances que chacune d'entre elles ne soit pas un ensemble, votre chance de ne pas trouver un ensemble examinant toutes les combinaisons possibles serait portée à la 220ème puissance, soit 0.0606, qui est d'environ 17: 1 chances.

Il me manque quelque chose ...?

Christopher