Ну это-то понятно.

И это проходили. К сожалению, как играть на 12 картах не ясно совершенно. Не говоря о том, что таблицы транспонирования и кэширование превратятся из изящных решений в громоздкую хрень. Вместе с увеличением числа вариантов при игре на 12 картах, это снизит производительность уже очень и очень сильно.

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

Вот вроде интуитивно кажется, что что-то можно придумать. Конкретика, правда, в голову не приходит)

Я, вообще, когда в конце того года от нечего делать решил "решатель" написать (сначала скачал БПС, он не запустился, а легендарная прога МишиХ канула в лету), думал, ха! Какие тут нафик таблицы для одного расклада! А оказалось, что без таблиц даже один расклад считается порой минуты и десятки минут. Даже если исключить из рассмотрения ходы с соседних карт (в случае трельяжа и т.п.). Пришлось мудрить. В общем, сделал таблицу на 2 млн ячеек, куда пишутся промежуточные расклады после каждого 3-го хода (начиная с 6-го и заканчивая 24-м), и идёт проверка, встречались ли они уже при другом ходе розыгрыша. Ну и ещё они перед записью в таблицу "минимизируются". Т.е. если в какой-то масти, например, ТД7 (и больше ничего), это тоже самое, что 987. Это значительно убыстряет подсчёт.

Кстати, я убрал этот глючок, что окно программы было всегда поверх других окон. Просто добавлением в код одной короткой строчки. Не знаю, почему не сделал это сразу) Если что, залил сюда новый вариант.

Любопытно, когда тестировал всё это дело на простых и не очень раскладах, нашёл несколько косяков в этюдах из книжки Лесного, например) В этюде, известном, как задача Галактионова (кажется, даже в Марьяже она есть), за вистующих в одном месте ход указан неправильно, он приведёт не к 4-м, а к 5 взяткам. Как же так можно?)

А вот тот мизер, который у меня по ссылке на яндекс-фотки, кто-нить смотрел? Не то чтобы я его придумал, он спонтанно получился в процессе тестирования. В нём, как оказалось, есть некоторая изюминка, которая сходу может быть не видна.

Подправил алгоритм, скорость просчёта увеличилась примерно в 2,5-3 раза. Оно здесь.

Я БПС на работе (Win8) не рискую запускать, а дома тоже XP. Поставил виртуалку, установил на нее Win7 - заработала. Но тормозит ужасно. Одну руку играющего при неизвестном раскладе вистующих может полчаса обсчитывать. Многовато будет, многовато ...

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

Минуты и десятки минут? Ну это слишком!
Я несколько лет назад написал на Delphi альфа-бета перебор без кэширования (без запоминания). Так там счет шел на секунды, десятки секунд в худшем случае. И это даже практически без всяких ускорителей для прогнозирования лучшего хода. Единственное что было сделано - вначале рассматривались ходы, форсированно берущие взятку, а потом - отдающие. Даже этого было достаточно, чтобы сократить время перебора раза в 2.

То что Вы назвали "минимизированием" на самом деле называется транспонированием (преобразованием) расклада к некоей нормализованной форме. И транспонировать каждую масть отдельно - это только первый шаг.

Мы с Николаем-extasy кроме этого применили так же транспонирование порядка мастей (с учетом козырности игры), от полученной транспозиции вычислялся Zobrist-хеш, что позволяло снизить число коллизий при обращении к таблицам кэширования (и уменьшить их размер без существенной потери производительности), потом он экспериментировал с различными типами организации кэша (прямое вытеснение, отложенное вытеснение, прямая адресация и пр.). Сейчас он хочет сделать многотабличный кэш, в котором каждая таблица отвечает за отдельное число карт в руке. Но эффективность этого на расчете одного фиксированного расклада - нулевая или отрицательная, а проявится только на переборе всех раскладов вистующих. И то - неясно, насколько повысит скорость.

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

Предлагаю всё-таки начать с 2-х вариантов сноса. Игру против всех возможных сносов пока опустим. Это реальная задача или нет?

Я сам указываю проге "снос А" и "снос Б".

Результат должен быть таким:

При сносе А = ТД(х)-(х):
1) И вистующие играют на этот снос (т.е. угадывают снос) = то 5,5 взяток.
2) Вистующие играют на снос Б (т.е. ошибаются в сносе) = то 5,6 взяток
И наоборот,
При сносе Б = Т(Дх)-х:
3) И вистующие играют на этот снос (т.е. угадывают снос) = то 5,4 взятки.
4) Вистующие играют на снос А, (т.е. ошибаются в сносе) то 5,6 взяток

Ответьте мне на этот простой вопрос.

Не в такой постановке ...

Сам подход "играть на снос" в данном контексте ошибочен. Потому что играть на какой-то известный (предполагаемый) снос можно несколькими способами. И только некоторые из них будут одновременно игрой на другой снос.

Т.е. надо найти такой розыгрыш, при котором ситуации "ошибаются в сносе" даже не возникает (как в приведенном выше раскладе). Если он существует, конечно.

Если же не существует, то это уже совсем другая задача: о смешанных стратегиях сноса/ловли. Которую тоже хотелось бы решать при помощи программного инструмента, но смешивать эти две задачи нельзя.

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

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

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

Уже и ошибки нашли… хотя я ничего пока не предлагал как это сделать.

Абстрагируйтесь вы от общего, решаем частный пример.

Я игрок, у меня рука ТК87-ТД87-ТД7-7 и я должен сделать снос. Варианта у меня всего 2. Не 1, не 3, не 4 не 5, а 2.

Проге не надо думать как сносить, я сам указываю ей эти варианты.

