Я пишу Калах AI для турнира в моем университете, в котором я собираюсь участвовать.
Во время разработки я наткнулся на некоторое неинтуитивное поведение, касающееся изменения времени вычислений в зависимости от размера таблицы транспонирования, которое я не могу объяснить самому себе. По сути, проблема заключается в следующем: увеличение размера таблицы транспонирования уменьшает количество искомых позиций, но не уменьшает количество времени, затрачиваемого на их поиск.
Таблица транспонирования
Транспонирующая таблица - это, по сути, хеш-таблица, в которой сохраняются уже найденные позиции и результаты их поиска. Это похоже на динамическое программирование, где вы компенсируете время вычисления для памяти.
Таким образом, интуитивно понятное увеличение доступной памяти должно ускорить вычисления. Ниже вы можете увидеть код, который управляет поведением таблицы транспонирования. (Да, программа написана на Java. Я знаю, что в C ++ подобные вещи будут проще, но для участия в программе необходимо наличие программы)
Инициализация, вызываемая перед поиском:
public TranspositionTable(int power) {
entries = (int) Math.pow(2, power);
table = new Entry[entries];
hashmask = entries - 1;
for(int i = 0; i < table.length; i++) {
table[i] = new Entry();
table[i].depth = Byte.MIN_VALUE;
}
}
Доступ для записи:
public void add(NodeType type, short value, byte bestMove, byte depth, long hash) {
int idx = (int) (hash & hashmask);
Entry tte = table[idx];
synchronized (tte) {
if(!tte.used) {
tte.used = true;
curEntries++;
rewrites--;
}
//don't overwrite higher search depth entries with lower ones.
if(tte.depth <= depth){
rewrites++;
tte.hash = hash;
tte.type = type;
tte.value = value;
tte.bestMove = bestMove;
tte.depth = depth;
}
}
}
Обратите внимание, что в настоящее время я использую только один поток для поиска, поэтому синхронизированные операторы на данный момент бесполезны.
Доступ для чтения:
public Entry get(long hash) {
int idx = (int) (hash & hashmask);
Entry e = table[idx];
synchronized (e) {
if(!e.used) {
misses++;
return null;
}
if(hash == e.hash) {
accesses++;
return e;
}
}
misses++;
return null;
}
Я использую 64-битную хеш-функцию Jenkins для генерации ключей.
Поиск
Вызовы в таблицу транспонирования выполняются в рамках итеративного углубления, альфа-бета-поиска с использованием окон аспирации, поиска по умолчанию и некоторых других, относящихся к этой теме, которые, вероятно, не имеют отношения к оптимизации. Процедура поиска выглядит примерно так:
public static int search(int alpha, int beta, int stackIdx, MutableState node, int depth, TranspositionTable tt) {
...
long hash = tt.getHash(node);
Entry e = tt.get(hash);
if (e != null) {// entry is valid?
if (e.depth >= depth) {
switch (e.type) {
case EXACT:
ss[stackIdx].pvIdx = e.bestMove;
return e.value;
case LOWERBOUND:
if (e.value > alpha)
alpha = e.value;
break;
case UPPERBOUND:
if (e.value < beta)
beta = e.value;
break;
}
if (alpha >= beta) {
ss[stackIdx].pvIdx = e.bestMove;
return alpha;
}
}
}
...
// store node in TT
NodeType type;
if (best <= alphaOriginal) {
type = NodeType.UPPERBOUND;
} else if (best >= beta) {
type = NodeType.LOWERBOUND;
} else {
type = NodeType.EXACT;
}
tt.add(type, (short) bestValue, (byte) bestMove, (byte) depth, hash);
return best;
}
Метрики поиска
Выбранные метрики доступа к таблице поиска и транспонирования представлены ниже, показывая прошедшее время в миллисекундах, усредненное за три прогона, количество найденных позиций, использованные записи таблицы транспонирования, загрузку (использованные записи, разделенные на общее количество записей), успешный доступ, переписывание ( перезапись уже использованных записей) и промахов с изменяющимся размером таблицы, захваченных во время поиска глубиной в 13 половину от начальной позиции Калаха (7,7)
table size 2^20:
Passed: 5581 ms
nodesSearched 6_781_473
qsnodesSearched 10_355_860
TT: entries: 966_427
TT: load: 0.9216566
TT: accesses: 426_747
TT: rewrites: 1_479_636
TT: misses: 2_800_001
table size 2^21:
Passed: 5473 ms
nodesSearched 6_571_630
qsnodesSearched 10_156_993
TT: entries: 1_487_042
TT: load: 0.7090769
TT: accesses: 471_566
TT: rewrites: 1_174_011
TT: misses: 2_665_098
table size 2^22:
Passed: 5688 ms
nodesSearched 6_449_400
qsnodesSearched 10_019_367
TT: entries: 1_908_758
TT: load: 0.45508337
TT: accesses: 501_231
TT: rewrites: 863_635
TT: misses: 2_585_731
table size 2^23:
Passed: 5667 ms
nodesSearched 6_380_913
qsnodesSearched 9_945_442
TT: entries: 2_174_936
TT: load: 0.25927258
TT: accesses: 517_884
TT: rewrites: 649_352
TT: misses: 2_538_265
table size 2^24:
Passed: 6015 ms
nodesSearched 6_356_761
qsnodesSearched 9_920_876
TT: entries: 2_329_595
TT: load: 0.13885468
TT: accesses: 526_862
TT: rewrites: 525_318
TT: misses: 2_519_007
table size 2^25:
Passed: 5924 ms
nodesSearched 6_332_790
qsnodesSearched 9_895_421
TT: entries: 2_408_029
TT: load: 0.07176486
TT: accesses: 531_226
TT: rewrites: 457_211
TT: misses: 2_504_210
Примечание:
- Существует два типа узлов: узлы поиска по умолчанию и "нормальные" узлы поиска. Что касается таблицы транспонирования, они отличаются только тем, что во время поиска по умолчанию таблица не используется для получения или сохранения результатов поиска.
- Аналогичные результаты получены для разных стартовых позиций.
- Инициализация таблицы транспонирования исключена из измерения времени.
Как вы, вероятно, заметили, количество искомых узлов уменьшается с увеличением размера таблицы, но прошедшего времени нет.
Моя первая теория заключалась в том, что индексирование массива (вычисление адреса памяти для конкретной записи массива) в Java занимает больше времени с увеличением размера массива, сводя на нет ускорение получения меньшего дерева поиска, делая узлы более дорогими для поиска. Но я чувствую, что это не тот случай, так как вы ожидаете некоторой линейности в результатах поиска.
Итак, мой вопрос : что заставляет поиск занимать больше времени при увеличении размера таблицы транспонирования?
Спасибо! :)