SET游戏赔率模拟(MATLAB)

Question

我最近发现了很棒的卡片--SET.简而言之,有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代码,但我还没有测试它.

所以你能找到错误吗？欢迎任何关于性能改进的评论.

Answer 1

在查看您的代码之前，我解决了编写自己的实现的问题。我的第一次尝试与您已有的非常相似:)

\n\n

%# some parameters\nNUM_ITER = 100000;  %# number of simulations to run\nDRAW_SZ = 12;       %# number of cards we are dealing\nSET_SZ = 3;         %# number of cards in a set\nFEAT_NUM = 4;       %# number of features (symbol,color,number,shading)\nFEAT_SZ = 3;        %# number of values per feature (eg: red/purple/green, ...)\n\n%# cards features\nfeatures = {\n    \'oval\' \'squiggle\' \'diamond\' ;    %# symbol\n    \'red\' \'purple\' \'green\' ;         %# color\n    \'one\' \'two\' \'three\' ;            %# number\n    \'solid\' \'striped\' \'open\'         %# shading\n};\nfIdx = arrayfun(@(k) grp2idx(features(k,:)), 1:FEAT_NUM, \'UniformOutput\',0);\n\n%# list of all cards. Each card: [symbol,color,number,shading]\n[W X Y Z] = ndgrid(fIdx{:});\ncards = [W(:) X(:) Y(:) Z(:)];\n\n%# all possible sets: choose 3 from 12\nsetsInd = nchoosek(1:DRAW_SZ,SET_SZ);\n\n%# count number of valid sets in random draws of 12 cards\ncounterValidSet = 0;\nfor i=1:NUM_ITER\n    %# pick 12 cards\n    ord = randperm( size(cards,1) );\n    cardsDrawn = cards(ord(1:DRAW_SZ),:);\n\n    %# check for valid sets: features are all the same or all different\n    for s=1:size(setsInd,1)\n        %# set of 3 cards\n        set = cardsDrawn(setsInd(s,:),:);\n\n        %# check if set is valid\n        count = arrayfun(@(k) numel(unique(set(:,k))), 1:FEAT_NUM);\n        isValid = (count==1|count==3);\n\n        %# increment counter\n        if isValid\n            counterValidSet = counterValidSet + 1;\n            break           %# break early if found valid set among candidates\n        end\n    end\nend\n\n%# ratio of found-to-notfound\nfprintf(\'Size=%d, Set=%d, NoSet=%d, Set:NoSet=%g\\n\', ...\n    DRAW_SZ, counterValidSet, (NUM_ITER-counterValidSet), ...\n    counterValidSet/(NUM_ITER-counterValidSet))\n

\n\n

使用 Profiler 发现热点后，可以通过在可能的情况下尽早退出循环来进行一些改进。主要瓶颈是对 UNIQUE 函数的调用。上面我们检查有效集的两行可以重写为：

\n\n

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

\n\n

不幸的是，对于较大的模拟来说，模拟仍然很慢。因此，我的下一个解决方案是矢量化版本，对于每次迭代，我们从 12 张抽取的牌中构建所有可能的 3 张牌组的单个矩阵。对于所有这些候选集，我们使用逻辑向量来指示存在哪些特征，从而避免调用 UNIQUE/NUMEL（我们希望该组的每张卡上的特征全部相同或全部不同）。

\n\n

我承认代码现在可读性较差且难以遵循（因此我发布了两个版本以进行比较）。原因是我尝试尽可能地优化代码，以便每个迭代循环都是完全矢量化的。这是最终的代码：

\n\n

