Рассказываю эту историю по порядку.
Года два назад в теме «стоит ли играть мизер?» обсуждался некий мизер со своим ходом после прикупа для двух стратегий сноса:
https://www.gambler.ru/forum/index.php?show...dpost&p=1481354
Пытались определить, какой снос лучше. Один из участников обсуждения - ув. Pochemuk - использовал метод Монте-Карло и программу Алексея Словеснова «Bridge-Preference Studio». Он написал генератор случайных раскладов, сгенерил 200 раскладов вистующих и «прорешал каждый при помощи BPS». При этом каждый конкретный расклад вручную посылал на BPS и сохранял результат. Были получены результаты для двух сносов – довольно близкие. Далее прикинули СКО и дисперсию и пришли к выводу, что для этого конкретного мизера достоверность полученных результатов совершенно недостаточна – мало число испытаний. А для получения достоверного результата в этом случае нужно от 5000 до 15000 испытаний, что сделать с помощью текущей версии программы BPS нереально. Т.е. вопрос о лучшем сносе для той карты остался открытым. Не привожу здесь тот мизер, потому что дело не в нем, а в способе получения результата.

Весной этого года я снова обдумывал эту тему и этот метод получения результата. Решил написать автору BPS Алексею Словеснову письмо с просьбой немного усовершенствовать его программу. В письме я просил Алексея добавить в его программу такие возможности:
• для заданных карт и сноса играющего - генерировать случайный расклад карт у вистующих, и производить розыгрыш,
• задавать необходимое число розыгрышей,
• выдавать конечный результат серии – процентную долю исходов игры разного типа.
В своей просьбе я ссылался на то, что энтузиасты тратят часы и дни своего времени на попытки решения таких задач, на то, что большая часть того, что требуется для реализации такого усовершенствования программы, уже имеется (есть и генератор случайных раскладов, и, самое главное - высококачественный решатель), и на то, что для BPS определение лучшего сноса – это новый большой класс решаемых задач.

Через некоторое время Словеснов выполнил мою просьбу, за что ему огромное спасибо. Причем сделал он это намного лучше, чем просили! Он не стал вводить случайные расклады с помощью ММК, а сделал точное решение – полный перебор всех 184756 раскладов. Эту версию программы он назвал «версия 5.01 7 июня 2017»:
http://slovesnov.users.sourceforge.net/ind...?bridge,russian
С помощью этой версии любой желающий может, задав 10 карт играющего и 2 карты сноса, получить ожидаемый результат игры. Результат выдается в виде вероятностей получения 0, 1, 2, …10 взяток. На расчет требуется несколько минут в зависимости от карты и производительности компьютера.

Далее я попытался предложить Словеснову кое-что подправить и сделать некоторые другие усовершенствования. Однако он сообщил, что у него теперь нет ни времени, ни желания заниматься этим делом, а потом и вовсе перестал отвечать. Даже на своем собственном сайте он выложил новую версию программы 5.01, но не дал к ней никаких пояснений.

Думаю, что последняя версия BPS многим будет полезна, тем более что там выложены и исходные коды. Ниже приведу краткие объяснения и комментарии к работе этой программы.
• Новая опция - последняя в меню "дополнительно"/"(преферанс) решить все расклады противников",
• опция работает как для мизера, так и для игры на взятки,
• результаты расчета получаются при копировании в буфер обмена в виде вероятностей получения 0, 1, 2, …10 взяток,
• для начала расчета необходимо, чтобы были заданы 10 карт у игрока и 2 карты в сносе,
• (не уверен, что обязательно, но рекомендуется) – карты играющего следует располагать в верхней части экрана,
• возможны два варианта расчета: когда сделан первый ход (одна карта на столе), и когда первый ход еще не сделан,
• в случае второго варианта расчета, когда первый ход не сделан, для каждого из 184756 раскладов определяется оптимальный первый ход. То есть, это подразумевает игру на картах, открытых ДО первого хода. (Нужно заметить, что в преферансе такая возможность действительно есть, если первый ход у вистующих, и для этого случая программа все посчитает верно. Но играющему расклад перед своим первым ходом не известен никогда (по правилам вистующие открывают карты только после хода играющего), поэтому для первого хода играющего такой лучший ход и расчет не имеет практического смысла. Словеснову я посоветовал убрать эту возможность расчета с первым ходом играющего и не заданной картой выхода, но он уже замолчал).

