五角大楼董事会的优胜者

[poster]

对于那些不知道Pentago是什么的人来说，对这个问题并不是很重要，但是只要说您有一个带有四个象限的6x6电路板就足够了。每个玩家轮流放置一个棋子，然后旋转一个象限。当一名玩家连续获得五名（在该玩家的旋转阶段之前或之后），便赢得了这场比赛。

我正在写一个算法来播放各种不同的随机转盘五子棋游戏。但是，由于它是完全随机的，所以我看不出有什么好办法来检查是否有人在该位置和转弯旋转阶段之间获胜（否则，您可能会意外旋转获胜的举动）。最终，我计划将其重写为涉及更多策略而不是完全随机的策略，但这是出于统计目的，因此随机性就可以了（实际上在某些方面很有用）。

无论如何，目前我正在Matlab中编程，一个空白的板看起来像这样

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

简而言之，我的问题是这样的：

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



回答：

编辑：

我提出了两种解决方案：一种基于卷积（使用功能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的解决方案无法检测到平局。即使基于卷积的解决方案的代码是最短且最容易实现的（我不必手动创建索引列表），但我上面给出的索引解决方案最终还是最快的。



更多&回答...