Здравствуйте, Shmj, Вы писали:

S>Есть история — если сможешь выиграть — то после поздравления — нажми кнопку отмена и скопируй историю как тебе это удалось.

ну я почему-то думаю, что игра ничейная. Стратегия довольно простая вырисовывается. Избегаем центра b2 (немного контринтуитивно, поэтому для новичков может быть сложно). Расставили например a1 b3 c2. Если поле b2 свободно прыгаем туда. Если мы уже стоим на b2 отпрыгиваем от центра в сторону максимальной "свободы" (где хотя бы две клетки пустые). И там носимся треугольником. Играть на победу аналогично — ждать, когда соперник этот алгоритм нарушит. Выставить по диагонали избегая центра (н-р a1 c3), а оставшейся шашкой запатовать шашки соперника, чтобы он вынужен был отпрыгнуть из центра.

	Н-р
	1: A2->B2 2: C3->B3 3: A1->B1 4: C2->C3 5: B2->A1 6: C3->B2 7: A1->A2 8: B2->A1 9: A2->B2 10: A1->A2 11: B2->C3 12: B3->B2 13: C3->C2 14: B2->C3 15: C2->B2 16: C3->B3 17: B2->C3 18: B3->B2 19: C3->C2 20: B2->C3 21: C2->B2 22: C3->B3 23: B2->C3 24: A2->B2 25: C3->C2 26: B2->A1 27: C2->B2 28: A1->A2 29: B2->C3 30: B3->B2

Ну в принципе по сложности не намного сложнее крестиков-ноликов. Развлечение на день. Но для новичка просадить в первый же день 10 "туалетов" запросто.

Здравствуйте, Shmj, Вы писали:

Храни тогда дельту не занятых мест, а наоборот дельту возможных ходов

Здравствуйте, sergii.p, Вы писали:

SP>можешь правила описать нормально? Или ссылку кинь, где они описываются. Сейчас ничего не понятно. Так в классической мельнице достаточно запатовать соперника, что здесь достигается элементарно b1-b3 a3-a2 c1-c2.

Попробуй тут: https://f4a512d8-0778-405a-a706-268b4652bb16.selstorage.ru/index.html

Только там те самые 10 Мб. ходов в несжатом виде.

Есть история — если сможешь выиграть — то после поздравления — нажми кнопку отмена и скопируй историю как тебе это удалось.

Начало тут: https://rsdn.org/forum/etude/9018754.flat

Автор: Shmj
Дата: 15.11 12:34

В общем то классическая мельница 3*3, но с условием запрета обратного хода (т.е. походив фишкой, потом не можешь отменить/пойти взад этой последней фишкой).

Интересно что если нет этого условия — список состояний (и разрешенных ходов из данного состояния) в простом массиве занимает около 180 Кб. — что норм. Т.е. даже об этом не думал, чтобы как-то сжимать.

А вот если добавить правило запрета обратного хода — то чтобы правильно походило (с учетом запретов себя и противника) — полный список всех состояний и данных куда можно ходить — уже занимает 15.9 MB, что проблема. Т.е. уже загружать — быстро не откроется...

Что можно сделать. Очевидное — это симметрия. Левая и правая клеточка равнозначны. А вот верх и низ — уже нет, т.к. там зависит от игрока.

Т.е. за счет симметричности левого и правого — можно ужать в 2 раза.

Далее, я пишут в таком виде:

{
  red: [A1, A2, A3],
  black: [B1, B2, B3],
  redForbidden: null,
  blackForbidden: null,
  transitions: [
    [B1, C1],
    [B2, C1],
    [B2, C2],
    [B2, C3],
    [B3, C3],
  ],
}

т.е. текущее состояние и transitions — разрешенные переходы.

Но состояний то вроде не много, менее 16 тыс., значит влезет в 2 байта. Первые 4 поля значит — 8 байт с лихвой. Ну и преходы.

Еще вариант вычислять на лету, но будет нагружать слабые телефоны.

S>Начало тут: https://rsdn.org/forum/etude/9018754.flat

Автор: Shmj
Дата: 15.11 12:34

S>В общем то классическая мельница 3*3,

Суть игры-то в чем?
Как ходить? Какая цель?

Здравствуйте, Shmj, Вы писали:

S>Начало тут: https://rsdn.org/forum/etude/9018754.flat

Автор: Shmj
Дата: 15.11 12:34

S>В общем то классическая мельница 3*3, но с условием запрета обратного хода (т.е. походив фишкой, потом не можешь отменить/пойти взад этой последней фишкой).

S>Интересно что если нет этого условия — список состояний (и разрешенных ходов из данного состояния) в простом массиве занимает около 180 Кб. — что норм. Т.е. даже об этом не думал, чтобы как-то сжимать.

S>А вот если добавить правило запрета обратного хода — то чтобы правильно походило (с учетом запретов себя и противника) — полный список всех состояний и данных куда можно ходить — уже занимает 15.9 MB, что проблема. Т.е. уже загружать — быстро не откроется...

S>Что можно сделать. Очевидное — это симметрия. Левая и правая клеточка равнозначны. А вот верх и низ — уже нет, т.к. там зависит от игрока.

S>Т.е. за счет симметричности левого и правого — можно ужать в 2 раза.

S>Далее, я пишут в таком виде:

S>

S>{
S>  red: [A1, A2, A3],
S>  black: [B1, B2, B3],
S>  redForbidden: null,
S>  blackForbidden: null,
S>  transitions: [
S>    [B1, C1],
S>    [B2, C1],
S>    [B2, C2],
S>    [B2, C3],
S>    [B3, C3],
S>  ],
S>}
S>

S>т.е. текущее состояние и transitions — разрешенные переходы.

S>Но состояний то вроде не много, менее 16 тыс., значит влезет в 2 байта. Первые 4 поля значит — 8 байт с лихвой. Ну и преходы.

S>Еще вариант вычислять на лету, но будет нагружать слабые телефоны.

Обзор алгоритмов сжатия графов если что, я не читал что там, но может полезное. А вообще 15.9 MB это не много, запихни в source пусть при установки программы загружаются.

Здравствуйте, Muxa, Вы писали:

S>>В общем то классическая мельница 3*3,

M>Суть игры-то в чем?

Выстроить линию как с крестиках ноликах — и не дать противнику выстроить линию первым.

M>Как ходить? Какая цель?

См. 2 схему — разрешенные направления хода — по линиям:

S>>>В общем то классическая мельница 3*3,
M>>Суть игры-то в чем?

S>Выстроить линию как с крестиках ноликах — и не дать противнику выстроить линию первым.

Судя по описанию по ссылке, изначально фишки уже находятся в выигрышной позиции выстроенные в линию. Ходы можно пропускать?

Здравствуйте, Muxa, Вы писали:

M>Судя по описанию по ссылке, изначально фишки уже находятся в выигрышной позиции выстроенные в линию. Ходы можно пропускать?

Эта линия — исключение — для красных своя линия 1, которая не выигрышная. Для черных — своя.

Здравствуйте, Qulac, Вы писали:

Q>Обзор алгоритмов сжатия графов если что, я не читал что там, но может полезное. А вообще 15.9 MB это не много, запихни в source пусть при установки программы загружаются.

Для сайта — много.

Q>>Обзор алгоритмов сжатия графов если что, я не читал что там, но может полезное. А вообще 15.9 MB это не много, запихни в source пусть при установки программы загружаются.

S>Для сайта — много.

А сколько у тебя на сайте запросов в секунду?

Здравствуйте, Muxa, Вы писали:

S>>Для сайта — много.
M>А сколько у тебя на сайте запросов в секунду?

Да просто человеку ждать загрузки страницы — 10 Мб даже — это много. Ну 1 Мб — еще куда ни шло...

Здравствуйте, Shmj, Вы писали:

S>Начало тут: https://rsdn.org/forum/etude/9018754.flat

Автор: Shmj
Дата: 15.11 12:34

А зачем тебе хранить "дерево ходов"?
Ну ты же правила описал с помощью нескольких русских фраз.
Опиши это на любом языке программирования.
И ничего не надо хранить/пересылать —
ты будешь строить дерево по мере необходимости.

Здравствуйте, alpha21264, Вы писали:

A>А зачем тебе хранить "дерево ходов"?
A>Ну ты же правила описал с помощью нескольких русских фраз.
A>Опиши это на любом языке программирования.
A>И ничего не надо хранить/пересылать —
A>ты будешь строить дерево по мере необходимости.

Так цель же не просто чтобы программа играла — цель чтобы гарантированно не проиграла и по возможности выиграла. А в этой игре есть ходы, которые приводят к поражению.

Возможно существует простое правило как не проиграть, но я такого правила не знаю.

Здравствуйте, Shmj, Вы писали:

A>>И ничего не надо хранить/пересылать —
A>>ты будешь строить дерево по мере необходимости.

S>Так цель же не просто чтобы программа играла — цель чтобы гарантированно не проиграла и по возможности выиграла. А в этой игре есть ходы, которые приводят к поражению.

S>Возможно существует простое правило как не проиграть, но я такого правила не знаю.

Научи программу смотреть на несколько ходов вперёд.

Здравствуйте, alpha21264, Вы писали:

S>>Возможно существует простое правило как не проиграть, но я такого правила не знаю.
A>Научи программу смотреть на несколько ходов вперёд.

Пробовал — нужно достаточно на много ходов смотреть, иначе есть возможность "загнать в угол". Т.е. ходов вообще нет, к примеру (а обратный запрещен).

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

Причем, что интересно, ни одной полноценной реализации этой игры не встречал. Есть несколько в маркете, но везде алгоритм поверхностный, не гарантирует победу компьютера. А это не интересно — один раз победишь и уже знаешь как играть. В моей версии победа кожаного исключена и кожаный обычно на 30-40 шаге делает ошибку и проигрывает, это в лучшем случае.

Здравствуйте, Shmj, Вы писали:

S>Интересно что если нет этого условия — список состояний (и разрешенных ходов из данного состояния) в простом массиве занимает около 180 Кб. — что норм. Т.е. даже об этом не думал, чтобы как-то сжимать.
S>А вот если добавить правило запрета обратного хода — то чтобы правильно походило (с учетом запретов себя и противника) — полный список всех состояний и данных куда можно ходить — уже занимает 15.9 MB, что проблема. Т.е. уже загружать — быстро не откроется...

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

Здравствуйте, mike_rs, Вы писали:

S>>А вот если добавить правило запрета обратного хода — то чтобы правильно походило (с учетом запретов себя и противника) — полный список всех состояний и данных куда можно ходить — уже занимает 15.9 MB, что проблема. Т.е. уже загружать — быстро не откроется...

_>ты отменяешь только последний ход — банально запомни его отдельно не давай переходить, даже если стандартное состояние разрешает это. Зачем усложнять-то?

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

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

Здравствуйте, Shmj, Вы писали:

Ты хранишь целиком все состояния? Можно же дельту от предыдущего. Ну типа как git работает

Здравствуйте, Hоmunculus, Вы писали:

H>Ты хранишь целиком все состояния? Можно же дельту от предыдущего. Ну типа как git работает

Так я храню состояния, чтобы для каждого из них знать куда можно походить а куда нельзя. Т. е. чтобы программа 100% гарантировано никогда не проиграла и выиграла, если кожаный допустил хотя бы одну ошибку (а кожаный ее обязательно допустит рано или поздно — устанет и допустит ошибку).

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

Здравствуйте, Shmj, Вы писали:

S>Здравствуйте, Hоmunculus, Вы писали:

H>>Ты хранишь целиком все состояния? Можно же дельту от предыдущего. Ну типа как git работает

S>Так я храню состояния, чтобы для каждого из них знать куда можно походить а куда нельзя. Т. е. чтобы программа 100% гарантировано никогда не проиграла и выиграла, если кожаный допустил хотя бы одну ошибку (а кожаный ее обязательно допустит рано или поздно — устанет и допустит ошибку).

S>Возможно есть эвристические правила, которые позволяют не проиграть и не попасть в безвыходную ситуацию — но я их не знаю Видимо знахарь их знал.

А почему бы тогда просто не перенести логику игры на сервер, а фронт просто показывает?

Здравствуйте, Qulac, Вы писали:

Q>А почему бы тогда просто не перенести логику игры на сервер, а фронт просто показывает?

А если кто-то в оффлайне захочет время коротать? Онлайн и так куча развлечений.

