Недавно я создал онлайн-версию классической игры для двух игроков Connect Four. Пошаговая игра имеет простую предпосылку, согласно которой 2 игрока по очереди бросают жетоны в сетку шириной семь столбцов и шестью рядами, пытаясь сформировать непрерывную линию из 4 жетонов в горизонтальном, вертикальном или диагональном направлениях.

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

checkForWins(grid)

Функция должна принимать на вход «сетку», которая представляет собой массив из 7 «столбцов», каждый из которых представляет собой массив из 6 строк, представляющих пробелы. Каждая из этих строк может быть либо пустой, либо строкой, представляющей фигуру в них («r» или «y» для красного или желтого цвета). Он должен возвращать ноль, если нет победителя, цвет победителя, если он есть, или «ничью», если доска заполнена И никто не выиграл.

Итак, как мы это делаем?

Давайте начнем с проверки всей доски и просмотра каждой части, начиная с нижнего левого и двигаясь по рядам, а затем вверх по доске. Сохраните его соседей в каждом из 8 направлений и для каждого пути (направления) сравните все части и посмотрите, совпадают ли они. Если мы не накладываем никаких ограничений на наш поиск, это означает, что мы рассматриваем 42 пробела * 8 путей * 3 сравнения = 1008 операций (не включая все операции для получения всех переменных).

Но мы можем это немного снизить.

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

С учетом этих соображений мы ищем 3 пути для пробелов по бокам доски и 5 путей в центральной колонке. Всего мы сейчас ищем 138 путей и 414 сравнений.

Тем не менее, мы все еще много повторяемся, так как мы движемся прямо через доску, нам никогда не нужно проверять путь прямо слева от клетки. Точно так же нам не нужно проверять нисходящие пути (вниз, вниз-влево и вниз-вправо), поскольку мы движемся вверх по доске. Это приводит нас к 61 пути или 183 сравнениям.

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

Мы также можем уменьшить количество сравнений, убедившись, что мы проверяем только третью часть в пути, если вторая была совпадением, и четвертую, если третья была совпадением.

Итак, обыскивая всю доску, мы находим 61 путь.

Но нам это не нужно. Нам нужно только проверить, есть ли победитель, когда на доску помещается новая фигура. Каждое пространство расположено на четырех линиях — Вертикальной, Горизонтальной и 2-х Диагональных. Итак, 4 пути.

Посмотрите на кусок, который вы только что вставили. Возьмите кусочки в каждой из его строк (столбец, ряд, левая диагональ, правая диагональ) и поместите их в массив. Превратите эти массивы в строки (например, с помощью Array.join()), а затем проверьте, содержит ли эта строка 4 элемента в строке («rrrr» или «yyyy»), совпадающие с элементом, который только что был размещен. Если они это сделают. Если они это сделают, у вас есть свой победитель!

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

Как бы вы это сделали? Дай мне знать в комментариях! Мой код ниже.