Да разве кто-то против общаться на одном языке?

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

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

И ничего ... разобрались со временем. Что-то в Инете прочитали, что-то методом проб и ошибок сами придумали. Зато считает и одиночные расклады и всевозможные руки вистующих в несколько раз быстрее Словесновской программы.

Хотели переходить к решению неизвестного сноса (двухвариантного и многовариантного), но запал уже потихоньку за год иссяк. Да и задачка оказалась не такой "простой", как представлялось.

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

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

Готов обсудить разные алгоритмы нахождения фиксажа, но для этого нужно иметь представление о работе таких механизмов, как альфа-бета перебор, кэширование, транспонирование и пр. Чтобы понимать, как можно совместить эти алгоритмы с этими механизмами.

Это сообщение отредактировал Pochemuk - 16/03/2018, 01:07

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

Приходилось рассматривать похожую проблему в связи со сносами на мизерах. В связи с этим любопытно было посмотреть на дискуссию, на озвученные "трудности"...
Главное впечатление и вывод: вы пытаетесь преферанс адаптировать под ваши алгоритмические достижения, а я считаю правильным с помощью алгоритмических подходов решать проблемы преферанса.

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

Если уже готовые варианты сноса обсчитать не могут, то заставить прогу ещё и выбирать снос – звучит как издевательство )))

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

Определение вистующим сноса игрока и, как следствие, тактики разыгрывания - аспект (проблема) преферанса.
А вы во что "играть" собрались? Если в преферанс, то я и посоветовал вам попробовать "с помощью алгоритмических подходов решать проблемы преферанса". Но нет - так нет, я не настаиваю. )

Никто ж не против создания проги, которая сразу умеет всё. Так мы и последних программистов распугаем.
Честно говоря, если б я был программистом я б разобрал сначала марьяж. Но не мне им советовать, ребята толковые, сами разберутся, не будем им мешать нашими советами)))

Тут программисты не нужны и даже вредны. Тут нужны "алгоритмисты".
Но согласен, что это бесполезный разговор.

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

Но скорость расчета очень маленькая. Я запускаю на одной машине BPS Словеснова и вашу программу. На вашей программе время расчета, например, задачи Галактионова - около 5 секунд. На BPS – около1 сек. Причем в BPS это время расчета для опции «Решение для всех игроков и козырей», т.е. там считается и выдается результат для 3*6 = 18 разных вариантов. Получаем, что BPS быстрее в 5*18 = 90 раз. А программа Extasy и Pochemuk по их словам еще быстрее.

Одна из причин медленной работы вашей программы, видимо, то, что в ней не реализованы альфа-бета перебор и другие приемы ускорения. Но не может ли быть и другой причины? Может, дело в том, что у вас отличается базовая логика решения?

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

Существует ли литература, где описаны подходы к решению таких задач в карточных играх, например, для бриджа? Или каждый, кто изобретает это велосипед, идет своим путем?

Это сообщение отредактировал Кутруповезет - 18/03/2018, 11:07

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

Но скорость расчета очень маленькая. Я запускаю на одной машине BPS Словеснова и вашу программу. На вашей программе время расчета, например, задачи Галактионова - около 5 секунд. На BPS – около1 сек. Причем в BPS это время расчета для опции «Решение для всех игроков и козырей», т.е. там считается и выдается результат для 3*6 = 18 разных вариантов. Получаем, что BPS быстрее в 5*18 = 90 раз. А программа Extasy и Pochemuk по их словам еще быстрее.

Одна из причин медленной работы вашей программы, видимо, то, что в ней не реализованы альфа-бета перебор и другие приемы ускорения. Но не может ли быть и другой причины? Может, дело в том, что у вас отличается базовая логика решения?

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

Существует ли литература, где описаны подходы к решению таких задач в карточных играх, например, для бриджа? Или каждый, кто изобретает это велосипед, идет своим путем?

Если бы не был реализован альфа-бета перебор, то решение единичного расклада имело бы порядок десятков минут, а то и нескольких часов. Альфа-бета отсечения - основной способ сокращения дерева перебора. В свое время он был революционным. Сейчас является неотъемлемой частью игровых программ. Кроме новейших, основанных на ИНС. Но ИНС для решения раскладов пока что мало подходит.

Как конкретно всё реализовано у Николая - сказать затрудняюсь. Ибо не программист и во все тонкости реализации не вникал (только в некоторые). Но основые моменты логики могу описать. Надеюсь, Николай не будет против.

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

1. Перебор дерева решений осуществляется с применением алгоритма альфа-бета отсечений. Подход NegaMax не применяется, т.к. усложняет логику программы дополнительными проверками. Вместо этого применяются несколько более простых различных процедур для каждой из сторон, а так же для начальной атаки (т.к. для начальной атаки альфа-бета отсечения не применяются). Так же не применяется альфа-бета отсечения с амортизацией - тесты не выявили существенного повышения эффективности работы с кэшем, а сложность алгоритма амортизации чуть выше, что привело к просадке производительности почти на 1%.
2. Дерево отсечений не строится для последней взятки, т.к. дерева нет - все ходы единственно возможные. Вместо дерева непосредственно расчитывается принадлежность этой взятки. Это снижает глубину рекурсий.
3. Для позиций, в которых нет выхоженных на стол карт (т.е. для позиций перед первым ходом во взятку, кроме первой) строится транспозиция - карты мастей и сами масти переупорядочиваются с учетом выхоженных карт (так же сноса), длины/силы некозырных мастей, козырной масти.
4. От полученной транспозиции вычисляется хеш. Мы решили применять Zobrist-хеширование. Во-первых, просто, во вторых - равномерно.
5. В качестве индекса кэш-таблицы можно брать несколько старших или младших битов хеша. Но Николай решил брать остаток от деления на размер кэш-таблицы. Это несколько дольше, но позволяет более гибко оперировать ее размером, что немаловажно для исследования его влияния на производительность.
6. В кэш-таблице хранятся транспозиции с оценкам альфа-бета интервала. Если транспозиция не найдена (ячейка с соответствующим индексом не заполнена или имеет место коллизия - заполнена другой транспозицией), то запускаем процедуру альфа-бета перебора. После чего записываем полученный интервал в таблицу.
7. Если транспозиция найдена в кэш-таблице, то дальнейшее поведение зависит от хранимого в ней диапазона альфа-бета, текущего значения альфа-бета диапазона и числа оставшихся на руках карт. Либо сразу возвращаем оценку, либо тоже запускаем перебор для уточнения диапазона. Уточненное значение альфа-бета диапазона записывается в таблицу.
8. Для позиций с выхоженными на стол картами транспозиции не вычисляются и кэширование не производится. Вместо этого применяются эвристики нахождения лучшего ответа, повышающие вероятность нахождения хорошего хода уже в начале перебора. Эти эвристики реализованы в виде процедур, обращение к которым производится по ссылкам из массива. Это позволяет легко менять такие эвристики для экспериментов.
9. Для первого хода во взятку тоже применяются эвристики, но их эффективность несколько ниже. Вернее, эффект от них был до применения кэширования, но кэширование само по себе реализовано столь эффективно, что перекрывает весь эффект от этих эвристик.
10. Еще надо отдельно отметить, что перед перебором на любом уровне сначала создается список допустимых ходов/ответов с учетом секвенсов и отсутствующих карт. Так, если в руке {10 9 7} одной масти а восьмерка уже вышла (или в сносе), то достаточно рассмотреть ход только в одну карту из этого набора. У Словеснова наборы допустимых ответов для второй и третьей руки создаются оба на этапе перебора ответов второй руки. Это позволяет для третьей руки создавать этот набор тоже один раз. Еще там, кажется, если масть хода первой руки не сменилась, то эти наборы не переформируются. У Николая это не так. Ибо основная сложность не в получении набора (он применил весьма изощренные структуры данных, позволяющие получать эти наборы достаточно просто), а в сортировке этих ответов по рекомендациям эвристик. А эти рекомендации будут разными в зависимости от уже выхоженных во взятку карт. Поэтому выигрыш от повторного использования этих наборов минимален или отсутствует.

Что не релизовано, так это перебор с нулевым окном. Я склонялся к MTD(f), а Николай к NegaScout. Но эксперименты с NegaScout он проводил еще до реализации кэширования. Выигрыш был, но после реализации кэширования сошел на нет. А до MTD(f), который как раз заточнен под работу с кэшем, так руки и не дошли.

Вот как-то так ...

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

Кроме того, в этих играх, обычно, применяется перебор на переменную глубину. Причем, оценка вычисляется для позиции в конце перебора. Для решения расклада это не подходит, т.к. в конечной позиции (все карты вышли) оценка всегда 0 - никто ничего уже не возьмет. Т.е. тут важна не только конечная позиция, но то, каким образом к ней пришли (кто сколько взяток уже взял). Чтобы не учитывать эти разные пути, приходится тоже алгоритм перебора слегка видоизменять.

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

Это сообщение отредактировал Pochemuk - 18/03/2018, 13:21

Андрей, спасибо за подробные объяснения, очень интересно и познавательно.
Да, это целая наука, и немаленькая.

А поясните еще, пожалуйста, почему никто до сих пор не сделал калькулятор раскладов для распасов? На форуме я не раз встречал упоминания об этом с объяснениями, что это невозможно, т.к. распасы, в отличие от игры на взятки и мизера - это игра троих, а не двоих игроков. Но действительно ли это препятствие непреодолимо? У меня, как и положено дилетанту, есть некоторые сомнения в этом. Может, ребята всего лишь немного недодумали, недоработали?

Это сообщение отредактировал Кутруповезет - 18/03/2018, 16:27