Здравствуйте, Shmj, Вы писали:

_>>ты отменяешь только последний ход — банально запомни его отдельно не давай переходить, даже если стандартное состояние разрешает это. Зачем усложнять-то?
S>Я изначально тоже так и сделал, но потом оказалось что попадаешь в ситуацию, что из доступных ходов — только обратный. Запоминать нужно 2 хода (для каждого цвета) и две конкретные фишки, которые походили последними.

ок, запомни эти 4 параметра, всяко быстрее будет

Здравствуйте, Shmj, Вы писали:

S>Здравствуйте, alpha21264, Вы писали:

S>>>Возможно существует простое правило как не проиграть, но я такого правила не знаю.
A>>Научи программу смотреть на несколько ходов вперёд.

S>Пробовал — нужно достаточно на много ходов смотреть, иначе есть возможность "загнать в угол". Т.е. ходов вообще нет, к примеру (а обратный запрещен).

S>По этому выход — хранить все возможные состояния доски (включая запрещенные ходы и фишки, которым запрещено) — и разрешенные варианты, которые позволяют не проиграть. Из разрешенных вариантов выбираем ход рандомно (кроме случаев, когда победа — тогда такой ход).

S>Причем, что интересно, ни одной полноценной реализации этой игры не встречал. Есть несколько в маркете, но везде алгоритм поверхностный, не гарантирует победу компьютера. А это не интересно — один раз победишь и уже знаешь как играть. В моей версии победа кожаного исключена и кожаный обычно на 30-40 шаге делает ошибку и проигрывает, это в лучшем случае.

Ну храни только выигрышные ходы. Или попробуй шахматы/го написать с таким подходом — удивишься, сколько нужно будет памяти.

Здравствуйте, SaZ, Вы писали:

SaZ>Ну храни только выигрышные ходы. Или попробуй шахматы/го написать с таким подходом — удивишься, сколько нужно будет памяти.

Там выигрышные появляются только если соперник допустил ошибку — а так можно играть бесконечно долго. И хранить нужно те ходы, которые не являются ошибочными (не приводят к поражению).

S>>>Для сайта — много.
M>>А сколько у тебя на сайте запросов в секунду?

S>Да просто человеку ждать загрузки страницы — 10 Мб даже — это много. Ну 1 Мб — еще куда ни шло...

Ну, так сколько у тебя посетителей-то на сайте с игрой (кроме тебя)?
А то сейчас выяснится что там и нет-то никого.

S>Т. е. чтобы программа 100% гарантировано никогда не проиграла и выиграла, если кожаный допустил хотя бы одну ошибку (а кожаный ее обязательно допустит рано или поздно — устанет и допустит ошибку).

У тебя опять какая-то херня с терминологией.
Если выигрыш зависит от ошибки оппонента, то это совсем не «100% гарантировано».

Здравствуйте, Muxa, Вы писали:

S>>Т. е. чтобы программа 100% гарантировано никогда не проиграла и выиграла, если кожаный допустил хотя бы одну ошибку (а кожаный ее обязательно допустит рано или поздно — устанет и допустит ошибку).

M>У тебя опять какая-то херня с терминологией.
M>Если выигрыш зависит от ошибки оппонента, то это совсем не «100% гарантировано».

1. Прога гарантировано никогда не проиграет. Гарантии победы — нет. Просто игра начавшись однажды — может длиться вечно.
2. Если пользователь сделает неверный шаг (хотя бы один) — то все, он проиграет.

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

Здравствуйте, Shmj, Вы писали:

S>Начало тут: https://rsdn.org/forum/etude/9018754.flat

Автор: Shmj
Дата: 15.11 12:34

можешь правила описать нормально? Или ссылку кинь, где они описываются. Сейчас ничего не понятно. Так в классической мельнице достаточно запатовать соперника, что здесь достигается элементарно b1-b3 a3-a2 c1-c2.

Здравствуйте, sergii.p, Вы писали:

SP>Ну в принципе по сложности не намного сложнее крестиков-ноликов. Развлечение на день. Но для новичка просадить в первый же день 10 "туалетов" запросто.

Вот что значит естественный интеллект — сразу все 100 тыс. комбинаций свел к 5 простым правилам

Как бы заставить ИИ думать так же?