SET游戏赔率模拟（MATLAB）

[poster]

我最近发现了一张很棒的卡片-SET 。简而言之，共有81种具有以下四个特征的卡片： 符号 （椭圆形，花形或菱形）， 颜色 （红色，紫色或绿色）， 数字 （一，二或三）和阴影 （实心，条纹或空心）。任务是（从选定的12张卡中）找到3张卡的SET，其中四个功能在每个卡上都相同，或者在每个卡上都不同（没有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代码，但我尚未对其进行测试。

那你能找到一个错误吗？欢迎对性能改进发表任何意见。



回答：

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

%# 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] [WXYZ] = 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)) 使用探查器发现热点后，主要可以通过在可能的情况下提早打破循环来进行一些改进。主要瓶颈是对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 不幸的是，对于较大的仿真，仿真仍然很慢。因此，我的下一个解决方案是矢量化版本，其中对于每次迭代，我们从12张抽奖牌的手中构建一个由3张卡的所有可能集合组成的矩阵。对于所有这些候选集，我们使用逻辑向量指示存在的功能，从而避免调用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] [WXYZ] = 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) 如果你有并行处理工具箱，你可以很容易地并行PARFOR（您可能需要移动矩阵的初始化代替普通的for循环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，no-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报告的结果一致。



更多&回答...