performance - Pentago 董事会的获胜者

Question

对于那些不知道 Pentago 是什么的人来说，它对问题来说并不是那么重要，但足以说明您有一个 6x6 的板和四个象限。每个玩家轮流放置一个棋子，然后旋转一个象限。当一名玩家连续获得五个(在玩家轮换阶段之前或之后)时，游戏获胜。

我正在编写一种算法来玩许多不同的随机 Pentago 游戏。但是，由于它是完全随机的，我看不出有什么好方法可以绕过检查是否有人在转弯的位置和旋转阶段之间获胜(否则，您可能会不小心旋转获胜的 Action )。最终，我计划将其重写为涉及更多策略的地方，而不是完全随机的，但这是出于统计目的，因此随机性很好(实际上在某些方面非常有用)。

无论如何，目前我正在用 Matlab 编程，空板看起来像这样

eeeeee
eeeeee
eeeeee
eeeeee
eeeeee
eeeeee

随着游戏的进行，棋盘上会填满 w 和 b。我检查获胜板的方法实际上是遍历每一列和每一行(以及每条对角线)，通过对返回的“字符串”执行正则表达式检查来查看是否有获胜者。

简而言之，我的问题是:

是否有更有效的方法来确定 Pentago 板的获胜者？

Answer 1

编辑:

我想到了两种解决方案:一种基于卷积(使用函数 CONV2 )，另一种基于对所有可能的 5 个元素的字符串进行强力索引(类似于 b3's newer answer )。他们在这里:

卷积:

function winner = pentago_winner_conv(board)
%# Input should be a 6-by-6 matrix with:
%#   - 0 for an empty space
%#   - 1 for pieces from one player
%#   - -1 for pieces from the other player
%# The return value is 0 for no winner, -1 or 1 for the winning player,
%#   or 2 if there is a draw.

  metric = [conv2(board,ones(1,5),'same') ...     %# Check horizontal strings
            conv2(board,ones(5,1),'same') ...     %# Check vertical strings
            conv2(board,eye(5),'same') ...        %# Check diagonal strings
            conv2(board,fliplr(eye(5)),'same')];  %# Check anti-diagonal strings
  limits = [min(metric(:)) max(metric(:))];  %# Find the min and max values
  limits = fix(limits/5);                    %# Convert them to -1, 0, or 1
  if all(limits)
    winner = 2;            %# A draw condition
  else
    winner = sum(limits);  %# Find the winner, if any
  end

end

索引:

function winner = pentago_winner_brute(board)
%# Input should be a 6-by-6 matrix with:
%#   - 0 for an empty space
%#   - 1 for pieces from one player
%#   - -1 for pieces from the other player
%# The return value is 0 for no winner, -1 or 1 for the winning player,
%#   or 2 if there is a draw.

  index = reshape(1:36,6,6);
  index = [index(1:5,:).'; index(2:6,:).'; ...  %# Vertical string indices
           index(:,1:5); index(:,2:6); ...      %# Horizontal string indices
           1:7:29; 2:7:30; 7:7:35; 8:7:36; ...  %# Diagonal string indices
           5:5:25; 6:5:26; 11:5:31; 12:5:32];   %# Anti-diagonal string indices
  metric = sum(board(index),2);
  limits = [min(metric) max(metric)];  %# Find the min and max values
  limits = fix(limits/5);              %# Convert them to -1, 0, or 1
  if all(limits)
    winner = 2;            %# A draw condition
  else
    winner = sum(limits);  %# Find the winner, if any
  end

end

出于好奇，我想我应该用 b3's newer answer 来衡量这些解决方案的速度和准确性。 .我创建了 4 个测试板:-1 胜，没有赢家，1 胜，双赢(平局)。然后我为每个板运行每个解决方案 10,000 次并计时。以下是结果:

               |   Calculated winner
---------------+-----------------------
convolution    |  -1     0     1     2
indexing       |  -1     0     1     2
b3 solution    |  -1     0     1    -1

               |   Running time for 10,000x (seconds)
---------------+---------------------------------------
convolution    |  0.4863    0.5305    0.5248    0.4787
indexing       |  0.1706    0.1770    0.1755    0.1889
b3 solution    |  0.6607    1.3958    1.4223    0.7507

请注意，b3 的解决方案未能检测到平局。尽管基于卷积的解决方案的代码最短且最容易实现(我不必手动创建索引列表)，但我上面给出的索引解决方案最终是最快的。