%# some parameters\nNUM_ITER = 100000;  %# number of simulations to run\nDRAW_SZ = 12;       %# number of cards we are dealing\nSET_SZ = 3;         %# number of cards in a set\nFEAT_NUM = 4;       %# number of features (symbol,color,number,shading)\nFEAT_SZ = 3;        %# number of values per feature (eg: red/purple/green, ...)\n\n%# cards features\nfeatures = {\n    \'oval\' \'squiggle\' \'diamond\' ;    %# symbol\n    \'red\' \'purple\' \'green\' ;         %# color\n    \'one\' \'two\' \'three\' ;            %# number\n    \'solid\' \'striped\' \'open\'         %# shading\n};\nfIdx = arrayfun(@(k) grp2idx(features(k,:)), 1:FEAT_NUM, \'UniformOutput\',0);\n\n%# list of all cards. Each card: [symbol,color,number,shading]\n[W X Y Z] = ndgrid(fIdx{:});\ncards = [W(:) X(:) Y(:) Z(:)];\n\n%# all possible sets: choose 3 from 12\nsetsInd = nchoosek(1:DRAW_SZ,SET_SZ);\n\n%# optimizations: some calculations taken out of the loop\nss = setsInd(:);\nset_sz2 = numel(ss)*FEAT_NUM/SET_SZ;\ncol = repmat(1:set_sz2,SET_SZ,1);\ncol = FEAT_SZ.*(col(:)-1);\nM = false(FEAT_SZ,set_sz2);\n\n%# progress indication\n%#hWait = waitbar(0./NUM_ITER, \'Simulation...\');\n\n%# count number of valid sets in random draws of 12 cards\ncounterValidSet = 0;\nfor i=1:NUM_ITER\n    %# update progress\n    %#waitbar(i./NUM_ITER, hWait);\n\n    %# pick 12 cards\n    ord = randperm( size(cards,1) );\n    cardsDrawn = cards(ord(1:DRAW_SZ),:);\n\n    %# put all possible sets of 3 cards next to each other\n    set = reshape(cardsDrawn(ss,:)\',[],SET_SZ)\';\n    set = set(:);\n\n    %# check for valid sets: features are all the same or all different\n    M(:) = false;            %# if using PARFOR, it will complain about this\n    M(set+col) = true;\n    isValid = all(reshape(sum(M)~=2,FEAT_NUM,[]));\n\n    %# increment counter if there is at least one valid set in all candidates\n    if any(isValid)\n        counterValidSet = counterValidSet + 1;\n    end\nend\n\n%# ratio of found-to-notfound\nfprintf(\'Size=%d, Set=%d, NoSet=%d, Set:NoSet=%g\\n\', ...\n    DRAW_SZ, counterValidSet, (NUM_ITER-counterValidSet), ...\n    counterValidSet/(NUM_ITER-counterValidSet))\n\n%# close progress bar\n%#close(hWait)\n

\n\n

如果您有并行处理工具箱，您可以轻松地用并行 PARFOR 替换普通的 FOR 循环（您可能希望再次将矩阵的初始化移到M循环内：替换M(:) = false;为M = false(FEAT_SZ,set_sz2);）

\n\n

以下是 50000 次模拟的一些示例输出（PARFOR 与 2 个本地实例池一起使用）：

\n\n

\xc2\xbb tic, SET_game2, toc\nSize=12, Set=48376, NoSet=1624, Set:NoSet=29.7882\nElapsed time is 5.653933 seconds.\n\n\xc2\xbb tic, SET_game2, toc\nSize=15, Set=49981, NoSet=19, Set:NoSet=2630.58\nElapsed time is 9.414917 seconds.\n

\n\n

经过一百万次迭代（PARFOR 为 12 次，no-PARFOR 为 15 次）：

\n\n

\xc2\xbb tic, SET_game2, toc\nSize=12, Set=967516, NoSet=32484, Set:NoSet=29.7844\nElapsed time is 110.719903 seconds.\n\n\xc2\xbb tic, SET_game2, toc\nSize=15, Set=999630, NoSet=370, Set:NoSet=2701.7\nElapsed time is 372.110412 seconds.\n

\n\n

该比值比与Peter Norvig报告的结果一致。

\n