Comments 23
Но… Но, зачем? Зачем это, какая практическая ценность от решения частной задачи?
Это вопрос не к автору, а к тем кто в избранное добавил…
Это вопрос не к автору, а к тем кто в избранное добавил…
Что за снобизм
Снобизм — претензия на высокую интеллектуальность, изысканный вкус или авторитетность в какой-то области, и при этом надменное отношение к тем, кто якобы лишён этих достоинств
И вы столько всего увидели в простом вопросе о целесообразности?
Мне было бы интересно посмотреть решение-исследование для неограниченного поля и победной комбинации любой длины, зачем искусственные ограничения:
Я рассмотрю пример проверки победы в игре крестики-нолики, но на поле 6х6 и блоком подряд заполненных значений равному 4-м.
Почему именно такие условия, почему не использовать общее решение? В чём практическая ценность задачи? Она логично выглядела бы как часть общей задачи о, например, стратегии игры. Но вот так… Мне непонятно, поэтому и спросил, зачем читатели сохраняют в избранное, если это не боты, конечно.
UFO just landed and posted this here
Можно было бы сделать это более заметно.
Также, как и оценить сложность алгоритма.
Я не очень хотел публиковать в статье уж совсем готовое решение. Я пытался показать как можно графически сделать самое простое решение для двумерного массива и чтобы новичок увидел путь. Спасибо вам за комментарий. Пока, пожалуй, вы единственный кто высказался по делу.
if (toright || toleft) return true; return false;
Код прямо из книги вредных советов.
Предложенный алгоритм представляет из себя тупой перебор.
Центральные линии проверяются по нескольку раз.
Ага, в статье с заголовком «алгоритм», его-то и забыли завезти. Это конечно лучше, чем полная неспособность решить задачу (кто-бы спорил), но решить ее «как-нибудь» и запилить статью — даже не знаю. Отпишитесь ниже те, кто вникнул и нашел рассказанное полезным или интересным (хотя каюсь, первые абзацы захватили развитием сюжета). Прямо аж самому захотелось написать статью побесполезнее…
Вот, кстати, да. Тоже не очень понятно в чем принципиальная необходимость возврата true и отдельно false.
return ( toleft || toright )Чем не вариант?
Да, мне тоже кажется что алгоритмически лучше зайти с другой стороны. В блоке размером N есть N горизонтальных, N вертикальных и 2 диагональные линии. Заранее подготовим список этих линий [h1, h2,… hN, v1, v2,… vN, ld, rd]. Дальше пойдем по исходному блоку и для всех нулевых ячеек будем выбрасывать линии имеющие эту ячейки. Оставшиеся в списке после полного прохода: выигрышные. Можно оптимизировать, построив не только список возможных линий но и карту входимости ячеек в линии. Можно оптимизировать путь обхода блока, не последовательно строка за строкой а по спирали. Можно оптимизировать крайние случаи: когда обошли только треть блока, а в списке осталась одна линия, лучше проверить оставшиеся ячейки этой линии.
Так что дети, брать чужой код не разобравшись плохо еще и потому, что разобравшись в алгоритме вы поймете, что он не очень то и хорош. Перефразируя поговорку про золото, «Не все то O(n), что алгоритм».
Так что дети, брать чужой код не разобравшись плохо еще и потому, что разобравшись в алгоритме вы поймете, что он не очень то и хорош. Перефразируя поговорку про золото, «Не все то O(n), что алгоритм».
Если говорить о разработке настольных игр, на первый план выходит производительность. В более менее серьёзных играх (типа Рендзю), подобные проверки будут выполняться сотни тысяч раз за игру. Описанный в статье алгоритм сильно избыточен, в самой постановке задачи. Я не знаю ни одной игры в которой требовалось бы искать ряд из фигур, расположенный на доске неизвестно где. Ряд возникает не просто так, а с добавлением в него очередной фигуры. Это означает, что мы всегда знаем хотя бы одну позицию входящую в ряд (то поле, на котором завершила движение последняя сходившая фигура). Это верно и для тех игр, где фигуры могут убираться с доски (Пенте, Хасами Сёги) и для тех игр, где фигуры двигаются (Мельница, Хасами Сёги). В Мельнице может возникнуть задача поиска ряда противника, но опять же, мы ищем этот ряд в связи с правилом о том, что в первую очередь, должны удаляться фигуры не входящие в ряд. То есть мы снова знаем с какого поля начинать поиск ряда. Так что статья действительно из цикла вредных советов.
Буквально неделю назад делал на заказ игру «Пять в ряд» на поле 15х15. GlukKazan верно указал, что проверять диагонали/вертикали/горизонтали надо от поставленного значка, а не искать последовательности каждый раз по всему полю. Код будет сложнее, но быстрее.
По коду автора невозможно определить выигрышную последовательность значков, чтобы потом как-то ее выделить на игровом поле (это требовалось в моем заказе).
По коду автора невозможно определить выигрышную последовательность значков, чтобы потом как-то ее выделить на игровом поле (это требовалось в моем заказе).
Вообще говоря, можно пойти ещё дальше и хранить длины рядов (по 8 направлениям) в свойствах каждой фигуры на доске. Это незначительно замедлит выполнение хода, но значительно упростит поиск рядов (при постановке нового камня просто смотрим счётчики соседей и инкрементируем). Как-то вот так (этот код пока не протестирован!).
Я согласен. Статья для тех, кто вообще не понимает как подойти к проблеме. Надеюсь, что он просто поможет начать думать, какие подходы вообще могут быть.
Как раз для таких статья максимально вредна.
Я не верю, что вы гениальны настолько, что вам в первом классе дали решать дифуры в частных производных или хотя бы уравнение с 3-мя неизвестными. Когда человек проверяет поле 3x3 через if (map[1][1] && ...) этот вариант как раз для него. Он на этом этапе больше не поймет. По-моему заголовок статьи это как раз отражает.
Ваша статья — сборник плохих советов. Тот читатель на которого Вы ориентируетесь… да пусть он лучше сам до всего доходит, чем учится у Вас плохому. Впрочем, если ему (читателю) захочется, я не смогу ему в этом помешать, да и нет у меня такого желания. Но увидев подобную статью я просто обязан предупредить, насколько она плохая. Разумеется, это не относится к Вам лично. Речь идёт только о статье.
а разве не все начинали программировать с игр типа «три в ряд»? ))
я не читал: в статье какой-то особый метод, считающий одинаковых соседей в 3 раза быстрей, чем что-либо?
P.S.: а почему бы и нет? завести рубрику «юные программисты», куда постить статьи школьников (в прямом смысле). может быть интересно, как они там яблочки считают или домики рисуют. я бы почитал )
я не читал: в статье какой-то особый метод, считающий одинаковых соседей в 3 раза быстрей, чем что-либо?
P.S.: а почему бы и нет? завести рубрику «юные программисты», куда постить статьи школьников (в прямом смысле). может быть интересно, как они там яблочки считают или домики рисуют. я бы почитал )
Если это решение именно задачи "определить, выигрышна ли заданная позиция в игре крестики-нолики", то решение не верное. Оно не учитывает "невозможные" ситуации, как та, которая представлена на второй иллюстрации (нолики ни разу не сходили, правильный ответ — "крестики мухлюют", а не "крестики выиграли"), не учитывает ситуации, когда кто-то выиграл дважды (две выигрышных ситуации на одном поле, за исключением частных случаев вроде пересекающихся выигрышных комбинаций), не учитывает ситуаций, когда игра была продолжена после выигрыша одной из сторон, или когда выиграли обе стороны.
Sign up to leave a comment.
Простой алгоритм проверки победы в крести-нолики на не стандартном поле