1

In 如何在 Grundy 的游戏中将一堆分成两堆？

将一个堆分成任意数量的堆（其中没有两个相等）怎么样？

4

2 回答 2

1

此类游戏在“数学游戏的获胜方式”系列丛书中进行了详细分析。您正在寻找的大部分内容可能都在第 1 卷中。

您还可以查看以下链接：Nimbers (Wikipedia)、Sprague-Grundy theorem (Wikipedia)或搜索“组合博弈论”。

我对此的了解相当生疏，所以恐怕我无法帮助您解决这个具体问题。如果您已经知道我链接的所有内容，我的借口。

编辑：一般来说，解决这些类型的游戏的方法是“建立”堆栈大小。因此，从筹码 1 开始，并决定谁以最佳方式获胜。然后对一堆 2 做同样的事情，它可以分成 1 和 1。移动到 3，可以分成 1 和 2。4 也一样（这里变得更棘手）：3 & 1 或 2 & 2、利用Spague-Grundy定理和nimbers的代数规则，你可以计算出谁会赢。继续前进，直到达到您需要知道答案的堆栈大小。

编辑 2：我在评论中谈论的网站似乎已关闭。这是它的备份链接：Wayback Machine - Introduction to Combinatorial Games。

于 2012-03-21T11:22:24.493 回答
0

Grundy 的游戏，以及许多类似的游戏，都可以用这样的算法来解决：

//returns a Move object representing the current player's optimal move, or null if the player has no chance of winning
function bestMove(GameState g){
    for each (move in g.possibleMoves()){
        nextState = g.applyMove(move)
        if (bestMove(nextState) == null){
            //the next player's best move is null, so if we take this move, 
            //he has no chance of winning. This is good for us!
            return move;
        }
    }

    //none of our possible moves led to a winning strategy.
    //We have no chance of winning. This is bad for us :-(
    return null;
}

GameState 和 Move 的实现取决于游戏。对于 Grundy 的游戏，两者都很简单。

GameState存储一个整数列表，表示游戏中每个堆的大小。

Move存储一个initialHeapSize整数和一个整数resultingHeapSizes列表。

GameState::possibleMoves遍历其堆大小列表，并确定每个的合法划分。

GameState::applyMove(Move)返回 GameState 的副本，但给予它的移动应用于棋盘。

GameState::possibleMoves可以像这样为“经典”Grundy's Game 实现：

function possibleMoves(GameState g){
    moves = []
    for each (heapSize in g.heapSizes){
        for each (resultingHeaps in possibleDivisions(heapSize)){
            Move m = new Move(heapSize, resultingHeaps)
            moves.append(m)
        }
    }
    return moves
}

function possibleDivisions(int heapSize){
    divisions = []
    for(int leftPileSize = 1; leftPileSize < heapSize; leftPileSize++){
        int rightPileSize = heapSize - leftPileSize
        if (leftPileSize != rightPileSize){
            divisions.append([leftPileSize, rightPileSize])
        }
    }
    return divisions
}

修改它以使用“分成任意数量的不等桩”规则只是改变possibleDivisions.

我没有准确计算过，但未优化的 bestMove 有一个非常疯狂的最坏情况运行时。一旦你开始给它一个大约 12 块石头的起始状态，你会得到很长的等待时间。所以你应该实施记忆来提高性能。

为获得最佳结果，请保持每个 GameState 的堆大小列表排序，并丢弃任何大小为 2 或 1 的堆。

于 2012-03-21T18:04:41.307 回答