Algorithm to detect no movable pieces in Stratego.

Question

I am creating a Stratego Game and am having trouble creating an algorithm that can detect when there are no more possible moves because all your pieces are gone or the remaining pieces are unmovable or trapped by forbidden squares, unmovable pieces, or other trapped pieces.

For simplicity you can think of the board as an array of Squares which can contain pieces.

Square[][] gameBoard = new Square[10][10]

Squares have easily checkable state such as hasPiece(), hasEnemyPiece(), hasUnMovablePiece(), hasMoveablePiece(), isBlocked().

It would also probably be nice if this algorithm wasn't run every time a player moved but maybe checked in the beginning and then only certain conditions were checked when the player moved.

[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
[B][ ][ ][ ][ ][ ][B][B][ ][ ]
[F][B][ ][ ][ ][B][3][4][B][ ]

This is an example situation towards the end of a game, you need to be able to check each of the non-movable pieces (3 & 4) to see whether they are movable[not trapped by water(blocked), other unmovable pieces(bomb or flag), or other trapped pieces].

Answer 1

Stratego's movement rules are pretty basic. There's two states. CAN move, and SHOULD move.

CAN move is easy. CAN move is practically a simple space check.

Why not simply:

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

Obviously, Flags and Bombs "canMove" routine returns false all the time. This works for Scouts because they need at least one blank to move, so this counts for that.

The only thing this does not track is the "back-forth 5 times" limit, but, that's hardly arduous.

Finally:

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

This is hardly an expensive process.

Answer 2

I think something like this would work:

// 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;

This simply iterates over each square and checks if it has your piece, and that it is a moveable type piece. Then it checks the surrounding spaces to see if there are enemy pieces, or a non-blocked space. If it finds one, we know that there are still moves left, so we exit.

At worst, you check every space and every neighbor (~500 checks) which is really not much at all. You could make it faster by counting as you get to each of your pieces, and if you reach the number of pieces you have left, you can exit as well.

Answer 3

I don't see any reason why Will's answer would be too expensive, but I'll provide another idea just for grins. One option would be to maintain a list of pieces that are currently movable, one list for each player. Checking to see if there are no moves left to a player is as simple as looking at the current size of that list.

The cost, however, is that you have to maintain the list on every move. A single piece's move can unblock any of the pieces around it, as well as block pieces that were free. Conceptually, you can see, this is much more difficult than checking every square on the board.

Answer 4

I think counting liberties might make sense here.

The idea is to keep a count of how many directions your collective pieces can move in. This is equivalent to the number of open squares or enemy pieces (available squares) adjacent to your movable pieces. If an available square is touched by more than one of your pieces, then it is counted multiple times. We'll call each available square/potential move direction a liberty.

You start by counting the number of initial liberties. You only have to count the number of movable pieces in the front row not touching water. No other piece can move and each piece only has one direction they can move in.

After that, the algorithm to update the number of liberties is fairly simple. You count the number of liberties the old position has, subtracting the number of your pieces it blocks and count the number of liberties the new position has, again subtracting the number of pieces it blocks. You add this to the total liberties and you have the new value.

I haven't coded java for a while, so my examples will be in pseudo code/python, but the idea should transfer.

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 is true if the spot is empty or the opponent. SpaceIsMovable is true if the spot is your piece and is movable.

When the opponent moves his piece, your liberties can't change. Neither SpaceIsAvailable or SpaceIsMovable will change values.

If your piece is removed, you just run the same algorithm, but drop the newPosition section.

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

Now, if liberties > 0, you have movable pieces. All you need to do is keep track of an integer for both players, and you can skip any calculations determining if any pieces are available.

This doesn't quite work if you enforce the rules preventing move repetition. I'm not sure how you're going to implement that. If you do it by figuring out which pieces aren't allowed to move, you can simply compare the total number of liberties to their liberties instead of to 0. If it's equal, then there's no moves left. If the total liberties is lower than the liberties of the pieces that can't move, there's either something wrong with my algorithm or your code.

If I read the rules for repetition correctly, there can only be one piece at a time that can't move and thus only one set of liberties that you have to consider.

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

Answer 5

One thing to note is that all the algorithms here either ignore the boundary conditions or check for them. Another possibility would be to just make your board 12x12 and put water along the edges. You have to account for this in all your code, but if you have a Board object with an accessor to get the info about a particular square, just subtract one before getting the result. Then board.GetSquare(0,0) would return the piece in the corner, whereas board.GetSquare(-1,5) would return water, as would board.GetSquare(3,10). board.GetSquare(-2,1) would throw an exception.

I think with this, all the algorithms would be much simpler, without complicating access to the pieces.