黑白棋

文化娱乐游戏案例ID：205579

墨林

1 年经验· 苏嵌

微信扫码沟通，客服可协助直接对接工程师；如当前档期不合，也可继续推荐相似案例作者。

案例介绍

在此次的黑白棋程序中，我们使用了人工智能树搜索算法（最大最小搜索、蒙特卡洛树搜索），利用这种智能算法达成玩家与ai的智能对战。游戏中玩家不能点击违反规则的空地，在ai下棋时间中也同样无法下棋，需要等待ai落子之后才能下棋。违反规则时鼠标点击无效。
蒙特卡洛树搜索（简称 MCTS）是 Rémi Coulom 在 2006 年在它的围棋人机对战引擎「Crazy Stone」中首次发明并使用的的。它经历下面几个过程（重复千千万万次）：选择（Selection）扩展 (expansion)模拟（Simulation）回溯（Backpropagation）。
模拟借鉴了蒙特卡洛方法，快速走子，只走一盘，分出个胜负。每个节点（每个节点代表每个不同的局面）都有两个值，代表这个节点以及它的子节点模拟的次数和赢的次数，比如模拟了 10 次，赢了 4 盘，记为 4/10。节点分成三类：
未访问：还没有评估过当前局面
未完全展开：被评估过至少一次，但是子节点（下一步的局面）没有被全部访问过，可以进一步扩展
完全展开：子节点被全部访问过
我们找到目前认为「最有可能会走到的」一个未被评估的局面（双方都很聪明的情况下），并且选择它。选择的过程如下——从根节点出发，遵循最大最小原则，每次选择己方 UCT 值最优的一个节点，向下搜索，直到找到一个「未完全展开的节点」。
扩展（expansion），将刚刚选择的节点加上一个统计信息为「0/0」的节点，然后进入下一步模拟（Simluation）。
回溯（Backpropagation），即反向传播，从子节点开始，沿着刚刚向下的路径往回走，沿途更新各个父节点的统计信息。
最大最小搜索算法是在对抗搜索中最为基本的一种让玩家来计算最优策略的方法.。在开始之前我们需要定义如下基本概念：初始状态、玩家、行动、状态转移模型、终局状态检测和终局得分。