В общем то классическая мельница 3*3, но с условием запрета обратного хода (т.е. походив фишкой, потом не можешь отменить/пойти взад этой последней фишкой).
Интересно что если нет этого условия — список состояний (и разрешенных ходов из данного состояния) в простом массиве занимает около 180 Кб. — что норм. Т.е. даже об этом не думал, чтобы как-то сжимать.
А вот если добавить правило запрета обратного хода — то чтобы правильно походило (с учетом запретов себя и противника) — полный список всех состояний и данных куда можно ходить — уже занимает 15.9 MB, что проблема. Т.е. уже загружать — быстро не откроется...
Что можно сделать. Очевидное — это симметрия. Левая и правая клеточка равнозначны. А вот верх и низ — уже нет, т.к. там зависит от игрока.
Т.е. за счет симметричности левого и правого — можно ужать в 2 раза.
S>В общем то классическая мельница 3*3, но с условием запрета обратного хода (т.е. походив фишкой, потом не можешь отменить/пойти взад этой последней фишкой).
S>Интересно что если нет этого условия — список состояний (и разрешенных ходов из данного состояния) в простом массиве занимает около 180 Кб. — что норм. Т.е. даже об этом не думал, чтобы как-то сжимать.
S>А вот если добавить правило запрета обратного хода — то чтобы правильно походило (с учетом запретов себя и противника) — полный список всех состояний и данных куда можно ходить — уже занимает 15.9 MB, что проблема. Т.е. уже загружать — быстро не откроется...
S>Что можно сделать. Очевидное — это симметрия. Левая и правая клеточка равнозначны. А вот верх и низ — уже нет, т.к. там зависит от игрока.
S>Т.е. за счет симметричности левого и правого — можно ужать в 2 раза.
S>Далее, я пишут в таком виде:
S>
S>т.е. текущее состояние и transitions — разрешенные переходы.
S>Но состояний то вроде не много, менее 16 тыс., значит влезет в 2 байта. Первые 4 поля значит — 8 байт с лихвой. Ну и преходы.
S>Еще вариант вычислять на лету, но будет нагружать слабые телефоны.
Обзор алгоритмов сжатия графов если что, я не читал что там, но может полезное. А вообще 15.9 MB это не много, запихни в source пусть при установки программы загружаются.
Программа – это мысли спрессованные в код
Re[2]: Как лучше сжать данные разрешенных ходов для игры?
S>>>В общем то классическая мельница 3*3, M>>Суть игры-то в чем?
S>Выстроить линию как с крестиках ноликах — и не дать противнику выстроить линию первым.
Судя по описанию по ссылке, изначально фишки уже находятся в выигрышной позиции выстроенные в линию. Ходы можно пропускать?
Re[4]: Как лучше сжать данные разрешенных ходов для игры?
Здравствуйте, Muxa, Вы писали:
M>Судя по описанию по ссылке, изначально фишки уже находятся в выигрышной позиции выстроенные в линию. Ходы можно пропускать?
Эта линия — исключение — для красных своя линия 1, которая не выигрышная. Для черных — своя.
=сначала спроси у GPT=
Re[2]: Как лучше сжать данные разрешенных ходов для игры?
Здравствуйте, Qulac, Вы писали:
Q>Обзор алгоритмов сжатия графов если что, я не читал что там, но может полезное. А вообще 15.9 MB это не много, запихни в source пусть при установки программы загружаются.
Для сайта — много.
=сначала спроси у GPT=
Re[3]: Как лучше сжать данные разрешенных ходов для игры?
Q>>Обзор алгоритмов сжатия графов если что, я не читал что там, но может полезное. А вообще 15.9 MB это не много, запихни в source пусть при установки программы загружаются.
S>Для сайта — много.
А сколько у тебя на сайте запросов в секунду?
Re[4]: Как лучше сжать данные разрешенных ходов для игры?
А зачем тебе хранить "дерево ходов"?
Ну ты же правила описал с помощью нескольких русских фраз.
Опиши это на любом языке программирования.
И ничего не надо хранить/пересылать —
ты будешь строить дерево по мере необходимости.
Течёт вода Кубань-реки куда велят большевики.
Re[2]: Как лучше сжать данные разрешенных ходов для игры?
Здравствуйте, alpha21264, Вы писали:
A>А зачем тебе хранить "дерево ходов"? A>Ну ты же правила описал с помощью нескольких русских фраз. A>Опиши это на любом языке программирования. A>И ничего не надо хранить/пересылать — A>ты будешь строить дерево по мере необходимости.
Так цель же не просто чтобы программа играла — цель чтобы гарантированно не проиграла и по возможности выиграла. А в этой игре есть ходы, которые приводят к поражению.
Возможно существует простое правило как не проиграть, но я такого правила не знаю.
=сначала спроси у GPT=
Re[3]: Как лучше сжать данные разрешенных ходов для игры?
Здравствуйте, Shmj, Вы писали:
A>>И ничего не надо хранить/пересылать — A>>ты будешь строить дерево по мере необходимости.
S>Так цель же не просто чтобы программа играла — цель чтобы гарантированно не проиграла и по возможности выиграла. А в этой игре есть ходы, которые приводят к поражению.
S>Возможно существует простое правило как не проиграть, но я такого правила не знаю.
Научи программу смотреть на несколько ходов вперёд.
Течёт вода Кубань-реки куда велят большевики.
Re[4]: Как лучше сжать данные разрешенных ходов для игры?
Здравствуйте, alpha21264, Вы писали:
S>>Возможно существует простое правило как не проиграть, но я такого правила не знаю. A>Научи программу смотреть на несколько ходов вперёд.
Пробовал — нужно достаточно на много ходов смотреть, иначе есть возможность "загнать в угол". Т.е. ходов вообще нет, к примеру (а обратный запрещен).
По этому выход — хранить все возможные состояния доски (включая запрещенные ходы и фишки, которым запрещено) — и разрешенные варианты, которые позволяют не проиграть. Из разрешенных вариантов выбираем ход рандомно (кроме случаев, когда победа — тогда такой ход).
Причем, что интересно, ни одной полноценной реализации этой игры не встречал. Есть несколько в маркете, но везде алгоритм поверхностный, не гарантирует победу компьютера. А это не интересно — один раз победишь и уже знаешь как играть. В моей версии победа кожаного исключена и кожаный обычно на 30-40 шаге делает ошибку и проигрывает, это в лучшем случае.
Здравствуйте, Shmj, Вы писали:
S>Интересно что если нет этого условия — список состояний (и разрешенных ходов из данного состояния) в простом массиве занимает около 180 Кб. — что норм. Т.е. даже об этом не думал, чтобы как-то сжимать. S>А вот если добавить правило запрета обратного хода — то чтобы правильно походило (с учетом запретов себя и противника) — полный список всех состояний и данных куда можно ходить — уже занимает 15.9 MB, что проблема. Т.е. уже загружать — быстро не откроется...
ты отменяешь только последний ход — банально запомни его отдельно не давай переходить, даже если стандартное состояние разрешает это. Зачем усложнять-то?
Re[2]: Как лучше сжать данные разрешенных ходов для игры?
Здравствуйте, mike_rs, Вы писали:
S>>А вот если добавить правило запрета обратного хода — то чтобы правильно походило (с учетом запретов себя и противника) — полный список всех состояний и данных куда можно ходить — уже занимает 15.9 MB, что проблема. Т.е. уже загружать — быстро не откроется...
_>ты отменяешь только последний ход — банально запомни его отдельно не давай переходить, даже если стандартное состояние разрешает это. Зачем усложнять-то?
Я изначально тоже так и сделал, но потом оказалось что попадаешь в ситуацию, что из доступных ходов — только обратный. Запоминать нужно 2 хода (для каждого цвета) и две конкретные фишки, которые походили последними.
Если правило запрета обратного хода убрать — то быстро приходим к туды-сюды, когда красный игрок, чтобы не проиграть — возвращает назад и черные тоже возвращает назад, потом вперед-назад. А это неинтересно, как бы ничья. Вот когда запрет на обратный ход — намного интереснее.
Здравствуйте, Hоmunculus, Вы писали:
H>Ты хранишь целиком все состояния? Можно же дельту от предыдущего. Ну типа как git работает
Так я храню состояния, чтобы для каждого из них знать куда можно походить а куда нельзя. Т. е. чтобы программа 100% гарантировано никогда не проиграла и выиграла, если кожаный допустил хотя бы одну ошибку (а кожаный ее обязательно допустит рано или поздно — устанет и допустит ошибку).
Возможно есть эвристические правила, которые позволяют не проиграть и не попасть в безвыходную ситуацию — но я их не знаю Видимо знахарь их знал.
Здравствуйте, Shmj, Вы писали:
S>Здравствуйте, Hоmunculus, Вы писали:
H>>Ты хранишь целиком все состояния? Можно же дельту от предыдущего. Ну типа как git работает
S>Так я храню состояния, чтобы для каждого из них знать куда можно походить а куда нельзя. Т. е. чтобы программа 100% гарантировано никогда не проиграла и выиграла, если кожаный допустил хотя бы одну ошибку (а кожаный ее обязательно допустит рано или поздно — устанет и допустит ошибку).
S>Возможно есть эвристические правила, которые позволяют не проиграть и не попасть в безвыходную ситуацию — но я их не знаю Видимо знахарь их знал.
А почему бы тогда просто не перенести логику игры на сервер, а фронт просто показывает?
Программа – это мысли спрессованные в код
Re[4]: Как лучше сжать данные разрешенных ходов для игры?
Видимо знахарь их знал.
