Подрязване на Move Tree и Alpha Beta

Алфа-бета подрязването е оптимизация на алгоритъма за преминаване на дървото за преместване въз основа на познаване на текущите най-добри резултати, получени на предишни нива на дървото.

Преместване на дърво

Фигурата показва дърво с възможни ходове. При кръгли възли ние правим избор, а при квадратни възли нашият противник.

В един момент процесът на обмисляне на възможни реакции спира. Дървото за преместване има краен размер и се прави някаква евристична оценка за неговите листа.

Функцията за оценка в шаха може да се основава на това какви фигури са останали на дъската (претеглената сума от фигурите на белите минус претеглената сума от фигурите на черните).

Ако ситуацията е добра за белите, функцията за оценка е положителна, ако за черните е отрицателна. Ще приемем, че и в други игри единият играч е "бял", а другият е "черен". Например, в tic-tac-toe ще зададем кръст като "белия" играч.

Сред възможните ходове ние („белите“) ще изберем хода, който ни отвежда до позицията с максимална оценка, а мислейки за противника, естествено е да изберем хода, който води до ситуацията с най-малката оценка.

* Оценка (позиция, дълбочина) оценка на позицията ситуация с дълбочината на дълбочината на мислене.

Удобно е да го дефинирате рекурсивно:

  • Резултат (позиция, 0) = Евристичен резултат? (позиция)
  • Резултат (позиция, дълбочина) = MAX < (Резултат(р, дълбочина-1) > ако d е странно;
  • Резултат (позиция, дълбочина) = MIN < (Резултат (p, дълбочина-1)> ако d е четен;
  • където p преминава през всички възможни позиции, които могат да бъдат достигнати от позицията на позицията.

Така, ако погледнем през дървото на ходовете до дълбочина 4 (4 половин хода), тогава

  • Резултат(4) = МАКС ( МИН (МАКС (МИН (резултат на листната ситуация), ..), ..), ..)

Първотърси се максимумът от възможните ни ходове; следващият минимум се търси от възможните отговори на противника на нашия ход; следващият максимум се търси чрез нашите възможни отговори на отговора на противника и т.н. Ето схематичен C код, който изчислява Score (дълбочина):

алфа бета изрязване

Идеята за оптимизиране на работата на функцията Score(depth) започва със следното разсъждение:

  • S1: Да предположим, че вече сме обмислили един от нашите ходове MOVE1 и всички възможни отговори на опонента и сме започнали да обмисляме нашия втори ход MOVE2. Веднага щом сред отговорите на опонента се появи ход, който ни поставя в ситуация, по-лоша от най-лошата ситуация, в която опонентът може да ни постави, ако тръгнем с MOVE1, тогава можем да спрем да изброяваме възможните отговори на опонента на MOVE2 и да преминем към разглеждане на нашия следващ ход MOVE3.
  • S2: РазсъждениеS1 може да се направи на всяко ниво, разсъждавайки както за себе си, така и за опонента си
  • S3: Всъщност, за да приложим идеятаS2, трябва да запомним най-добрия резултат, постигнат на предишното ниво. Нека наречем най-добрия резултат от параметъра на предишното ниво алфа.
  • S4: Възможно ли е да използвате най-добрия резултат от предходното ниво за вашите собствени цели? Да, можеш! Това ще бъде бета параметърът.

Така процедурата score_alphabeta(int depth, int alpha, int beta), в допълнение към дълбочината на мисълта, получава още два параметъра alpha и beta.

Значението му може да се обясни по следния начин:Намерете оценка на текущата ситуация (някоя глобална променлива X), като приемете, че е между алфа и бета. Ако това предположение не е вярно и реалната оценка на ситуацията е A, лежащо извън [алфа, бета], тогава

  • върне бета+1, ако A>= бета;
  • върне алфа-1, ако А е алфа.

Така, ако познаем интервала, в който се намира реалната оценка на ситуацията, тогава ще получим правилната оценка, в противен случай ще знаем само от коя страна на интервала [алфа, бета] се намира правилният отговор.

Функцията score_alphabeta може да бъде извикана с параметри alpha=-infty, beta=+infty и да получи точната стойност. Когато тази стойност бъде изчислена, ще бъдат направени рекурсивни повиквания, за които стойностите на параметрите вече не са безкрайни. Колкото по-дълбоко е нивото на рекурсия, толкова по-близки са средно алфа и бета аргументите.

Допълнителни оптимизации

Ето и сканирана версия на статия от списание "Програмист": Алгоритми: търсене в games.doc