改进极小化极大算法

Question

目前我正在使用C++开发一个黑白棋(Othello/Reversi)游戏，在算法方面我采用了Minimax算法来作为电脑玩家的智能决策。目前代码已经完成，但是当深度设置到可以产生半挑战性AI时，算法运行速度缓慢。

我的游戏基本设置是：通过一个二维数组表示棋盘，每个格子都被分配了一个值（xMarker, oMarker或underscore）。

以下是目前的Minimax算法代码：

signed int Computer::simulate(Board b, int depth, int tempMarker) {

if (depth > MAX_DEPTH || b.gameOver()) {
    int oppMarker = (marker == xMarker) ? oMarker : xMarker;
    return b.countForMarker(marker) - b.countForMarker(oppMarker);
}

//if we're simulating  our turn, we want to find the highest value (so we set our start at -64)
//if we're simulating the opponent's turn, we want to find the lowest value (so we set our start at 64)
signed int start = (tempMarker == marker) ? -64 : 64;

for (int x = 0; x < b.size; x++) {
    for (int y = 0; y < b.size; y++) {

        if (b.markerArray[x][y] == underscore) {

            Board *c = b.duplicate();

            if(c->checkForFlips(Point(x,y), tempMarker, true) > 0) {

                int newMarker = (tempMarker == xMarker) ? oMarker : xMarker;
                int r = simulate(*c, depth+1, newMarker);

                //'marker' is the marker assigned to our player (the computer), if it's our turn, we want the highest value
                if (tempMarker == marker) {
                    if(r > start) start = r;
                } else {
                //if it's the opponent's turn, we want the lowest value
                    if(r < start) start = r;
                }

            }

            delete c;

        }

    }
}

return start;

}

函数 checkForFlips() 返回在给定单元格下棋所导致的翻转数量。目前 MAX_DEPTH 设为 6，运行速度较慢（每次下棋大约需要 10-15 秒）。

我目前想到的唯一主意就是每次都存储树形结构，然后从上次离开的地方继续进行，但我不确定如何实现这一点，或者它是否太有效了。如果您有任何想法或建议，将不胜感激！

- williamg

---

你那边可能存在内存泄漏问题。 - Gilad Naor

我对C++还比较新，能不能和我分享一下这个泄漏（leak）？ - williamg

搜索“RAII”。通常情况下，如果您自己编写delete，则应非常小心。例如，如果simulate()抛出异常，则c将不会被删除。 - Gilad Naor

Answer 1

计算最小极大值较为耗时。 第一个可能的优化是alpha-beta剪枝： http://en.wikipedia.org/wiki/Alpha-beta_pruning

- Shiroko

---

我刚刚实现了这个功能，运行时间减少了一半！感谢您的分享！ - williamg

Answer 2

不应该复制棋盘，这样非常低效。在递归调用之前进行移动，但要保存足够的信息，在从递归调用返回后撤销相同的移动。这样您只需要一个棋盘。

但是Shiroko是正确的，alpha-beta剪枝是第一步。

- jahhaj

---

我会考虑实现这个。谢谢你的提示！ - williamg

@williamg，正如你和jahhaj所正确指出的那样，优化的第一步是算法的大O复杂度。只有在此之后，才应该考虑代码优化。而为此，第一件最重要的事情就是进行性能分析。 - Gilad Naor

Answer 3

最明显的改进方法是通过alpha-beta剪枝或negascout。

然而，如果你想坚持使用minimax，你不能让它运行得太快，因为这是一种蛮力算法。改进的一种方法是将其改为Negamax，这将消除此代码中所需的某些逻辑。另一种方法是使用一维数组代替Board来表示棋盘。为了使计算更容易，使用长度为100，以便位置以行-列形式表示（例如，索引27是第2行，第7列）。

但如果你想让它运行得更快，尝试进行剪枝。

- jcolen19

Answer 4

@Shiroko的建议很棒，但还有更多的优化机会。

你通过值传递了Board的状态，然后在循环内复制它。我会将Board作为指针或const Board& b来传递。如果仍然很昂贵，你可以使用指向单个Board的指针，在评估完后反转每个移动。无论如何，不要在堆上分配它。

你也可以在多个核心上运行这个算法。你需要编写一个使用openmp（或等效）的for循环的变种。

- user180326

---

好的观点，我错过了复制棋盘时是按值传递的。 - jahhaj