ALG(3

12.1, Reprezentacja problemów 283

jaki cel należy osiągnąć. Popatrzmy jednak na inne przedstawienie tej samej sytuacji (patrz rysunek 12 - 2).

Jeśli założymy, że dany konik może poruszać się tylko o dwa pola (w przód i w tył po wyznaczonej ścieżce 0-5-6-1-8-3-2-7-0), to zauważymy, że modelujemy w ten sposób bardzo łatwo ruchy dozwolone i umiemy napisać funkcję, która stworzy listę takicli mchów dla danego konika. Z rysunku została usunięta również pozycja „martwa” (4), całkowicie niedostępna i w związku z tym w ogóle nam niepotrzebna.

Rys. 12- 2. Problem konika szachowego (2).

Ćwicz. 12-1

Proszę się zastanowić, jak rozwiązać postawione zadanie, dozwalając być może jednoczesne ruchy kilku pionów?

Ważną reprezentacją zagadnień sztucznej inteligencji są tzw. grafy stanów ilustrujące w węzłach stany problemu (np. planszę z zestawem pionów), a poprzez krawędzie możliwości zmiany jednego stanu na inny (np. poprzez wykonanie ruchu). W przypadku gry w szachy należałoby zatem zapamiętywać w węźle aktualne stany szachownicy, co czyniłoby reprezentację dość kosztowną, zważywszy na liczbę możliwych sytuacji i co za tym idzie - rozmiar grafu!

12.2.Gry dwuosobowe i drzewa gier

Zaletą typowych gier dwuosobowych jest względna łatwość ich programowej implementacji. Decydują o tym następujące cechy:

• w danym etapie mamy komplet wiedzy o sytuacji, w jakiej znajduje się gra (stan planszy);