Алгоритм обнаружения подвижных частей в Stratego

Question

Я создаю стратегическую игру, и у меня возникают проблемы при создании алгоритма, который может определять, когда больше нет возможных ходов, потому что все ваши фигуры ушли или оставшиеся фигуры неподвижны или захвачены запрещенными клетками, неподвижными фигурами или другими ловушками шт.

Для простоты вы можете рассматривать доску как массив квадратов, которые могут содержать фигуры.

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

Квадраты имеют легко проверяемое состояние, такое как hasPiece (), hasEnemyPiece (), hasUnMovablePiece (), hasMoveablePiece (), isBlocked ().

Также было бы неплохо, если бы этот алгоритм запускался не каждый раз, когда игрок двигался, а, возможно, проверялся в начале, а затем, когда игрок двигался, проверялись только определенные условия.

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

Это пример ситуации к концу игры, вы должны быть в состоянии проверить каждую из неподвижных частей (3 и 4), чтобы увидеть, являются ли они подвижными [не захвачены водой (заблокированы), другие неподвижные предметы (бомба или флаг) или другие захваченные предметы].

Answer 1

Правила движения у Stratego довольно простые. Есть два состояния. МОЖЕТ двигаться, и ДОЛЖЕН двигаться.

МОЖЕТ двигаться легко. МОЖЕТ двигаться, это практически простая проверка пространства.

Почему бы просто:

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

Очевидно, что подпрограмма "canMove" для флагов и бомб всегда возвращает false. Это работает для скаутов, потому что им нужен хотя бы один пробел для перемещения, поэтому это учитывается.

Единственное, что не отслеживается, - это ограничение «пять раз назад», но это вряд ли трудно.

Наконец:

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

Это вряд ли дорогой процесс.

Answer 2

Я думаю, что-то вроде этого будет работать:

// 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 проверок), что на самом деле совсем немного. Вы можете сделать это быстрее, считая, как вы добираетесь до каждой из ваших фигур, и если вы достигнете количества оставшихся фигур, вы также можете выйти.

Answer 3

Я думаю, здесь может иметь смысл подсчет свобод.

Идея состоит в том, чтобы вести подсчет количества направлений, в которых могут двигаться ваши коллективные фигуры. Это эквивалентно количеству открытых квадратов или вражеских фигур (доступных квадратов), смежных с вашими подвижными фигурами. Если доступный квадрат затронут более чем одной из ваших фигур, то он считается несколько раз. Мы будем называть каждый доступный квадрат / потенциальное направление движения свободой.

Вы начинаете с подсчета количества начальных свобод. Вы только должны посчитать количество подвижных частей в первом ряду, не касаясь воды. Никакая другая фигура не может двигаться, и у каждой фигуры есть только одно направление, в котором они могут двигаться.

После этого алгоритм обновления количества свобод довольно прост. Вы подсчитываете количество свобод в старой позиции, вычитаете количество блоков, которые она блокирует, и подсчитываете количество свобод в новой позиции, снова вычитая количество фигур, которые она блокирует. Вы добавляете это к общей свободе, и у вас есть новое значение.

Я некоторое время не кодировал 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 верно, если пятно является вашей фигурой и является подвижным.

Когда противник перемещает свою фигуру, ваши свободы не могут измениться. Ни 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.

Answer 4

Я не вижу причин, почему ответ Уилла был бы слишком дорогим, но я приведу другую идею только для улыбок. Одним из вариантов может быть сохранение списка фигур, которые в данный момент являются подвижными, по одному списку для каждого игрока. Проверить, не осталось ли ходов игроку, так же просто, как посмотреть текущий размер этого списка.

Стоимость, однако, заключается в том, что вы должны вести список на каждом шаге. Ход одной фигуры может разблокировать любую фигуру вокруг нее, а также блокировать фигуры, которые были свободны. Концептуально, как вы видите, это намного сложнее, чем проверка каждого квадрата на доске.

Answer 5

Следует отметить, что все алгоритмы здесь либо игнорируют граничные условия, либо проверяют их. Другой возможностью было бы просто сделать доску 12х12 и поливать водой по краям. Вы должны учитывать это во всем своем коде, но если у вас есть объект Board с аксессором для получения информации о конкретном квадрате, просто вычтите один, прежде чем получить результат. Тогда board.GetSquare(0,0) вернет кусок в угол, тогда как board.GetSquare(-1,5) вернет воду, как и board.GetSquare(3,10). board.GetSquare(-2,1) выдаст исключение.

Я думаю, что с этим все алгоритмы были бы намного проще, без затруднения доступа к частям.