Логическая часть решателя версия 5.1 |
Cодержание
| Основные нововведения | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Опция очистки хеш-таблицы | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Введение специальных функций | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Увеличение хеша и изменение функции вычисления индекса | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Неудачная попытка отсечения нижних слоев | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Сравнение скоростей программ на javascript и c++ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Таблица сравнения времен расчета
Теперь хеш-код организован следующим образом. Есть четыре кода, по одному на каждую масть. Программа идет от самой старшей карты в масти к младшей, все ушедшие карты игнорируются. Если находится карта принадлежащая одному из игроков, то она добавляется к хеш-коду. Преферансный игрок имеет двухбитовый код 00 (в нашем случае это юг), следующий за ним код 01 (запад), через одного игрока за ним имеет код 10 (восток). В самом конце, для того чтобы указать конец, указывается код 11. Самая старшая карта в обеих позициях принадлежит западу (код 01), вторая по старшинству востоку (код 10) и последняя югу (код 00). Таким образом в обеих позициях мы получим двоичный код пиковой масти 11001001, для остальных мастей код будет 11. Коды мастей считаются только один раз при загрузке позиции и затем для них выполняются операции удалить и вставить обратно карту, когда идет перебор всех ходов. В старой версии для учета ходов велась работа с двусвязными списками и параллельно обнулялся/восстанавливался соответствующий бит в хеш-коде. Теперь списков нет - есть только коды мастей. В новой версии хеширование организовано таким образом, что игрок всегда имеет код 00 (неважно кто это юг, север, запад или восток), таким образом можно не очищать хеш если меняется только игрок, а козырь остается прежним. Все это дает ускорение примерно 1.6-1.9 раза или 37-47% по сравнению со старой версией. При работе с программой нужны следующие опции:
Старая версия уже работала достаточно быстро для всех опций, кроме последней, поэтому имеет смысл ускорять только опцию решить все расклады противников. Начиная с версии 5.1 для опции решить для всех игроков и козырей первый ход может быть любым, получается, что нужно сделать оценку 54=18*3 раскладов, что быстро даже для старой версии. Причем 36 из 54 раскладов нужно посчитать без очистки хеша, что намного быстрее (смотрите ниже). Опция очистки хеш-таблицыВ новой версии как и у бриджевого решателя появилась новая опция - очищать или нет хеш таблицу. Как говорилось выше хеш обязательно очищать только при смене козыря. Так как для опции решить все расклады противников козырь один для всех раскладов, то очищать хеш нужно только один раз - для первого расклада, а затем использовать хеш-таблицу для всех остальных раскладов. Это дает огромный прирост в скорости. Ниже приведена таблица времен расчетов для старой и новой версий. Старая версия решателя написана таким образом, что опция не очищать хеш была невозможна, поэтому невозможно сравнивать скорости расчетов старой и новой версий без очистки хеша. Даны результаты для трех тестовых задач, бралось время расчета первых 20 000 раскладов противников, расчеты были выполнены на одном ядре, время дано в секундах. Видно, что новая версия намного быстрее старой даже без очистки хеша, а с очисткой хеша скорость еще больше.
Колонка новая версия без очистки хеша выведена в таблице сравнений в колонку новая 1. Были какие-то изменения в коде поэтому времена не совпадают. Введение специальных функцийПервоначально в классе Preferans были одни и те же функции для мизерных и немизерных игр. Также функции поиска имели опцию, по которой нужно или не нужно сохранять лучший ход. Но лучший ход требуется сохранять только в самой верхней функции поиска, а если, например, мы просто оцениваем расклады, то нам вообще не нужен лучший ход. Также лучший ход вообще не нужен если оцениваются все расклады противников. Поэтому были сделаны четыре типа функций:
Увеличение хеша и изменение функции вычисления индексаНесмотря на то, что код масти code[i] может иметь максимум 18 бит (по два бита на каждую карту, всего 8 карт и два замыкающих бита 11), достаточно сравнивать только младшие 16 бит. Докажем это. Нужно доказать, что если равны младшие 16 бит кодов мастей, то коды равны. Рассмотрим три случая.
Изменение функции вычисления индекса и размера хеш-таблицы должно идти одновременно, так как нужно знать число бит в ключе хеш-таблицы, чтобы задать эффективную формулу вычисления индекса. Увеличение размера хеша до 64mb и изменение расчета индекса хеша дало значительный прирост для всех задач. Колонка в таблице сравнений называется новая 3. Неудачная попытка отсечения нижних слоевИдея состоит в том, чтобы не хешировать позиции, когда карт на руках остается меньше определенного числа. Такие позиции считаются быстро и при этом забивают хеш. Таким образом если не хешировать их, то можно освободить элементы хеш-таблицы с бо́льшим числом карт, которые считаются дольше. Все попытки такого рода оптимизаций приводят к замедлению программы, поэтому не используются.Сравнение скоростей программ на javascript и c++Первоначально новая версия решателя появилась на языке javascript с целью узнать можно ли написать online преферансный решатель, который будет находить лучший ход и оценивать другие ходы за разумное время. Также попутно была поставлена цель сравнить скорости расчетов одинаковых программ на языках js и c++. Потом код был переписан с js на c++ и, так как он быстрее, внедрен в программу, заменив старую версию, но в процессе внедрения он был сильно изменен и для чистоты эксперимента опять переписан уже с c++ на js. Для этого создана вспомогательная программа на языке php, которая делает замены в исходном коде cpp файла, так, чтобы получить файл js. Язык php использовался, потому что программа на c++ работающая с std::regex очень долго компилируется. Поэтому было принято решение использовать php где вообще нет компиляции. Программа на php не делает работоспособный js код, но позволяет сильно упростить процесс переписывания. Затем js код был доделан вручную.Примечание. Программа php не работает с перегружаемыми функциями членами класса, которые появились в c++ уже после переписывания с c++ на js, поэтому в данный момент php программа не сможет переделать текущий c++ код на js. Отличия c++ и js программ.
Таблица сравнения времен расчетаЗадачи, на которых проводились испытания, находятся в файле в папке problems, файл называется solveallfoe.pts. Время указано в секундах, перебирались первые 20 000 позиций, задачи решались в однозадачном режиме. Общее время расчета в многозадачном режиме всей задачи будет примерно равно 184 756/20 000*t/N=9.2378*t/N, где t - время расчета 20 000 позиций, N - число ядер. Последняя колонка показывает время расчета задач на мобильном телефоне, брались только первые три задачи, так как четвертая считается слишком долго. Время расчета на мобильном телефоне на разных браузерах chrome, opera и нативного браузера примерно совпадают. Общее замедление на мобильном, по сравнению с браузером опера, составляет (22.26+13.94+9.39)/(9.61+5.98 +5.38)=2.17 раза.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
-
-
-