Игровое моделирование разногласий НАБОРА (MATLAB)

Question

Игровое моделирование разногласий НАБОРА (MATLAB)

Я недавно нашел, что большая карта прибыла - НАБОР. Кратко, существует 81 карта с этими четырьмя функциями: символ (овальный, загогулина или ромб), цвет (красный, фиолетовый или зеленый), число (один, два или три) и заштриховывающий (тело, чередуемое или открытое). Задача состоит в том, чтобы определить местоположение (от выбранных 12 карт) ряда 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 картами и 4 функциями я двигался 13:1 наличия набора. Это - на самом деле проблема. В книге инструкции было сказано, что это число должно быть 33:1. И это было недавно подтверждено Peter Norvig. Он предоставляет код Python, но я еще не протестировал его.

Таким образом, можно ли найти ошибку? Любые комментарии по поводу повышения производительности приветствуются.

5

matlab set simulation probability

задан skaffman 8 July 2011 в 06:53

3 ответа

Другие вопросы по тегам:

matlab set simulation probability

Похожие вопросы:

score 1 · Answer 1

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

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

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

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

score 2 · 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)))

score 1 · Answer 3

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

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

Я, должно быть, что-то упускаю?

Кристофер