Moving Shapes Algorithm in Stratego

Question

I am creating a Strategyo Game, and I 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 motionless or captured by forbidden squares, fixed pieces or other captured pieces.

For simplicity, you can think of the board as an array of squares that can hold pieces.

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

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

It would also be nice if this algorithm did not start every time the player moved, but perhaps was checked at 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 of a situation at the end of the game, you should be able to check each of the fixed parts (3 and 4) to see if they are moving (not trapped in water (blocked), other integral parts (bomb or flag) or other captured parts] .

Answer 1

I think something like this will 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; 

It just repeats itself over each square and checks to see if it has your piece and that it is a movable type. He then checks the surrounding spaces to see if there are enemy units or unblocked spaces. If he finds one, we know that there are still moves, so we go out.

In the worst case, you check every place and every neighbor (~ 500 checks), which is actually not so much. You can do it faster by calculating how you get to each of your parts, and if you reach the number of remaining parts, you can also exit.

Answer 2

Stratego traffic rules are pretty simple. There are two states. CAN move, and SHOULD move.

CAN move easily. CAN movement is an almost simple space check.

Why not just:

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

Obviously, with the canMove flags and bombs, the procedure returns false all the time. This works for scouts, because they need at least one space to move, so it’s important for this.

The only thing this does not track is the "back 5 times" restriction, but this is hardly difficult.

Finally:

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

This is hardly an expensive process.

Answer 3

I see no reason why the answer will be too expensive, but I will give one more idea just for grins. One option would be to maintain a list of the parts that are currently moving, one list for each player. Checking to see if there are any moves left to the player is as simple as looking at the current size of this list.

The cost, however, is that you need to keep a list at every step. Movement in one piece can unlock any part around it, as well as blocks that were free. It is clear that this is much more complicated than checking every square on the board.

Answer 4

I think that counting rights can make sense here.

The idea is to count how many directions your collective objects can move. This is equivalent to the number of open squares or enemy units (available squares) located next to your moving objects. If an available square is affected by more than one of your parts, it is counted several times. We will call each available square / potential direction free.

You start by counting the number of initial freedoms. You only need to count the number of moving parts in the front row without touching the water. No other part can move, and each part has only one direction in which they can move.

After that, the algorithm for updating the number of freedoms is quite simple. You count the number of freedoms that the old position has, subtracting the number of your blocks that it blocks, and count the number of freedoms that the new position has, again subtracting the number of blocks it blocks. You add this to general freedoms, and you have a new meaning.

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

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

When the adversary moves his figure, your freedoms cannot change. Neither SpaceIsAvailable nor SpaceIsMovable will change the value.

If your part is deleted, you simply run the same algorithm, but release the newPosition section.

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

Now, if liberties > 0 , you have movable parts. All you have to do is track an integer for both players, and you can skip any calculations that determine if any fragments are available.

This does not work if you apply rules prohibiting the repetition of movement. I'm not sure how you are going to implement this. If you do this by finding out which parts cannot move, you can simply compare the total number of freedoms with their freedoms instead of 0 . If it is equal, then no movements are left. If total freedom is lower than the liberties of the parts that cannot move, then something is wrong with my algorithm or your code.

If I read the rules of repetition correctly, there can only be one part at a time that cannot move and therefore only one set of freedoms that you must 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

It should be noted that all the algorithms here either ignore the boundary conditions or check them. Another possibility is to simply make your board 12x12 and place water at the edges. You should take this into account in all your code, but if you have a Board object with an accessory to get information about a specific square, simply subtract it before getting the result. Then board.GetSquare(0,0) will return the piece to the corner, while board.GetSquare(-1,5) will return water, like board.GetSquare(3,10) . board.GetSquare(-2,1) will throw an exception.

I think that with this all the algorithms will be much simpler without complicating access to parts.