SET Spiel Odds Simulation (MATLAB)

Question

Ich habe vor kurzem die große Karte kam - SET. Kurz gesagt, gibt es 81 Karten mit den vier Funktionen: Symbol (oval, Kringel oder Diamant), Farbe (rot, violett oder grün), Nummer (ein, zwei oder drei) und Shading (fest, gestreift oder offen). Die Aufgabe besteht darin, (aus ausgewählten 12 Karten) ein SET von 3 Karten zu finden, wobei jedes der vier Merkmale entweder auf jeder Karte gleich ist oder auf jeder Karte unterschiedlich ist (keine 2 + 1 Kombination).

Ich habe es in MATLAB codiert, um eine Lösung zu finden und die Chancen zu schätzen, in zufällig ausgewählten Karten gesetzt zu haben.

Hier ist mein Code Chancen zu schätzen:

%% 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 Iterationen sind schnell, aber mit vorsichtiger sein. Eine Million Iterationen dauert ungefähr 15 Stunden auf meinem Heimcomputer. Wie auch immer, mit 12 Karten und 4 Features habe ich ungefähr 13: 1 von einem Set. Das ist eigentlich ein Problem. Das Instruktionsbuch sagte, dass diese Nummer 33: 1 sein sollte. Und es wurde kürzlich von Peter Norvig bestätigt. Er stellt den Python-Code zur Verfügung, aber ich habe ihn noch nicht getestet.

So können Sie einen Fehler finden? Kommentare zur Leistungsverbesserung sind willkommen.

Answer 1

Ich löste das Problem, bevor meine eigene Implementierung schreiben in Ihrem Code suchen.Mein erster Versuch war sehr ähnlich zu dem, was Sie bereits :)

%# 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)) 

Nach dem Profiler Hot Spots zu entdecken, kann eine gewisse Verbesserung in erster Linie durch gemacht wird früh break'ing aus Schleifen, wenn möglich. Der wichtigste Engpass ist der Aufruf der UNIQUE-Funktion. Diese beiden Linien oben, wo wir für gültige Sätze überprüfen können neu geschrieben werden als:

%# 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 

Leider ist die Simulation für größere Simulation noch langsam ist. Daher ist meine nächste Lösung eine vektorisierte Version, bei der wir für jede Iteration eine einzige Matrix aller möglichen Sätze von 3 Karten aus der Hand von 12 gezogenen Karten erstellen. Für all diese Kandidatensätze verwenden wir logische Vektoren, um anzuzeigen, welche Eigenschaft vorhanden ist, wodurch die Aufrufe von UNIQUE/NUMEL vermieden werden (wir wollen gleiche oder alle Merkmale auf jeder Karte der Menge).

Ich gebe zu, dass der Code jetzt weniger lesbar und schwerer zu folgen ist (also habe ich beide Versionen zum Vergleich gepostet). Der Grund dafür ist, dass ich versucht habe, den Code so weit wie möglich zu optimieren, so dass jede Iterationsschleife vollständig vektorisiert ist. Hier ist der endgültige Code:

%# 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) 

Wenn Sie die Parallel Processing Toolbox haben, können Sie einfach auf die Ebene FOR-Schleife mit einem parallelen parfor ersetzen kann (man könnte die Initialisierung der Matrix M innerhalb der Schleife verschieben wollen wieder :

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

Und mit einer Million Iterationen (parfor:

Hier sind einige Beispiele für Ausgaben von 50000 Simulationen (parfor mit einem Pool von 2 lokalen Instanzen verwendet) M(:) = false; mit M = false(FEAT_SZ,set_sz2);) ersetzen no-parfor 15) für 12:

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

Die Odds Ratio stimmen mit den von Peter Norvig berichteten Ergebnisse.

Answer 2

Hier ist eine vektorisierte Version, wo 1M Hände in etwa einer Minute berechnet werden können. Ich habe damit etwa 28: 1 bekommen, so dass es vielleicht noch ein bisschen daneben geht, wenn ich "alle verschiedenen" Sets finde. Meine Vermutung ist, dass dies auch Ihre Lösung ist.

%# 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

Ich habe meinen Fehler gefunden. Danke Jonas für den Hinweis mit RANDPERM.

Ich benutzte RANDI, um zufällig gezogene K-Karten, aber es gibt etwa 50% Chance, Wiederholungen sogar in 12 Karten zu bekommen. Als ich diese Zeile durch randperm ersetzt habe, habe ich 33.8: 1 mit 10000 Iterationen, sehr nahe an der Zahl im Instruktionsbuch.

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

Jedenfalls wäre es interessant, andere Ansätze für das Problem zu sehen.

Answer 4

Ich bin mir sicher, dass etwas mit meiner Berechnung dieser Quoten nicht stimmt, da einige andere mit Simulationen bestätigt haben, dass es wie in den Anweisungen 33: 1 ist, aber was stimmt mit der folgenden Logik nicht?

Für 12 zufällige Karten gibt es 220 mögliche Kombinationen von drei Karten (12!/(9! 3!) = 220). Jede Kombination von drei Karten hat eine Chance von 1/79, ein Set zu sein, also besteht eine Chance von 78/79, dass drei beliebige Karten nicht gesetzt sind. Wenn Sie also alle 220 Kombinationen untersucht haben und eine Chance von 78/79 bestanden hat, dass es sich nicht um einen Satz handelt, würde Ihre Chance, keinen Satz zu finden, der alle möglichen Kombinationen untersucht, 78/79 auf die 220. Potenz oder 0.0606 erhöht. Das ist ca. 17: 1 Quoten.

Ich muss etwas verpassen ...?

Christopher