Главная » Игры, Теория » Повторы позиций

0

Определение повторов позиций — не такая тривиальная тема. Она затрону­та многими корифеями шахматного программирования. Я не буду пытаться объять необъятное, а покажу, как простейшим способом научить программу распознавать повторы позиций.

Допустим, наше перемещение представлено в виде

albl а8Ь8

В этой строке игры показано, как белая ладья пошла с al на Ы, а черная — с а8 на Ь8. Как может исходная позиция повториться в одной строке игры? Очевидно, ладьи должны встать на исходные позиции:

Ыа1 Ь8а8

Полная строка, приводящая к повтору, выглядит следующим образом:

albl а8Ь8 Ыа1 Ь8а8

Повтор получился через 4 полухода. Мы и будем рассматривать только по­вторы через 4 полухода в одной строке. Если позиция повторится 3 раза, то строка выглядит

albl а8Ь8 Ыа1 Ь8а8 albl а8Ь8 Ыа1 Ь8а8 albl а8Ь8 Ыа1 Ь8а8

Как программа в процессе счета может понять, что есть повторение три раза через 4 полухода? Самый простой способ заключается в ZObrist- ключах. Это 8-байтовые хеш-ключи позиции. Вместо строки игры мы рабо­таем со строкой ключей. Определение повтора не составляет труда. Перед началом счета мы инициализируем массив с ZObrist-ключами последних 8—9 позиций. Во время счета переменная ply отслеживает глубину узла в строке от 0. Таким образом, при равенстве текущего ключа и ключа в стро­ке на 4 и на 8 позиций ранее возвращаем 0 — оценку draw. Выглядит этот программный код примерно так:

//позиция с индексом 8 соответствует корню дерева перебора при ply = О ZObrist line[100]; //где-то в функции AlphaBeta

int AlphaBeta(int alpha,int beta, int ply, U64 key) {

line[ply+8] = key; if( ply >0      &&

line[ply+8-4] = key && line[ply+8-8] = key) return 0; //draw

}

Здесь есть одна небольшая тонкость. Проверять повторы позиций можно только в пределах гарантированного полного перебора. Если мы используем нулевой ход или другой метод подрезки дерева, нужно оставлять несколько полуходов в начале перебора, где эти методы не используются. Если про­грамма пытается раскрыть главную строку изменения, возможно, что она сможет отслеживать повторы позиций и глубже. Если у нас есть гарантиро­ванные 4—5 полуходов полного перебора, то мы сможем научить программу распознавать элементарные зацикливания в игре, чего для практических целей вполне достаточно.

Простейшие повторы через 4 полухода можно распознавать и без ZObrist- ключей, написав следующий блок программного кода:

TMove line[20];

//ход 12 – корень дерева перебора

int AlphaBeta(PMove node, int ply, …)

{

line[ply+12] = node;

if(ply >0 && ply < 5) {

int n;

for(n =0; n < 4; n++) {

if (

!CompareMove(line[ply+12-n],          line[ply+12-4-n) II

!CompareMove(line[ply+12-n],             line[ply+12-8-n) )goto next;

}//for

return DRAW;

}

next: {…}

}

С ZObrist-ключами получается намного компактнее.

Оценка draw в большинстве случаев равна 0. Чтобы заставить программу играть дальше, если у нее небольшой минус в оценке, пытаются возвращать отрицательную величину. Если кто-то желает углубиться в эту тему, ему можно посоветовать почитать корифеев вроде Кена Томпсона.

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии