Cool Folders ® :: Форум Игротека :: О крестиках-ноликах на бесконечной доске

О крестиках-ноликах на бесконечной доске

Автор: Большой Грызь
Дата : 12-08-04, Чтв, 08:00:12

Тут вот вопросец возник. Есть доска 15х15. Каким способом наиболее быстро проверить нет ли на ней 5 крестиков или ноликов в ряд (по горизонтали, вертикали или диагонали).

Скажем, крестик=1, нолик=2, пустое место=0. Как вариант - доска закодирована строкой из 225 символов "0","1" или "2" (первый символ - левая верхняя клетка, дальше - по горизонтальным рядам)

Кто может предложить какой алгоритм?

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)
[ 12-08-04, Thu, 15:02:15 Отредактировано: Большой Грызь ]

О крестиках-ноликах на бесконечной доске

№ 2

Автор: Большой Грызь
Дата : 12-08-04, Чтв, 08:06:22

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

Например, поиск маски "(1)([012]{14})(1)([012]{14})(1)([012]{14})(1)([012]{14})(1)" выясняет нет ли 5 крестиков по вертикали (соответственно (2)([012]{14})(2)([012]{14})(2)([012]{14})(2)([012]{14})(2) - для ноликов).

Точно также можно проверить диагонали заменив {14} на {15} или {13} (соответствено, для двух диагоналей - с левым и правым уклоном).

А вот горизонтали проверять сложнее: просто искать "11111" - не проходит вариант. В виду того, что могут быть, скажем, 2 крестика в конце одной строки и 3 крестика - в начале следующей. Что даст при кодировке как раз 5 крестиков подряд, которые на доске не находятся в одном ряду.

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)
[ 12-08-04, Thu, 15:09:44 Отредактировано: Большой Грызь ]

О крестиках-ноликах на бесконечной доске

№ 3

Автор: Большой Грызь
Дата : 12-08-04, Чтв, 08:10:34

Упс.. с вертикалями и диагоналями та же фигня при переходе через строку/столбец

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)
[ 12-08-04, Thu, 15:14:33 Отредактировано: Большой Грызь ]

О крестиках-ноликах на бесконечной доске

№ 4

Автор: Большой Грызь
Дата : 12-08-04, Чтв, 08:13:08

Короче

любой быстрый алгоритм приветствуется

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

О крестиках-ноликах на бесконечной доске

№ 5

Автор: Dimka
Дата : 12-08-04, Чтв, 08:13:37

Грызь, тебе как идея для игрушки - не просто крестики-нолики, а вертикалные. То есть на доске надо выстроить в ряд (по вертикали, горизонтали или диагонали) 4 крестика (или нолика). При этом можно кликать только на вертикальные ряды, так как фишка как бы падает в самый низ по ряду

Человеческое сердце отказывается верить во вселенную у которой нет цели... - Иммануэль Кант

О крестиках-ноликах на бесконечной доске

№ 6

Автор: Большой Грызь
Дата : 12-08-04, Чтв, 08:15:49

Димк

идей игрушек у меня много

Мне нужны алгоритмы проверки ходов/завершения игры

В данном случае проверка хода примитивна (в отличие от Реверси, Шашек или Шахмат) - ходи в любое свободное место. А вот проверка завершения игры (и определение победителя) - не так тривиально.

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

О крестиках-ноликах на бесконечной доске

№ 7

Автор: Большой Грызь
Дата : 12-08-04, Чтв, 08:16:48

Так что вот.. задача - в первом постинге.. нужен алгоритм, который получает строку из 225 символов и возвращает:

    -1 - игра не завершена
    0 - игра завершена - ничья
    1 - выиграли крестики
    2 - выиграли нолики.

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

О крестиках-ноликах на бесконечной доске

№ 8

Автор: Dimka
Дата : 12-08-04, Чтв, 08:19:07

вся эта строка выдает только одну строчку поля? или в ней все поле?

Человеческое сердце отказывается верить во вселенную у которой нет цели... - Иммануэль Кант

О крестиках-ноликах на бесконечной доске

№ 9

Автор: Большой Грызь
Дата : 12-08-04, Чтв, 08:24:19

Всё поле. Поле - 15х15 = как раз 225 клеток.

Клетки поля пронумерованы по горизонтальным строкам:

001 002 003 ... 014 015
016 017 018 ... 029 030
031 032 033 ... 044 045
... ... ... ... ... ...
211 212 213 ... 224 225

Передаваемая строка как раз содержит 225 символов, которые кодируют соответствующие клетки ( 0 - пустая клетка, 1 - крестик, 2 - нолик).

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)
[ 12-08-04, Thu, 15:24:48 Отредактировано: Большой Грызь ]

О крестиках-ноликах на бесконечной доске

№ 10

Автор: Большой Грызь
Дата : 12-08-04, Чтв, 08:26:49

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

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

О крестиках-ноликах на бесконечной доске

№ 11

Автор: Dimka
Дата : 12-08-04, Чтв, 08:36:01

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

Человеческое сердце отказывается верить во вселенную у которой нет цели... - Иммануэль Кант
[ 12-08-04, Thu, 15:36:27 Отредактировано: Dimka ]

О крестиках-ноликах на бесконечной доске

№ 12

Автор: Большой Грызь
Дата : 12-08-04, Чтв, 08:39:03

Тогда кол-во проверок будет оччч.. хорошо расти при увеличении кол-ва крестиков/ноликов.
При этом будут лишние проверки.. Как бы.. возьмем три крестика в ряд.. Проверим один из них - получим, что он не входит в "пятерку".. Так тогда какой смысл проверять остальные два?

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

О крестиках-ноликах на бесконечной доске

№ 13

Автор: Большой Грызь
Дата : 12-08-04, Чтв, 08:43:28

Так.. регулярное выражение для вертикалей я таки составил (и упростил). Вот оно:

(1{1}.{14}){4}1{1}

ищет последовательность из одной "1", за которой идут 14 любых символов, четыре раза подряд, а затем еще одну "1".
То есть 1...<14 символов>...1...<14 симв>...1...<14 симв>...1...<14 симв>...1

Если таковое найдено - есть вертикальная пятерка

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

О крестиках-ноликах на бесконечной доске

№ 14

Автор: Dimka
Дата : 12-08-04, Чтв, 08:45:31

ну... мое решение - решение для пролога

забыл какой из меня программер? хотя можно добавить метки и внести их в тнаи ацира тоже - таким образом убрав лишние проверки

Человеческое сердце отказывается верить во вселенную у которой нет цели... - Иммануэль Кант

О крестиках-ноликах на бесконечной доске

№ 15

Автор: Большой Грызь
Дата : 12-08-04, Чтв, 08:46:23

Для горизонтали тоже кажется всё ясно..

(.{15})*(.{0,10}1{5})

Ищет горизонтальные "пятерки", которые начинаются не позже 11-ого символа от начала строки: первая часть выражения - до "звездочки" - отсчитывает целые строки (по 15 символов), затем отступается от 0 до 10 символов и проверяется наличие пяти "1".

Хм.. кажется таки верно.. тогда диагонали по аналогии..

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

О крестиках-ноликах на бесконечной доске

№ 16

Автор: Большой Грызь
Дата : 12-08-04, Чтв, 08:46:57

Так

спецы в регулярных выражениях

скажите так или не так

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)

О крестиках-ноликах на бесконечной доске

№ 17

Автор: Большой Грызь
Дата : 12-08-04, Чтв, 08:56:34

Вот... так.. окончательный вариант проверки:

Вертикаль:
((1{1}.{14}){4})(1{1})

Горизонталь:
((.{15})*)(.{0,10})(1{5})

Левая Диагональ:
((.{15})*)(.{0,10})((1{1}.{15}){4})(1{1})

Правая Диагональ:
((.{15})*)(.{4,14})((1{1}.{13}){4})(1{1})

Гы.. ничего, что это я тут так вслух порассуждал?

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)