stratego中不可移动件的检测算法

我想这样的办法行得通:

// Cardinal directions
int[] dx = { 1, 0, -1,  0 };
int[] dy = { 0, 1,  0, -1 };

// Loop through each space
for (int j=0; j<10; j++) {
    for (int i=0; i<10; i++) {

        // Check if you have a movable piece there
        if(gameBoard[i][j].hasMovablePiece() && !gameBoard[i][j].hasEnemyPiece()) {

            // Check neighbors
            for (int k=0; k<4; k++) {
                int ni = i+dx[k];
                int nj = j+dy[k];

                // Bounds check
                if(ni >= 0 && nj >=0 && ni < 10 && nj < 10) {

                    // Check if space is an enemy or empty and not blocked
                    // If so we still have a move
                    if((!gameBoard[ni][nj].hasPiece() || gameBoard[ni][nj].hasEnemyPiece()) && !gameBoard[ni][nj].isBlocked()){
                        return false;
                    }
                }

            }
        }
    }
}

// We made it without finding a movable piece
return true;

这只需遍历每个正方形并检查它是否有您的块,以及它是否是一个可移动类型的块。然后它检查周围的空间,看看是否有敌人的碎片,或一个没有被封锁的空间。如果它找到一个,我们知道仍然有左移,所以我们退出。

最坏的情况是,你检查每个空间和每个邻居(大约500张支票),这真的不算什么。当你数到每一块的时候,你可以数得更快,如果你达到剩下的块数,你也可以退出。

Stratego的动作规则非常基本。有两个州。可以移动,也应该移动。

动起来很容易。可以移动实际上是一个简单的空间检查。

为什么不干脆:

boolean canMove() {
    return squareEmpty(myX - 1, myY) ||
        squareEmpty(myX + 1, myY) ||
        squareEmpty(myX, myY - 1) ||
        squareEmpty(myX, myY + 1));
}

显然,旗子和炸弹“可以移动”的程序总是返回false。这对童子军有效,因为他们需要至少一个空格来移动,所以这是有意义的。

唯一不能追踪的是“后退5倍”的限制,但这并不难。

最后:

movesAvailable = 0;
for(Piece p : pieces) {
    if (p.canMove()) {
        movesAvailable++;
    }
}

这几乎不是一个昂贵的过程。

我看不出威尔的答案会太贵的原因,但我会提供另一个想法只是为了笑一笑。一个选择是维护一个当前可移动的片段列表,每个玩家一个列表。检查一个玩家是否没有剩余的移动,就像查看列表的当前大小一样简单。

然而,代价是你必须在每次移动时都保持列表。一个棋子的移动可以打开它周围的任何棋子,以及自由的棋子。从概念上讲,你可以看到,这比检查黑板上的每一个正方形要困难得多。

我认为计算自由在这里可能是有意义的。

这样做的目的是要计算出你的集体作品能朝哪个方向发展。这相当于与你的可移动棋子相邻的开放方格或敌人棋子(可用方格)的数量。如果一个可用的正方形被你的一个以上的块触摸,那么它将被多次计数。我们将每个可用的正方形/潜在移动方向称为自由。

你从计算初始自由的数量开始。你只需数一下前排不沾水的活动件的数量。没有其他部件可以移动,每个部件只有一个可以移动的方向。

之后,更新自由数的算法相当简单。你计算旧位置的自由度,减去它阻塞的碎片数,再计算新位置的自由度,再减去它阻塞的碎片数。你把它加到总自由中,你就有了新的价值。

我有一段时间没有编码Java,所以我的例子将在伪代码/Python中,但是这个想法应该被转移。

directions = [(0,1),(0,-1),(1,0),(-1,0)]
for d in directions:
   if (SpaceIsAvailable(oldPosition + d)):
      liberties--
   if (SpaceIsMovable(oldPosition + d)):
      liberties++
   if(SpaceIsAvailable(newPosition + d)):
      liberties++
   if(SpaceIsMovable(newPosition + d)):
      liberties--

SpaceIsAvailable 如果位置为空或对手为真。 SpaceIsMovable 是真的,如果这个点是你的作品,是可移动的。

当对手移动他的棋子时,你的自由不能改变。既不 空间可用 或 可移动空间 将更改值。

如果你的文章被删除了,你只需要运行相同的算法,但是删除 newPosition 部分。

for d in directions:
   if (SpaceIsAvailable(position + d)):
      liberties--
   if (SpaceIsMovable(position + d)):
      liberties++

现在,如果 liberties > 0 ,你有可移动的碎片。你所需要做的就是跟踪两个玩家的整数,你可以跳过任何计算来确定是否有可用的棋子。

如果强制执行防止移动重复的规则,这就不太有效。我不知道你要怎么实现。如果你想知道哪些部分是不允许移动的,你可以简单地将自由的总数与它们的自由进行比较,而不是与 0 . 如果是相等的,那么就没有移动了。如果总的自由度低于不能移动的部分的自由度,那么我的算法或者你的代码可能有问题。

如果我读了正确的重复规则,一次只能有一块不能移动,因此只有一组你必须考虑的自由。

frozenLiberties = 0
if (frozenPiece):
   for d in directions:
      if (SpaceIsAvailable(frozenPiece + d)):
         frozenLiberties++
if (liberties > frozenLiberties):
    // moves available.
else:
    // No moves available.

需要注意的是,这里的所有算法要么忽略边界条件,要么检查它们。另一个可能的方法是把你的木板做成12x12,然后在边缘放些水。你必须在所有代码中解释这个,但是如果你有 Board 使用访问器获取有关特定正方形的信息,只需在获取结果之前减去一个。然后 board.GetSquare(0,0) 会把那块放在角落里,而 board.GetSquare(-1,5) 会把水还回去 board.GetSquare(3,10) . board.GetSquare(-2,1) 会抛出异常。

我认为有了这个,所有的算法都会简单得多,而不会使访问这些片段变得复杂。