每日算法 — 使用java实现威佐夫博弈：黄金分割比与必败态分析

可莉爸爸 AI算法

威佐夫博弈（Wythoff’s Game）是组合数学中最优雅的取石子游戏之一，由荷兰数学家 Willem Abraham Wythoff 于 1907 年提出。它的规则极其简单，却隐藏着与黄金分割比密切相关的深刻数学结构。本文将用 Java 实现一个完整的命令行版威佐夫博弈，并深入剖析其必败态判定算法与最优策略。

一、游戏规则

桌上有两堆石子，两名玩家轮流操作。每轮玩家必须执行以下两种操作之一：

  • 从其中一堆中取走任意数量的石子（至少取 1 个）；
  • 从两堆中同时取走相同数量的石子（至少各取 1 个）。

取走最后一颗石子的玩家获胜。游戏初始状态可以随机生成两堆石子的数量。

二、核心算法：必败态与黄金分割比

2.1 必败态（P-position）的定义

在组合博弈论中，必败态（P-position，Previous player win）是指轮到当前玩家行动时，无论怎么操作都会让对手进入必胜态的状态。威佐夫博弈的必败态序列如下：

k a_k b_k
0 0 0
1 1 2
2 3 5
3 4 7
4 6 10
5 8 13

观察这组数对，你会发现一个惊人的规律：相邻两项的比率趋近于 1.618…，也就是黄金分割比 φ。

2.2 数学定理

威佐夫博弈的必败态 (a_k, b_k) 满足如下通项公式：

  • a_k = ⌊k × φ⌋
  • b_k = ⌊k × φ²⌋ = a_k + k

其中 φ = (1 + √5) / 2 ≈ 1.6180339887。由于 φ² = φ + 1，所以 b_k 也可以直接写成 a_k + k。

这意味着：对于状态 (a, b) 且 a ≤ b，令 k = b − a，该状态是必败态当且仅当 a == ⌊k × φ⌋。

2.3 最优策略

如果当前状态是必败态，任何合法移动都会进入非必败态（对手有利）；如果当前状态不是必败态，一定存在至少一种移动方式可以到达某个必败态，从而将”困境”抛给对手。

因此，AI 的核心策略就是：每当轮到自己时，判断是否处于必败态；若不是，则计算并移动到最近的必败态。

三、Java 项目实现

下面是完整的项目结构，包含三个核心类：WythoffGame（主程序与游戏循环）、GameState（状态管理）、WythoffAI（AI 决策）。

3.1 GameState.java — 游戏状态与移动验证

package wythoff;

/**
 * 游戏状态类，封装两堆石子的数量，并提供移动合法性校验。
 */
public class GameState {
    private int pileA; // 第一堆石子数
    private int pileB; // 第二堆石子数

    public GameState(int a, int b) {
        this.pileA = a;
        this.pileB = b;
    }

    public int getPileA() { return pileA; }
    public int getPileB() { return pileB; }

    /**
     * 判断游戏是否结束（两堆均为 0）。
     */
    public boolean isGameOver() {
        return pileA == 0 && pileB == 0;
    }

    /**
     * 执行一次合法移动。
     *
     * @param takeA 从第一堆取走的数量（可以为 0）
     * @param takeB 从第二堆取走的数量（可以为 0）
     * @return 移动后的新状态；若非法则返回 null
     */
    public GameState move(int takeA, int takeB) {
        // 必须至少取走一颗石子
        if (takeA < 0 || takeB < 0 || (takeA == 0 && takeB == 0)) {
            return null;
        }
        // 不能超出现有石子数
        if (takeA > pileA || takeB > pileB) {
            return null;
        }
        // 威佐夫博弈规则：要么只从一堆取，要么从两堆取相同数量
        boolean singlePile = (takeA == 0 && takeB > 0) || (takeA > 0 && takeB == 0);
        boolean bothEqual = (takeA == takeB && takeA > 0);
        if (!singlePile && !bothEqual) {
            return null;
        }
        return new GameState(pileA - takeA, pileB - takeB);
    }

    @Override
    public String toString() {
        return "(" + pileA + ", " + pileB + ")";
    }
}

3.2 WythoffAI.java — 必败态判定与最优决策

package wythoff;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 威佐夫博弈 AI，基于必败态（P-position）理论实现最优策略。
 *
 * 核心公式：
 *   φ = (1 + sqrt(5)) / 2 ≈ 1.6180339887
 *   状态 (a, b) 且 a ≤ b 是必败态 ⟺ a == floor((b - a) * φ)
 */
