为什么我基于线性回归训练的终极井字棋 Minimax AI 表现不如手调？

Question

我正在用 Minima+ Alpha-Beta 剪枝 实现一个终极井字棋（Ultimate Tic-Tac-Toe）的 AI，要求只使用 Minima，不允许强化学习或深度搜索（比如禁止MCTS）。我的做法如下：

当前实现方式：
搜索算法： 使用标准的 Minima（带 Alpha-Beta 剪枝）

评估函数： 从棋盘状态中提取若干特征（例如赢得小棋盘数、是否控制中心、潜在胜利线等），然后对这些特征打分。评估函数永远是基于player1（圈玩家）的视角

评分模型： 假设评估值与这些特征之间存在线性关系

权重训练： 我手头有一组高质量标注数据（状态 → utility），于是使用了线性回归拟合出每个特征的权重

尽管训练数据的标注很准，线性模型在拟合损失上表现也不错，但在实际对抗中：

线性模型训练出来的评估函数效果很差，甚至不如我随便拍脑袋设的权重，连一个随机选择动作的 AI 都很难稳定战胜。
我自己的直觉是提取的特征集不好。但是我换了几个特征集结果也仍不理想。

欢迎大家指点迷津，非常感谢！

以下是我的特征提取函数，评估函数的代码，和状态表示

我使用了一个state类来表示棋盘状态，以下是state的一些方法和变量
state.board: 一个 4 维数组，形状为 333*3

前两个维度表示大棋盘上的位置（即小棋盘的索引）

后两个维度表示该小棋盘内部的 3*3 网格

每个格子的值为：

0 表示空

1 表示 Player 1（圈）落子

2 表示 Player 2（叉）落子

state.local_board_status: 一个 3*3 的矩阵，表示每个小棋盘的胜负状态

0: 游戏未结束

1: Player 1 胜出该小棋盘

2: Player 2 胜出该小棋盘

3: 该小棋盘打平

state.coefficients, state.intercept: 通过线性模型训练出来的每个特征的权重，和线性函数的常数项

其他辅助函数：

get_all_valid_actions(): 返回当前合法动作

change_state(action): 返回执行动作后的新状态

terminal_utility(): 返回终局得分，Player1 赢为 1.0，平局为 0.5，输为 0.0

特征提取函数：

    def e*tract_features(self, state):
        features = []
        board = state.board
        local = state.local_board_status
        # 1. Global status: Features: # of potential lines in meta board and game state of each local board
        features.append(self.count_potential_lines(local, 1))
        features.append(self.count_potential_lines(local, 2))
        features += local.flatten().tolist()
        
        # 2. Local threats. Features: number about-to-win and about-to-lose in each local board
        for i in range(3):
            for j in range(3):
                sub = board[i][j]
                features.append(self.count_potential_lines(sub, 1))  # Player 1 threats
                features.append(self.count_potential_lines(sub, 2))  # Player 2 threats
        
        # 3. Center control
        if local[1][1] == 1:
            features.append(7)
        elif local[1][1] == 2:
            features.append(-7)
        elif local[1][1] == 3:
            features.append(0)
        else:
            features.append(np.sum(local[1][1] == 1) - np.sum(local[1][1] == 2))
        
        # 4. Active board evaluation (2 features)
        if state.prev_local_action:
            ai, aj = state.prev_local_action[0], state.prev_local_action[1]
            if local[ai][aj] == 0: # ne*t player cannot move freely
                features.append(0)
            else:
                features.append(1)
        else:
            features.append(1)
            
        return np.array(features)

    def count_potential_lines(self, board, player):
        winning_lines = [
            [(0,0), (0,1), (0,2)],
            [(1,0), (1,1), (1,2)],
            [(2,0), (2,1), (2,2)],
            [(0,0), (1,0), (2,0)],
            [(0,1), (1,1), (2,1)],
            [(0,2), (1,2), (2,2)],
            [(0,0), (1,1), (2,2)],
            [(0,2), (1,1), (2,0)]
        ]
        
        count = 0
        for line in winning_lines:
            values = [board[pos] for pos in line]
            if values.count(player) == 2 and 0 in values:
                count += 1
        
        return count

评估函数

    def evaluate(self, state):
        features = self.e*tract_features(state)
        return np.dot(features, self.coefficients) + self.intercept

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

问题分析

您使用线性回归训练的 Minimax AI 在 Ultimate Tic-Tac-Toe 中表现不如手调，这可能是由于以下几个原因：

1. 线性回归的限制：线性回归只能学习线性关系，Ultimate Tic-Tac-Toe 是一个复杂的游戏，需要考虑多个因素和可能的游戏状态，线性回归可能无法捕捉这些复杂关系。
2. Minimax 算法的限制：Minimax 算法是一种基于树搜索的算法，需要在搜索树中选择合适的节点，Ultimate Tic-Tac-Toe 的搜索树可能非常深，Minimax 算法可能无法有效地搜索整个树。
3. Alpha-Beta 剪枝的限制：Alpha-Beta 剪枝是一种优化技术，可以减少搜索树的大小，但是Ultimate Tic-Tac-Toe 的搜索树可能非常大，Alpha-Beta 剪枝可能无法有效地剪枝。

解决方案

1. 尝试使用非线性模型：可以尝试使用非线性模型，如神经网络或 decision tree，来学习 Ultimate Tic-Tac-Toe 的策略。
2. 改进 Minimax 算法：可以尝试使用其他的 Minimax 算法，如 Monte Carlo Tree Search（MCTS），来搜索 Ultimate Tic-Tac-Toe 的搜索树。
3. 优化 Alpha-Beta 剪枝：可以尝试使用其他的 Alpha-Beta 剪枝算法，如 iterative deepening，来优化 Ultimate Tic-Tac-Toe 的搜索树。

代码示例

以下是一个使用 Python 实现的 Ultimate Tic-Tac-Toe AI，使用 Minimax 算法和 Alpha-Beta 剪枝：

import numpy as np

class TicTacToeAI:
    def __init__(self):
        self.board = np.zeros((3, 3, 3, 3))
        self.alpha = -float('inf')
        self.beta = float('inf')

    def evaluate(self, board):
        # 评估游戏状态
        # ...
        return score

    def minimax(self, board, depth, alpha, beta):
        # Minimax 算法
        # ...
        return best_move

    def alphabeta(self, board, depth):
        # Alpha-Beta 剪枝
        # ...
        return best_move

    def play(self, board):
        # 选择最佳移动
        best_move = self.alphabeta(board, 0)
        return best_move

# 使用示例
ai = TicTacToeAI()
board = np.zeros((3, 3, 3, 3))
ai.play(board)

Note: 以上代码只是一个示例，Ultimate Tic-Tac-Toe 的实现需要考虑更多的因素和可能的游戏状态。