Проге не надо думать над приоритетностью одного сноса над другим.

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

Хитрость реализации в том, что в определённый момент времени всплывает другой снос… я об этом и спрашиваю. Это можно алгоритмизировать?

Мне надо подумать над алгоритмом. Завра напишу как сделать.

осталось/не осталось смягчение - это ведь тоже угадайка, не прада ли?)))

Это сообщение отредактировал american_boy - 14/03/2018, 00:12

Да кто ж говорит об ошибках?

Речь идет только о том, что если существует безопасный розыгрыш, то это должно быть отмечено. Т.е., практически, такой розыгрыш должен быть найден.

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

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

Весь вопрос в том, как определить наличие/отсутствие фиксажа без значительного падения производительности?

А потеря производительности будет грандиозная. Доказать не могу, но могу показать на пальцах:

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

2. Мало использовать для разных вариантов сноса один кэш. Надо как-то в нем еще разделять варианты "до определения сноса" и "после определения сноса" и еще по вариантам сноса. И еще проводить параллельно анализ: вот так в момент определения сноса результат зафиксирован не зависимо от сноса, а вот здесь различается, в зависимости от сноса.

Не говоря уже о том, что кэш расклада строится не на 10, а на 12 картах играющего до определения сноса и скачком исчезают 2 карты после того, как снос выяснен. Т.е. работа с кэшем (и таблицами транспозиции) усложняется в разы или на порядки.

А сам розыгрыш тоже будет иметь более широкое дерево перебора за счет лишних карт.

Т.е. и сам перебор и работа с кэшем могут очень сильно уронить производительность. И это только для одного расклада вистующих. А их надо перебрать 184756.

А, так вот что такое транспонирование. Оказывается, его я и делал) Ну конечно, масти я тоже транспонировал, это очевидный шаг. Чтобы не считать два раза похожие расклады с, так сказать, симметричным расположением мастей. И в таблицу записывается конечно уже транспонированный расклад. Правда, почему-то транспонирование мастей не привело к повышению производительности в рамках обсчёта одного расклада. Может, это проявляется, когда считаешь много раскладов?

Меня на самом деле напрягает другое. Почему изначально у меня считалось всё так медленно. Подозреваю, дело в организации массива данных и способа реализации ходов по правилам игры. У меня фактически 12 динамических одномерных массивов (4 масти х 3 руки), длина каждого из которых варьируется от 0 до 8 и которые складываются в многомерный массив под названием "расклад". Плюс массив из вышедших карт, он нужен для возврата ходов, а последние 1-2 его карты всегда нужны, когда номер хода не кратен 3.

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

Во-первых, давайте сразу правильно определимся с атмосферой, в которой находимся. Призываю к общению на одном языке. На языке программирования мне не удастся всё растолковать и понять тоже, воспринимайте меня скорее как генерального директора фирмы, племянника руководителя холдинга, состоящей из 80 таких фирм, 25 лет, закончил плехановку, красный диплом, работаю в фирме 3 дня, слова типа "Zobrist-хеш", "транспонирование", "избыточный минимум" услышал от вас впервые на вчерашней планёрке. Кроме того, специально приглашённые мной программисты из других фирм нашего холдинга, (по словам сказанным в кулуарах), также не смогли разобраться в данной терминологии.

Вы - руководитель технического подразделения, академик РАН, теоретик, имеете всяческие регалии, 65 лет, в подчинении у вас талантливые ребята, которых вы сами подобрали, работаете в фирме 20 лет. Т.е. стандартная ситуация.

У нас проходит примерно такой разговор. Я говорю: "Николай Николаевич! Сделайте-ка мне быстренько одну программку, я уже всё придумал надо просто дать задание вашим программистам."

Я не хочу никого обидеть, просто поймите меня правильно, я искренне заинтересован в решении этой задачи.

Необходимо усовершенствовать существующие проги на работу с двумя вариантами сноса. Т.е создать решатель на 2 сноса.

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

Пара слов о безопасном способе розыгрыша. Тупо конечно, когда прога прямолинейно играет против одного сноса, не учитывая, что в природе могут быть и другие. Это умение существенно повысит качество розыгрыша решателя в принципе. Как это сделать? Есть же варианты, когда вистующие, если не начнут сразу проверять один из вариантов сноса, под конец розыгрыша могут попасть под угадайку, хотя её и не было изначально. Этого не умеют делать существующие проги.

Возьмём типичный пример.

Снос А = ТД(х)-(х)
Снос Б = Т(Дх)-х

Решение вижу следующим образом. Программе указываются 2 варианта сноса. Во всех вариантах оптимальной игры при сносе А отмечаются те ходы, где мелькают эти 4 карты (или где они должны промелькнуть). Теперь перед этим ходом, переключается тумблер. Вистующие переключают свою мысль на снос Б, и разыгрывают в уме расклад до конца при сносе Б. При сносе А они тоже естественно знают чем всё должно закончиться т.к. играют оптимально. Теперь сравниваются результаты. Если результат хуже – это ход отмечается негативным, соответственно этот способ розыгрыша несёт опасность. Значит надо выбирать другой! Если результаты при А и Б совпадают - такой ход можно делать безопасно, он не навредит оптимальности.
Таким образом, если в ключевых ходах находится безопасный способ – он и будет лучший при 2-х возможных вариантах сноса.

Но может оказаться, что безопасного способа может не быть. Тогда прога ориентируется на приоритетный снос А, который мы ей указали.

Подчеркну - берутся все оптимальные способы розыгрыша при сносе А. И прогоняются именно все. Т.к. только среди всех может найтись оптимальный способ сразу при двух вариантах.