Drzewo gry
Partia danej gry może być zapisana jako kolejne, naprzemienne ruchy obu graczy (Gra dwuosobowa). Drzewo gry - reprezentacja umożliwiająca opisanie sytuacji możliwych do osiągnięcia po kolejnych ruchach graczy.
Węzły drzewa to przedstawienie poszczególnych sytuacji na planszy. Przy każdym węźle musi być określona informacja, który z graczy powinien wykonać ruch. Poziom 0 to poziom gracza, kolejny poziom jest poziomem przeciwnika, itd.
Gałęzie przedstawiają wszystkie możliwe ruchy graczy.
Liczba liści (węzłów stopnia 1) w kompletnym drzewie gry jest nazywana złożonością gry. Jest to liczba możliwych różnych sposobów rozegrania gry. Przykładowo, złożoność klasycznej gry w "kółko i krzyżyk" jest równa 26830.
Drzewa gry są ważne w sztucznej inteligencji, ponieważ jednym ze sposobów wybrania najlepszego ruchu w grze jest przeszukanie drzewa gry przy użyciu algorytmu minimax lub jego wariantów. Drzewo gry dla "kółka i krzyżyka" jest łatwe do przeszukania, lecz kompletne drzewa gry dla większych gier (jak szachy) są na to zbyt duże. Zamiast tego, programy grające np. w szachy przeszukują częściowe drzewa gry tak daleko, na ile pozwala im określony z góry dostępny czas.
Mając kompletne drzewo danej gry, można "rozwiązać" grę - to znaczy znaleźć sekwencję ruchów, które prowadzą zawsze jednego z graczy do zwycięstwa, bądź gwarantują osiągnięcie remisu.