n维井字棋：如何检测m维n边长棋盘上的所有获胜线

一、明确获胜线定义 #

在m维、边长为n的棋盘中，获胜线需满足：

• 点集共线，相邻点在各维度坐标差的绝对值之和为1（即棋盘内的“直线”）
• 点集长度≥l
• 点集内所有元素属于同一玩家（非空占位）

获胜线分为三类：

• 轴对齐线：仅沿单个维度延伸，其余维度坐标固定（如2维的行/列、3维的x/y/z方向直线）
• 主对角线：所有维度同时递增或递减（如2维左上→右下、3维(0,0,0)→(n-1,n-1,n-1)）
• 混合对角线：部分维度递增、部分维度递减（如2维右上→左下、3维(0,n-1,0)→(n-1,0,n-1)）

二、通用算法思路 #

1. 生成所有合法方向向量 #

方向向量为m维数组，每个分量∈{-1,0,1}：

• 轴对齐方向：仅一个分量为±1，其余为0（共2*m种）
• 对角线方向：所有分量为±1（共2^m种，反向向量对应同一条线的两个方向，可去重处理）

2. 遍历方向向量生成合法线 #

对每个方向向量d：

• 确定起点范围：若d_i=1，起点s_i ≤ n-1-(l-1)；若d_i=-1，起点s_i ≥ l-1；若d_i=0，s_i可取0到n-1任意值
• 对每个合法起点，沿d方向生成最长线（直到超出棋盘）
• 筛选长度≥l的线，检查是否所有元素属于同一玩家

三、基于Numpy的代码实现 #

1. 辅助函数：生成所有唯一方向向量 #

import numpy as np
from itertools import product

def generate_directions(m):
    directions = []
    # 生成轴对齐方向
    for i in range(m):
        for sign in [1, -1]:
            d = np.zeros(m, dtype=int)
            d[i] = sign
            directions.append(d)
    # 生成对角线方向（所有分量为±1）
    for signs in product([-1, 1], repeat=m):
        directions.append(np.array(signs, dtype=int))
    # 去重（反向向量视为同一方向）
    unique_dirs = []
    seen = set()
    for d in directions:
        # 用元组作为唯一标识，正向/反向只保留一个
        key = tuple(d) if d[0] != 0 else tuple(-d)
        if key not in seen:
            seen.add(key)
            unique_dirs.append(d)
    return unique_dirs

2. 核心获胜检测函数 #

def winEvaluation(boardInput, l):
    n = boardInput.shape[0]  # 棋盘边长（假设各维度边长一致）
    m = len(boardInput.shape)  # 维度数
    # 获取非空的玩家标记
    player_marks = np.unique(boardInput)
    player_marks = player_marks[player_marks != 0]
    
    directions = generate_directions(m)
    
    for d in directions:
        # 计算每个维度的起点取值范围
        start_ranges = []
        for i in range(m):
            if d[i] == 1:
                start_ranges.append(range(0, n - l + 1))
            elif d[i] == -1:
                start_ranges.append(range(l - 1, n))
            else:
                start_ranges.append(range(0, n))
        
        # 遍历所有合法起点
        for start in product(*start_ranges):
            start = np.array(start, dtype=int)
            # 生成当前起点沿d方向的最长线
            steps = 0
            while True:
                current = start + steps * d
                if np.any(current < 0) or np.any(current >= n):
                    break
                steps += 1
            # 检查线长是否达标
            if steps >= l:
                # 提取线上所有元素
                line_coords = start + np.arange(steps)[:, None] * d
                line = boardInput[tuple(line_coords.T)]
                # 检查是否存在连续l个相同玩家标记
                for mark in player_marks:
                    # 若需严格整条线都是同一标记，替换为np.all(line == mark)
                    if np.any(np.convolve(line == mark, np.ones(l), mode='valid') == l):
                        return True, mark  # 返回获胜状态及玩家标记
    return False, None  # 无获胜者

3. 原有轴对齐代码的优化说明 #

原有代码仅处理了部分轴对齐线，逻辑局限性强。优化后的方案通过方向向量统一处理所有类型的获胜线，无需单独区分轴对齐和对角线场景，同时覆盖了高维棋盘的所有可能获胜线。

四、关键注意事项 #

• 假设棋盘为各维度边长相同的m维数组（即boardInput.shape = (n, n, ..., n)）
• 空位置用0标记，玩家标记用非0值（如1、-1）
• 若允许“长度≥l的线中存在连续l个相同标记”而非“整条线都是同一标记”，需保留代码中的卷积检查逻辑；若要求整条线完全一致，替换为np.all(line == mark)即可

内容的提问来源于stack exchange，提问作者Rohith Ramanujam