X&O : сохранение вычисленных данных
Для сохранения вычисленных рейтингов узлов, добавим класс Persister. Каждый отбракованный узел (т.е., распознанный как culled_N_X) теперь сохраняется в файле xo.dat, в той же папке, откуда была запущена программа. Поскольку хэш коды узлов опираются на карту простых чисел, последняя тоже сохраняется в файл primes.txt, так чтобы при последующем запуске программы она не генерировалась заново, а считывалась бы из файла, как и список отбракованных узлов.
Итак, при старте программы, загружаем узлы с рейтингами из файла xo.dat в таблицу. Узлы, созданные таким способом, получают флаг fixedRating = true. Это позволит сэкономить большое количество вычислительного времени при повторных запусках, ведь уже не нужно будет вычислять поддеревья для известных забракованных узлов.
Изменения в метриках
- Для Cull_N_R метрик:
- Понизим минимальный порог для N с 9 тысяч до 6066. (Впоследствии, для работы с массивом атак, порог был повышен до 8 тысяч).
- Уменьшим рабочие значения R.
- Введём новые метрики missExpand, missNode и missAge
Новшества помогут нам быстрее производить отбраковку и следить за наличием ошибок (несостыковок) в ходе исполнения вычислений. Соответствующий коммит находится тут. Дополнительно, добавим метрики вида missXCount, для отслеживания ситуаций, когда ожидалось что на игровом поле уже существует ряд из X последовательных камней (для текущего игрока или его оппонента), но возможность продолжить эту комбинацию не была найдена.
| FRD-R_5 + EXP | FRD-R_5 + AXE | FRD-R_5 + EXP + BF1 | ATTACKS | PAIRED ATTACKS | PAIRED ATT. + BF1 | P.ATT. + BF2 | |
| Cull_7k_6k / Cull_7k_13k | 45 / 32 | 135 / 73 | 28 / 6 | 149 / 124 | 222 / 207 | 132 / 170 | 257 / 105 |
| Cull_14k_6k / Cull_14k_13k | 27 / 10 | 28 / 4 | 12 / 4 | 41 / 14 | 80 / 30 | 56 / 36 | 117 / 39 |
| Cull_28k_6k / Cull_28k_13k | 13 / 4 | 5 / 0 | 10 / 1 | 9 / 6 | 22 / 9 | 28 / 13 | 59 / 21 |
| Cull_60k_6k / Cull_60k_13k | 3 / 0 | 6 / 0 | 1 / 0 | 1 / 1 | 10 / 8 | 9 / 2 | 18 / 6 |
| Cull_120k_6k / Cull_120k_13k | 1 / 0 | 4 / 0 | 0 / 0 | 1 / 0 | 2 / 0 | 4 / 1 | 20 / 6 |
| missExpand | 4824 | 15613 | 5049 | 96727 | 47553 | 20291 | 17256 |
| missCount | 0,0, 65, 18,0 | 0,0, 316, 43, 35332 | 0,0, 21, 1,0 | 439,356, 2230, 1975, 13832 | 28824,7840, 33511, 8591, 134392 | 37784,9293, 61940, 14777, 157109 | 19932, 10181, 16453, 5296, 99889 |
| missNode | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| missAge | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Update frequency | 6.59% | 3% | 10.7% | 16.4% | 7.6% | 14.6% | 6% |
| Max childs updated | 29,42M | 29,48M | 29.94M | 29.88M | 29,95M | 29.96M | 23,4M |
| Update count | 1653 | 9054 | 2549 | 7141 | 2086 | 3267 | 1090 |
| Skip count | 23415 | 292358 | 21241 | 36430 | 25385 | 19117 | 16976 |
| Avg Diff | 1 | 0 | 0 | 0 | 1 | 0 | 5 |
| Avg Abs Diff | 197 | 245 | 239 | 326 | 246 | 256 | 198 |
| max path length | 21 | 29 | 20 | 23 | 21 | 21 | 18 |
| Rating | 2961 | 1310 | 2394 | 1616 | 2445 | 1628 | 6077 |
Комментарии к полученным результатам
- FRD-R_5 + EXP
- Это фильтрация относительно счётчиков троек и четвёрок (своих и оппонента). Т.е. например, если у текущего игрока есть четвёрка, то отфильтруются все ходы кроме тех, где можно поставить 5. Если нет, то проверяем далее остальные счётчики в порядке приоритетности, выставляя соответствующие условия на фильтрацию.
- Как видим, фильтрация показала себя с хорошей стороны, значительно снизив Cull_ХХ метрики, хотя сам процесс занимает заметно существенное время. Иногда также удаётся достичь увеличения max path length.
- Код для фильтрации изначально был представлен этим коммитом.
- FRD-R_5 + AXE
- Здесь счётчики двоек также используются для фильтрации. Поэтому показатели тут ещё лучше, хотя и скорость вычисления заметно меньше.
- FRD-R_5 + EXP + BF1
- Здесь был исправлен некий баг.
- ATTACKS
- В структуру узла (игровой позиции) TNode введён массив атак. Изначально это был массив атакующих ходов для каждого из игроков.
- Нужен, чтобы экономить время, не перевычисляя атаки каждый раз при помощи отфильтровывания.
- Фильтрация по newChilds для метода Expander::expand (и Builder::build) была отключена, поскольку вместо неё стали применятся вектора атак, так что рост дерева происходит в их направлении.
- PAIRED ATTACKS
- Атаки теперь хранятся в виде пары ходов, задавая диапазон, внутри которого также могут быть ходы атак.
class TAttack { TMove l,r; };
- Атаки теперь хранятся в виде пары ходов, задавая диапазон, внутри которого также могут быть ходы атак.
- ATTACKS FILTERED
- Фильтрация снова включена. Теперь она находится в функции bool Expander::isExpected
- Таким образом, чтобы определить какие новые дочерние элементы нарастить на определённый узел дерева (TNode), отфильтровываем ходы только из заранее подготовленного набора атак, а не из всего набора пустых клеток расположенных рядом с уже сделанными ходами (а это быстрее).
- Включение фильтрации заметно улучшает метрики Cull- и max path length. А также заметно улучшает качество игры (при тестировании в ручную).
- A.FILTERED BF2
- Багфиксы, как видно, улучшают Cull- показатели, а также делают рейтинг первого хода более адекватным, обычно он должен быть около 2500-4000.
- A.FILTERED SO
- Skip Overflown attacks. Эксперементальный режим, в котором массив атак игнорируется (методами Expander-a) если он заполнен полностью (т.е. возможно что часть атак была потеряна из-за переполнения).
- A.FILTERED SO-8
- То же самое, но макс. размер массива атак теперь увеличен до 8 (со старого значения 7).
| P.ATT. + BF3 | ATTACKS FILTERED | A.FILTERED BF2 | A.FILTERED BF3 | A.FILTERED SO | A.FILTERED SO-8 | A.Filtered SO-9 | |
| Cull_7k_8k / Cull_7k_13k | 222 / 124 | 171 / 56 | 41 / 32 | 44 / 30 | 71 / 32 | 59 / 30 | 43 / 12 |
| Cull_14k_8k / Cull_14k_13k | 91 / 54 | 78 / 13 | 18 / 12 | 10 / 3 | 26 / 9 | 18 / 10 | 20 / 7 |
| Cull_28k_8k / Cull_28k_13k | 45 / 18 | 32 / 4 | 8 / 5 | 8 / 1 | 16 / 9 | 7 / 3 | 10 / 6 |
| Cull_60k_8k / Cull_60k_13k | 15 / 8 | 7 / 0 | 3 / 0 | 3 / 0 | 6 / 2 | 2 / 2 | 4 / 2 |
| Cull_120k_8k / Cull_120k_13k | 9 / 4 | 7 / 0 | 3 / 0 | 3 / 0 | 0 / 1 | 2 / 0 | 1 / 0 |
| missExpand | 16685 | 6113 | 5574 | 5012 | 6995 | 6915 | |
| missCount | 1272, 908, 2481, 1350, 87795 | 584, 112, 115, 61, 485599 | 4575, 50, 730, 269, 89515 | 4847, 201, 893, 323, 84334 | 0, 184, 124, 1352, 76625 | 0, 146, 76, 414, 83278 | 15, 198, 56, 170, 80829 |
| missNode | 0 | 0 | 0 | 0 | |||
| missAge | 0 | 0 | 0 | 0 | |||
| Update frequency | 8% | 1.98% | 8.5% | 4.8% | 5.6% | 7.6% | 5.9% |
| Max childs updated | 26.4M | 19.8M | 29.9M | 29.3M | 29.3M | 29.9M | 28.8 |
| Update count | 2065 | 1299 | 3167 | ||||
| Skip count | 23349 | 64264 | 33945 | ||||
| Avg Diff | 2 | 4 | 1 | 1 | 1 | 1 | 1 |
| Avg Abs Diff | 218 | 217 | 209 | 214 | 213 | 223 | 204 |
| max path length | 17 | 31 | 27 | 28 | 25 | 24 | 23 |
| Rating | 6021 | 6021 | 3642 | 2774 | 4436 | 3516 | 3203 |
- NOATTACKS - Это режим с отключённым массивом атак. Поэтому ожидалось что результаты будут такие же, как и для FRD-R_5 + EXP + BF1. Однако тут присутствует дополнительный багфикс, зануляющий счётчики missXCount
- NEURO - включает некоторые оптимизации, например функцию multiExpand. В этом запуске параметр N был взят равным 8000, в отличии от запуска для NOATTACKS где он был 6066. P.S. Называется Neuro потому что замер делался уже после добавления нейросети в код, но в данном запуске код нейросети не активен.
| NOATTACKS | NEURO | |
| Cull_7k_6k / Cull_7k_13k | 151 / 115 | 44 / 55 |
| Cull_14k_6k / Cull_14k_13k | 36 / 8 | 13 / 11 |
| Cull_28k_6k / Cull_28k_13k | 4 / 1 | 5 / 3 |
| Cull_60k_6k / Cull_60k_13k | 5 / 0 | 2 / 1 |
| Cull_120k_6k / Cull_120k_13k | 1 / 0 | 4 / 0 |
| missExpand | 21392 | 10716 |
| missCount | 0,0,0,0,0 | 0,0,0,0,0 |
| Update frequency | 2.8% | 93,28% |
| Max childs updated | 29,5M | 28.9 |
| Avg Diff | 0 | 2 |
| Avg Abs Diff | 349 | 207 |
| max path length | 30 | 36 |
| Rating | 2209 | 2194 |