Главная » Алгоритмы, Игры » Испытанный метод сортировки перемещений

0

Существует старый и простой способ сортировки, популярный на протяже­нии многих лет. Перемещения генерируются в некотором буфере. У каждо­го описателя перемещения есть поле, назовем его sortvalue. Это поле со­держит значение данного перемещения для сортировки. Применяют аналог пузырьковой сортировки: весь массив не сортируют сразу, а подкачивают вверх только одно самое лучшее перемещение. Функция подкачки получила даже традиционное название Pick.

Вот пример кода: Const

MaxPly = 100;

Type TMove = record

from, {откуда пошла фигура}

to,   {куда}

piece, {код фигуры} kind:byte;{тип хода} sortValue:LongInt; {поле сортировки} end;

var

Tree:array[0..MaxPly-1] of TMove; {буфер для перемещений} TreeCnt:array[0..MaxPly-1] of integer; {начало-конец списка перемещений}

procedure Pick(N1,N2:integer); •var maxV:TScore; maxN,N:integer; tmp:TMove; begin

maxV := Tree[Nl].mSortValue; maxN := N1; N := N1 + 1; while N < N2 do begin with Tree[N] do

if SortValue > maxV then begin maxV := mSortValue;

maxN := N; end; N := N + 1; end;

if maxN <> N1 then begin

tmp := Tree[N1]; Tree[Nl] := Tree[maxN]; Tree[maxN] := tmp; end; end;

function Search(alpha,beta,ply,depth,side,xside:integer):integer; var

mCnt,tmp:integer; begin

if (depth < 0) or (ply >= MaxPly) then begin Search := Evaluate(side); exit; end;

TreeCnt[ply+1] := TreeCnt[ply]; GenerateAllMoves(side,ply)); mCnt := TreeCnt[ply];

while (mCnt < TreeCnt[ply+1]) and (alpha < beta) do begin Pick(mCnt,TreePnt[ply+1]);

tmp := -Search(-beta,-alpha,depth-1,ply+1,xside,side); if tmp > alpha then alpha := tmp; mCnt := mCnt + 1; end;{while} Search := alpha; end;

procedure IterativDeep; var

depth:integer; begin

TreeCnt[0] := 0; depth := 1;

while (depth < MaxPly) and rfot TimeUp do begin

Search(-INFINITY,INFINITY,0,depth,cWhite,cBlack); depth := depth + 1; end;

end;

Перемещения откладываются в буфере Tree. Массив TreeCnt содержит ин­декс первого пустого элемента для данного ply. Если мы, например, сгене­рировали перемещения для глубины 0 (ply = о), то индекс первого элемента будет TreeCnt[0], а индекс последнего (TreeCnt[i]-i). Функция Pick для скорости даже не меняет элементы местами в массиве, как при пузырьковой сортировке. Она только запоминает индекс элемента с наибольшим значе­нием и, если это не первый элемент, меняет его местами с первым. При alpha-beta алгоритме очень часто не нужны все перемещения, и совершенно не обязательно сортировать весь буфер. Лучший ход может сразу вызвать отсечку за beta, и расчет этого узла прекратится. В качестве поля для сорти­ровки для взятий может использоваться вес фигуры минус код взявшей фи­гуры, для соблюдения порядка "наиболее ценная жертва — наименее цен­ный нападающий". Перед взятиями идет ход из хеша. После взятий может быть один или два лучших хода для соседнего узла. Далее простые переме­щения могут сортироваться по значению (приращение оценки при ходе), или может использоваться значение из таблицы истории. Для самого быст­рого варианта взятия должны генерироваться сначала отдельной функцией, а тихие перемещения потом. Если поле сортировки нулевое (например, для таблицы истории), то оставшиеся в буфере перемещения можно брать без сортировки.

0x88

Это старое и хорошо известное представление позиции. Поле представлено массивом не 8 х 8, а 8 х 16. Это дает возможность контролировать выход за пределы доски всего одной операцией сравнения:

if( (N & 0x88) ! = 0)

{

//вышли за пределы поля

}

Если клетки за пределами доски обозначить F, то массив будет выглядеть:

TSquare pos[8*16] = {

0, 0, 0, 0, 0, 0, 0, 0, F, F, F, F, F, F, F, F 0, 0, 0, 0, 0, 0, 0, 0, F, F, F, F, F, F, F, F 0, 0,0, 0,0, 0,0,0, F,F,F,F,F, F,F,F 0, 0, 0, 0, 0, 0, 0, 0, F, F, F, F, F, F, F, F 0, 0, 0, 0, 0, 0, 0, 0, F, F, F, F, F, F, F, F 0, 0, 0, 0, 0, 0, 0, 0, F, F, F, F, F, F, F, F 0, 0, 0, 0, 0, 0, 0, 0, F, F, F, F, F, F, F, F 0, 0, 0, 0, 0, 0, 0, 0, F, F, F, F, F, F, F, F } ;

Преимуществом данного представления является то, что размер есть сте­пень числа 2, и если нужно перевести координату N в X,Y массива 8×8 (стандартного представления), то это можно сделать очень быстро на дво­ичном уровне:

Y = N » 4;       // N / 16

X = N & 15;      // N % 16

Приращения при движении фигуры можно представить обычной строкой с 0 в конце, например:

? приращения при движении ферзя и короля

int delQueenf] = {-1,1,-16,16,-17,-15,17,15, 0};

П при движении ладьи

int delRook[] = {-1,1,-16,16, 0};

Мы можем объединить генерацию перемещений для нескольких фигур сразу.

Недостатком является сложная структура массива атаки. Кроме того, пред­ставление 16 х 16 вообще не нуждается в контроле выхода за пределы поля.

Литература:

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

По теме:

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