Не вижу больше за счет чего можно сократить еще построение даже на один ход, не говоря уже на два или три :)

P.S. В этюдах количество ходов не лимитировано :) Это все же задача

Не вижу больше за счет чего можно сократить еще построение даже на один ход, не говоря уже на два или три :)

P.S. В этюдах количество ходов не лимитировано :) Это все же задача

О, вот это ответ. Других ждать не будем.
Мой монстр нашел решение за 17 ходов.
Могу показать первый ход, могу все. Если вам интересно.

P.S. Ну, так здесь же тоже не лимитировано... В каком-то роде.

"Из дома в дом". Диагональ, 4х3. Найти кратчайшее решение.

А это задача в диагонали, за одно поле до начала. Еще немного и будет найдено решение перехода из дома в дом в диагоналях, 4х3.

"Из дома в дом". Диагональ, 4х3. Найти кратчайшее решение.

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

Всего порядка 14 млрд расстановок
Генерим список решаемых в 1 ход (14 штук)
затем список за 2 хода (181)
...
11 - 421 млн
12 - 653 млн
,,,
23 - 16
(тут неточно но порядок такой)
компу надо 4 дня для этого
+ месяц на исправление ошибок (они всегда есть)
генерим базу длины решения для каждой позиции
затем сжимаем до 300-500Мб
Получится программа дающая мнгновенное решение для любой расстановки
Будет настроение - займусь

Это решит (убьет) задачу
При этом люди получавшие удовольствие от процесса ее решения этот интерес потеряют
И зачем их лишать удовольствия

Это сообщение отредактировал B_A_D - 9/11/2017, 07:56

Что-то маловато 14 млрд для 12 шашек.

https://www.wolframalpha.com/input/?i=64+choose+12
Вроде заметно больше позиций вышло, если в расчёт брать все-все-все.

Да и позиций решаемых в один ход даже в 3 на 3 в диагональ выходит 23, в 3 на 4 29.

Upd: 14 это в классику 3 на 4, я понял!:)

Это сообщение отредактировал kalaw - 9/11/2017, 09:53

--------------------

Кубок по уголкам.

Я не совсем понял к кому обращено письмо от товарища BAD, на какой вопрос и чьего авторства от отвечает, и не совсем понял логику. Если ко мне - спасибо, я всё это знаю.

Насчет логики... То есть "Зачем это делать, ведь это убьет задачу, наверное сделаю я..."? В смысле - вам можно убить задачу, а остальным - нет? Наверное я что-то не так понял.

Чисто с точки зрения математики, приведу "пару цифр".

Как все знают, существуют программы End для поиска одноцветных окончаний. Их особенность в том, что там вместо всей доски 8х8 вырезается кусок 6х6 и уже в нем идет работа. И вот, что можно в цифрах сказать про эти базы:

6x6
3x3 - 94.143.280 - 89.78Mb
Hal - 254.186.856 - 242.4Mb
4x3 - 1.254.677.700 - 1.17Gb

То есть, если идти от полного конца, как в шашках, то это размеры баз в таком стиле. Проверьте по файлам End.dat и ГальмаКлассика.dat. Размеры у них именно такие, то есть я иду по верному пути. Легко предположить, что в 4х3 будет такой же размер, как здесь написано - 1.17 Gb.

К таким базам можно сделать два уточнения.

Первое. Ну, можно очень легко уменьшить их в два раза (это я не про сжимание), ну, а я бы сделал в 4. При этом все останется совершенно легко работающее, с небольшими усложнениями в коде. Тогда вместо тех баз, которые лежат на сервере были бы файлы размером в 22 и 60Мб вместо 89 и 242Мб.

Второе. Ответа на вопрос: "как пройти из одного дома в другой", это не даст! 6х6 это не 8х8.

Давайте посмотрим, что получится, если делать на полной доске 8х8, то есть такую базу которая "убьёт задачу".

8x8
3x3 - 27.540.584.512 - 25.6Gb
Hal - 151.437.214.816 - 141.0Gb
4x3 - 3.284.214.703.056 - 2.98Tb

Здесь возможны теже самые сокращения в 2 (легко) и 4 раза (небольшое улучшение в коде).

К сожалению, я не нашел 14 миллиардов позиций ни в одной из таблиц (видимо я где-то ошибся), поэтому никак не могу комментировать работу компьютера в днях (понятия не имея о его скорости). В размерах файла после сжимания тоже не очень уверен, но, как я понял, это разговор о том как 2.98Tb ужать в 300-500Мб. Буду с нетерпением ждать конечного результата.

Также подтверждаю, что реально проверка на ошибки может занять много времени и их невозможно избежать. Вот у меня, там где первых ходов 14, вторых 179. Буду проверять.

P.S. В Европе и Японии играют на досках 9х9 и проблемы кратчайшего пути были решены, в том числе и на компьютерах, еще в 80-х годах прошлого года. Смерти игры я не заметил. Возможно у меня просто недостаток информации...

P.S.S. Для тех, кто хочет проверить мои вычисления, предлагаю использовать формулу:
R!/S!(R-S)!, где R - размер доски (здесь 36 и 64), S - количество шашек (9, 10 и 12), а знак ! - это факториал, то есть произведение всех подряд идущих чисел от 1 до указанного.

Это сообщение отредактировал StepanovOleg - 9/11/2017, 11:16

боже, этот гений ещё м факториалы знает!

Если задача просто пройти из угла в угол, то там моментально для расчетов можно вырезать лишние поля с доски. Очень много полей.

--------------------

Кубок по уголкам.

Прога End была написана наспех с одной целью - помочь быстро собрать дом в позиции где черные не мешают белымю Тут достаточно доски 5х5
Никакого сжатия не применялось - даже 5 бит вместо 8 на позицию. И ни симметрии ни еще на 2 или 3 за счет оставления покрываюзей сети позиций.

проверять 179 не нало. Моя прога в этой версии не считает все симметричные позиции (для увеличения скорости некоторые симметричные не сопостовляются ~1%)

в Карлсон симметрия выставляется галочкой.
Для обладающих мнением что ходы A3A4 и C1D1 симметричны скажу, что это не так. В те времена было правило "покидания своей половины доски" отличное от текущего.

Насчет убийств я никому это не запрещаю, а сам не всегда люблю

применяемое мной сжатие готовых баз (~20-50 раз) дает возможность в режиме реального времени пользователю посмотреть результат со скоростью порядка 500 поз в сек.
Для расчетных же задач я пользую более слабое сжатие, но со скоростью порядка 10 000 поз в секунду
либо вообще не сжимаю
Вообщем тут подход в зависимости от потребностей

Автор данного топика просил нас решать его задачи. Если наши попытки их обсуждать ему не интересны, то Спасибо и извините.
Никаких e-mail писем я не писал. Либо я не так понял либо это не мое письмо было.
------------------

Вот предварительные результаты еще не отлаженной программы грубого перебора
- больше всего позиций решается за 14-16 ходов
- Нет позиций длинее 22 ходов
- вот список поз которые она считает трудными
a5a7b4b8d1d2g1h2h8
a5a7b4b8d1f1g1h2h8
a4a7b8c7d2e1g1h2h8
a5a7b4b8d1e1g1h2h8
a5a7b4b8e1g1h1h2h8
a4a6a8c8d1d3f1h1h3
a4a7b8c8d2e1g1h2h8
a5a7b4b8d1g1h1h2h8
a5a7b4b8d2e1g1h2h8
(не нравится мне h8)
а вот без него a4a6a7c8d1d3e1h1h5 21 ход

Я бы не советовал верить неотлаженной проге и воспринимю ее ответ как рекомендацию.
Заниматься ее доработкой пока не тянет особенно после комментариев автора топика.

Разумеется это грубый подход не позволяющий решать задачи на доске 20х20х20х20
Но для конкретных приведенных задач он наиболее эффективен по критреию
время = разработка+просчет+использование

Не буду больше раздражать творческих людей.
Удачи!

Это сообщение отредактировал B_A_D - 9/11/2017, 12:12