О точности полученных результатов. Результаты, полученные с помощью последней версии программы BPS, мне кажутся очень правдоподобными. Подобные расчеты на Гамблере несколько раз выкладывал ув. Extasy, и даже грозился сделать их общедоступными. Я сравнил приведенные на сайте результаты Extasy с результатами Словеснова для десятка разных раскладов. Все результаты оказались совершенно одинаковы, точнее, совпадающими до 8 знака. Это, конечно, радует.

Загрузил программу Словеснова. Действительно, очень полезное нововведение.
Протестировал на 1 раскладе, результаты совпали с работой моей программы.

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

Мне интересно только одно, как ему удалось распараллелить рекурсивную задачу и насколько эффективно работает многопоточность по сравнение с одним потоком.

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

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

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

the elephant has you..

Ну, он же исходники не жадничает выкладывать

Правда, в них разобраться без поллитры невозможно, а с нею - затруднительно ...

А есть ли смысл? Я еще не пробовал, но BPS теперь считает быстрее, чем твоя программка?

В Скачках и некоторых других конвенциях вистующие вскрываются перед атакой играющего. Но не на мизере, разумеется.

Чёрт!

После установки программа не запускается. Мол не найдена какая-то точка входа в процедуру.

Ну, он же исходники не жадничает выкладывать

Правда, в них разобраться без поллитры невозможно, а с нею - затруднительно ...

А есть ли смысл? Я еще не пробовал, но BPS теперь считает быстрее, чем твоя программка?

Не, там нереально в исходниках разобраться сколько литров ни возьми, все на Си, насколько помню.

BPS, хоть и многопоточная, но медленнее моей однопоточной проги.
Пока лень тестировать нормально, но 1 расклад у меня считался на 70% быстрее.

Другое дело, что моя прога требует немало оперативки для хэш-таблицы. А BPS совсем мало ест памяти.

Буду реализовывать многопоточность. В принципе знаю как, но для расчета задач с фикс. сносом прогнозируется небольшой прирост порядка 300%, причем увеличение числа ядер компьютера уже не даст преимуществ и 4-ядерный комп будет давать максимум нужных потоков.
То есть, на 1 руке у нас цикл по всем возможным ходам (врядли, больше 8) и на каждый ход выделим свой поток. Но жертвуем альфа-бета отсечением на 1 итерации, поэтому ускорение будет не в теоретические 8 раз(точнее, количество раз по числу различных ходов с первой руки), а раза в 3 (максимум, учитывая издержки на формирование потоков).
Но тут пока непонятно, как поведут себя потоки при запросах к единой хэш-таблице: у нас же будет постоянная запись/считывание раскладов.

Зато многопоточность идеально подойдет для случая самой тяжелой задачи - то есть, расчета МО до взятия прикупа. Там на каждый прикуп создаем свою хэш-таблицу и выделяем свой поток. Поэтому, ускорение будет пропорционально числу ядер процессора.
Пожалуй, для случая 8-ядерного процессора можно добиться х10 увеличения производительности для этой задачи.

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

the elephant has you..

Ну так у нас лучше организованы транспозиции. Поэтому и быстрее.

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

И если какая-то ячейка переполнится и начнет очищаться, то это ни к чему плохому не приведет.

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

Поэтому ее и приходится делать большой, в отличие от хеш-таблицы с вытеснением.

Может быть стоит попробовать так, как у Словеснова. Но еще лучше - в чистом виде вытеснение. Это самый быстрый вариант при достаточной памяти. А при недостаточной - краха все равно не будет. Только медленнее будет считать.

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

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

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

В том то и дело. Не хотелось бы вникать в тонкости многопоточности, если это не даст существенного прироста на простом типе задач.
Эти блокировки явно будут время отнимать. Если там профит 100% всего, то нет смысла мучаться, тем более и так задача достаточно быстро решается в одном потоке.
А для сложных задач уже можно использовать частные таблицы и реализовать это достаточно просто.

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

the elephant has you..

А ты сравнивал производительность с прямым вытеснением (без массива в каждой ячейке)?

Думаю, кстати, что там на 4-ядерном процессоре выигрыш будет раза в 1,5-2. Ведь одно ядро будет обслуживать систему, второе тоже сильно не загрузишь. Остаются 2 ядра, которые на маленьких хеш-таблицах будут мешать друг другу. А на больших и без многопоточности неплохо работает.

А как там с мультитэйблом?

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

на xp тоже не пошло, dll подсунул - на что-то другое ругаться начало.
на форумах советуют что-то там править и пересобирать.

а на w7 нормально работает