public class WythoffAI {
    // 黄金分割比，预计算以提高精度
    private static final double PHI = (1.0 + Math.sqrt(5.0)) / 2.0;
    private final Random random = new Random();

    /**
     * 判断给定状态是否为必败态。
     */
    public boolean isLosingPosition(int a, int b) {
        if (a == 0 && b == 0) {
            return true; // (0, 0) 是终止必败态
        }
        int small = Math.min(a, b);
        int large = Math.max(a, b);
        int diff = large - small;
        // 关键判定：small 是否等于 floor(diff * φ)
        int expected = (int) Math.floor(diff * PHI);
        return small == expected;
    }

    /**
     * 寻找从当前状态出发可以到达必败态的最佳移动。
     * 若当前已经是必败态，则随机执行一次合法移动。
     *
     * @return int[2] = {takeA, takeB}，表示从两堆分别取走的数量
     */
    public int[] findBestMove(int a, int b) {
        // 若已是必败态，无法强制获胜，随机走
        if (isLosingPosition(a, b)) {
            return getRandomMove(a, b);
        }

        int small = Math.min(a, b);
        int large = Math.max(a, b);
        int diff = large - small;

        // 策略 1：尝试将状态调整为 (floor(k*φ), floor(k*φ)+k) 形式的必败态
        int targetA = (int) Math.floor(diff * PHI);
        int targetB = targetA + diff;

        // 由于当前不是必败态，small 一定不等于 targetA
        // 如果 small > targetA，说明多出来的石子全部在 small 这堆
        if (small > targetA) {
            int reduce = small - targetA;
            // 需要从两堆同时减少 reduce，保持差值 diff 不变
            if (a == small) {
                return new int[]{reduce, reduce};
            } else {
                return new int[]{reduce, reduce};
            }
        }

        // 策略 2：尝试让差值变小，找到合适的 k 使得必败态可达
        // 枚举 k 从 0 到 large，寻找满足条件的必败态
        for (int k = 0; k <= large; k++) {
            int ak = (int) Math.floor(k * PHI);
            int bk = ak + k;
            // 检查 (ak, bk) 是否能通过合法移动从 (a, b) 到达
            if (ak <= a && bk <= b) {
                // 情况 A：从两堆同时减少相同数量
                if (a - ak == b - bk) {
                    return new int[]{a - ak, b - bk};
                }
            }
            if (ak <= b && bk <= a) {
                if (b - ak == a - bk) {
                    return new int[]{a - bk, b - ak};
                }
            }
            // 情况 B：只从第一堆减少到 ak 或 bk
            if (bk == b && ak < a) {
                return new int[]{a - ak, 0};
            }
            if (ak == b && bk < a) {
                return new int[]{a - bk, 0};
            }
            if (bk == a && ak < b) {
                return new int[]{0, b - ak};
            }
            if (ak == a && bk < b) {
                return new int[]{0, b - bk};
            }
        }

        // 理论上不会到达此处，作为兜底返回随机移动
        return getRandomMove(a, b);
    }

    /**
     * 生成一次随机合法移动。
     */
    private int[] getRandomMove(int a, int b) {
        List<int[]> moves = new ArrayList<>();
        // 枚举所有从单堆取的移动
        for (int i = 1; i <= a; i++) moves.add(new int[]{i, 0});
        for (int j = 1; j <= b; j++) moves.add(new int[]{0, j});
        // 枚举所有从两堆同时取相同数量的移动
        int maxBoth = Math.min(a, b);
        for (int k = 1; k <= maxBoth; k++) moves.add(new int[]{k, k});

        return moves.get(random.nextInt(moves.size()));
    }
}

3.3 WythoffGame.java — 主程序与游戏循环

package wythoff;

import java.util.Scanner;

/**
 * 威佐夫博弈主程序，支持人机对战与 AI 自动演示模式。
 */
public class WythoffGame {

    private final WythoffAI ai = new WythoffAI();
    private final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        WythoffGame game = new WythoffGame();
        System.out.println("===== 威佐夫博弈 (Wythoff's Game) =====");
        System.out.println("规则：两堆石子，每次可单堆取任意个，或双堆取相同个。取最后石子者胜。\n");

        System.out.println("请选择模式：");
        System.out.println("1. 人机对战（玩家先手）");
        System.out.println("2. 人机对战（AI 先手）");
        System.out.println("3. 观看 AI 自我对弈演示");
        System.out.print("输入选项 (1/2/3): ");
        int mode = game.scanner.nextInt();

        System.out.print("请输入第一堆石子数量: ");
        int a = game.scanner.nextInt();
        System.out.print("请输入第二堆石子数量: ");
        int b = game.scanner.nextInt();

        GameState state = new GameState(a, b);

        switch (mode) {
            case 1 -> game.playHumanVsAI(state, true);
            case 2 -> game.playHumanVsAI(state, false);
            case 3 -> game.playAIDemo(state);
            default -> System.out.println("无效选项。");
        }
    }

    /**
     * 人机对战模式。
     *
     * @param state     初始状态
     * @param humanFirst 是否玩家先手
     */
    private void playHumanVsAI(GameState state, boolean humanFirst) {
        boolean humanTurn = humanFirst;
        int round = 1;

        while (!state.isGameOver()) {
            System.out.println("\n第 " + (round++) + " 轮 —— 当前状态: " + state);

            if (humanTurn) {
                System.out.print("你的回合。请输入 (takeA takeB): ");
                int ta = scanner.nextInt();
                int tb = scanner.nextInt();
                GameState next = state.move(ta, tb);
                if (next == null) {
                    System.out.println("非法移动，请重新输入！");
                    round--;
                    continue;
                }
                state = next;
                if (state.isGameOver()) {
                    System.out.println("你取走了最后一颗石子，恭喜你获胜！");
                    return;
                }
            } else {
                int[] move = ai.findBestMove(state.getPileA(), state.getPileB());
                System.out.println("AI 回合 —— 从两堆分别取走: (" + move[0] + ", " + move[1] + ")");
                state = state.move(move[0], move[1]);
                if (state.isGameOver()) {
                    System.out.println("AI 取走了最后一颗石子，AI 获胜！");
                    return;
                }
            }
            humanTurn = !humanTurn;
        }
    }

    /**
     * AI 自我对弈演示，展示从同一初始状态双方均采取最优策略的走法。
     */
    private void playAIDemo(GameState state) {
        System.out.println("\n=== AI 自我对弈演示（双方均采取最优策略）===");
        int round = 1;
        boolean turnA = true; // true = AI-A, false = AI-B

        while (!state.isGameOver()) {
            System.out.println("第 " + (round++) + " 轮 —— 当前状态: " + state);
            String name = turnA ? "AI-A" : "AI-B";

            boolean isLosing = ai.isLosingPosition(state.getPileA(), state.getPileB());
            System.out.println("  " + name + " 分析: 当前" + (isLosing ? "是" : "不是") + "必败态");

            int[] move = ai.findBestMove(state.getPileA(), state.getPileB());
            System.out.println("  " + name + " 执行移动: (" + move[0] + ", " + move[1] + ")");
            state = state.move(move[0], move[1]);

            if (state.isGameOver()) {
                System.out.println("\n" + name + " 取走最后一颗石子，获得胜利！");
            }
            turnA = !turnA;
        }
    }
}

3.4 编译与运行

将以上三个文件放入同一包目录下，执行：

# 编译
javac wythoff/*.java

# 运行
java wythoff.WythoffGame

四、算法复杂度分析

操作 时间复杂度 空间复杂度 说明
必败态判定 O(1) O(1) 仅涉及一次乘法和取整
AI 最优决策 O(n) O(1) n 为较大堆的石子数，最坏需枚举所有 k
随机移动生成 O(n) O(n) 需构建全部合法移动列表后随机选取

在实际游戏中，由于 findBestMove 中策略 1（差值不变，同时减少）能覆盖绝大多数非必败态，AI 的决策通常能在常数时间内完成。只有当策略 1 不适用时才会进入枚举分支。

五、扩展思考

  1. φ 的精度问题：Java 的 double 类型在石子数非常大（超过 10⁹）时可能因浮点精度导致误判。此时可改用 Math.floor(diff * PHI + 0.5) 做补偿，或预计算一个足够大的必败态查找表。

  2. 记忆化优化：对于频繁重复的对局，可以将 findBestMove 的结果缓存到 HashMap 中，将后续查询降至 O(1)。

  3. 图形化扩展：可以将命令行版本扩展为 Swing/JavaFX 图形界面，用两列方块直观表示石子堆，并增加动画效果展示 AI 的取石过程。

六、总结

威佐夫博弈以其简洁的规则和背后深奥的数学结构，成为学习组合博弈论的绝佳案例。通过本文的 Java 实现，你不仅掌握了一个可交互的完整游戏项目，更理解了如何利用黄金分割比快速判定必败态、如何基于理论构造 unbeatable 的 AI 对手。这种”从数学定理到代码实现”的思维路径，正是算法设计的精髓所在。

Tagged with: