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

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

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

Версии 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 В

	север
	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

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

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

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

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

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

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

альфа-бета отсечения (основа-основ)
непрерывные последовательности карт пусть на руке имеются карты 8 , 9 , 10 . Понятно что ход с любой из этих карт дает одну и ту же позицию. Поэтому достаточно рассмотреть ход любой из этих карт. Аналогичная ситуация возникает когда на руке имеются 4 и 7, а 5 и 6 уже в сносе.
отсечения нижних слоев рассмотрим случай, когда у каждого игрока осталось по одной карте, тогда никакой рекурсии вызывать не надо, а просто сразу подсчитать оценку. Это отбрасывает три нижних слоя дерева.
усечение интервала альфа-бета (возможно это является новшеством, по крайней мере в интернете я такого не видел) идея чрезвычайно проста. Пусть у каждого из игроков осталось по k карт, понятно, что в этом случае оценка узла лежит в отрезке [ -k , k ], интервал (alpha , beta) возможно не полностью лежит в отрезке [ -k , k ]. То есть нас интересует только пересечение в частности если оно пусто ( alpha>=k или beta<= -k ) то оценку можно сразу вернуть, иначе усечение интервала.

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

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

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

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

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

коз	1	2	3	4	5	6	7	8	9*	10	11	12	13	14
БК	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

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

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

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

1	14	15*	16	17	18	19	20	21*	22	23*	24	25	26*	27	28*
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

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

1	28*	29	30*
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

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

№	1	2	3	4	5	7	8
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	10cards	8/2	3	-	0.04	0.02	0.04

Версия 1.0-1.3

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

31 окт 2002

Косметические ускорения по хешированию. Структура ListItem содержит теперь хеш-индекс карты.
Упрощена рекурсия. Теперь она вызывается на глубину равную числу карт у одного из игроков. То есть число рекурсивных вызовов уменьшено примерно в 4 раза. Удалены функции g1,g2,g2 (В проекте переписывание процедуры альфа-бета без рекурсии)
Изменены функции g,fg, теперь перебор ведется последовательно, то есть не улучшенный инверсный перебор, а просто инверсный перебор, смотри преферанс.

ноябрь

Размер хеш-таблицы увеличен до 60*10⁶ элементов.
Техническое ускорение, по поводу генерации вглубь ускорение ~3%
Техническое ускорение, для сравнения ходов, кто берет взятку берется таблица bool CompareTable[781][781] и просчитывается, ускорение примерно 4%, сравнение осуществляется по параметру suitcard которое является объединением параметров suit, card
СМ результаты в колонке №9 Обнаружена ошибка если после задачи 4 (или 3) и рассчитать ее, загрузить задачу 5 - она будет неверно считаться. Эта же ошибка есть в версии от 1 ноября
Попытки ввести число элементов таблицы кратным 2^n независимо от числа элементов в таблице. Аналогично попытки изменить строку ZobristKey%TableSize на ZobristKey & 0xFFFF замедляют
Замедляют попытки применения Enhanced Trasposition cutoffs. Несмотря на то, что число узлов сокращается примерно на 18-20%
Попытки применения Dual, (восходящий/нисходящий поиск с нулевым окном) подтормаживают

Версия 2.0

25 мая 2003

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

Поиск с нулевым окном NegaScout. При поиске подходящего хода мы ищем не с полным интервалом [min,max], а используем поиск с нулевым окном для начала ищем на отрезке [(min+max)/2,(min+max)/2+2], потом в зависимости от результата делим оставшееся окно пополам. В связи с этим упростился код программы (сейчас функции g надо передавать лишь один параметр) отсечения по хеш-таблице тоже стали проще. Точной оценки узла уже нет и так далее. Общее ускорение от этого метода составило около 4-5%
Быстрая взятка. Рассмотрим пример. Пусть у каждого осталось по 5 карт, тогда оценка позиции может быть -5 -3 -1 +1 +3 +5 Пусть нам задан поиск в интервале [-5,-3], ясно, что если сторона, которая должна ходить возьмёт хотя бы одну взятку, то можно сразу вернуть оценку -3. Поэтому мы делаем быструю проверку на взятку.
Второй пример. У каждого осталось по 5 карт, и задан поиск в интервале [3,5] тогда ясно, что если мы не берём все взятки, то можно сразу вернуть оценку позиции 3. Здесь была лишь только сделана проверка, что у противника есть самый старший козырь, тогда ясно, что всех взяток нам не взять. (Более сложная проверка, что противник перебивает наш ход в любой масти сделан не был.) Прирост в скорости около 30%
Две быстрые взятки. Аналогичная проверка, что противник в любом случае берёт минимум две взятки. Это бывает в тех случаях, когда у одного из них два старших козыря или старшие козыри находятся у противников на разных руках и у одного из них козырь с прикрытием.

Примечание. Ускорение "две быстрые взятки" даёт очень маленький прирост в скорости для большинства задач. Только для задачи 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 (код востока), вторая по старшинству карта валет - она у севера, следовательно заполним третий и четвёртый биты нулями и так далее для всех карт в масти. После этого дополним код числом оставшихся карт. Очевидно, что получившееся при этом коды для первой и второй позиции совпадут. Не будем вдаваться в бо́льшие подробности.

В связи с тем, что был использован новый вид хеширования была сделана очередная попытка, и на этот раз удачная, сделать число элементов таблица равным 2ⁿ. Переменная ZobristKey, а также многие другие, связанные с ней вещи были удалены из программы. Число элементов таблицы теперь равно 2²¹. В качестве альтернативного варианта использовался размер таблицы 3*10⁶. При этом, если используется размер таблицы равный 2²¹ то число узлов немного увеличивается, в связи с тем, что число элементов в таблице меньше чем 3*10⁶. Но теперь для определения индекса в таблице вместо 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 байтам. На данный момент хеш-таблица содержит 2¹⁹ элементов. Итого размер таблицы равен 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

сдвиг на 16 разрядов вместо 15. На большее число сдвигать нельзя.
при хешировании замена в KeyZob [who] -> [who-1]
один из кодов масти стал наполовину входить в ключ хеш-таблицы. В связи с этим размер хеш уменьшился до 32 мб
попытка хеширования после первого хода, то есть при ходе второй руки замедляет
попытка заполнять code длиной в младших битах замедляет
попытка не считать коды а брать их у предков не замедляет и не ускоряет

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

code[3] переделан через union
в KeyZob входит только нижняя часть code[3]
члены класса who,who1,who2,who3 так что они принимают значения 0,1,2,3 раньше было 1,2,3,4
попытка объединить value и flag в ячейке хеш-таблицы подтормаживает, но не сильно

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

изменено формировании индекса в хеш-таблице теперь он вычисляется по формуле
hashIndex=(code[0]+code[1]+code[2])^_lowcode^(who<<16)
где code[i]-код масти, _lowcode - нижняя часть от code[3], who - первый ход во взятке

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

изменено формирование индекса в хеш-таблице теперь он вычисляется по формуле
hashIndex=(code[0]*code[1]+code[2])^_lowcode^(who<<16)
это повышает заполнение хеш-таблицы на 2-4%

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

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

формирующиеся коды code[0..2],_code записываются в массив и при надобности берутся оттуда

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

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

Версия 2.5

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

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

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

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

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

28 сентября 2004

таблица сравнения сделана одномерным массивом ускорение 0.5%
_who_ заполняется через массив ускорение 0.5%

1 октября 2004

suretricks для бескозырных раскладов и когда уже нет козырей ускорение 20.7% (в основном из-за последней задачи)

3 октября 2004

изменение формирования кода ускорение 0.25% теперь код формируется по формуле ((code[0]*(code[1]+1)+code[2])^_lowcode)

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

размер хеш-таблицы увеличен до 68 мб (ускорение 25%). Задачи без первого хода считаются намного быстрее, по остальным ускорение 6-10%. Дальнейшее увеличение параметров уже не даёт сильного эффекта для медленных задач.

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

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

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

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

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

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

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

SURE=сумма взяток из пункта 1 по четырём мастям
Введём понятие общего бита передачи хода он равен 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 партнёра заходящего в первой взятке игрока)

B0=B2=0 нет ни одной передачи, это означает, что по пункту 1 нет ни одной взятки. Тогда ST=SURE+SURE0 розыгрыш такой: отбираем все взятки по пункту 2
B0=1,B2=0 ST=SURE+SURE0 розыгрыш такой: нужно отобрать все SURE после этого ход будет у заходящего, затем SURE0
пункты 1) и 2) можно объединить, получим что при B2=0 ST=SURE+SURE0
B0=0,B2=1 ST=SURE+SURE2+SURE0-сумма_i [sure0_i,i-масть передачи хода к партнёру] розыгрыш: отбираем все взятки заходящего из пункта 2, кроме взяток в мастях передачи партнеру. После этого разыгрываем все взятки из пункта 1. Затем отбираем все взятки партнёра по пункту 2
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);

who=2 заменяем биты 00<->10 01<->11 code ^= (0x2aaaaaa>>(26-len2)); Последовательность битов b1 b2 переходит в последовательность b1^1 b2
who=3 заменяем биты кода по правилу 11->00->01->10->11 code ^= j^ ( (code&j)<<1 ); Последовательность битов b1 b2 переходит в последовательность b1^b2 b2^1
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 Мб
n= 9	0.66*15        =  10 Мб
n=10  2.66*15        =  40 Мб

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

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

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