ALG(4

284 Rozdział 12. Czy komputery mogą myśleć?

•    role graczy są symetryczne;

•    reguły gry są znane z wyprzedzeniem.

W przypadku gier dwuosobowych, bardzo wygodną strukturą danych ułatwiających reprezentację stanu i przebiegu gry jest drzewo Ruchy kolejnych graczy są przedstawiane przy pomocy węzłów drzewa, w którym poszczególne „piętra” (poziomy zagłębienia) odpowiadają wszystkim możliwym do wykonania ruchom danego gracza. Przykład drzewa gry jest podany na ry sunku 12-3.

{pozycja wyjściowa, zaczyna gracz A)

nil i    .liii    ; ■ r

■ 1    ■    pn

ntti    ititl    Htp

Rys. 12-1 Przykład drzewa pewnej wyimaginowanej gry (2).

Poszczególne węzły są dość skomplikowanymi strukturami danych, pozwalającymi zapisać kompletny stan pola gry (w naszym przykładzie jest to kratownica 4x4, omawiana gra jest całkowicie fikcyjna). Gracz A, jako zaczynający grę ma największą swobodę ruchów. Jeśli wybierze on ruch 1, to gracz B powinien się dostosować do jego wyboru według dwóch kryteriów:

•    wybór musi być najkorzystniejszy dla B (kryterium zdrowego rozsądku);

•    wybór musi być zgodny z regularni gry (kryteriumpoprawności).

Drzewo gry jest tym prostsze, im mniej skomplikowana jest gra pod względem możliwości ruchów. Tak więc nietrudno sobie wyobrazić, że drzewo gry „kółko i krzyżyk” jest o wiele prostsze od drzewa gry w warcaby lub szachy.

Drzewa gry w pewnym momencie się kończą (nawet jeśli są bardzo duże): każda sensowna gra prowadzi przecież prędzej czy później do wygranej, przegranej jednej ze stron lub remisu! Powstaje zatem praktyczne pytanie: czy da się tak poprowadzić przebieg partii, aby zaproponować jednemu z graczy strategią wygrywającą? Aby komputer mógł „rozumować” w kategoriach strategii wygrywającej lub przegrywającej, musi być wyposażony w algorytm skutecznie symulujący w nim zdolność inteligentnego podejmowania decyzji. W praktyce oznacza to wbudowanie w program dwóch typów funkcji: