Pentago板上的获奖者

Question

对于那些不知道Pentago是什么的人来说,问题并不是那么重要,但足以说你有一个带有四个象限的6x6板.每个玩家轮流放置一块然后旋转一个象限.当一个玩家连续五次(在玩家的旋转阶段之前或之后)赢得游戏.

我正在编写一个算法来玩许多不同的随机 Pentago游戏.然而,由于它是完全随机的,我认为没有好办法绕过检查是否有人在转弯的位置和旋转阶段之间获胜(否则,你可能会意外地旋转获胜的动作).最后,我计划将其重写为涉及更多策略而不是完全随机的地方,但这是出于统计目的,因此随机性很好(事实上在某些方面非常有用).

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

eeeeee
eeeeee
eeeeee
eeeeee
eeeeee
eeeeee

随着比赛的进行,董事会充满了w's b' 和's'.我检查获胜板的方式是通过对每个列和每一行(以及每个对角线)进行迭代,通过对返回的"字符串"执行正则表达式检查来查看是否有赢家.

简而言之,我的问题是:

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

Answer 1

编辑：

我提出了两种解决方案：一种基于卷积（使用函数CONV2），另一种基于对 5 个元素的所有可能字符串进行强力索引（类似于b3 的新答案）。他们来了：

卷积：

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 的新答案的速度和准确性。我创建了 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 的解决方案无法检测到平局。尽管基于卷积的解决方案的代码是最短且最容易实现的（我不必手动创建索引列表），但我上面给出的索引解决方案最终是最快的。