Politechnika Śląska w Gliwicach Gliwice
Wydział Automatyki, Elektroniki i Informatyki Rok Akademicki 2009/2010
Kierunek Automatyka i Robotyka Semestr Letni
Laboratorium
Komputerowego Wspomagania Podejmowania Decyzji
Ćwiczenie nr 4:
Procesy decyzyjne w postaci ekstensywnej o sumie zerowej
Wykonali:
Elżbieta GRZESICZAK
Sebastian KURCZYK
Data odbycia ćwiczenia:
17.05.2010
Spis treści
1. Wstęp teoretyczny .......................................................................................................................... 3
2. Przykładowy problem wieloetapowy .............................................................................................. 4
1. Opis problemu ............................................................................................................................. 4
2. Rozwiązanie zagadnienia ............................................................................................................. 4
3. Wyjaśnienie rekurencji problemu ............................................................................................... 8
3. Przykładowy problem dla trzech graczy .......................................................................................... 9
1. Opis problemu ............................................................................................................................. 9
2. Rozwiązanie zadania.................................................................................................................... 9
3. Modyfikacja zadania .................................................................................................................. 11
4. Skrypt rozwiązujący problem wieloetapowy................................................................................. 13
1. Opis problemu ........................................................................................................................... 13
2. Symulacja................................................................................................................................... 14
5. Wnioski .......................................................................................................................................... 18
6. Listing............................................................................................................................................. 19
1. Rozwiązanie gry macierzowej o sumie zerowej ........................................................................ 19
2. Rozwiązanie problemu wieloetapowego .................................................................................. 19
1. Wstęp teoretyczny
teoretyczny
Przykładem formy ekstensywnej jest poniższy graf:
Przykładem formy ekstensywnej jest poniższy graf:
Graf ten jest:
acykliczny  nie posiada przejść zapętleń. Do każdego możliwego stanu prowadzi tylko jeden
nie posiada przejść -zapętleń. Do każdego możliwego stanu prowadzi tylko jeden
łuk.
nieskierowany  nie ma narzuconego kierunku przejścia pomiędzy stanami.
nie ma narzuconego kierunku przejścia pomiędzy stanami.
nie ma narzuconego kierunku przejścia pomiędzy stanami.
spójny  cała struktura grafu jest ze sobą połączona. Nie występują elementy oddzielne.
cała struktura grafu jest ze sobą połączona. Nie występują elementy oddzielne.
cała struktura grafu jest ze sobą połączona. Nie występują elementy oddzielne.
Korzeń reprezentuje punkt początkowy, czyli pewnego rodzaju sytuację w której nie została podjęta
Korzeń reprezentuje punkt początkowy, czyli pewnego rodzaju sytuację w której nie została podjęta
Korzeń reprezentuje punkt początkowy, czyli pewnego rodzaju sytuację w której nie została podjęta
żadna decyzja. A
uki wychodzące z korzenia reprezentują możliwe decyzje (tutaj dwie decyzje), które
ja. A
uki wychodzące z korzenia reprezentują możliwe decyzje (tutaj dwie decyzje), które
ja. A
uki wychodzące z korzenia reprezentują możliwe decyzje (tutaj dwie decyzje), które
prowadzą do następnego stanu, wymagającego podjęcia decyzji (po lewej), lub do wyniku
prowadzą do następnego stanu, wymagającego podjęcia decyzji (po lewej), lub do wyniku
prowadzą do następnego stanu, wymagającego podjęcia decyzji (po lewej), lub do wyniku
ostatecznego (po prawej). Ten problem posiada trzy rozwiązania.
Ten problem posiada trzy rozwiązania.
Problem jednoetapowy to taki, w którym każdy z decydentów podejmuje decyzję tylko raz. W
owy to taki, w którym każdy z decydentów podejmuje decyzję tylko raz. W
owy to taki, w którym każdy z decydentów podejmuje decyzję tylko raz. W
przypadku kiedy decydenci podejmują decyzje kilkakrotnie, wówczas mamy do czynienia z
przypadku kiedy decydenci podejmują decyzje kilkakrotnie, wówczas mamy do czynienia z
przypadku kiedy decydenci podejmują decyzje kilkakrotnie, wówczas mamy do czynienia z
problemem wieloetapowym, o K etapach, gdzie K to ilość decyzji którą podejmuje każdy z graczy.
problemem wieloetapowym, o K etapach, gdzie K to ilość decyzji którą podejmuje każdy z graczy.
problemem wieloetapowym, o K etapach, gdzie K to ilość decyzji którą podejmuje każdy z graczy.
2. Przykładowy problem wieloetapowy
1. Opis problemu
Omawiany problem to decyzje podejmowane przez strategów wojskowych podczas działań
wojennych. Załóżmy:
W potyczce biorą udział dwie strony konfliktu
Armia A jest armią broniącą się, natomiast armia B atakuje
Decyzje podejmowane są w tajemnicy przed wrogiem, raz na kwartał
Możliwe są dwie strategie prowadzenia działań wojennych:
ofensywna (strategia 1)
defensywna (strategia 2)
Utrata terytorium państwa A jest zyskiem terytorium państwa B i opisana drzewem gry
trzyetapowej o wartościach wypłat odpowiednio:
Od lewej:
3 0 2 1 6 0 4 2 9 0 6 3 12 0 8 4 15
0 10 5 18 0 12 6 21 0 14 7 24 0 16 8 27 0
18 9 30 0 20 10 33 0 22 11 36 0 24 12 39 0 26
13 42 0 28 14 45 0 30 15 48 0 32 16
Gracz A minimalizuje, gracz B maksymalizuje wartość wypłaty
Wojna trwa trzy kolejne kwartały: wiosnę, lato, jesień.
2. Rozwiązanie zagadnienia
Zakładając że każdy ze strategów będzie podejmował bezpieczne dla siebie decyzje, to zagadnienie
można rozwiązać w sposób następujący, od końca drzewa:
Myśli jednego ze strategów:
 Na jesień mamy możliwych 16 rozstrzygających potyczek, w których będę musiał dowodzić, a
