Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Algorithm to detect no movable pieces in Stratego

Tags:

java

algorithm

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].

like image 613
Maleki Avatar asked Jan 22 '23 07:01

Maleki


1 Answers

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.

like image 196
Will Hartung Avatar answered Feb 04 '23 15:02

Will Hartung