SET моделирование шансов игры (MATLAB)

Question

Я недавно нашел отличную карту - SET. Если коротко, то есть 81 карты с четырьмя функциями: символ (овальные, закорючка или алмаз), цвет (красный, пурпурный или зеленый), номер (один, два или три) и затенения (твердое вещество, полосатый или открытый). Задача состоит в том, чтобы найти (из выбранных 12 карт) SET из 3-х карт, в которых каждая из четырех функций либо одинакова на каждой карте, либо все на каждой карте (без комбинации 2 + 1).

Я закодировал его в MATLAB, чтобы найти решение и оценить вероятность наличия набора в случайно выбранных карточках.

Вот мой код, чтобы оценить шансы:

%% 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 итераций быстро, но будьте осторожны с более. Один миллион итераций занимает около 15 часов на моем домашнем компьютере. Во всяком случае, с 12 картами и четырьмя функциями у меня есть около 13: 1 из набора. Это на самом деле проблема. В учебной книге сказано, что это число должно быть 33: 1. И это было недавно подтверждено Peter Norvig. Он предоставляет код Python, но я еще не тестировал его.

Так вы можете найти ошибку? Любые комментарии по улучшению эффективности приветствуются.

Answer 1

Я решал проблему писать свою собственную реализацию, прежде чем смотреть на ваш код.Моя первая попытка была очень похожа на то, что уже было :)

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

После использования Profiler, чтобы обнаружить горячие точки, некоторые улучшения могут быть сделаны в основном на ранних break'ing из циклов, когда это возможно. Основным узким местом является вызов функции UNIQUE. Эти две строки выше, где мы проверяем для действительных наборов можно переписать в виде:

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

К сожалению, моделирование по-прежнему медленно для увеличения моделирования. Таким образом, мое следующее решение представляет собой векторизованную версию, где для каждой итерации мы создаем единую матрицу из всех возможных наборов из 3-х карт из руки из 12 карт. Для всех этих наборов кандидатов мы используем логические векторы, чтобы указать, какая функция присутствует, тем самым избегая вызовов UNIQUE/NUMEL (мы хотим, чтобы все функции были одинаковыми или все разные на каждой карте набора).

Я признаю, что код стал менее читабельным и труднее отслеживать (таким образом, я опубликовал обе версии для сравнения). Причина в том, что я старался максимально оптимизировать код, так что каждый цикл итерации полностью векторизован. Вот окончательный код:

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

Если у вас есть Parallel Processing Toolbox, вы можете легко заменить равнину для цикла с параллельным PARFOR (вы можете снова переместить инициализацию матрицы M внутри цикла : заменить M(:) = false; с M = false(FEAT_SZ,set_sz2);)

Вот некоторые примеры выходов 50000 моделирования (PARFOR, используемых с бассейном 2-х местных экземпляров):

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

И с миллиона итераций (PARFOR в течение 12, не-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. 

Отношение шансов не согласуются с результатами, представленных Peter Norvig.

Answer 2

Анимированная версия, где 1M руки могут быть рассчитаны примерно через минуту. Я получил около 28: 1 с ним, так что все еще может быть что-то немного с поиском «всех разных» наборов. Я предполагаю, что это то, к чему у вашего решения проблемы.

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

Я нашел свою ошибку. Спасибо Jonas за подсказку с RANDPERM.

Я использовал RANDI для случайного нарисования карт K, но есть вероятность 50% получить повторы даже в 12 картах. Когда я заменил эту строку randperm, у меня есть 33.8: 1 с 10000 итерациями, очень близко к числу в инструкции.

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

В любом случае было бы интересно увидеть другие подходы к проблеме.

Answer 4

Я уверен, что что-то не так с моим вычислением этих коэффициентов, так как некоторые другие подтвердили с помощью моделирования, что это близко к 33: 1, как в инструкциях, но что не так со следующей логикой?

Для 12 случайных карт есть 220 возможных комбинаций из трех карт (12!/(9! 3!) = 220). Каждая комбинация из трех карт имеет шанс 1/79 быть установленным, так что существует вероятность 78/79 из трех произвольных карт, которые не являются набором. Поэтому, если вы изучили все 220 комбинаций и вероятность 78/79, что каждый из них не был установлен, тогда ваш шанс не найти набор, исследующий все возможные комбинации, будет 78/79 поднят до 220-й мощности, или 0.0606, который составляет ок. 17: 1.

Должно быть, мне что-то не хватает ...?

Кристофер