Drzewo gry - drzewo, którego węzły są możliwymi stanami gry. A czym jest stan gry? To pewne położenie, które można osiągnąć po wykonaniu ruchu w danej grze.
Dla przykładu spójrzmy na problem z dzbanami. Mamy do dyspozycji 2 dzbany, o pojemności 4l i 3l. Celem jest doprowadzenie do sytuacji, w której wyłącznie w dużym dzbanie otrzymamy dokładnie 2l wody (stan docelowy). Początkowo oba dzbany są maksymalnie wypełnione.

Ścieżek, które prowadzą do rozwiązania może być wiele, ale najbardziej pożądaną przez użytkownika jest zwykle ta najkrótsza. Aby ograniczyć nadmierny rozrost drzewa należy wykrywać stany już odwiedzone i nie powtarzać już raz wykonanych czynności.

Rozpatrzmy teraz drzewo gry NIM. Na stole leży 7 zapałek (początkowo w jednej grupie) i dwaj gracze na przemian dzielą je na podzbiory o różnej liczności. Przegrywa gracz, który nie może wykonać prawidłowego ruchu.
Uwaga: zapis 2,2,3 w węźle oznacza, że zapałki podzielone są na podzbiory o liczności 2, 2 i 3. Stan ten jest tożsamy ze stanami 2,3,2 i 3,2,2.

Na czerwono zaznaczyłem stany, w których zwycięzcą zostaje gracz nr 1, a na zielono ten, w którym wygrywa gracz 2.
Po krótkiej analizie drzewa można zauważyć, że gracz, który rozpoczyna grę, nie ma szans na zwycięstwo przy odpowiedniej grze drugiego gracza. Po dowolnym ruchu inicjującym, rywal "zmusza" gracza nr 1 (poprzez doprowadzenie do stanu 1,2,4 lub 1,3,3) do wykonania przez niego ruchu prowadzącego do stanu 1,1,2,3, a stąd już tylko jeden ruch do zwycięstwa.
Grę tę można uogólnić wprowadzając założenie: przeciwnicy posiadają taką samą wiedzę o przestrzeni stanów i wykorzystują ją konsekwentnie do końca. Dodatkowo stan dobry dla jednego gracza jest jednocześnie zły dla drugiego. Gracze wykonują więc takie posunięcia, aby zmaksymalizować (zminimalizować) wartość funkcji obliczającej stan gry, ale także aby drugi gracz (który także będzie się starał wykonać jak najlepszy ruch) miał jak najgorszą możliwość wykonania posunięcia.
Oczywiście przy bardziej skomplikowanych grach (szachy, warcaby) czas przeglądania kolejnych poziomów drzewa jest bardzo duży. Metodami jego zmniejszania zajmę się za chwilę.

Rozpatrzmy kolejny przykład. Tym razem stany opiszę jedynie przez wartości funkcji oceny. Gracz 1 (MAX) chce oczywiście ją maksymalizować, a gracz 2 (MIN) minimalizować.

Na razie umieściłem jedynie wartośći funkcji stanów końcowych. Przy każdym poziomie znajduje się też oznaczenie gracza, do którego należy wybór ruchu. Grę rozpoczyna więc gracz chcący maksymalizować wynik.
Aby uzupełnić oceny pozostałych stanów zastosujmy następujący algorytm:

• Jeżeli uzupełniany stan należy do poziomu gracza MIN, to nadaj mu najmniejszą wartość spośród dzieci.
• Jeżeli uzupełniany stan należy do poziomu gracza MAX, to nadaj mu największą wartość spośród dzieci.

Końcowa postać drzewa:

Widzimy więc, że gracz MAX może wygrać 1 "punkt" (znaczenie "punktów" zależy oczywiście od rozważanej gry), a jednocześnie MIN przegrywa 1 "punkt". Jest to podejście stosowane w tzw. grach o zerowej sumie.
Rzadko jednak kiedy mamy możliwość (czas) przeglądania całego drzewa, czyli rozważania wszystkich możliwych ruchów (obu graczy) aż do końca gry. Zwykle musimy się ograniczyć do kilku poziomów zagłębienia, czyli do kilku możliwych posunięć od aktualnej pozycji.Funkcja oceniająca dany stan musi więc także przybliżać wartości pozostałych położeń.

Projektując komputerowego gracza powinniśmy pamiętać, że w pewnych przypadkach przeglądanie i rozpatrywanie danego fragmentu drzewa jest bezcelowe. Spójrzmy na przykład:

Ruch gracza MIN do stanu o wartości +3 (zaznaczony na czerwono) może zostać zablokowany przez gracza MAX, który wie już, że może wymusić stan +5 (oznaczony na zielono),gdzie MIN może liczyć na co najwyżej wynik równy 5 (MIN dąży do minimalizacji!). Dlatego też rozpatrywanie stanów objętych na rysunku kolorem niebieskim jest bezcelowe, ponieważ gracz MAX nigdy nie pozwoli na dojście do sytuacji oznaczonej kolorem szarym (wartość tego stanu jest przecież gorsza od +5).
W algorytmie stosujemy więc dwa parametry:

• alfa - nasze najlepsze położenie uzyskane do tego momentu
• beta - najlepsze położenie uzyskane przez przeciwnika do tej pory

Zasady stosowania odcięć:

• alfa - Przeszukiwanie można zakończyć poniżej dowolnego wierzchołka typu MIN o wartości mniejszej lub równej wartości alfa dowolnego z jego poprzedników (typu MAX)
• beta - Przeszukiwanie można zakończyć poniżej dowolnego wierzchołka typu MAX o wartości niemniejszej od wartości beta dowolnego z jego poprzedników (typu MIN).

Powyżej przedstawiłem podstawy stosowania drzewa gry w opracowywaniu swojego własnego gracza komputerowego. Istnieje wiele udoskonaleń algorytmu obcinania alfa-beta. Chcielibyśmy przecież, aby poddrzewa obcinać jak najszybciej. Jest to jednak zbyt złożony temat (ruchy należy w jakiś sposób porządkować), aby opisywać go w tym artykule.