Здесь описан алгоритм поиска, над которым хотелось бы поработать.

 

По сути, это обычный альфа-бета алгоритм, но вместо поиска

на заданную глубину, выполняется поиск "в ширину", без

необходимости задавать какую-то глубину.

 

Главная особенность - вместо таблицы транспозиций, которая

в обычном алгоритме занимает наибольший возможный объём памяти,

будем хранить в этой памяти всё пройденное дерево. В каждом узле

дерева определяется минимаксная оценка поддерева, а также - два

числа, характеризующие непроверенные шансы альфа и бета игроков.

Под шансами можно понимать некоторые оценки следующих невыполненных

ходов в дереве. В корне дерева и на четных уровнях (назовём их

альфа-узлами), альфа-шанс определяется как максимум из оценки

следующего хода в этом узле (если он есть) и альфа-шансов всех имеющихся

дочерних узлов. Бета-шанс в таких узлах берется из бета-шанса

того дочернего узла, в котором оценка минимакса наибольшая, т.е.

из узла, в который пойдет альфа-игрок.

На нечётных уровнях дерева (бета-узлах) картина аналогичная, но

с точностью до наоборот.

В терминальных узлах, где не было сделано ни одного хода,

придётся определить альфа и бета шансы из одного числа - оценки

первого хода.

 

Таким образом, в корень дерева можно поднять не только минимаксную

оценку (т.е. текущий достигнутый результат поиска), но и две оценки

шансов. По этим трём числам после каждой итерации поиска можно

принимать решение о том, какое следующее ответвление/продолжение

в дереве выполнять, или решение о прекращении поиска.

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

которое способно превзойти текущий результат, то на следующей

итерации поиска выполняем соответствующий ход из соответствующего

альфа-узла. Если же альфа-шанс невелик, но имеется высокое

значение бета-шанса (т.е. бета-игрок имеет высокий потенциал

опровергнуть текущий результат), то выполняем ход из бета-узла.

Решение о завершении поиска принимаем в том случае, если текущий

результат достаточно высок, а шансы его улучшить или опровергнуть

невелики. Или же кончилось время, или дерево заполнило всю память

(хотя, можно найти способ освобождать из памяти неактульные

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

 

Весь поиск можно описать как цикл итераций, на каждой из которых

выполняется очередное ответвление/продолжение в дереве:

 

while (!stop_variations()) {

  find_next_variation();

  make_variation();

  result_definition();

}

 

Функции:

 

stop_variatons() - принимается решение о прекращении поиска

по достигнутому результату, оставшимся шансам или по времени.

При необходимости выполняется процедура освобождения памяти.

 

find_next_variation() - если поиск продолжаем, то в этой функции

определяем, какое ответвление/продолжение выполнять следующим

(в альфа или бета узле), и затем смещаемся от корня дерева

к соответствующему узлу.

 

make_variation() - выполняем от текущего узла следующий ход.

Можно выполнить даже не один ход, а пройти целую цепочку ходов,

до достижения некоторого нового результата (превышения предыдущего

результата в случае альфа-ответвления, или опровержения в случае

бета-ответвления). Здесь же заносим в дерево очередные пройденные

узлы.

 

result_definition() - от конца нового пройденного варианта

поднимаемся к корню дерева, и определяем в каждом проходимом

узле новую оценку минимакса, а также оценки альфа и бета шансов,

как это описано выше.