SET simulación de probabilidades de juego (MATLAB)

Question

Recientemente he encontrado que la gran tarjeta vino - SET. En pocas palabras, hay 81 tarjetas con las cuatro características: símbolo (oval, garabato o diamante), color de (rojo, violeta o verde), número (uno, dos o tres) y sombreado (sólido, rayado o abierto). La tarea es ubicar (de 12 tarjetas seleccionadas) un conjunto de 3 cartas, en el que cada una de las cuatro características es la misma en cada tarjeta o todas diferentes en cada tarjeta (sin combinación 2 + 1).

Lo he codificado en MATLAB para encontrar una solución y estimar las probabilidades de tener un conjunto de tarjetas seleccionadas al azar.

Aquí está mi código para estimar probabilidades:

%% 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 iteraciones son rápidos, pero tenga cuidado con más. Un millón de iteraciones dura aproximadamente 15 horas en la computadora de mi casa. De todos modos, con 12 cartas y 4 características, tengo alrededor de 13: 1 de tener un conjunto. Esto es realmente un problema. El libro de instrucciones dice que este número debe ser 33: 1. Y fue confirmado recientemente por Peter Norvig. Él proporciona el código de Python, pero aún no lo he probado.

¿Puede encontrar un error? Cualquier comentario sobre la mejora del rendimiento es bienvenido.

Answer 1

que abordó el problema de escribir mi propia aplicación antes de mirar a su código.Mi primer intento fue muy similar a lo que ya tenía :)

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

Después de usar el Analizador de descubrir los puntos calientes, algunas mejoras se pueden hacer sobre todo a principios-break'ing de bucles cuando sea posible. El cuello de botella principal es la llamada a la función ÚNICA. Esas dos líneas anteriores, donde comprobamos para conjuntos válidos pueden reescribirse como:

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

Por desgracia, la simulación sigue siendo lento para la simulación más grande. Por lo tanto, mi próxima solución es una versión vectorizada, donde para cada iteración, construimos una matriz única de todos los conjuntos posibles de 3 cartas de la mano de 12 cartas dibujadas. Para todos estos conjuntos candidatos, usamos vectores lógicos para indicar qué característica está presente, evitando así las llamadas a UNIQUE/NUMEL (queremos características iguales o todas diferentes en cada tarjeta del conjunto).

Admito que el código ahora es menos legible y más difícil de seguir (así que publiqué ambas versiones para comparar). La razón es que traté de optimizar el código tanto como sea posible, de modo que cada ciclo de iteración esté completamente vectorizado. Aquí está el código 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 usted tiene la caja de herramientas de procesamiento en paralelo, se puede sustituir fácilmente a la llanura bucle-FOR con una parfor paralelo (es posible que desee mover la inicialización de la matriz M dentro del bucle de nuevo : sustituir M(:) = false; con M = false(FEAT_SZ,set_sz2);)

Estas son algunas salidas de muestra de 50000 simulaciones (parfor utilizados con un grupo de 2 instancias 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. 

y con un millón de iteraciones (parfor para 12, no-parfor para 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. 

El odds ratio de acuerdo con los resultados reportados por Peter Norvig.

Answer 2

Aquí hay una versión vectorizada, donde las manos de 1M se pueden calcular en aproximadamente un minuto. Obtuve alrededor de 28: 1 con él, por lo que todavía podría haber algo un poco desagradable en la búsqueda de conjuntos "diferentes". Creo que esto es lo que también tiene problemas con tu solución.

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

Encontré mi error. Gracias Jonas por la pista con RANDPERM.

Utilicé RANDI para dibujar K cartas al azar, pero hay aproximadamente 50% de posibilidades de obtener repeticiones incluso en 12 cartas. Cuando sustituí esta línea por randperm, obtuve 33.8: 1 con 10000 iteraciones, muy cerca del número en el libro de instrucciones.

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

De todos modos, sería interesante ver otros enfoques del problema.

Answer 4

Estoy seguro de que hay algo mal en mi cálculo de estas probabilidades, ya que varios otros han confirmado con simulaciones que está cerca de 33: 1 como en las instrucciones, pero ¿qué hay de malo con la siguiente lógica?

Para 12 cartas aleatorias, hay 220 combinaciones posibles de tres cartas (12!/(9! 3!) = 220). Cada combinación de tres cartas tiene una probabilidad de 1/79 de ser un conjunto, por lo que hay una posibilidad de 78/79 de que tres cartas arbitrarias no sean un conjunto. Entonces, si examinaste las 220 combinaciones y hubo una probabilidad de 78/79 de que cada una no fuera un conjunto, entonces tu probabilidad de no encontrar un conjunto examinando todas las combinaciones posibles sería 78/79 elevado a la 220ª potencia, o 0.0606, que es aprox. 17: 1 probabilidades.

Me falta algo ...?

Christopher