老虎和山羊：JavaScript 和 HTML5 中的一个有趣的 AI 游戏

• 下载 TG2.zip - 214.2 KB

引言   

我一直对国际象棋引擎编程以及国际象棋引擎中使用的各种搜索算法很感兴趣，但我一直没有一个简单的例子来研究并掌握其中的主要思想。我总是需要花费大量时间去研究成千上万行的技巧、优化和智能技术，才能开始理解这类程序的通用结构。然后，我在学校参加了一门入门级人工智能课程，在那里我使用著名的AIMA框架（本项目源代码在很大程度上借鉴了该框架）完成了几个有趣的 AI 项目，最终我意识到一切原来如此简单，那种困惑最终烟消云散了。在那门课上，我被分配到的一个项目就是实现“老虎与山羊”游戏，这是一款不像国际象棋那样广为人知的印度棋盘游戏，但它拥有非常相似且更简单的结构和规则。经过仔细考虑，我决定用 JavaScript 和 HTML 来实现这个游戏，以保持其简单性和跨平台性。本文的目的是提供一个代码基础，用于理解和比较不同的对抗搜索算法，如 Minimax 和 Alpha-Beta，并使用尽可能少的特定平台或框架知识来理解此类 AI 程序的通用结构。

背景   

“老虎与山羊”是一款印度双人棋盘游戏，在一个特殊的棋盘上进行，如下所示：

一个玩家必须一次一只地将山羊引入场内，在所有山羊都入场前不能移动任何山羊。另一个玩家扮演老虎，可以通过跳跃的方式吃掉山羊。老虎每次只能朝一个方向移动一格（像山羊一样），并且只能跳跃一格。它们的目标是吃掉所有的山羊。山羊的目标是包围老虎，使它们无法移动。我还添加了一个规则，即如果某个局面出现超过两次，游戏将以平局结束，以避免重复。要移动棋子，用户需要点击一个棋子，然后点击目标方格。我建议在继续阅读下一节之前，先下载源代码并运行几次游戏来理解游戏规则。

使用代码

   这类对抗游戏的核心是“游戏状态”对象，它代表了游戏的当前状态，即棋子的位置或该轮谁来走棋。我在 TigersAndGoats.js 文件中用 GameState() 类表示了游戏的当前状态，如下所示：

function GameState() {
    this.SideToPlay = 1; //0 == Tigers, 1 == Goats same as AgentIndex
    this.OutsideGoats = 15;
    //array of 23 elements corresponding to 23 squares of the board.
    // Each square is either empty or has a goat or a tiger in it.
    this.CurrentPosition = ['T', 'E', 'E', 'T', 'T', 'E', 'E', 'E', 
      'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E', 'E'];
    this.Hash = 0; // A compact representation of the game state. Hash is a 51 bit binary number.
    this.Result = -1; // 0 == Tigers win, 1 == Goats Win, 2 == Draw, -1 == no result
}  

这可能不是最高效的表示方法，但它是最简单的。

当游戏首次加载时（window.onload() 函数），会创建一个新的 GameState 对象并将其存储为游戏的当前状态。然后，会调用 UIUtility.js 文件中的 UpdateUserInterface() 函数，该函数负责查看当前游戏状态并相应地更新游戏棋盘和用户界面元素。

一旦我们表示了游戏的当前状态，我们就可以获取玩家在该状态下可以采取的所有可用动作或移动的列表。

var state = new GameState();

var actions = state.getLegalActions();  

每当用户进行一次移动时，就会调用 ProcessUserInput()，它会判断用户的操作是否在合法动作列表中，如果是，则通过生成后继状态来完成移动，然后更新用户界面。

var newState = oldState.generateSuccessor(action, history);  

但是，当轮到计算机走棋时，就会调用 computerPlay() 函数。它会启动一个新的Web Worker，这是 JavaScript 中线程的等价物，然后 Worker 会运行 agent.getAction()，该函数会进行搜索，并在搜索树深入时不断返回最佳动作。

算法

我主要实现了 5 种不同的搜索算法：Minimax、Expectimax、Alpha-Beta、Scout 和 MTD(f)[2]。所有这些算法都在迭代加深框架内运行。例如，这是 Minimax 代理的 getAction() 函数的一部分：

