Обнаружить выигрышную игру в ноль и крестики

Question

Мне нужно знать, как лучше всего определить выигрышный ход в игре крестиков и ноликов. Исходный код не имеет значения, мне просто нужен пример или что-то, с чего я могу начать.

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

Answer 1

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

Крестики и нолики обычно представляют собой сетку 3 на 3. Если вы назначаете каждой позиции в вашей сетке число от одного до девяти (не в числовом порядке), вы можете расположить числа таким образом, чтобы каждая горизонтальная, вертикальная и диагональная строка складывалась до 15

+----+----+----+
| 4  | 3  | 8  |
|    |    |    |
+----+----+----+
| 9  | 5  | 1  |
|    |    |    |
+----+----+----+
| 2  | 7  | 6  |
|    |    |    |
+----+----+----+ 

Почему это полезно? Если вы можете выбрать любые три квадрата, принадлежащие либо «О», либо «Х», и эти три квадрата в сумме составят общую сумму 15, вы знаете, что игрок выиграл игру.

Answer 2

Самое простое решение - просто проверить последний сделанный ход ... очевидно, ни один предыдущий ход не мог бы выиграть игру, иначе вас бы здесь не было ... поэтому вам просто нужно проверить, есть ли 5 (или сколько угодно) в строке / столбце / диагонали вокруг только что размещенного хода.

Например, если доска выглядит следующим образом, а X отмечает самый последний ход:

.............
.............
.............
.............
.....X.......
.............
.............
.............
.............
.............

Вам не нужно проверять что-либо вне диапазона «C»:

.C...C...C...
..C..C..C....
...C.C.C.....
....CCC......
.CCCCXCCCC...
....CCC......
...C.C.C.....
..C..C..C....
.C...C...C...
.............

Это помогает? (Похоже, вы намекаете на это в своем первоначальном вопросе, но я не был уверен.)

Помимо этого, простые петли станут вашим лучшим другом. Возможно, вы могли бы провести некоторую микрооптимизацию, но (в зависимости от того, что делает ваше реальное приложение), это, вероятно, того не стоит.

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

From the new move
    left = how many in a row we have to the left of the lastest move
    right = how many in a row we have to the right of the latest move
    if (left + right + 1 >= 5) then you have a winner

    up = how many in a row we have above the latest move
    down = how many in a row we have below the latest move
    if (up + down + 1 >= 5) then you have a winner

    // repeat for both diagonal directions.

Answer 3

Рассмотрим плату 3X3

Пусть X = 1 Пусть O = -1 и пробел представлен нулем.

Так что, если верхний ряд выглядит так [X] [X] [X], сумма равна 3, следовательно, это выигрыш [O] [O] [O] сумма равна -3, следовательно, это другой выигрыш.

[X] [X] [] равно 2, следовательно, если это ход Х, он может выиграть, перейдя на пробел, или O должен блокировать.

[X] [O] [X] равно 1, следовательно, нет выигрыша.

На доске 3х3 есть 8 позиций для оценки.

В NXN число увеличивается, но идея остается прежней

если N = 8 и сумма строки или столбца равна 7, то вы знаете, что в этой строке / столбце есть выигрышный ход для X

Этот метод работал для меня в старшей школе.

С наилучшими пожеланиями

Evil

Answer 4

Я не знаю лучшего способа, чем зацикливание, но плата такая маленькая, что она тривиальна.

Небольшой псевдо-код Python:

def get_winner(board):
    if board[0][0] != EMPTY and board[0][0] == board[1][1] == board[2][2]:
        return board[0][0]
    if board[2][0] != EMPTY and board[2][0] == board[1][1] == board[0][2]:
        return board[2][0]
    for i in xrange(3):
        if board[i][0] != EMPTY and board[i][0] == board[i][1] == board[i][2]:
            return board[i][0]
        if board[0][i] != EMPTY and board[0][i] == board[1][i] == board[2][i]:
            return board[0][i]

Answer 5

Это вопрос представительства. Как вы храните игровое поле? Теперь мыслите нестандартно; как еще вы могли бы хранить его? Например, вы можете представить доску в виде пары растровых изображений - одно для нолей и одно для крестов, а затем выполнить числовое сопоставление с шаблоном, чтобы определить условия победы.

Answer 6

Существуют более эффективные способы, но они действительно имеют значение только тогда, когда вы расширяете эту игру для гораздо более крупных конфигураций доски. Например, если вы сохранили группировки крестиков и крестов в направленных объектах (например, сохраните диагональную конфигурацию), вы можете отсортировать их по длине winLength-1 и проверить только новое движение по этим группам. Вы сохраняете некоторые итерации, но вам необходимо хранить много дополнительной информации в памяти.