В процессе работы над программой возникла прикладная задача.

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


Для этого рассмотрим 2 типа игры: мизер и обычная игра на взятки.

1. Мизер.
Очевидная мысль - взять да исключить все 7ки на руке игрока из числа 12 карт.
Например, если на руке 3 семерки, то всего нужно вычислить 36 сносов вместо 66.
Очень даже неплохо, учитывая, что оптимальное машинное решение не может быть заключено в сносе, содержащем 7ку. Тут вроде все в порядке.

2. Обычная игра на взятки.
Тут почти то же самое. Исключим все Тузы из 12 карт и будет счастье. Но так ли все просто?

Вопрос в том, могут ли быть оптимальными всветлую сносы, содержащие Т?

Это сообщение отредактировал extasy - 23/05/2017, 18:19

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

the elephant has you..

1) Могут при сносе в чистой короткой масти, при соответствующей тактике ловящих. Можно оставить возможность сноса только в короткой масти. А можно оставить только для 7 бланк, потому как если не бланк можно снести постарше, разница там психологическая,а не алгоритмическая.
2) Могут, но редко, можно исключить, потому как там и так ясно.
Пример: ТК_ТКД987_ТКДВ - чужой ход, правильно снести ТК левые.

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

Верно, но примеры могут быть и не такие очевидные, например:
ТК_КД1987_ТКДВ, Т_ТДJ1987_ТКДВ и т.д.

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

Собственно, вопрос не только в тузах, но еще и в том, какие есть идеи по сокращению числа сносов без потери решения?

Это сообщение отредактировал extasy - 23/05/2017, 19:00

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

the elephant has you..

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

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

Сегодня думал над этой идеей, она имеет изьяны.

Например, склеив непрерывный ряд в 1 карту мы уже не сможем снести 2 карты из этого ряда.

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

То есть, все сносы из непрерывного ряда создадут множество эквивалентных 10+2 последовательностей с единой оценкой.

Это сообщение отредактировал extasy - 23/05/2017, 19:22

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

the elephant has you..

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

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

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

А в чем преимущество такого алгоритма перед хэш-таблицей?

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

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

the elephant has you..

Хочется "финта ушами", как с исключением 7рок. Вот с тузами уже не так все гладко.

Исключение 7рок отлично накладывается на идею с хэштаблицами.
Поэтому, нужны какие-нибудь хитрые маневры, которые можно наложить на основной алгоритм.

Это сообщение отредактировал extasy - 23/05/2017, 19:54

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

the elephant has you..

По поводу обычной игры на взятки.

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

Это сообщение отредактировал extasy - 23/05/2017, 20:26

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

the elephant has you..

По "основной задаче" ничего вразумительного сказать не могу - не занимался, - а по поводу "оценки карты до взятия прикупа" замечу, что тут исследователя ждет и другая задача, можно сказать, обратная: а будет ли вообще что сносить после получения прикупа?
Чуть подробнее. В моем алгоритме торговли для розданной руки считаются "железные" взятки с раздачи, плюс оцениваются "прикупные" взятки, плюс "раскладные". Дополнительные нюансы (поправки) опускаем. И вот, бывает, что для какой-то руки ожидаемое значение получается больше 8 взяток, но торговаться до 8 нельзя по той причине, что если 8 таки будет, то не будет что сносить. В смысле, сносить придется взятку.
Проблема, конечно, не самая актуальная, но имеет место быть. )