var depth = 1;
var result;
while (true) {
    result = minimax(gameState, depth, this.Index);
    //result = score, action, depth, nodesExpanded
    postMessage([result[0], result[1], depth, nodesExpanded]);
    depth++;
}

关于空窗搜索

Alpha-Beta 剪枝算法通过仅搜索搜索树中可能改变树顶最终得分的节点来提高效率。换句话说，那些对搜索结果没有影响的分支会被剪掉。它通过递归地为搜索树中的每个节点分配一个期望窗口（最初是 [-Inf, +Inf]）来实现这一点。首先，搜索树顶部的最上层最大化节点会告诉它的最小化子节点，它正在寻找一个介于 -Inf 和 +Inf 之间的值。然后，随着搜索的进行，一些值会冒泡到搜索树的顶层，最上层的最大化节点会被赋予一个临时最大值。之后，最大化节点只关心高于临时最大值的值，因此它会给它的子节点分配一个期望窗口的下限：[临时最大值, +Inf]。子节点知道最大化节点对低于下限的值不感兴趣，因此，当它们从它们的子节点获得一个低于下限的值时，由于它们是最小化节点，并且知道它们最终返回的任何值都将低于或等于该值，它们会立即返回该值，从而结束该树分支的搜索（剪掉分支，并被其父节点最大化节点忽略！）。同样的情况也适用于最小化节点以及它们如何为最大化子节点分配上限。随着算法深入搜索树，期望窗口只会变小，结果是更多的剪枝（也称为截止）会发生，我们剪枝越多，访问的节点就越少，搜索算法的速度就越快。

Scout 算法通过在大多数节点上进行空窗或零窗搜索，运行速度甚至比 Alpha-Beta 更快。空窗搜索就像一个测试。假设树顶的最大化节点想知道搜索结果是否可能高于其当前分配的临时最大值。如果不能，那么继续搜索就没有意义了。在这种情况下，最大化节点应该立即结束搜索，返回其临时最大值，从而节省时间！该测试通过将期望窗口的宽度设置为零来完成。例如，如果最大化节点的当前临时最大值为 40，它可以将期望窗口设置为 [40, 40]，并告诉其子节点它不关心低于 40 的任何值，因此立即返回，并且如果存在任何高于 40 的值，则立即返回，因为它不关心该值是多少，它只想知道是否存在！

Scout 算法仅对第一个子节点进行完整的 Alpha-Beta 搜索，然后测试其他子节点是否可以做得更好！由于这些测试是以零宽度期望窗口运行的，因此会有更多的截止，并且运行速度比常规 Alpha-Beta 快得多。因此，如果存在良好的移动排序，即 Scout 算法的第一个猜测是最佳猜测，那么 Scout 的运行速度将比 Alpha-Beta 快得多。

在迭代加深框架中实现良好的移动排序的一种方法是，将先前较低深度搜索的结果存储在置换表中，然后在搜索树中遇到相同的游戏状态时，查找置换表并优先考虑先前已知的最佳移动。

MTD(f) 通过猜测一个分数，然后在搜索树顶层立即进行零窗搜索，从而运行速度甚至比 Scout 还快！实际上，它会进行一个猜测，然后进行一个测试来检查猜测是否正确，然后相应地调整猜测。在我的测试中，MTD(f) 在起始位置的表现不如带内存的 Scout，但在平均情况下，给定大量测试位置，MTD(f) 的速度应该比 Scout 快大约 10%[3]。

一些结果

为了进行性能比较，我在我的 2.5 GHz Core i3 笔记本电脑上，以 6 的深度限制，在起始位置运行了所有算法。结果如下：

	Expectimax	Minimax	Alpha-Beta	Alpha-Beta 带内存	Scout 不带内存	Scout 带内存	MTD(f)
达到的最大深度	6	6	6	6	6	6	6
时间（毫秒）	52,219	51,301	1,585	577	1,015	559	648
扩展的总节点数	3,769,060	3,769,060	111,450	27,842	68,421	24,253	31,204
访问的叶子节点数	2,997,798	2,997,798	58,835	12,202	41,177	10,681	12,874
得分	52.3	49	49	49	49	49	49
移动	-1,-1,1	-1,-1,7	-1,-1,7	-1,-1,7	-1,-1,7	-1,-1,7	-1,-1,7

 

值得关注的点  

哈希表

每个新游戏状态的哈希值在调用 gameState.generateSuccessor 函数时生成，并存储在该新游戏状态中：

state.Hash = 0;
for (var i = 0; i < state.CurrentPosition.length; i++) {
    if (state.CurrentPosition[i] == 'T')
        state.Hash += 2;
    else if (state.CurrentPosition[i] == 'G')
        state.Hash += 1;
    state.Hash *= 4;
}
state.Hash *= 4;
state.Hash += state.OutsideGoats;
state.Hash *= 2;
state.Hash += state.SideToPlay; 

此算法生成了一个完美的哈希，消除了哈希冲突的可能性。因此，哈希值可以用来判断两个游戏状态是否相等，例如判断一个局面是否以前在历史记录中出现过。

哈希的另一个用途是在置换表中。在具有内存的这些搜索算法的每次迭代中，算法都会将搜索结果存储在哈希表中。

if (TTresult == null || (TTresult != null && TTresult[2] < depth))
    transpositionTable.insert(state.Hash, [action, score, depth, a, b]); 

然后，在每次迭代开始时，算法会检查是否以前进行过具有更深深度的相似搜索，如果是，则从置换表中返回结果以节省时间。但如果没有，它仍然可以利用这些信息进行移动排序。

var TTresult = transpositionTable.find(state.Hash);
if (TTresult != null) {
    if (TTresult[1] >= depth) {
        if (TTresult[2] == TTresult[3]) {
            history.pop();
            return [TTresult[2], TTresult[0]];
        }
        if (TTresult[2] > b) {
            history.pop();
            return [TTresult[2], TTresult[0]];
        }
        if (TTresult[3] < a) {
            history.pop();
            return [TTresult[3], TTresult[0]];
        }
        a = Math.max(a, TTresult[2]);
        b = Math.min(b, TTresult[3]);
    }
    for (var i = 0; i < actions.length; i++) {
        if (actions[i].compare(TTresult[0])) {
            actions.splice(i, 1);
            actions.splice(0, 0, TTresult[0]);
            break;
        }
    }
} 

现在，经过几秒钟的搜索后，哈希表中将有数百万个元素。如果哈希表仅仅是一个元素列表，并且每次我们要查找哈希表时都必须遍历数百万个元素，那么具有内存的搜索算法的性能将会大大降低。因此，哈希表插入和查找操作应该比 O(n) 更快。为此，我实现了一个自定义哈希表，具有恒定的插入和查找操作时间（O(1)）。具体来说，在实践中，无论哈希表中包含多少元素，插入和查找（find）操作只需要 7 步即可完成。

因为哈希键始终是一个 51 位二进制数，我们可以创建如下的树：

HashTree.prototype.find = function(key) {
    function treeSearch(depth, key, node) {
        var nextKey = key & 0xff;
        if (depth == 1 && node.Nodes[key] != null) {
            return node.Nodes[key].Data;
        }
        else if (node.Nodes[nextKey] != null) {
            key = key - (key & 0xff);
            return treeSearch(depth - 1, key / 256, node.Nodes[nextKey]);
        }
        return null;
    }
    return treeSearch(7, key, this);
}

这样，插入和查找操作的运行时间将仅取决于哈希键的长度，这是一个常数（51 位）。

运行程序

如果您使用 Google Chrome，您应该使用 `--allow-file-access-from-files` 标志运行它。这是由于 Chrome 的安全限制。

历史 

• 2013年12月10日
• 修复了置换表更新算法中的一个错误，该错误曾导致带内存的算法达到异常高的深度
• 重新实现了 MTD(f)，使其与原始论文中的版本相似
• 提高了 UI 响应能力
• 添加了一个新指标来衡量每次迭代访问的叶子节点数量
• 更新了结果表，以进行更有意义的比较
• 2013 年 12 月 8 日，修复了下载链接
• 2013 年 12 月 7 日，修复了文章图片

参考

[1] Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, ISBN 0-13-790395-2

[2] Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1995). A New Paradigm for Minimax Search. Technical Report EUR-CS-95-03

[3] Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1996). Best-First Fixed-Depth Minimax Algorithms. Artificial Intelligence, Vol. 87, Nos. 1-2, pp. 255-293. ISSN 0004-3702