强化学习-第一章

发表于 2026-07-06 更新于 2026-07-14 分类于强化学习

第一章第一次阅读，只能发现扩展实例有价值扩展实例: 井字棋问题：井字棋由两名玩家轮流在 3×3 棋盘上落子，一方使用 X，另一方使用 O。率先在行、列或对角线上连成三个棋子者获胜；若棋盘填满仍无人获胜，则为平局。由于完美玩家永远不会输，我们考虑与一个偶尔犯错的对手对弈，...

第一章

第一次阅读，只能发现扩展实例有价值

扩展实例: 井字棋

问题：井字棋由两名玩家轮流在 3×3 棋盘上落子，一方使用 X，另一方使用 O。率先在行、列或对角线上连成三个棋子者获胜；若棋盘填满仍无人获胜，则为平局。

由于完美玩家永远不会输，我们考虑与一个偶尔犯错的对手对弈，并将平局视为与失败同样糟糕。问题是：能否构造一个能识别对手失误、通过学习不断提高胜率的玩家？

强化学习

首先对这个问题进行建模

状态空间\(S\)是棋盘上的9个位置 我们可以记为 \[ S = \lbrace -1, 0, 1 \rbrace^9 \] 将其表示为 \[ board = \big[ \underbrace{0, 0, 0, 0, 0, 0, 0, 0, 0}_{\text{一共9个0}} \big] \] 胜利条件表示为一个三元数组列表 \[ WIN\_LINES = [ (0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6) ] \]

动作空间\(A\) 表示为 \[ A(S) = \{s[i] \mid i \in [0,8], s[i] = 0 \} \] 这里的\(s[i]=0\)是因为我们落子必须要在棋盘空位上落子。

奖励函数\(R\)表示为

\[ R= \begin{cases} +1, & \text{学习玩家获胜} \\ -1, & \text{学习玩家失败} & or & \text{双方平局} \\ 0, & \text{游戏尚未结束} \end{cases} \]

但是书上的奖励函数是定义的

\[ V= \begin{cases} +1, & \text{学习玩家获胜} \\ -1, & \text{学习玩家失败} & or & \text{双方平局} & or & \text{游戏尚未结束}\\ \end{cases} \] 这里的V是终局状态的固定价值后面根据书上给出的状态方程进行解释 状态转移方程 \[ V(S_t) \leftarrow V(S_t) + \alpha [V(S_{t+1}) - V(S_t)] \]

练习

1	TODO: 这里的练习没做的后面再做

练习 1.1 左右互搏假设上面的强化学习算法不是对战随机对手，而是以左右互搏的方式与自己对战来训练自己你认为在这种情况下会发生怎样的事情？它是否会学习到不同的策略？

A:经过充分探索过后，自我对弈通常会逼近井字棋的最优策略，导致agent在能赢的时候选择获胜，对方即将获胜时及时阻挡，面对完美对手时至少保持平局。

练习 1.2 对称性由千对称性，井字棋的很多位置看起来不同但其实是相同的我们如何利用这一点来修改上面提到的学习过程呢？这种改变会怎样改善学习过程？假设对方没有利用对称性，那我们应该利用吗？对称相等的位置是否必然具有相同的价值呢？

练习 1.3 贪心策略假设强化学习的玩家是贪心的，也就是说，他总是把棋子移动到他认为最好的位置，而从不进行试探比起一个非贪心的玩家，他会玩得更好，还是更差呢？可能会出现什么问题？

练习 1.4 从试探中学习假设学习更新发生在包括试探动作在内的所有动作之后，如果步长参数随着时间而适当减小（试探的趋势并不减弱），那么状态的价值将收敛到一组概率我们从试探性的行动中学习或者不从中学习，计算出两组概率（从概念上说），分别会是什么？假设我们继续进行试探性的行动，哪一组概率对于学习来说可能更好？哪一组更可能带来更大的胜率？

练习 1.5 其他提升方法你能想出其他方法来提升强化学习的玩家能力吗？你能想出更好的方法来解决井字棋的问题吗？

这里可以使用MiniMax算法来解决井字棋同时还可以直接进行树搜索

MiniMax算法

他妈的本质树搜索。

预测赢家

impl Solution {
    pub fn predict_the_winner(nums: Vec<i32>) -> bool {
        
        let n = nums.len();
        if nums.len() == 0{
            return true;
        }


        fn minimax(
            nums:&[i32],
            left:usize,
            right:usize,
            player1_turn:bool,
            memo:&mut [Vec<[Option<i32>;2]>])-> i32{
            
            let mut turn:usize =  player1_turn as usize;

            if let Some(result) = memo[left][right][turn]{
                return result;
            } //记忆化搜索

            let result;
            if left == right {
                result = if player1_turn {
                    // 玩家1拿走
                    nums[left]} 
                    else {
                    // 玩家2拿走
                    -nums[left]};
            }
            else if player1_turn
            {
                let player1_left = nums[left] + minimax(nums,left+1,right,!player1_turn,memo);
                let player1_right = nums[right] + minimax(nums,left,right-1,!player1_turn,memo);
                
                result = player1_left.max(player1_right);
            }
            else
            {
                let player2_left = -nums[left] + minimax(nums,left+1,right,!player1_turn,memo);
                let player2_right = -nums[right] + minimax(nums,left,right-1,!player1_turn,memo);
                
                result = player2_left.min(player2_right);
            }

            memo[left][right][turn] = Some(result);
            result
        }

        let mut memo = vec![vec![[None; 2]; n]; n];

        let score_difference = minimax(
            &nums,
            0,
            n - 1,
            true,
            &mut memo,
        );
        return score_difference>=0;
    }
}