Gliwice, 19.03.2014

Laboratorium

Komputerowe wspomaganie podejmowania decyzji

Ćw. 1 – Gry macierzowe o sumie zerowej, strategie czyste

Walentek Adrian

Olberek Kamil

AiR, sem. 6, TI-2, sekcja 1

1. Dowolna gra macierzowa o wymiarach 3x4

D1\D2	1	2	3	4
1	2	0	-2	3
2	1	2	-1	2
3	0	3	0	-1

Przedstawiona w powyższej tabeli gra macierzowa może zostać rozegrana na dwa sposoby:

1. Gracz pierwszy D1 chce uzyskać jak najmniejszą stratę (minimalizuje), gracz drugi D2 chce uzyskać jak największy zysk (maksymalizuje)

Strategie bezpieczne gracza D1: i₀ = 2

Odpowiadający im poziom bezpieczeństwa: S1 = 2

Strategie bezpieczne gracza D2: j₀₁ = 1, j₀₂ = 2

Odpowiadający im poziom bezpieczeństwa: S2 = 0

Poziomy bezpieczeństwa nie są sobie równe (S1 != S2), dlatego nie istnieje punkt siodłowy.

1. Gracz pierwszy D1 chce uzyskać jak największy zysk (maksymalizuje), gracz drugi D2 chce uzyskać jak najmniejszą stratę (minimalizuje)

Strategie bezpieczne gracza D1: i₀₁ = 2, i₀₂ = 3

Odpowiadający im poziom bezpieczeństwa: S1 = -1

Strategie bezpieczne gracza D2: j₀ = 3

Odpowiadający im poziom bezpieczeństwa: S2 = 0

Poziomy bezpieczeństwa nie są sobie równe (S1 != S2), dlatego nie istnieje punkt siodłowy.

Zmiana ról graczy D1 oraz D2 spowodowała otrzymanie innych strategii bezpiecznych i innych poziomów bezpieczeństwa.

1. Program realizujący powyższą grę macierzową

Kod programu:

function program(A, rola) [Nx,Ny]=size(A); %'maxmin'; %pierwszy maksymalizuje, drugi minimalizuje %'minmax'; %pierwszy minimalizuje, drugi maksymalizuje %-------------------------------------------------- if rola=='maxmin' A=A'; [Nx,Ny]=size(A); end %gracz pierwszy if rola=='maxmin' disp('Gracz drugi (kolumknowy) maksymalizujacy'); else disp('Gracz pierwszy (wierszowy) minimalizujacy'); end for i=1:Nx Tab_max(i)=max(A(i,:)); end S_D1=min(Tab_max); disp(' Strategie bezpieczne:'); for i=1:Nx if S_D1==Tab_max(i) disp([' i=' num2str(i) ]); end end

disp([' Poziom bezpieczeństwa: ' num2str(S_D1)]); %gracz drugi if rola=='maxmin' disp('Gracz pierwszy (wierszowy) minimalizujacy'); else disp('Gracz drugi (kolumnowy) maksymalizujacy'); end for j=1:Ny Tab_min(j)=min(A(:,j)); end S_D2=max(Tab_min); disp(' Strategie bezpieczne:'); for j=1:Ny if S_D2==Tab_min(j) disp([' j=' num2str(j) ]); end end disp([' Poziom bezpieczeństwa: ' num2str(S_D2)]); if S_D1==S_D2 disp(['Punkt siodlowy istnieje. Poziom bezpieczeństwa graczy to: ' num2str(S_D2)]); end if S_D1~=S_D2 disp('Punkt siodlowy nie istnieje.'); end

Wynik działania:

1. Gra macierzowa o wymiarach 6x6

D1\D2	1	2	3	4	5	6
1	-2	-3	1	1	0	1
2	2	-1	1	-1	-3	-1
3	0	-3	-3	-1	1	0
4	0	-2	-3	-2	-2	3
5	2	1	3	0	-1	3
6	1	0	1	0	1	-2

Gracz pierwszy D1 chce uzyskać jak najmniejszą stratę (minimalizuje), gracz drugi D2 chce uzyskać jak największy zysk (maksymalizuje).

Strategie bezpieczne gracza D1: i₀₁ = 1, i₀₂ = 3, i₀₃ = 6

Odpowiadający im poziom bezpieczeństwa: S1 = 1

Strategie bezpieczne gracza D2: j₀₁ = 1, j₀₂ = 4, j₀₃ = 6

Odpowiadający im poziom bezpieczeństwa: S2 = -2

Poziomy bezpieczeństwa nie są sobie równe (S1 != S2), dlatego nie istnieje punkt siodłowy.

Możliwe do uzyskania wyniki gry przy zagraniach strategiami bezpiecznymi:

(i = 1, j = 1) wynik -2	(i = 3, j = 1) wynik 0	(i = 6, j = 1) wynik 1
(i = 1, j = 4) wynik 1	(i = 3, j = 4) wynik -1	(i = 6, j = 4) wynik 0
(i = 1, j = 6) wynik 1	(i = 3, j = 6) wynik 0	(i = 6, j = 6) wynik -2