sytuacja będzie wyglądała tak..
A \ B 1 2
1 3 0
2 2 1
potyczka ta zakończyłaby się wynikiem: 2
A \ B 1 2
1 6 0
2 4 2
potyczka ta zakończyłaby się wynikiem: 4
A \ B 1 2
1 9 0
2 6 3
potyczka ta zakończyłaby się wynikiem: 6
A \ B 1 2
1 12 0
2 8 4
potyczka ta zakończyłaby się wynikiem: 8
A \ B 1 2
1 15 0
2 10 5
potyczka ta zakończyłaby się wynikiem: 10
A \ B 1 2
1 18 0
2 12 6
potyczka ta zakończyłaby się wynikiem: 12
A \ B 1 2
1 21 0
2 14 7
potyczka ta zakończyłaby się wynikiem: 14
A \ B 1 2
1 24 0
2 16 8
potyczka ta zakończyłaby się wynikiem: 16
A \ B 1 2
1 27 0
2 18 9
potyczka ta zakończyłaby się wynikiem: 18
A \ B 1 2
1 30 0
2 20 10
potyczka ta zakończyłaby się wynikiem: 20
A \ B 1 2
1 33 0
2 22 11
potyczka ta zakończyłaby się wynikiem: 22
A \ B 1 2
1 36 0
2 24 12
potyczka ta zakończyłaby się wynikiem: 24
A \ B 1 2
1 39 0
2 26 13
potyczka ta zakończyłaby się wynikiem: 26
A \ B 1 2
1 42 0
2 28 14
potyczka ta zakończyłaby się wynikiem: 28
A \ B 1 2
1 45 0
2 30 15
potyczka ta zakończyłaby się wynikiem: 30
A \ B 1 2
1 48 0
2 32 16
potyczka ta zakończyłaby się wynikiem: 32
 Skoro mogę przewidzieć do jakiego wyniku doprowadzi mnie jesienna potyczka, mogę przyjąć że
jeśli dojdzie do którejś z tych 16 potyczek, zakończy się ona określonym przeze mnie wynikiem.
Zatem już w lato będę wiedział jak zakończy się wojna. Dlatego przemyślę teraz możliwe strategie na
lato.
A \ B 1 2
1 2 4
2 6 8
potyczka ta zakończyłaby się wynikiem: 4
A \ B 1 2
1 10 12
2 14 16
potyczka ta zakończyłaby się wynikiem: 12
A \ B 1 2
1 18 20
2 22 24
potyczka ta zakończyłaby się wynikiem: 20
A \ B 1 2
1 26 28
2 30 32
potyczka ta zakończyłaby się wynikiem: 28
 Skoro mogę określić wynik wojny w zależności od tego jakie będą nasze wiosenne decyzje, zostaje
mi jedynie zastanowić się od jakiej strategii zacząć wiosną tą wojnę.
A \ B 1 2
1 4 12
2 20 28
potyczka ta zakończyłaby się wynikiem: 12
 Teraz już wiem, że podejmując bezpieczne decyzje, mogę uzyskać wynik 12
Rozwiązanie problemu polegało na rozwiązaniu osobnych gier (analizując od dołu grafu)
sprowadzających się do gry macierzowej o sumie zerowej. Uzyskany w każdej z tych gier wynik stawał
się wypłatą problemu wieloetapowego o liczbie etapów K-1 (problem został zredukowany o jeden
etap). Następnie należało rozwiązać osobno kolejne gry, redukując drugi etap. Ostateczny wynik
uzyskano rozwiązując grę macierzową o sumie zerowej będącą przedstawieniem wartości wypłat
wyznaczonych w sposób rekurencyjny opisany powyżej.
W ostateczności ścieżkę decyzji będących rozwiązaniem problemu można zwizualizować korzystając z
grafu:
3. Wyjaśnienie rekurencji problemu
Dla tego przypadku, analizując od wnętrza rekurencji:
Rozwiązano 42 gier dających się sprowadzić do gry macierzowej o sumie zerowej (zaznaczono
kolorem zielonym). Wyniki tych gier stały się wartościami wypłaty w drzewie zredukowanym o jeden
etap.
Rozwiązano 41 gier dających się sprowadzić do gry macierzowej o sumie zerowej (zaznaczono
kolorem niebieskim). Wyniki tych gier stały się wartościami wypłat w drzewie zredukowanym do gry
jednoetapowej.
Rozwiązano grę jednoetapową, sprowadzając ją do gry macierzowej o sumie zerowej.
Rozwiązaniem problemu jest wartość wypłaty najniższego poziomu (zaznaczonego kolorem
zielonym), oraz ścieżka utworzona przez podjęte przez graczy decyzje.
3. Przykładowy problem dla trzech graczy
1. Opis problemu
Omawianym problemem jest rodzinna gra w tenisa. Ojciec gra z dziećmi w tenisa (mama sędziuje).
Załóżmy:
Ojciec  gracz A minimalizuje ilość punktów zdobytych przez swoje pociechy
Córka  gracz B i syn  gracz C maksymalizują zdobyte przez siebie punkty
Wynikiem gry jest ilość zdobytych przez dzieci punktów
Możliwe są dwa rodzaje zagrania preferowanego:
forehand (strategia 1)
backhand (strategia 2)
Ilość zdobytych przez młodszą drużynę punktów determinują przyjęte przez graczy strategie,
zgodnie z poniższym drzewem decyzyjnym:
2. Rozwiązanie zadania
Powyższy problem można sprowadzić do gry macierzowej obu drużyn:
A / BC FF FB BF BB
F 0 1 3 2
B 9 4 4 1
F  forehand
B  backhand
Dla gracza A (ojca) strategią bezpieczną jest preferowanie forehandu jako stylu odbić, co zapewnia
mu poziom bezpieczeństwa 3.
Dla drużyny graczy B i C (dzieci) strategią bezpieczną jest preferowanie styli: backhand (córka) i
forehand (syn), co zapewnia im poziom bezpieczeństwa 3.
Istnieje zatem punkt siodłowy: ojciec gra forehand, córka backhand, syn forehand.
W rezultacie mama powinna ogłosić wynik 3ch punktów dla drużyny pociech.
3. Modyfikacja zadania
Modyfikacja zadania
W poniższym przypadku zmieniono tempo gry. Ojciec rodziny daje fory drużynie pociech, przez co
W poniższym przypadku zmieniono tempo gry. Ojciec rodziny daje fory drużynie po
młodsza drużyna ma czas na przeanalizowanie zagrywki ojca. Wprowadzono hierarchię:
młodsza drużyna ma czas na przeanalizowanie zagrywki ojca. Wprowadzono hierarchię:
młodsza drużyna ma czas na przeanalizowanie zagrywki ojca. Wprowadzono hierarchię:
Znając zagranie przeciwnika drużyna pociech może przyjąć następujące strategie:
Znając zagranie przeciwnika drużyna pociech może przyjąć następujące strategie:
córka:
1. d2(u1) = u1
2. d2(u1) = F
3. d2(u1) = B
4. d2(u1) = F jeżeli (u1 = B), B jeżeli (u1 = F)
, B
syn:
1. d2(u1) = u1
2. d2(u1) = F
3. d2(u1) = B
4. d2(u1) = F jeżeli (u1 = B), B jeżeli (u1 = F)
= B), B jeżeli (u
Zbiór dopuszczalnych strategii powstaje poprzez stworzenie wszystkich możliwych kombinacji tych
dwóch taktyk. Dopuszczalne rozwiązania:
A/BC 11 12 13 14 21 22 23 24 31 32 33 34 41 42 43 44
F 0 0 1 1 0 0 1 1 3 3 2 3 3 3 2 3
B 1 4 1 4 4 9 4 4 1 4 1 4 4 9 4 4
Po uproszczeniu powyższej tablicy można uzyskać następującą macierz:
A/BC 11 12 13 14 22 31 32 33 42 43
21 23 34
24 41
44
F 0 0 1 1 0 3 3 2 3 2
B 1 4 1 4 9 1 4 1 9 4
Dla takiej macierzy gry, strategią bezpieczną dla gracza A (ojca) jest preferowanie forehandu, gdzie
uzyskany poziom bezpieczeństwa wyniesie 3. Dla drużyny pociech strategia bezpieczną jest
odpowiednio dobór strategii 42, gdzie poziom bezpieczeństwa wyniesie również 3:
Istnieje punkt siodłowy.
Córka: zagrywa przeciwnie do zagrywki ojca
Syn: zawsze zagrywa z forehandu
Mama ogłosi najprawdopodobniej wynik 3ch punktów.
Spostrzeżenia:
Wprowadzenie hierarchii do opisanej gry nie zmieni spodziewanego wyniku gry. Jednak w przypadku,
gdy drużyna pociech może wyznaczyć  lepszą strategię bezpieczną dla siebie, ponieważ w przypadku
zagrywki z backhandu ojca, drużyna ta zyska 9 punktów, a nie 4 tak jakby miało to miejsce podczas
ciągłej gry backhand (córka) forehand (syn)  wyznaczonej w grze bez hierarchii.
4. Skrypt rozwiązujący problem wieloetapowy
1. Opis problemu
Analizowanym problemem są decyzje podejmowane przez kierowców rajdowych na torze
wyścigowym. Dla uproszczenia modelu decyzyjnego wprowadzono założenia:
wyścig rozstrzyga się pomiędzy dwoma najlepszymi zawodnikami
zawodnik A jedzie za zawodnikiem B i jego zadaniem jest minimalizacja przewagi rywala
zawodnik B prowadzi i jego zadaniem jest zwiększanie przewagi nad rywalem
decyzje podejmowane dotyczą manewrowania pojazdem na zakrętach:
jechać bezpiecznie (strategia 1)
ścinać zakręt (strategia 2)
zawodnicy muszą zareagować jednocześnie (brak hierarchii)
zmiana przewagi zawodnika B nad zawodnikiem A jest opisana drzewem, którego końce mają
wartości:
od lewej:
0 3 1 -1 0 6 2 -2 0 9 3 -3 0 12 4 -4 0
15 5 -5 0 18 6 -6 0 21 7 -7 0 24 8 -8 0 27
9 -9 0 30 10 -10 0 33 11 -11 0 36 12 -12 0 39 13
-13 0 42 14 -14 0 45 15 -15 0 48 16 -16
Do końca wyścigu pozostały trzy zakręty
Omówienie:
Obaj zawodnicy jadą bezpiecznie: przewaga zawodnika B nad zawodnikiem A nie ulega zmienia.
Zawodnik A próbuje ścinać zakręt, zawodnik B jedzie bezpiecznie: zawodnik B korzystając ze swoich
umiejętności zmusza zawodnika A do porzucenia podjętego manewru. Zawodnik B zwiększa
przewagę.
Zawodnik B próbuje ścinać zakręt, zawodnik A jedzie bezpiecznie: samochód będący na
prowadzeniu zwiększa swoją przewagę.
Obaj zawodnicy ścinają zakręt: Dochodzi do sytuacji zagrożenia kolizją. W tej sytuacji zawodnik A ma
większe umiejętności, przez co zmniejsza przewagę rywala.
Ilość etapów tej gry sprowadza się do ilości zakrętów dzielących zawodników od mety.
2. Symulacja
Skrypt programu matlab generuje raport w postaci (dla K = 3 i problemu opisanego powyżej):
[wynik,decyzje] = program(3,wyplaty)
wynik =
6
decyzje =
1 2
1 2
2 1
Dodatkowo wyrysowuje dwa drzewa decyzyjne:
Układ drzewa decyzyjnego wszystkich dostępnych rozwiązań tego problemu:
Którego analizę zamieszczono poniżej:
A także ścieżkę podjętych decyzji:
Której analiza wygląda następująco:
5. Wnioski
Za pomocą drzew decyzyjnych możliwa jest konstrukcja zadania o strukturze bardziej
skomplikowanej, niż w przypadku gier macierzowych o sumie zerowej. W przypadku gier
jednoetapowych (każdy z decydentów podejmuje decyzję jednokrotnie) znalezienie rozwiązania
polega na przeglądzie dostępnych strategii i sprowadzeniu problemu do gry macierzowej.
W przypadku gier wieloetapowych (każdy z decydentów podejmuje decyzję wielokrotnie) problem
znacznie się komplikuje. Rozwiązania takiego problemu należy szukać metoda rekurencyjną,
rozwiązywania podgier jednoetapowych.
Ponadto drzewa decyzyjne są prostym i wygodnym sposobem wizualizacji zagadnień związanych z
podejmowaniem decyzji. Analiza poprawnie opisanego drzewa decyzyjnego jest intuicyjna
i przyjemna nawet dla osób nie związanych z zagadnieniem komputerowego wspomagania
podejmowania decyzji.
Zastosowanie drzew decyzyjnych w raportach znacznie poprawia ich przejrzystość, natomiast
w dziedzinie informatyki znacznie upraszcza projektowanie bardziej rozbudowanych algorytmów.
Drzewa decyzyjne mogą również zostać wykorzystane w innych celach, jak na przykład dla klasyfikacji
grupy obiektów.
6. Listing
1. Rozwiązanie gry macierzowej o sumie zerowej
Poniższy kod jest przekształceniem kodu wykorzystanego w sprawozdaniu dotyczącym gier
macierzowych o sumie zerowej:
function [gracz1, maks, gracz2, mini] = lab1(A)
maksy = max(A');
miny = min(A);
maks = min(maksy); %poziom bezpieczeństwa dla minimalizującego
mini = max(miny); %poziom bezpieczeństwa dla maksymalizującego
for i = 1 : length(maksy)
if(maksy(i)== maks)
disp('gracz pierwszy(minimalizuje) gra: ');
disp(i);
gracz1 = i;
end
end
for i = 1 : length(miny)
if(miny(i)== mini)
disp('gracz drugi(maksymalizuje) gra: ');
disp(i);
gracz2 = i;
end
end
if(maks == mini)
disp('istnieje punkt siodłowy');
end
end
2. Rozwiązanie problemu wieloetapowego
Poniższy kod rozwiązuje problem wieloetapowy o K etapach, zwracając wynik, oraz wyrysowuje
drzewa decyzyjne:
function [ przewaga, decyzje ] = program( K, wyplaty )
if(length(wyplaty) == 4^K)
poziom = zeros(K, 4^K);
poziom(K,:) = wyplaty;
licznik = 1;
A = zeros(2,2);
for k = K : -1 : 2
for i = 1 : 4 : 4^k
A(1,1) = poziom(k,i);
A(1,2) = poziom(k,i+1);
A(2,1) = poziom(k,i+2);
A(2,2) = poziom(k,i+3);
[gracz1, maks, gracz2, mini] = lab1(A);
poziom(k-1,licznik) = A(gracz1,gracz2);
licznik = licznik + 1;
 end
licznik = 1;
end
A(1,1) = poziom(1,1);
A(1,2) = poziom(1,2);
A(2,1) = poziom(1,3);
A(2,2) = poziom(1,4);
[gracz1, maks, gracz2, mini] = lab1(A);
przewaga = A(gracz1,gracz2);
decyzje = zeros(k,2);
for k = 1 : 1 : K
for i = 1 : 4 : 4^k
A(1,1) = poziom(k,i);
A(1,2) = poziom(k,i+1);
A(2,1) = poziom(k,i+2);
A(2,2) = poziom(k,i+3);
if (A(1,1) == przewaga)
decyzje(k,:) = [1 1];
end
if (A(1,2) == przewaga)
decyzje(k,:) = [1 2];
end
if (A(2,1) == przewaga)
decyzje(k,:) = [2 1];
end
if (A(2,2) == przewaga)
decyzje(k,:) = [2 2];
end
end
end
% generacja pełnego drzewa
plot(ntree(2,K*2));
% generacja ście\
ki podjętych decyzji
pozycja = 0;
T = ntree(2,0);
for i = 1 : K
T = nodesplt(T,pozycja);
pozycja = pozycja*2 + decyzje(i,1);
T = nodesplt(T,pozycja);
pozycja = pozycja*2 + decyzje(i,2);
end
plot(T);
else
disp('nieprawidlowy wektor wyplat');
end
end