игрыстатьиматематические программырусский языкразноеоб авторе

Описание логической части решателя

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

Логическая часть решателя задач по преферансу

Версии 1.0 1.1

В своей программе я использовал альфа-бета отсечения и хеш-таблицы. Информацию о них можно найти в интернете. Это было реализовано в версиях 1.* Также для ускорения расчетов было использовано следующее правило.
Отсечения 1 (непрерывные последовательности карт)
Пусть на руке у нас есть карты: пика 7 8 9. Назовем это непрерывной последовательностью карт. Понятно, что какую карту из них не клади, оценка позиции будет одинакова. То есть достаточно рассмотреть только ход в 7 пик.
Это правило можно немного обобщить. пусть на руке имеются карты: пика 7 8 10. Если 9 пик уже в сносе, то очевидно, что ходы 7,8,10 дадут один и тот же результат.
Небольшое ускорение
Каждый раз мы должны выбрать карту первой руки и затем найти подходящие карты второй и третьей руки. пусть первый игрок может зайти картами {c1,c2} и пусть карты c1, c2 одной масти, тогда если мы нашли подходящие карты для второй и третьей руки, то они будут одинаковы для карт c1 и c2. То есть подходящие карты здесь надо искать только один раз.
Существенный прирост скорости, дал параллельный поиск подходящих карт для второй и третьей руки. То есть массив с картами просматривается только один раз.

Версия 2.0

В версии 2.0 была изменена схема хранения карт. Ранее они хранились в двумерном массиве. Теперь все организовано в виде массива двусвязных списков, по одному списку на каждую масть. Это дает большой выигрыш во времени. Почему? Пусть у нас есть массив карт. Мы ищем в нем подходящие карты. Понятно, что чем меньше осталось карт, тем больше мы ищем по нему. Я в самом конце, просто идет почти холостой бег по массиву карт, ведь в нем осталось всего три! карты. Списки позволяют избежать этого. Рассмотрим разницу во времени решения задач (я не буду рассматривать "задачи 7 взяток" и "10 взяток" так как считаются они очень быстро). Замечу что эти времена для второй версии даны когда хеш-таблицы не используются.
Ускорение 1. Инверсный перебор.
В ранних версиях программ я использовал перебор одной масти идя от семерки к тузу. Версия 2.0 использует обратный порядок перебора (версия 2.0* использует прямой порядок), то есть от туза к семерке. (время расчета в секундах)

задача В 1.1 В 2.0* В 2.0
Барбакару. 14.68 7.01 2.07
Мизер Ковалевской. 4.75 2.47 2.47
Мизер Ласкера. 24.19 13.65 13.7
Задача Галактинова. 32.35 15.27 6.3
Сложный расклад. 501.3 234.55 17.74
Из этой таблицы можно сделать несколько выводов. Во первых переход к спискам дал, огромный выигрыш в производительности. Во-вторых обратный перебор дал странный эффект. Еще можно понять, что обратный перебор дал выигрыш в задачах, где игралось на максимум. Но почему задачи на мизер стали считаться с той же скоростью, а не замедлились? Почему инверсный порядок дал такой огромный выигрыш в задаче "Сложный расклад".
Более правильная организация хранения карт дала выигрыш в полтора раза.

Версия 2.1 7 июня 2002

Отсечения 2 (нижние слои)
Рассмотрим ситуацию, когда осталось всего три карты, по одной у каждого игрока. В этом случае, вызывается рекурсивный перебор на глубину 3, (для первой, второй и третьей руки) Можно не рассматривать рекурсию дальше, а просто сразу посчитать оценку, то есть отсечь два нижних слоя (ply) рекурсии.
Удален параметр depth в рекурсии Отмечено в таблице как -depth
Отсечения 3 (усечение интервала alpha beta)
Мне даже сейчас непонятно, почему это отсекает что-то. Идея такова. Пусть функция генерации нового слоя для первой руки, была вызвана с параметрами alpha,beta. Пусть у каждого игрока осталось 1 карта, тогда для данной позиции мы можем получить оценку +1 или -1 У меня оценкой данной позиции является разность взяток своей и противоположной сторон. Если у каждого осталось по 2 карты, то возможная оценка -2,0,+2 и так далее. Введем доп. член класса depth равный числу оставшихся карт. Он вычисляется только один раз и поэтому не влияет на скорость. Отсечения данного рода применимы только тогда, когда у всех игроков равное число карт. Видно, что в данном случае, возможная оценка лежит в отрезке [-depth,depth], а нам был задан интервал [alpha,beta]. Понятно, что нас интересует только пересечение заданных отрезков и если оно пусто, то можно сразу вернуть оценку, позиции. Усечения для непустого пересечения по beta дали реальный результат только для задачи "Сложный расклад", но тем не менее они были оставлены, так как не сильно замедляют программу. Еще раз отмечу, что пустое пересечение дало выигрыш для всех раскладов. отмечено в таблице как"отс3".

задача В 2.0 -2 слоя -depth отс 3
Барбакару. 2.07 1.43 1.41 0.93
Мизер Ковалевской. 2.47 1.8 1.78 1.18
Мизер Ласкера. 13.7 9.7 9.51 4.95
Задача Галактинова. 6.3 4.77 4.69 2.82
Сложный расклад. 17.74 11.63 11.35 2.33

Версия 2.2 25 июня 2002

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

задача В 2.1 В 2.2
Барбакару. 0.93 0.07
Мизер Ковалевской. 1.18 0.64
Мизер Ласкера. 4.92 3.87
Задача Галактинова. 2.81 0.71
Сложный расклад. 2.31 0.18

Версия 3.0 13 июля 2002 - кажется, последняя

Два небольших ускорения.
Когда нет подходящей масти и козырей, перебор ведется в прямом направлении (*1).
Когда нет подходящей масти и есть козыри, перебор ведется в прямом направлении (*2). Это не влияет на число узлов для мизеров и "сложного расклада", так как там нет козырей.
Ниже приведена таблица числа узлов дерева.

задача число узлов *1 *2 "ускорение"
Мизер Ласкера 21, 744, 685 21, 759, 156 21, 759, 156 + 14, 471
Мизер Ковалевской 3, 892, 775 3, 894, 695 3, 894, 695 + 1, 920
Задача Галактинова 4, 234, 060 3, 811, 330 3, 111, 079 - 1, 122, 981
Сложный расклад 1, 264, 667 1, 000, 627 1, 000, 627 - 264, 040
Барбакару 471, 108 463, 744 462, 885 - 8, 223
10 взяток 268, 097 260, 729 286, 251 + 18, 154
7 взяток 2, 508 2, 497 3, 127 + 619
Надо отметить, что если бы в таблице были бы время расчета расклада, то замедление задач было бы незаметным. Хотя эти новшества и замедляют мизеры, но так как дополнительное число узлов не так велико, а уменьшение для задачи Галактинова и Сложного расклада весьма ощутимо, то я их решил оставить.
Использование хеш-таблиц.
В программе используется хеш-таблица из 200,000 элементов. Размер ячейки таблицы 6 байт, то есть программе необходимо чуть больше одного мегабайта оперативной памяти, что совсем немного.
задача без хеширования хеширование
Мизер Ласкера 21, 759, 156 135, 939
Мизер Ковалевской 3, 894, 695 61, 272
Задача Галактинова 3, 111, 079 205,309
Сложный расклад 1, 000, 627 166, 614
Барбакару 462, 885 19, 687
10 взяток 286, 251 21, 760
7 взяток 3, 127 1, 264
Сравнительная таблица расчета расклада в секундах.
задача В 2.2 В 3.0
Барбакару. 0.07 0.00
Мизер Ковалевской. 0.64 0.01
Мизер Ласкера. 3.87 0.03
Задача Галактинова. 0.71 0.04
Сложный расклад. 0.18 0.03

Что хотелось сделать

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

Барбакару
козырьТрефа
первый ходЗапад
играющийЗапад
мизер
бридж студия
снос 7 8
север
10 В Д
В К
7 9 Т
9 В
западвосток
Т 9 К
7 8 9 Т 10 Д
В К 8 10 Д
10 К Т 7 8 Д

Первый ходит запад, он же играющий. Попробуем оценить минимальное число взяток, которое он может взять. Мы видим, что зайдя в туза пик, туза треф, короля и туза бубен, никто не сможет перебить его, то есть он уже берет минимум 4 взятки. Далее если он ходит в трефу, то выбивает оставшиеся козыри, а у него их еще два, то есть еще две взятки, итого минимальная оценка 6 взяток. Это сокращает интервал перебора более чем в два раза.
Случай, когда ходят вистующие, более сложен, так как там возможны передачи хода. Рассмотрим задачу 7 взяток.

7взяток
козырьПика
первый ходЗапад
играющийСевер
мизер
бридж студия
снос К Т 7 10 Д К Т 10 В 10 В
север
7 8
В
Д К
Д К
западвосток
9 В 10 Д
8 9 -
8 7 9 Т
7 9 8 Т

Сравнительные характеристики с другими программами

задача Моя pulya PrefGuru
Барбакару. 0.00 0.701 1.**
Мизер Ковалевской. 0.01 0.030 0.**
Мизер Ласкера. 0.03 0.191 0.**
Задача Галактинова. 0.04 0.681 1.**
Сложный расклад. 0.03 7.631 14.**

Таблица первых оптимальных ходов для задач

задача опт. ход число взяток
Барбакару. T 7/3
Мизер Ковалевской. T 2/8
Мизер Ласкера. T 2/8
Задача Галактинова. T 4/6
Сложный расклад. K 3/7
10 взяток. K 0/10
7 взяток. 9 0/7

Логическая часть решателя задач по бриджу

Оценка позиции

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

Хранение и поиск подходящих карт

Перебор дерева возможных ходов

Таблица перестановок (Transposition table)

В бридже в отличие от преферанса число вариантов существенно больше, соответственно и хеш-таблица бралась побольше. 2,000,000 элементов. Каждые элемент содержит 10 байт (8 на ключ хеш-таблицы, 1 на оценку узла, 1 на флаг (точное значение, отсечение сверху, снизу.)) На все про все уходит около 20 МБ оперативной памяти. Ключ хеш-таблицы содержит 52 бита на оставшиеся карты и 2 бита на то, кто в данный момент ходит.
В отличие от преферанса здесь используется улучшенная схема хеширования. В ячейке хеш-таблице может содержаться три значения: точное значение узла, альфа - если значение узла меньше либо равно альфа (false low), бета - если значение узла больше либо равно бета (false high). В бридже в случае точного значения узла возвращается значение из хеш-таблицы. В случае false low берется пересечение интервалов [-depth, hashAlpha] c интервалом (alpha,beta) и если пересечение пусто, то можно сразу вернуть оценку.

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

Таблица времени расчета

  1. название задачи
  2. число взяток
  3. лучший ход(ы)
  4. уровень сложности (взят с сайта)
  5. время расчета в секундах на 1.4 GHz, стартовая версия, все взято из преферанса
  6. улучшенный инверсный перебор по комплексной руке (только для функции g(...)), до этого был просто улучшенный инверсный перебор.
  7. время расчета на 31 октября 2002. Число узлов (в миллионах) 5 - 2650, 32 - 3835, 127 - 1788
  8. время расчета на Pentium3 1 GHZ на 31 октября 2002
  9. время расчета Pentium3 1 GHZ (первые ноябрьские ускорения)
  10. время расчета Pentium3 1 GHZ май 2003 время/число узлов (в миллионах)/процент заполнения хеш-таблицы (округлён до целых долей процента)
  11. время расчета Pentium3 1 GHZ 31 мая 2003 время/число узлов (в миллионах округлено до двух знаков после запятой)/процент заполнения хеш-таблицы (округлён до целых долей процента)
  12. расчёт для улучшенного хеширования
  13. расчёт для хеширования с двумя элементами при одном коде
  14. расчёт для хеширования с четырьмя элементами при одном коде
  15. время расчёта на 2 июня 2003
  16. исправлена ошибка, связанная с поиском подходящих карт
  17. transposition tables с восьмерным элементом
  18. enhanced transposition cuttoff's

коз 123456789*1011121314
БК 1 12/1 5 dr4 0.86 1.47 1.6 2.30 2.07 0.83 1.44 4% 0.53 0.96 2% 0.41 0.39
БК 2 11/2 K dr7 15.82 30.14 32.42 46.16 26.72 12.98 22.006 27% 6.86 12.87 14% 6.7 11.09 14% 5.32 4.41
БК 3 10/3 5 dr3 9.56 10.97 14.05 20.06 13.35 8.48 14.81 19% 1.18 2.31 4% 1.33 2.28 4% 0.99 0.82
4 12/1 A dr7 3.48 5.40 2.72 3.86 3.25 2.28 3.851 9% 1.59 2.84 6% 1.11 0.95
5 9/4 10 dr8 460.16 492.55 414.13 580.10 297.69 229.41 404.328 45% 32.65 61.09 26% 32.24 58.70 26% 25.70 23.00
32 11/2 6 dr8 438.92 520.42 733.87 343.94 227.91 450.865 76% 68.99 147.21 39% 70.74 143.67 39% 46.30 44.41
102 8/5 3 dr8 26.00 10.29 14.62 10.40 8.63 12.376 19% 1.30 2.09 3% 1.38 2.09 3% 1.02 0.73
127 11/2 K dr8 433.83 266.28 374.06 197.20 79.75 ?? ??% 17.02 29.72 27% 18.13 29.61 27% 13.58 12.37
Общее время 894.62 570.27 130.12 94.43 87.08

Примечание. Жёлтым цветом отмечены задачи, которые долго считаются.

Примечание. Звёздочкой отмечены колонки, когда вышли новые версии решателя.

Продолжение таблицы времени расчёта.

11415*161718192021*2223*242526*2728*
2 4.41 4.37 4.68 4.23 4.49 4.34 4.22 4.81 4.71 4.69 4.64 4.26 4.18 3.70 3.73
5 23.00 22.73 23.55 20.15 16.53 16.10 15.34 12.87 11.09 11.07 10.95 9.32 8.69 7.68 7.73
32 44.41 44.25 35.78 32.56 29.83 29.18 24.41 22.27 20.07 19.77 19.77 17.00 16.21 14.32 14.42
127 12.37 12.26 12.81 11.62 11.18 10.83 8.94 9.68 9.38 9.32 9.24 8.30 8.06 7.18 7.24
Общ вр 84.19 83.61 62.03 60.45 52.91 49.63 45.25 44.84 44.60 38.89 37.14 32.88 33.12

Продолжение таблицы времени расчёта.

128*2930*
5 7.73 7.75 7.60
32 14.42 13.97 13.78
127 7.24 7.38 7.25
159_1 6.59 6.76 6.57
192 6.91 6.94 6.76
211 40.68 26.71 26.17
159 204.67 63.74 62.12
Общ вр 288.24 133.25 130.25

Быстрые задачи

1234578
9 #1 13/0 7- 0.11 0.13 0.19
10 #2 9/4 A- 1.42 1.39 1.94
11 #3 13/0 A- 0.08 0.07 0.10
12 10cards8/23- 0.04 0.02 0.04

Версия 1.0-1.3

Разработка решателя началась 30 июня 2002 года. Разработка решателя задач по преферансу началась в ноябре 2001 года.

31 окт 2002

ноябрь

Версия 2.0

25 мая 2003

Общее ускорение составляет примерно 33% смотри результаты в колонке 10

Примечание. Ускорение "две быстрые взятки" даёт очень маленький прирост в скорости для большинства задач. Только для задачи 127 прирост около 20%.

31 мая 2003

Обнаружилась удивительная вещь. Если размер хеш-таблицы делать равным 2^n то число узлов при расчёте уменьшается, число отсечений сделанных с помощью хеш-таблицы увеличивается. Но! Время расчёта увеличивается в 3-4 раза!!! Это при старом варианте хеширования, теперь используем более новый. Результаты смотри в колонке 11. Ускорение в 4.38 раза.

Хеш-таблицы по новому. Рассмотрим позицию.

Север
К В
ЗападВосток
3 2  Т Д
Юг
5 4

Запад собирается прорезать север в пике. На его ход в 2, при ходе севером в валета восток кладёт даму, если север кладёт короля - восток ответит тузом. При этом получается две позиции.

Север
В
ЗападВосток
3  Д
Юг
4
Север
К
ЗападВосток
3  Т
Юг
4

Совершенно очевидно, что эти позиции совершенно одинаковы. Но при старом варианте хеширования эти позиции имели разные коды, так как каждой карте присваивался отдельный код. Теперь используется новый способ, который сопоставляет этим двум позициям одинаковый код. Как это делается. Сопоставим каждой масти четырёхбайтный код. Для получения кода по позиции будем использовать следующий алгоритм. Будем идти по масти сверху, то есть перебирать оставшиеся карты в масти в порядке туз, король, дама, ... В первой позиции остались карты Д В 4 3, во второй Т К 4 3. Присвоим двухбитный код каждому из игроков. Например северу 00, востоку 01, югу 10 и западу 11 (числа даны в двоичном виде). Рассмотрим первую позицию самая старшая из оставшихся карт дама она находится у востока. Тогда мы установим два младших бита в 01 (код востока), вторая по старшинству карта валет - она у севера, следовательно заполним третий и четвёртый биты нулями и так далее для всех карт в масти. После этого дополним код числом оставшихся карт. Очевидно, что получившееся при этом коды для первой и второй позиции совпадут. Не будем вдаваться в бОльшие подробности.

В связи с тем, что был использован новый вид хеширования была сделана очередная попытка, и на этот раз удачная, сделать число элементов таблица равным 2n. Переменная ZobristKey, а также многие другие, связанные с ней вещи были удалены из программы. Число элементов таблицы теперь равно 221. В качестве альтернативного варианта использовался размер таблицы 3*106. При этом, если используется размер таблицы равный 221 то число узлов немного увеличивается, в связи с тем, что число элементов в таблице меньше чем 3*106. Но теперь для определения индекса в таблице вместо Table[Key%TableSize] используется строка Table[Key & 0x1FFFFF], а это быстрее. На общее время увеличение числа узлов не оказывает влияния.

Обнаруженные выше ошибки, связанные с тем, что если загрузить задачу 5 после задач 2 или 3 исчезли. Возможно ошибка была связана с хешированием.

1 июня 2003

Хеширование с двойным элементом - смотри результаты в колонке 13, хеширование с четверным элементом - смотри результаты в колонке 14. Общее ускорение 33%

Хеширование с двойным и четверным элементом. Подсчёт числа коллизий для улучшенного хеширования показал, что их чрезвычайно много, хотя это и неудивительно. Из-за этого было сделано двухуровневое хеширование. Поясним вкратце его суть. Код, идентифицирующий позиции содержит максимум 32*4+2=130 бит (по 32 бита на каждую масть+ 2 бита на то, чей сейчас ход). Естественно, что две позиции с разными кодами могут попасть в одну и ту же ячейку таблицы. Для получения индекса таблицы была использована следующая формула HashTable[(code[0]+code[1]+code[2]+code[3]+who) & 0xFFFFF]. Ранее таблица содержала по одному элементу на каждый индекс. Идея состоит в том, чтобы на каждый индекс таблицы приходился не один элемент, а несколько. В таблице выше в колонке 13 указано время расчёта для двух элементов при одном индексе, а в колонке 14 указано время расчёта для четырёх элементов при одном индексе. Естественно, что при этом надо поменять заполнение и чтение хеш-таблицы.

Каждый элемент таблицы теперь содержит по 4 элемента. Каждый элемент, состоит из четырёх кодов (по одному на каждую масть) по 4 байта каждый + 1 байт на флаг (hashALPA или hashBETA) + 1 байт на hashValue Итого общий размер для одной ячейки таблицы (каждая из которых включает в себя по 4 элемента) равен 72 байтам. На данный момент хеш-таблица содержит 219 элементов. Итого размер таблицы равен 36Мб. Опытом проверено, что размер хеш-таблицы слабо влияет на скорость программы, поэтому все опции выбора размера были изъяты.

Неудачная попытка второго обобщения хеширования. Показанный выше пример "нового" хеширования можно обобщить ещё дальше. Рассмотрим две позиции (игра без козыря)

Север
В
ЗападВосток
3  Д
Юг
4
Север
В
ЗападВосток
3  Д
Юг
4

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

2 июня 2003

Исправлены небольшие недочёты при хешировании. Смотри колонку 15.

Версия 2.1

7 июня 2003

Была исправлена ошибка - некоторые задачи считались неправильно. см. колонку 16

Каждая ячейка хеш-таблицы имеет 8 элементов, число самих элементов уменьшилось вдвое, размер хеш-таблицы остался тем же. см. колонку 17

Был применён метод enhanced transposition cuttoff's см. колонку 18

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

14 июня 2003 утро см колонку 19 (ускорение 2.5%)

был исправлен недочёт, связанный с поиском подходящих карт (раньше не отбрасывались некоторые секвенсы)

удалены вспомогательные функции поиска подходящих карт. Теперь осталась только одна функция, которая всё и делает

косметическое ускорение при переборе подходящих карт см колонку 20 (ускорение 13%)

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

sure tricks

супер списки

addcut

попытка вынести ListItem из класса

15 июня 2003 ускорение 6.2% см колонку 21

при заходной карте, сначала со старших в масти, а потом в обычном порядке.

попытка заходить сначала со старших в масти, потом с младших замедляет.

Версия 2.2 1 июля 2003

16 июня 2003 ускорение 10% см колонку 22

индекс в хеш-таблице code[0]+...+code[3]+(who << 15)

17 июня 2003 ускорение 1% см колонку 23

изменено формирование кода code[0] code[1] code[2] code[3], раньше в конце кода дописывалось число карт, теперь 13-число карт это изменение повышает заполнения хеша примерно на 1%.

Версия 2.3 18 июля 2003

5 июля 2003 ускорение 0.5% колонка 24

запись в хеш, начиная с нижнего индекса

7 июля 2003

8 июля 2003 (общее время 43.14)

9 июля 2003 колонка 25 (общее время 38.89)

15 июля 2003 колонка 26 (общее время 37.14 ускорение 4.5%)

Версия 2.4 3 сентября

21-22 июля 2003 колонка 27 ускорение 12%

1-2 сентября 2003 колонка 28

Версия 2.5

17-18 октября 2003 колонка 29

19-23 октября 2003 колонка 30 ускорение 2.2%

Версия 2.6 опубликовано 7 февраля 2005

28 сентября 2004

1 октября 2004

3 октября 2004

Версия 2.10 опубликовано 14 марта 2007

Версия 2.11 30 марта 2007 Sure Tricks

В конце-концов оказалось, что ускорение для бескозырных задач составило около 38%, что достаточно много. Для задач с козырями при попытках применения sureTricks, суммарное время расчёта для tr задач только увеличилось, даже несмотря на то, что отсечения вызвали сильное уменьшение числа узлов для некоторых задач.

Пока считаем, что игра без козыря

Производим оценку каждой масти.

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

    Для каждой масти будем учитывать у кого окажется ход после розыгрыша всех взяток в масти. Он может оказаться либо у заходящего в первой взятке b0, либо у его партнёра b2.

    Обозначим взятки по пункту 1 sure

  2. После отбора всех взяток пункта 1, могут возникнуть дополнительные взятки, когда у партнера уже нет карт в этой масти, но при этом один из игроков имеет старшие карты в масти. Если бы у партнёра ещё бы были карты, тогда такая взятка отнеслась бы к пункту 1. Эти дополнительные взятки считаются по заходящему в первой взятке и партнёру. Обозначим их sure0 и sure2. Эти взятки считаются даже если ход партнёру в данной масти не может быть передан, но они могут учитываться поскольку ход партнёру может передаться через другие масти.

При подсчёте взяток по всем мастям будем пользоваться следующим алгоритмом

Общая оценка ST

  1. SURE=сумма взяток из пункта 1 по четырём мастям
  2. Введём понятие общего бита передачи хода он равен 1 если хотя бы по одной из мастей есть бит передачи, иначе он равен 0. Таких общих бита передачи будет 2 По аналогии обозначим их B0,B2 B0=b0_1|b0_2|b0_3|b0_4 B2=b2_1|b2_2|b2_3|b2_4

Обозначим SURE0 = sure0_1 + sure0_2 + sure0_3 + sure0_4 (сумма взяток по пункту 2 заходящего в первой взятке игрока)

Обозначим SURE2 = sure2_1 + sure2_2 + sure2_3 + sure2_4 (сумма взяток по пункту 2 партнёра заходящего в первой взятке игрока)

  1. B0=B2=0 нет ни одной передачи, это означает, что по пункту 1 нет ни одной взятки. Тогда ST=SURE+SURE0 розыгрыш такой: отбираем все взятки по пункту 2
  2. B0=1,B2=0 ST=SURE+SURE0 розыгрыш такой: нужно отобрать все SURE после этого ход будет у заходящего, затем SURE0

    пункты 1) и 2) можно объединить, получим что при B2=0 ST=SURE+SURE0

  3. B0=0,B2=1 ST=SURE+SURE2+SURE0-сумма_i [sure0_i,i-масть передачи хода к партнёру] розыгрыш: отбираем все взятки заходящего из пункта 2, кроме взяток в мастях передачи партнеру. После этого разыгрываем все взятки из пункта 1. Затем отбираем все взятки партнёра по пункту 2
  4. B0=B2=1 ST=SURE+SURE0+SURE2-min_ij(sure0_i i-масть передачи к партнёру; sure2_j j-масть передачи к заходящему) розыгрыш: отбираем все взятки из пункта 1, кроме i-ой где есть передача партнёру. число взяток SURE-1 после этого отберём все взятки из п2 заходящего игрока. их будет SURE0-sure0_i после этого передаём ход партнёру и отбираем все его взятки из пункта 2. число взяток 1+SURE2 Таким образом получаем ST=SURE+SURE0+SURE2-sure0_i, поскольку i - можно варьировать получаем, что ST=SURE+SURE0+SURE2-min(sure0_i i-масть передачи к партнёру) Делая аналогичный розыгрыш, оставляя одну масть передачи от партнёра к игроку, получаем, что ST=SURE+SURE0+SURE2-min(sure2_j j-масть передачи к партнёру) Выбрав из этих двух розыгрышей лучший получаем нужную формулу.

Оценим количество памяти требуемое для сохранения таблицы всех последовательностей длины ровно n карт. всего таких последовательностей 4^n=2^(2n) Одна ячейка памяти хранит 2 бита передачи + число взяток пункта 1,2 + число взяток пункта 2. Однозначно, что в 8 бит эта информация не укладывается, поэтому укладываем её в 2 байта 2 бита передачи + 4 бита (число взяток пункта 1) 2*[4 бита (число взяток пункта 2) ] 4бита на взятки, хватит для всех 0<n<=13 Таким образом общее число памяти для последовательности карт длины n (ровно) требуется 2^(2n+1) байт Общее число память для последовательностей длины не более n требуется 2^(2n+1)+2^(2n-1)+..+2^(2+1)=2^3+2^5+...+2^(2n+1)=8*(4^n-1)/3 ~ 2^(2n+3)/3 (байт)=2^(2n+3-20)/3 Мбайт

n= 9 0.66 мб

n=10 2.66 мб

n=11 10.66 мб

коды были посчитаны для первого хода who=0 если who имеет другое значение, то код последовательности следует преобразовать по правилу len2 - удвоенное число карт в масти обозначим j = 0x1555555>>(26-len2);

  1. who=2 заменяем биты 00<->10 01<->11 code ^= (0x2aaaaaa>>(26-len2)); Последовательность битов b1 b2 переходит в последовательность b1^1 b2
  2. who=3 заменяем биты кода по правилу 11->00->01->10->11 code ^= j^ ( (code&j)<<1 ); Последовательность битов b1 b2 переходит в последовательность b1^b2 b2^1
  3. who=1 заменяем биты кода по правилу 11->10->01->00->11 Последовательность битов b1 b2 переходит в последовательность b1^b2^1 b2^1 code ^= ( 0x3ffffff>>(26-len2) ) ^ ( (code&j)<<1 );

Для козырной игры.

Будем также считать два бита передачи и три оценки точных взяток (sure sure0 sure2). Но будем это делать при различных вариантах существования козырей у всех четырёх игроков, это будет создавать 15 вариантов, вариант когда ни у кого нет козырей уже рассмотрен в бескозырной игре. Требуемая память в этом случае составит

n= 8	2^(2*8+3-20)*5 = 2.5 Mб
n= 9	0.66*15        =  10 Мб
n=10  2.66*15        =  40 Мб

Можно составить одну таблицу для козырной и бескозырной игры. По козырной масти(если она есть) определяются биты существования козырей у всех игроков и получается общий индекс i=0..15. При i=0 козырей ни у кого нет. Если игра без козыря, считаем i=0. Это всё будет предварительно рассчитываться в начале программы. Из-за ограниченности оперативной памяти будем для козырной игры считать n<=9

От всех этих ускорений (для козырных игр) работает медленнее. Даже если использовать отсечения когда нет козырей. Есть ещё версия, что программа будет работать быстрее если использовать сначала тактику выбивания козырей, а потом применять отсечения как для бескозырной игры, но поскольку, как мне кажется, при этом всё равно расчёт замедлится, то я даже не стал пробовать этот вариант.

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