Patrząc z perspektywy gracza pierwszego D1, najmniej ryzykownym zagraniem jest wybór i = 3, ponieważ najgorszym wynikiem jaki może uzyskać jest 0, gdy gracz D2 wybierze j = 1 lub j = 6, natomiast gdy gracz D2 wybierze j = 4, wynik gry będzie równy -1. Gracz D1 grając na i = 6 może uzyskać lepszy wynik, bo gdy gracz D2 zagra j = 6 uzyskamy -2, lecz istnieje ryzyko, że gracz D2 wybierze j = 1 i wtedy otrzymamy 1. W przypadku zagrania przez gracza D2 j = 4, wynik będzie równy 0. Ostatnią możliwością gracza D1 jest zagranie i = 1. Niestety tutaj wynik gry będzie równy -2 tylko wtedy, gdy gracz D2 zagra j = 1, w pozostałych sytuacjach przy j = 4 lub j = 6 otrzymamy wynik równy 1.

1. Modyfikacja gry, aby istniały pojedyncze strategie bezpieczne

Aby uzyskać pojedyncze strategie dla obu graczy, należy dokonać modyfikacji w odpowiednich wierszach i kolumnach tabeli. Usunięcia strategii bezpiecznych gracza pierwszego D1 można dokonać poprzez zmianę wartości komórek, znajdujących się w danym wierszu (1, 3 lub 6) tak, aby 1 – poziom bezpieczeństwa gracza D1 nie było największą wartością w wierszu. Analogicznie można tego dokonać w przypadku gracza D2, gdzie należy zmienić wartość komórek znajdujących się w 1, 4 lub 6 kolumnie na taką, aby była wartość mniejsza od -2 – poziomu bezpieczeństwa gracza D2.

D1\D2	1	2	3	4	5	6
1	-2	-3	3	1	0	1
2	2	-1	1	-1	-3	-1
3	0	-3	-3	-1	2	0
4	0	-2	-3	-3	-2	3
5	2	1	3	0	-1	-3
6	1	0	1	0	1	-2

Gracz pierwszy D1 chce uzyskać jak najmniejszą stratę (minimalizuje), gracz drugi D2 chce uzyskać jak największy zysk (maksymalizuje).

Strategie bezpieczne gracza D1: i₀ = 6

Odpowiadający im poziom bezpieczeństwa: S1 = 1

Strategie bezpieczne gracza D2: j₀ = 1

Odpowiadający im poziom bezpieczeństwa: S2 = -2

Poziomy bezpieczeństwa nie są sobie równe (S1 != S2), dlatego nie istnieje punkt siodłowy.

1. Modyfikacja gry, aby istniał punkt siodłowy

Aby uzyskać punkt równowagi siodłowej należy tak zmodyfikować wartości tabeli, aby liczba na przecięciu danego wiersza i kolumny była odpowiednio największa w danym wierszu i najmniejsza w danej kolumnie, co spowoduje, że stanie się ona poziomem bezpieczeństwa dla strategii bezpiecznych obu graczy. W naszym przypadku 1 jest już największą wartością w 6 wierszu i jest poziomem bezpieczeństwa gracza D1, dlatego wystarczy zmodyfikować wartości w 1 kolumnie na większe lub równe 1, oczywiście poza komórką (6,1), która jest miejscem przecięcia.

D1\D2	1	2	3	4	5	6
1	2	-3	3	1	0	1
2	2	-1	1	-1	-3	-1
3	1	-3	-3	-1	2	0
4	1	-2	-3	-3	-2	3
5	2	1	3	0	-1	-3
6	1	0	1	0	1	-2

Gracz pierwszy D1 chce uzyskać jak najmniejszą stratę (minimalizuje), gracz drugi D2 chce uzyskać jak największy zysk (maksymalizuje).

Strategie bezpieczne gracza D1: i₀ = 6

Odpowiadający im poziom bezpieczeństwa: S1 = 1

Strategie bezpieczne gracza D2: j₀ = 1

Odpowiadający im poziom bezpieczeństwa: S2 = 1

Poziomy bezpieczeństwa są sobie równe (S1 = S2), dlatego istnieje punkt siodłowy. Wartość punktu siodłowego wynosi 1 dla strategii punktu siodłowego (i₀,j₀)=(6,1).

1. Wprowadzenie hierarchii (dynamiki) w grze

Wprowadzenie hierarchii w grze ma znaczny wpływ na jej wynik, ponieważ gracz grający jako drugi zna wybór gracza pierwszego i w zależności od tego wyboru, może wykonać ruch zapewniający mu możliwie jak najlepszy wynik. Gracz pierwszy dokonując wyboru musi pamiętać o tym, że następny gracz będzie starał się osiągnąć jak najlepszy wynik, dlatego powinien rozważyć zagranie w strategie bezpieczną, która da mu możliwie najlepszy wynik przy dowolnym zagraniu gracza drugiego.