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

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

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

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

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

Небольшой псевдо-код 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]

Рассмотрим доску 3X3

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

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

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

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

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

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

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

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

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

Зло