Sztuczna inteligencja/SI Moduł 8 - Gry dwuosobowe

Zadanie wyboru ruchu w grach dwuosobowych

Nietrywialne gry planszowe, pasjonujące dla wielu ludzi, od początku rozwoju sztucznej inteligencji uważane były za naturalny obszar „testowania” inteligentnych programów. Partia gry, w trakcie której gracze naprzemiennie wykonują ruchy, wymaga sekwencyjnego podejmowania decyzji o wyborze ruchu, który maksymalizuje szanse wygranej. Nawet przy rosnących mocach obliczeniowych maszyn, którymi dysponujemy, w nietrywialnych grach nie da się rozwiązać tego zagadnienia brutalną metodą rozważenia wszystkich możliwych sekwencji ruchów własnych i przeciwnika. Oznacza to, że wybór ruchu w grach dwuosobowych, tak jak rozwiązywanie innych złożonych zadań, wymaga odpowiednich strategii przeszukiwania. Ze względu na specyfikę gry - uczestnictwo przeciwnika, którego decyzje nie są z góry znane - strategie przeszukiwania stosowane do wyboru ruchu są odmienne od poznanych przez nas wcześniej strategii przeszukiwania heurystycznego, i zasługują na oddzielne omówienie.

Podstawowy model gry

Przed przystąpieniem do rozważania strategii wyboru ruchu musimy dokładnie ustalić, jakiego rodzaju grami będziemy się zajmować, czyli określić przyjmowany dalej model gry. Na model ten składają się następujące zasady:

1. W grze uczestniczy dwóch graczy.
2. Gracze wykonują ruchy naprzemiennie.
3. W każdej sytuacji na planszy jest skończona liczba możliwych do wykonania ruchów.
4. Sytuacja na planszy i wykonany ruch jednoznacznie wyznaczają następną sytuację na planszy.
5. Każda możliwa sytuacja na planszy może być jednoznacznie zaklasyfikowana do jednej z następujących kategorii:
   • wygrana pierwszego gracza,
   • wygrana drugiego gracza,
   • remis,
   • sytuacja nierozstrzygnięta.

Czasem dopuszcza się także możliwość liczbowej oceny skali wygranej (przewagi) w rozstrzygniętej partii, lecz nie będziemy się szerzej zajmować takim rozszerzeniem.

Inne rodzaje gier

Przedstawiony powyżej model gry opisuje podstawowy rodzaj gier, które możemy nazwać dwuosobowymi naprzemiennymi deterministycznymi grami planszowymi. W szczególności obejmuje on takie klasyczne gry planszowe jak szachy i warcaby, ale nie jest jedynym, dla którego można rozważać inteligentne techniki wyboru ruchu. Odrzucając lub modyfikując niektóre z podanych wyżej zasad możemy otrzymywać inne rodzaje gier. Na szczególną uwagę zasługują gry niedeterministyczne, w których o zmianie sytuacji na planszy współdecyduje pewien czynnik losowy. Niedeterminizm może przyjąć dwie podstawowe formy:

• wynik ruchu zależny od czynnika losowego,
• zestaw dostępnych do wykonania ruchów zależy od czynnika losowego.

Drzewo gry

Pojedyncza partia gry może być w pełni opisana przez ciąg naprzemiennych ruchów obu graczy, od początkowego ustawienia do rozstrzygnięcia. Aby w dowolnym momencie w trakcie trwania partii wybrać najbardziej odpowiedni ruch dla jednego z graczy, można rozważyć wszystkie możliwe scenariusze jej dalszego ciągu, rozpoczynające się różnymi możliwymi do wybrania ruchami tego gracza, po każdym z których może nastąpić każdy możliwy ruch drugiego gracza, itp. Naturalną reprezentacją dla takiej przestrzeni sytuacji, możliwych do osiągnięcia po kolejnych ruchach graczy, jest drzewo gry.

Drzewiasta reprezentacja możliwych scenariuszy

Węzły drzewa gry odpowiadają sytuacjom na planszy. W korzeniu drzewa znajduje się węzeł odpowiadający sytuacji, w której poszukujemy najlepszego ruchu dla jednego z graczy - będziemy go dalej nazywać krótko graczem, zaś drugiego gracza - przeciwnikiem. Oprócz sytuacji na planszy z każdym węzłem - a ściślej, z każdym poziomem w drzewie - związana jest informacja, który z graczy ma w niej wykonywać ruch. Poziom korzenia (nazwiemy go poziomem 0) jest poziomem gracza, kolejny - poziomem przeciwnika i dalej naprzemiennie.

Gałęzie wychodzące z każdego węzła reprezentują wszystkie możliwe (ze względu na reguły gry i aktualną sytuację na plaszy) ruchy odpowiedniego gracza. Każda z tych gałęzi prowadzi do węzła potomnego związanego z kolejną sytuacją na planszy, osiąganą po wykonaniu odpowiedniego ruchu, w której ruch będzie wykonywać drugi z graczy.

Pełne drzewo gry dla danej sytuacji początkowej to takie drzewo, w którym każdy węzeł odpowiadający nierozstrzygniętej sytuacji na planszy ma gałęzie wychodzące odpowiadające wszystkim możliwym ruchom oraz odpowiednie węzły potomne, reprezentujące sytuacje uzyskane po tych ruchach. W pełnym drzewie wszystkie węzły terminalne (liście) reprezentują sytuacje, w których partia gry jest rozstrzygnięta. Ze względu na liczbę możliwych sytuacji w nietrywialnych grach budowanie takiego pełnego drzewa nie jest praktycznie możliwe. Zachodzi w związku z tym konieczność rozważania drzew gry, w których pozostają węzły terminalne odpowiadające nie rozstrzygniętym sytuacjom na planszy.

Powyższy rysunek ilustruje drzewo gry, reprezentujące możliwe scenariusze w dwóch kolejnych ruchach. Pokazano na nim trzy poziomy: poziom $0\,$ (gracza), poziom $1\,$ (przeciwnika) i poziom $2\,$ (gracza), używając trójkątów o podstawie u dołu na oznaczenie węzłów gracza oraz trójkątów o podstawie u góry na oznaczenie węzłów przeciwnika. Z każdego węzła poziomów $0\,$ i $1\,$ wychodzą trzy gałęzie, reprezentujące trzy możliwe do wykonania ruchu.

Wybór ruchu jako przeszukiwanie

Zadanie wyboru ruchu w grze możemy traktować jako zadanie przeszukiwania przestrzeni możliwych przyszłych scenariuszy partii, w celu znalezienia scenariusza najbardziej korzystneg dla gracza. Pierwszy ruch z takiego najkorzystniejszego scenariusza jest uznawany za poszukiwany najkorzystniejszy ruch. W tym przypadku wygodnie jest jednak zastąpić bezpośrednie przeszukiwanie przestrzeni scenariuszy przeszukiwaniem przestrzeni sytuacji na planszy, z zachowaniem kolejności przechodzenia między nimi. Ciąg kolejnych sytuacji wyznacza wówczas scenariusz. Ten sposób postępowania - zastąpienie przeszukiwaniem przestrzeni sekwencji decyzji przeszukiwaniem przestrzeni wyników pojedynczych decyzji - jest nam już znany z ogólnej dyskusji metod przeszukiwania.

Przyjmując takie podejście, zadanie wyboru ruchu odwzorowujemy na zadanie przeszukiwania w następujący sposób:

stany: stanem jest sytuacja na planszy wraz ze wskazaniem aktualnego gracza (wykonującego następny ruch),

operatory: operatorem jest dowolny możliwy ruch aktualnego gracza,

stan początkowy: stan odpowiadający sytuacji na planszy, w której mamy wybrać ruch dla gracza,

stany końcowe: stanem końcowym jest dowolny stan, w którym partia jest rozstrzygnięta.

Zauważmy jednak, że w zadaniu wyboru ruchu nie zadowala nas osiągnięcie jakiegokolwiek stanu końcowego (dowolnego rozstrzygnięcia partii), ani nawet „najlepszego” stanu końcowego (najbardziej korzystnego rozstrzygnięcia partii). Może nas interesować tylko taki stan końcowy, który jest zarazem „dobry” (jeśli chodzi o wynik partii) i który może być osiągnięty przy założeniu, że przeciwnik dążąc do własnej wygranej wybiera według własnego uznania korzystnie dla siebie ruchy. To obecność przeciwnika, którego ruchy nie mogą być przewidziane i dokładnie zaplanowane, decyduje o istotnej odmienności zadania przeszukiwania w grach od innych rozważanych przez nas zadań przeszukiwania, i powoduje konieczność posługiwania się innymi, specyficznymi algorytmami.

Drzewo gry reprezentuje przestrzeń przeszukiwań przy wyborze ruchu. Jego węzły odpowiadają stanom, a krawędzie operatorom - tak samo jak w przypadku ogólnego drzewa przeszukiwania. Algorytmy przeszukiwania mogą także być przedstawione jako algorytmy przeglądania drzewa przeszukiwania, lecz w przeciwieństwie do ogólnych algorytmów przeszukiwania, nie będą się one ograniczać do przechodzenia pewnej ścieżki w drzewie (być może z nawrotami).

Strategie minimaksowe

Zauważyliśmy już, że specyfika zadania wyboru ruchu w grze, wymuszająca zastosowanie specjalizowanych algorytmów przeszukiwania, polega na obecności przeciwnika, który autonomicznie wybiera swoje ruchy. W ogólnym przypadku ruchów tych nie można w związku z tym przewidzieć (ani w sensie dokładnym ani probabilistycznym). Najczęściej stosowane podejście do ominięcia tej trudności polega na przyjęciu założenia, że przeciwnik dążąc do wygrania partii zawsze wybiera najkorzystkiejszy dla siebie (a więc najmniej korzystny dla gracza) ruch. Gdybyśmy więc byli w stanie węzłom drzewa gry przypisać liczbowe oceny odzwierciedlające w pewien sposób szanse wygranej gracza, to na poziomie ruchu gracza należy zakładać wybór maksymalizujący taką ocenę, zaś na poziomie przeciwnika - wybór ją minimalizujący. Na takiej przesłance opierają się strategie minimaksowe.

Zasada minimaksu

Ignorując tymczasem praktyczne ograniczenia, weźmy pod uwagę pełne drzewo gry dla pewnej sytuacji początkowej, w której wybieramy ruch dla gracza. Węzły terminalne takiego drzewa odpowiadają sytuacjom, w których partia jest rozstrzygnięta. Węzłom tym przypiszemy liczbową ocenę ich użyteczności z punktu widzenia gracza w następujący sposób:

w przypadku wygranej gracza: ocena dodatnia $M\,$,

w przypadku wygranej przeciwnika: ocena ujemna $-M\,$,

w przypadku remisu: ocena $0\,$.

Przyjmiemy, że ocena dokonywana jest z punktu widzenia gracza, niezależnie od tego, czy oceniany węzeł terminalny drzewa gry znajduje się na poziomie gracza, czy na poziomie przeciwnika. W ten sposób interpretacja liczbowej oceny każdego węzła będzie jednolita: im większa jej wartość, tym węzeł odpowiada korzystniejszej sytuacji z punktu widzenia gracza, dla którego ruch ma zostać wybrany.

Dokładne wartości liczbowe ocen węzłów mogą być ustalane różnie i nie nie ma to na razie żadnego znaczenia, jeśli wyniki gry podlegają wyłącznie klasyfikacji na wygraną któregoś z graczy albo remis (bez oceny skali wygranej). Gdyby skala (przewaga) wygranej miała być także brana pod uwagę, należałoby dodatkowo wymagać, aby sytuacje takiej samej wygranej gracza i przeciwnika oceniane były jednakowo co do wartości bezwzględnej.

Po dokonaniu w opisany sposób oceny wszystkich węzłów terminalnych drzewa gry, oceny można propagować do węzłów wewnętrznych zgodnie z następującymi zasadami:

na poziomie gracza: wezeł otrzymuje ocenę równą maksimum ocen jego węzłów potomnych,

na poziomie przeciwnika: węzeł otrzymuje ocenę równą minimum ocen jego węzłów potomnych.

Takie postępowanie opiera się na dwóch przesłankach. Po pierwsze, wiemy, że w kolejnych krokach gry gracz będzie w dalszym ciągu dążył do wybrania jak najlepszego ruchu posługując się wciąż tym samym algorytmem. Po drugie, zakładamy, że tak samo będzie zachowywał się przeciwnik. Ponieważ o przyszłym zachowaniu przeciwnika nie mamy żadnej wiedzy, zakładamy ostrożnie najmniej korzystny dla gracza wariant, w którym przeciwnik wybierze ruch najlepszy dla siebie. Jest to tylko założenie, które dla praktycznych przeciwników, zwłaszcza niezalgorytmizowanych, nie musi być prawdziwe, lecz jest możliwie bezpiecznym rozwiązaniem przy braku znajomości przeciwnika. Opisany sposób postępowania jest zilustrowany na poniższym rysunku. Przy każdym węźle zapisana została jego liczbowa ocena.

Efektem stosowania opisanej wyżej metody oceniania węzłów wewnętrznych drzewa gry, nazywanej metodą minimaksową albo zasadą minimaksu, jest przypisanie każdemu węzłowi oceny odzwierciedlającej najlepszy możliwy wynik partii dla gracza, przy założeniu najmniej dla niego korzystnych decyzji przeciwnika. Dla węzłów z poziomu gracza (w tym w szczególności dla korzenia drzewa gry) ruch prowadzący do węzła o maksymalnej ocenie będziemy nazywać ruchem optymalnym w sensie zasady mini-maks, albo krótko ruchem minimaks-optymalnym. W konkretnej partii gry z przeciwnikiem, który nie zawsze wybiera ruchy minimaks-optymalne dla siebie, może istnieć ruch prowadzący do lepszego wyniku partii niż ruch minimaks-optymalny (np. ruch kiepski przy zachowującym się optymalnie przeciwniku może okazać się bardzo dobry jeśli przeciwnik popełni błąd), lecz w sytuacji, gdy strategia wyboru ruchu stosowana przez przeciwnika nie jest znana, nie można wykorzystać takich sytuacji. Jednocześnie można się spodziewać, że w większości sytuacji nieoptymalne zachowanie się przeciwnika raczej ułatwi niż utrudni sytuację gracza, a zatem stosowanie zasady mini-maks pozostaje uzasadnione także przy niskim poziomie kompetencji przeciwnika.

Pełny mini-maks

Zgodnie z określoną wyżej zasadą minimaksu można przypisać liczbową ocenę każdemu węzłowi pełnego drzewa gry, w którego korzeniu znajduje się węzeł odpowiadający sytuacji, w której wybieramy ruch dla gracza. Następnie należy wybrać ruch, który z korzenia prowadzi do węzła potomnego o najwyższej ocenie. Będzie to ruch minimaks-optymalny, zapewniający najlepszy osiągalny wynik partii dla gracza przy założeniu, że przeciwnik wybiera zawsze ruchy najkorzystniejsze dla siebie. Oparty na zasadzie mini-maks algorytm wyboru ruchu w grze dwuosobowej można zapisać w poniższy sposób.

1. przypisz liściom drzewa ocenę jako użyteczność z punktu widzenia aktualnego gracza;
2. dla każdego poziomu $k\,$ drzewa, zaczynając od poziomu przedostatniego i kończąc na poziomie $0\,$
   1. jeśli poziom $k\,$ odpowiada akualnemu graczowi, przypisz każdemu węzłowi tego poziomu ocenę wyznaczoną jako maksimum ocen jego węzłów potomnych z poziomu $k+1\,$;
   2. jeśli poziom $k\,$ odpowiada przeciwnikowi akualnego gracza, przypisz każdemu węzłowi tego poziomu ocenę wyznaczoną jako minimum ocen jego węzłów potomnych z poziomu $k+1\,$;
3. wybierz ruch prowadzący do węzła poziomu $1\,$ o maksymalnej ocenie.

Tak sformułowany algorytm zakłada, że dysponujemy zbudowanym pełnym drzewem gry, które następnie przeglądamy w kierunku od liści do korzenia, odpowiednio propagując oceny. Wymaga to jawnej reprezentacji drzewa gry. Jest jednak możliwa prostsza i bardziej elegancka implementacja tego algorytmu, która nie buduje w jawny sposób drzewa gry, lecz pośrednio reprezentuje je za pomocą odpowiednio zorganizowanej rekurencji. Jak łatwo się przekonać, algorytm równowazny podanemu wyżej można zapisać w postaci następującej funkcji rekurencyjnej, która zwraca liczbową ocenę węzła. Dla przejrzystości pomijamy w jej zapisie przekazywanie informacji o tym, który faktycznie ruch maksymalizuje ocenę węzła potomnego i powinien być wybrany w korzeniu drzewa.

minimax(stan s, gracz g): ocena stanu s z punktu widzenia gracza g

1. jeśli s jest stanem końcowym, zwróć użyteczność stanu s;
2. oblicz minimax(s', g) dla wszystkich możliwych stanów następnych s';
3. jeśli w stanie s ruch wykonuje gracz g, zwróć maksimum uzyskanych wartości;
4. jeśli w stanie s ruch wykonuje przeciwnik gracza g, zwróć minimum uzyskanych wartości.

Niezależnie od sformułowania algorytmu, może wydać się oczywistym „marnotrastwem” budowanie i analiza pełnego drzewa gry (zakładając, że jest to wykonalne) tylko po to, aby wybrać jeden ruch. Rzecz jasna pełne drzewo gry, gdyby zostało raz zbudowane, umożliwia przeprowadzenie partii do końca, gdyż po każdym wykonanym ruchu gracza i następującym po nim ruchu przeciwnika wystarczy przenieść się do odpowiedniego węzła, aby wybierać następny ruch na podstawie wcześniej wyznaczonych ocen. Co więcej, mając pełne drzewo zbudowane od początkowej sytuacji na planszy i ocenione wszystkie węzły, moglibyśmy przeprowadzić dowolną liczbę partii, wybierając ruchy na jego podstawie.

Obcięty mini-maks

Ze względu na ogromną liczbę możliwych sytuacji i scenariuszy w jakichkolwiek nietrywialnych grach stosowanie pełnego algorytmu mini-maks nie jest w nich możliwe. Nie jest dla nich wykonalne w żadnym rozsądnym czasie (i z wykorzystaniem pamięci o jakichkolwiek praktycznie dostępnych pojemnościach) przejrzenie pełnego drzewa gry. Naturalnym pomysłem na dostosowanie algorytmu mini-maks do wymogów praktycznych jest ograniczenie głębokości analizowania drzewa gry do pewnej liczby poziomów (zależnej od złożoności gry i dostępnej mocy obliczeniowej). Oznacza to, że w analizowanym drzewie gry będą węzły odpowiadające nierozstrzygniętej partii nie posiadające węzłów potomnych. Aby było wówczas możliwe zastosowanie algorytmu mini-maks, każdy z takich węzłów musi otrzymać ocenę opartą nie na wyniku partii (brak rozstrzygnięcia) ani na ocenach węzłów potomnych (brak węzłów potomnych), lecz wyłącznie na analizie związanego z nim stanu gry.

Jak widać, potrzebujemy do oceny węzłów terminalnych ograniczonego drzewa gry funkcji heurystycznej. Tak jak w ogólnym zadaniu przeszukiwania funkcja taka ocenia „jakość” stanu (tam rozumianą jako odległość od stanu docelowego) bez faktycznego generowania jakichkolwiek stanów następnych, lecz wyłącznie na podstawie jego analizy, tak tutaj funkcja heurystyczna oceniać będzie użyteczność stanu z punktu widzenia gracza bez rozważania dalszych możliwych ruchów, wyłącznie rozważając sytuację na planszy. Zakładając dostępność takiej heurystycznej funkcji oceny, obcięty algorytm mini-maks możemy sformułować jako prostą modyfikację rekurencyjnej wersji pełnego algorytmu.

minimax(stan s, gracz g, poziom k): ocena stanu s z punktu widzenia gracza g

1. jeśli s jest stanem końcowym, zwróć użyteczność stanu s;
2. jeśli k przekracza maksymalną głębokość przeszukiwania, zwróć heurystyczną ocenę stanu s;
3. oblicz minimax(s', g, k+1) dla wszystkich możliwych stanów następnych s';
4. jeśli w stanie s ruch wykonuje gracz g, zwróć maksimum uzyskanych wartości;
5. jeśli w stanie s ruch wykonuje przeciwnik gracza g, zwróć minimum uzyskanych wartości.

Możliwe usprawnienia

Przedstawiony obcięty algorytm mini-maks jest algorytmem, który może być z dobrym skutkiem zastosowany w praktyce. Z odpowiednio starannie zaprojektowaną funkcją herystyczną może w wielu grach skutecznie konkurować przynajmniej z średniej klasy graczami-ludźmi. Rozważając praktyczne stosowanie tego algorytmu warto jednak zwrócić na pewne możliwe usprawnienia.

Pierwsza możliwa zmiana to zastąpienie stałej głębokości rozważanego drzewa gry zmienną głębokością - poszczególne gałęzie drzewa mogłyby się różnić poziomem, na którym występują węzły terminalne. Do realizacji tej koncepcji należałoby wzbogacić funkcję heurystyczną o możliwość dostarczania poziomu ufności dokonywanej oceny - spodziewając się, że różne sytuacje na planszy można ocenić z niejednakową ufnością. W trakcie rozważania kolejnych węzłów zawsze najpierw stosowana byłaby funkcja heurystyczna, a dalsza rozbudowa drzewa w głąb - tylko wówczas, gdy poziom ufności oceny heurystycznej nie będzie wystarczająco wysoki. Oszczędzając w ten sposób na obliczeniach w oczywistych sytuacjach możemy staranniej (głębiej rozbudowując drzewo) przeanalizować sytuacje mniej oczywiste.

Drugi pomysł opiera się na spostrzeżeniu, że w trakcie partii stosując konsenwentnie algorytm mini-maks do wybierania kolejnych ruchów gracza i rozważając w nim drzewo gry o pewnej głębokości $k>2\,$ możemy przy wyborze kolejnego ruchu wykorzystać fragment drzewa zbudowanego przy rozważaniu poprzedniego ruchu. Jeśli wybieraliśmy ruch dla gracza na poziomie $0\,$ drzewa, to rozważyliśmy także wszystkie możliwe ruchy przeciwnika na poziomie $1\,$, następnie dla każdego z nich wszystkie możliwe kolejne ruchy gracza na poziomie $2\,$ itd. Jeśli teraz gracz faktycznie wykonał wybrany ruch, w odpowiedzi na co przeciwnik wybrał i wykonał własny ruch, w w poprzednio zbudowanym drzewie możemy znaleźć na poziomie $2\,$ węzeł odpowiadający aktualnej sytuacji i wykorzystać go ponownie (wraz z całym poddrzewem poniżej niego) jako korzeń aktualnego drzewa gry, pogłębiając je odpowiednio zamiast budować je całkowicie od nowa. Technika ta nie może niestety być wprost połączona z eleganckim rekurencyjnym sformułowaniem algorytmu mini-maks gdyż wymaga pewnej jawnej reprezentacji drzewa, w celu późniejszego powtórnego użycia jego fragmentu.

Cięcia alfa-beta

Algorytm mini-maks jest zadowalającym rozwiązaniem, jeśli ograniczymy jego stosowanie do umiarkowanie złożonych gier albo wymagamy tylko umiarkowanego poziomu gry (porównywalnego ze średnim ludzkim graczem, lecz ustępującego bardziej doświadczonym i błyskotliwym graczom). Aby jednak wykazać dobry poziom w naprawdę złożonych grach, potrzebny jest algorytm w bardziej racjonalny sposób wykorzystujący dostępną moc obliczeniową w celu możliwie głębokiego zbadania drzewa gry tam gdzie może to wpłynąć na zmianę wybieranego ruchu, kosztem rezygnacji z rozbudowy i analizy drzewa gry tam, gdzie jej wynik i tak nie wpłynie na wybierany ruch. Taką zracjonalizowaną alokację mocy obliczeniowej realizuje algorytm cięć alfa-beta (albo przycinania alfa-beta), oparty na obciętym algorytmie mini-maks, lecz wzbogacający go o kryteria umożliwiające bezpieczne pominięcie w analizie (wycięcie) fragmentów drzewa gry.

Kryteria cięć

Rozważmy sytuację, w której oceniamy pewien węzeł $w\,$ na poziomie $k\,$ drzewa gry i załóżmy, że jest to poziom gracza. W związku z tym powinniśmy zgodnie z zasadą minimaksu wyznaczyć oceny wszystkich węzłów potomnych na poziomie $k+1\,$, a następnie przyjąć ich maksimum jako ocenę węzła $w\,$.

Niech $w_{1}\,$ będzie pierwszym ocenionym węzłem potomnym węzła $w\,$ i niech $\alpha \,$ oznacza jego ocenę. Natychmiast po wyznaczeniu tej liczby wiemy już, że ostateczna ocena węzła $w\,$ będzie większa lub równa $\alpha \,$ (tymczasowe maksimum). Niech teraz $w_{2}\,$ oznacza kolejny brany pod uwagę węzeł potomny węzła $w\,$. Ocena tego węzła jest dla nas przydatna tylko pod warunkiem, że wpływa na ocenę węzła $w\,$. Taki wpływ miałby miejsce tylko wtedy, gdyby ocena węzła $w_{2}\,$ miała przewyższać $\alpha \,$ (dotychczasowe maksimim). Ponieważ węzeł $w_{2}\,$ jest węzłem na poziomie przeciwnika. jego ocena będzie wyznaczana przez minimalizację ocen jego węzłów potomnych z poziomu $k+2\,$. Przyjmijmy, że węzły te będą oceniane kolejno, i po ocenieniu każdego z nich aktualizowane będzie dotychczasowe minimum. Teraz zauważmy, że jeśli w którymkolwiek momencie okaże się, że to tymczasowe minimum jest mniejsze lub równe $\alpha \,$, to od razu wiadomo, że końcowa ocena węzła $w_{2}\,$ nie będzie przekraczać $\alpha \,$, w tym samym jej dalsze wyznaczanie nie ma uzasadnienia, gdyż nie może ona wpłynąć na ocenę węzła $w\,$. W tym momencie możemy porzucić dalsze rozważanie węzłów potomnych węzła $w_{2}\,$ i zająć się kolejnym węzłem potomnym węzła $w\,$.

Przedstawione rozumowanie jest podstawą eliminacji z rozważania fragmentu drzewa, nazywanej cięciem alfa. Można je przeprowadzić także dla przypadku, gdy oceniany jest węzeł na poziomie przeciwnika przez minimalizację ocen węzłów potomnych. Wówczas możemy pominąć dokładne ocenianie tych węzłów, dla których stwierdzimy, że ocena musiałaby być tak czy inaczej większa lub równa dotyczasowemu minimum $\beta \,$. Mamy wtedy do czynienia z cięciem beta. Zasada obu cięć może być zwięźle podsumowana następująco.

Cięcie alfa: oceniając węzeł przez maksymalizację ocen węzłów potomnych możemy zakończyć wyznaczanie oceny węzła potomnego natychmiast po stwierdzeniu, że musi być ona niższa niż dotychczasowe maksimum $\alpha \,$.

Cięcie beta: oceniając węzeł przez minimalizację ocen węzłów potomnych możemy zakończyć wyznaczanie oceny węzła potomnego natychmiast po stwierdzeniu, że musi być ona wyższa niż dotychczasowe minimum $\beta \,$.

Ilustrację koncepcji cięć alfa-beta przedstawia poniższy rysunek. Pokazano na nim, jak w trakcie wyznaczania węzła na poziomie gracza w korzeniu drzewa można było pominąć węzły na poziomie $2\,$, stosując cięcie alfa. Wycięte poddrzewa zaznaczono za pomocą „wiszących” gałęzi.

Algorytm alfa-beta

Przez algorytm alfa-beta rozumie się to w istocie algorytm mini-maks wzbogacony o operacje cięć alfa i beta. Najbardziej naturalne i przejrzyste jest jego sformułowanie rekurencyjne. W takim sformułowaniu cięcie odzwierciedlone jest przez rezygnację z niektórych wywołań rekurencyjncych, które nie są konieczne do wyznaczenia oceny węzła.

Ze względu na wyróżnienie dwóch rodzajów cięć, odpowiadających poziomom gracza i przeciwnika w drzewie gry, algorytm sformułujemy za pomocą dwóch procedur z pośrednią rekurencją. Procedura minimax-alfa stosowana jest dla węzłów poziomu gracza (w tym dla węzła początkowego, w którym poszukujemy ruchu do wykonania), zaś procedura minimax-beta - dla poziomu przeciwnika.

minimax-alfa(stan s, gracz g, poziom k, $\alpha \,$, $\beta \,$): ocena stanu s z punktu widzenia gracza g, jeśli w stanie s ruch wykonuje gracz g

1. jeśli s jest stanem końcowym, zwróć użyteczność stanu s;
2. jeśli k przekracza maksymalną głębokość przeszukiwania, zwróć heurystyczną ocenę stanu s;
3. dla każdego możliwego stanu następnego s' wykonaj
   1. $\alpha \leftarrow \max\{\alpha ,{\textit {alfa-beta-min(s',g,k+1,}}\alpha ,\beta {\textit {)}}\}\,$;
   2. jeśli $\alpha \geq \beta \,$, zwróć $\beta \,$;
4. zwróć $\alpha \,$.

minimax-beta(stan s, gracz g, poziom k, $\alpha \,$, $\beta \,$): ocena stanu s z punktu widzenia gracza g, jeśli w stanie s ruch wykonuje przeciwnik gracza g

1. jeśli s jest stanem końcowym, zwróć użyteczność stanu s;
2. jeśli k przekracza maksymalną głębokość przeszukiwania, zwróć heurystyczną ocenę stanu s;
3. dla każdego możliwego stanu następnego s' wykonaj
   1. $\beta \leftarrow \min\{\alpha ,{\textit {alfa-beta-max(s',g,k+1,}}\alpha ,\beta {\textit {)}}\}\,$;
   2. jeśli $\beta \leq \alpha \,$, zwróć $\alpha \,$;
4. zwróć $\beta \,$.

Heurystyczna ocena węzłów

Nie ulega wątpliwości, że skuteczność algorytmów opartych na zasadzie minimaksu w przypadku, gdy przeglądany może być tylko minimalny fragment pełnego drzewa gry (kilka pierwszych ruchów spośród kilkudziesięciu czy nawet kilkuset posunięć), w znacznej mierze zależy od jakości używanej funkcji heurystycznej. Odpowiednie określenie takiej funkcji jest w przypadku nietrywialnych gier złożonym zadaniem, w którym często niezbędny jest udział doświadczonych ekspertów. W grach planszowych takich jak szachy funkcja taka jest obliczana z uwzględnieniem liczby poszczególnych figur w posiadaniu gracza i przeciwnika, ich bezwzględnego i względnego położenia, występowania specyficznych układów sąsiedztwa figur itd. Funkcja heurystyczna powinna spełniać następujące warunki:

1. przypisywać ocenę dodatnią stanowi, z którego większe szanse wygranej ma gracz,
2. przypisywać ocenę ujemną stanowi, z którego większe szanse wygranej ma przeciwnik,
3. przypisywać ocenę tym większą co do wartości bezwzględnej, im przewaga szans wygranej odpowiednio gracza albo przeciwnika jest większa.

Ponieważ istnieje możliwość, że w ograniczonym drzewie gry niektóre węzły terminalne odpowiadają rostrzygniętej partii (i są oceniane bezpośrednio na podstawie jej wyniku), a niektóre nie (i są oceniane przez funkcję heurystyczną), liczbowe wartości funkcji heurystycznej i bezpośredniej oceny użyteczności muszą być wyrażone w ujednoliconej wspólnej skali. W sytuacji, gdy końcowa ocena użyteczności opiera się wyłącznie na klasyfikacji wyniku (wygrana, przegrana, remis) bez uwzględniania skali wygranej/przegranej i przyjmuje wartości $+M\,$ w przypadku wygranej oraz $-M\,$ w przypadku przegranej, należy zapewnić, że wartości funkcji heurystycznej znajdują się w przedziale $(-M,M)\,$.

W najbardziej skutecznych programach grających w gry (dotyczy to zwłaszcza szachów) stosowane są niezwykle wyrafinowane funkcje heurystyczne, oparte na najwyższej klasy wiedzy eksperckiej i szeroko zakrojonych eksperymentach. Szczególnie obiecujący jest także pomysł, aby (choćby bardzo skuteczna) funkcja heurystyczna mogła podlegać modyfikacjom na podstawie rozgrywanych partii, w sposób poprawiający dokładność, z jaką pozwala ona przewidywać szanse wygranej w nierozstrzygniętych sytuacjach. Jest to najbardziej naturalna technika wyposażenia programów grających w gry w zdolność do uczenia się.