Sztuczna inteligencja

Jan Kazimirski

Sztuczna inteligencja

wykład 5

Sztuczna inteligencja

Jan Kazimirski

2

Podstawy teorii

gier

Sztuczna inteligencja

Jan Kazimirski

3

Teoria Gier

●

Zestaw metod i modeli pozwalających analizować
zachowania i strategie w sytuacji konfliktu

interesów.

●

Zastosowania teorii gier:

–

Ekonomia

–

Biologia

–

Socjologia

–

Informatyka (sztuczna inteligencja)

Sztuczna inteligencja

Jan Kazimirski

4

John Nash

●

Urodzony w 1928 r.

●

Nagroda Nobla 1994r.

●

Pojęcie równowagi Nasha

●

Film „A Beautiful Mind”

Sztuczna inteligencja

Jan Kazimirski

5

Gra

●

Zestaw reguł określający jakie działania mogą
podejmować gracze w trakcie interakcji

●

Zasady gry określają jakimi informacjami
dysponują gracze

●

Zasady gry określają też zyski i straty związane z
działaniami graczy

●

Teoria gier sugeruje optymalne zachowania i
bada właściwości poszczególnych rodzajów gier

Sztuczna inteligencja

Jan Kazimirski

6

Charakterystyka gry

●

Gracze – Obiekty (ludzie, firmy, państwa)
uczestniczące w grze

●

Zasady gry

●

Strategia – wybrany przez gracza sposób
rozgrywki

●

Wynik gry – zdeterminowany przez strategie
wybrane przez graczy

●

Wypłata – przypada graczowi zależnie od wyniku

Sztuczna inteligencja

Jan Kazimirski

7

Typy gier

●

Kooperacyjne i niekooperacyjne – dla większego
zbioru graczy:

–

Gra kooperacyjna – gracze współpracują ze sobą

(np. gry ekonomiczne)

–

Gra niekooperacyjna – poszczególni gracze

działają niezależnie od siebie

Sztuczna inteligencja

Jan Kazimirski

8

Typy gier c.d.

●

Gry strategiczne i ekstensywne

–

Gra strategiczna – gracze określają swój plan

działania (strategię) i działają jednocześnie

–

Gra ekstensywna (gra pozycyjna) – gracze

podejmują decyzję na podstawie aktualnej

pozycji. Grę można opisać w postaci drzewa

decyzji

Sztuczna inteligencja

Jan Kazimirski

9

Typy gier c.d.

●

Gry o pełnej lub niepełnej informacji

–

Gra o pełnej informacji – w momencie

podejmowania decyzji gracz dysponuje pełną

informacją o aktualnej sytuacji i możliwościach

przeciwnika (np. szachy)

–

Gra o niepełnej informacji – gracz podejmuje

decyzję nie mając pełnej informacji o sytuacji i

możliwościach przeciwnika (np. brydż)

Sztuczna inteligencja

Jan Kazimirski

10

Typy gier c.d.

●

Gry nieantagonistyczne i antagonistyczne

–

Gra antagonistyczna – cele graczy są

przeciwstawne. Wygrana jednego z graczy to

przegrana innych

–

Gra nieantagonistyczna – nie wszyscy gracze

dążą do maksymalizacji zysków

Sztuczna inteligencja

Jan Kazimirski

11

Typy gier c.d.

●

Gry o sumie zerowej i niezerowej

–

Gra o sumie zerowej – wygrana jednego gracza

wiąże się z przegraną drugiego

–

Gra o sumie stałej – uogólnienie gry o sumie

zerowej

–

Gra o sumie niezerowej – gra w której wypłaty

mogą być „tworzone” lub „niszczone”.

Sztuczna inteligencja

Jan Kazimirski

12

Typy gier c.d.

●

Gry rozgrywane jednokrotnie lub wielokrotnie (gry
sekwencyjne)

●

Gry dwuosobowe lub n-osobowe

●

Gry ze skończoną lub nieskończoną liczbą
strategii

●

Gry losowe lub deterministyczne

Sztuczna inteligencja

Jan Kazimirski

13

„Racjonalny” gracz

●

Modele teorii gier zakładają że gracz zachowuje
się racjonalnie, tzn.

–

Gracz zna zasady gry i reguły wypłat

–

Gracz jest w stanie określić który z wyników jest

lepszy

–

Gracz zdaje sobie sprawę że inni gracze też są

racjonalni i potrafi określić strategie jakie mogą

wybrać

Sztuczna inteligencja

Jan Kazimirski

14

Gra strategiczna

●

W grze uczestniczy N graczy.

●

Każdy z graczy może podjąć określoną decyzję

●

Decyzje podejmowane są jednorazowo

●

Decyzje graczy są jednoczesne

●

Każda decyzja związana jest z określonym
wynikiem.

Sztuczna inteligencja

Jan Kazimirski

15

Macierz wypłat

(W1,W2)

(W1,W2)

(W1,W2)

(W1,W2)

GRACZ 2

GRACZ 1

A

B

A

B

Macierz wypłat

Określa korzyści każdego z graczy
w zależności od strategii
wybranych przez obu graczy

A,B – wybrane strategie

W1,W2 – wypłaty gracza 1 i 2
zależnie od wybranych strategii

Sztuczna inteligencja

Jan Kazimirski

16

Strategie dominujące

●

Strategia dominująca – strategia przynosząca
graczowi najwyższą wypłatę niezależnie od

zachowania drugiego gracza

●

Jeżeli każdy z graczy ma strategię dominującą to

zapewne ją wybierze jako najkorzystniejszą – gra
posiada stan równowagi

●

Strategię dominującą może posiadać tylko jeden
gracz lub może nie być jej w ogóle

Sztuczna inteligencja

Jan Kazimirski

17

Równowaga Nasha

●

Strategie graczy tworzą równowagę graczy jeżeli
maksymalizują wypłatę gracza przy danym

wyborze drugiego gracza

●

Każdy z graczy dokonał wyboru

maksymalizującego jego wypłatę. Żadnemu nie
opłaca się odstępstwo

●

Gra może posiadać wiele równowag Nasha, lub
nie mieć żadnej.

Sztuczna inteligencja

Jan Kazimirski

18

Strategie dominujące – przykład 1

(10,10)

(5,5)

(3,3)

(1,1)

GRACZ 2

GRACZ 1

A

B

A

B

Dla każdego z graczy strategią
dominującą jest strategia A

Para strategii dominujących to
(A,A). Przyniosą one obu graczom
największe zyski

Sztuczna inteligencja

Jan Kazimirski

19

Strategie dominujące – przykład 2

(10,10)

(3,3)

(11,5)

(1,1)

GRACZ 2

GRACZ 1

A

B

A

B

Dla gracza 2 strategią dominującą
jest strategia A.

Gracz 1 nie ma strategii
dominującej (jeżeli gracz 2
wybierze A to powinien wybrać B,
jeżeli gracz 2 wybierze B to
powinien wybrać A)

Sztuczna inteligencja

Jan Kazimirski

20

Strategie dominujące – przykład 3

(10,10)

(3,11)

(11,2)

(1,1)

GRACZ 2

GRACZ 1

A

B

A

B

Dla żadnego z graczy nie istnieje
strategia dominująca

Sztuczna inteligencja

Jan Kazimirski

21

Równowaga Nasha – przykład 1

(2,2)

(2,1)

(1,4)

(4,4)

GRACZ 2

GRACZ 1

A

B

A

B

Para strategii (A,A) tworzy
równowagę Nasha

Jeżeli gracz 1 wybierze strategię A
to gracz 2 też powinien wybrać
strategię A (2>1)

Jeżeli gracz 2 wybierze strategię A
to gracz 1 też powinien ją wybrać
(2>1)

Sztuczna inteligencja

Jan Kazimirski

22

Równowaga Nasha – przykład 2

(2,2)

(2,3)

(3,4)

(1,3)

GRACZ 2

GRACZ 1

A

B

A

B

Dwie równowagi Nasha: (A,B) i
(B,A)

Jeżeli gracz 1 wybierze A to gracz
2 powinien wybrać B, jeżeli gracz 2
wybierze B to gracz 1 powinien
wybrać A

Jeżeli gracz 1 wybierze B to gracz
2 powinien wybrać A, jeżeli gracz 2
wybierze A to gracz 1 powinien
wybrać B

Sztuczna inteligencja

Jan Kazimirski

23

Równowaga Nasha – przykład 3

(7,5)

(3,6)

(6,2)

(4,1)

GRACZ 2

GRACZ 1

A

B

A

B

Brak równowag Nasha

Jeżeli gracz 1 wybierze A to gracz
2 powinien wybrać B. Jeżeli gracz
2 wybierze B to gracz 1 powinien
wybrać B.

Jeżeli gracz 1 wybierze B to gracz
2 powinien wybrać 2. Jeżeli gracz 2
wybierze A to gracz 1 powinien
wybrać A.

Sztuczna inteligencja

Jan Kazimirski

24

„Wojna płci”

●

Klasyczny przykład z teorii gier

●

Para (kobieta i mężczyzna) umówili się na
spotkanie. Niestety zapomnieli gdzie się miało
odbyć. Do wyboru jest: opera lub mecz piłkarski.

●

Kobieta preferuje operę, mężczyzna mecz.

Sztuczna inteligencja

Jan Kazimirski

25

„Wojna płci” c.d.

(3,2)

(0,0)

(0,0)

(2,3)

M

K

O

F

O

F

Gracze: K – kobieta, M - meżczyzna

Strategie: O – opera, F - mecz

Przykład gry kooperacyjnej

Dwie równowagi Nasha: (O,O) i (F,F)

Sztuczna inteligencja

Jan Kazimirski

26

„Gra w tchórza”

●

Dwie osoby wsiadają do samochodów i z dużą
prędkością jadą naprzeciwko siebie. Kto pierwszy

skręci – jest tchórzem. Jeżeli żaden nie skręci –
obaj giną w wypadku

Sztuczna inteligencja

Jan Kazimirski

27

„Dylemat więźnia”

●

Najbardziej znany przykład z teorii gier

●

Dwóch podejrzanych umieszczono w osobnych
celach i przesłuchano. Jeżeli obaj się przyznają –
otrzymają obniżoną karę, jeżeli jeden się przyzna

to będzie wolny a drugi odbędzie karę, jeżeli
żaden się nie przyzna to obaj otrzymają niewielką
karę.

Sztuczna inteligencja

Jan Kazimirski

28

„Dylemat więźnia” c.d.

(1,1)

(10,0)

(0,10)

(5,5)

W2

W1

W

Z

W

Z

Więźniowie: W1 i W2

Strategie: W – współpraca, Z – zdrada

„Wypłaty” to liczba lat więzienia.

Dla każdego z graczy lepszą strategią jest
zdrada.
Np. dla W1 zdrada jest korzystniejsza: jeżeli W2
współpracuje to 0 jest lepsze niż 1. Jeżeli W2
zdradził to 5 jest lepsze niż 10.

Gdyby jednak obaj więźniowie współpracowali
to obaj zyskają najwięcej

Sztuczna inteligencja

Jan Kazimirski

29

Iterowany dylemat więźnia

●

Wersja gry w której jest ona powtarzana
wielokrotnie przez tych samych graczy

●

Gracze ustalają strategię na bazie poprzednich
wyników gry

●

Przy skończonej liczbie tur optymalną dla gracza
strategią jest zdrada

●

W przypadku nieznanej liczby tur zaczyna się
pojawiać współpraca

Sztuczna inteligencja

Jan Kazimirski

30

Iterowany dylemat więźnia c.d.

●

W 1984 roku – turniej programów grających w
iterowany dylemat więźnia

●

Różne strategie – egoistyczne, altruistyczne

●

Najlepsza strategia – deterministyczna strategia
„wet za wet” (pierwsza gra – współpraca, później
to, co poprzednio zrobił przeciwnik)

Sztuczna inteligencja

Jan Kazimirski

31

Gra dwumacierzowa

●

Wszystkie przedstawione przykłady opisują tzw.
gry „dwumacierzowe” - rezultat gry można

przedstawić w postaci dwóch macierzy wypłat
(dla 1 i 2 gracza).

●

Gra dwumacierzowa składa się z nastepujących
elementów:

–

Zbiory strategii graczy

–

Macierzy wypłat dla każdego z graczy

Sztuczna inteligencja

Jan Kazimirski

32

„Papier, nożyce, kamień”

●

Strategie: P – papier, N – nożyce, K – kamień

●

Macierze wypłat graczy:
A = ((0,-1,1),(1,0,-1),(-1,1,0))
B = ((0,1,-1),(-1,0,1),(1,-1,0))

●

Gra nie posiada równowagi.

Sztuczna inteligencja

Jan Kazimirski

33

Strategia mieszana

●

Strategia mieszana domyślnie zakłada że gra
będzie powtarzana – gdyż wprowadza do wyboru

strategii element losowy (prawdopodobieństwo)

●

Strategia mieszana określa prawdopodobieństwa

z jakimi gracz wybierze swoje strategie

●

Można wykazać że dla każdej gry o sumie stałej

istnieje optymalna strategia mieszana

Sztuczna inteligencja

Jan Kazimirski

34

Strategia mieszana c.d.

●

Wypłata w przypadku strategii mieszanej będzie
sumą elementów określających

prawdopodobieństwa wyborów określonych
strategii graczy mnożonych przez odpowiedni
element macierzy wypłat

●

Strategia czysta – przypadek szczególny – jedna
ze strategii ma prawdopodobieństwo 1, pozostałe

- 0.

Sztuczna inteligencja

Jan Kazimirski

35

„Papier, nożyce, kamień” c.d.

●

W przypadku strategii czystych gra nie posiada
równowagi.

●

W przypadku strategii mieszanych gra posiada
równowagę. Będzie nią para strategii p i q:

p = (1/3 , 1/3 , 1/3)
q = (1/3 , 1/3 , 1/3)

Sztuczna inteligencja

Jan Kazimirski

36

Gra ekstensywna o pełnej informacji

●

Charakterystyka gry

–

Gracze

–

Zbiór sekwencji decyzji graczy

–

Gracze decydują po kolei

–

Gracze znają całą historię poprzednich decyzji

Sztuczna inteligencja

Jan Kazimirski

37

Terminologia

●

Historia – element zbioru sekwencji

●

Akcja – pojedynczy element historii

●

Gra skończona – skończony zbiór historii

●

Skończona najdłuższa historia – gra ma
skończony horyzont

●

Pusta historia jest początkowym elementem gry

Sztuczna inteligencja

Jan Kazimirski

38

Reprezentacja gry

●

Wygodną reprezentacją gry ekstensywnej
(pozycyjnej) jest drzewo.

●

Wierzchołek drzewa reprezentuje początek gry

●

Gałęzie reprezentują możliwe decyzje
poszczególnych graczy

●

Przy każdej pozycji końcowej umieszczone są
wartości wypłaty

Sztuczna inteligencja

Jan Kazimirski

39

Reprezentacja gry c.d.

1,0

1,0

1,0

0,0

0,0

0,0

0,0

0,1

Decyzja gracza 1

Decyzja gracza 2

0,0

Sztuczna inteligencja

Jan Kazimirski

40

Przeszukiwanie drzewa gry

●

Wybór najlepszego ruchu w grze sprowadza się
do przeszukiwania zbioru historii

●

Zagadnienie przeszukiwania:

–

Stany – sytuacja na planszy ze wskazaniem

gracza wykonującego ruch

–

Operatory – możliwe ruchy gracza

–

Stan początkowy – stan w którym zaczyna się

poszukiwanie

–

Stany końcowe – stany rozstrzygające grę

Sztuczna inteligencja

Jan Kazimirski

41

Poszukiwanie c.d.

●

Poszukiwanie optymalnego ruchu komplikuje
obecność drugiego gracza

●

Należy przyjąć założenie, że przeciwnik wykonuje
ruchy najkorzystniejsze dla siebie – a więc

najmniej korzystne dla gracza

Sztuczna inteligencja

Jan Kazimirski

42

Strategie minimaksowe

●

Każdy węzeł drzewa gry ma przypisaną ocenę
szansy wygranej gry

●

Poszukiwanie:

–

Ruch gracza – wybór maksymalizujący szansę

wygrania gry

–

Ruch przeciwnika – wybór minimalizujący szansę

wygrania gry

Sztuczna inteligencja

Jan Kazimirski

43

Zasada minimaksu

●

Na węzłach terminalnych określamy ich „użyteczność” z
punktu widzenia gracza

–

Wartość dodatnia – wygrana gracza

–

Wartość ujemna – wygrana przeciwnika

–

Zero – remis

●

Cofając się w górę drzewa nadajemy węzłom wartości

–

Poziom gracza – maksimum wartości węzłów potomnych

–

Poziom przeciwnika – minimum wartości węzłów

potomnych

Sztuczna inteligencja

Jan Kazimirski

44

Pełny minimaks

●

Algorytm pełnego minimaksu zakłada budowanie
pełnego drzewa gry

●

Może być zaimplementowany za pomocą
podejścia rekurencyjnego

●

Dla wielu gier rozwiązanie takie jest bardzo
trudne – ze względu na rozmiar drzewa gry (np.

szachy)

Sztuczna inteligencja

Jan Kazimirski

45

Obcięty minimaks

●

Analizę drzewa gry zatrzymuje się na określonej
głębokości

●

Obcięcie wymaga oceny „użyteczności” węzła
bez znajomości rezultatu gry ani węzłów

potomnych

●

Zastosowanie heurystycznej funkcji oceny jakości

węzła

Sztuczna inteligencja

Jan Kazimirski

46

Usprawnienia algorytmu

●

Zastosowanie obcięcia o zmiennej głębokości.
Drzewo jest rozwijane jeżeli funkcja oceny nie

daje odpowiedniej pewności

●

Stopniowe budowanie drzewa w trakcie rozgrywki

– wykorzystywanie wcześniej wyliczonych
wartości

Sztuczna inteligencja

Jan Kazimirski

47

Cięcia alfa-beta

●

Cięcie alfa – oceniając węzeł poprzez maksymalizację

ocen węzłów potomnych można zrezygnować z analizy

węzła potomnego po stwierdzeniu że ocena musi być

niższa niż dotychczasowe maksimum

●

Cięcie beta – przy ocenie przez minimalizację ocen

węzłów potomnych można zrezygnować z analizy węzła

potomnego po stwierdzeniu że jego ocena musi być

wyższa niż dotychczasowe minimum

Sztuczna inteligencja

Jan Kazimirski

48

Heurystyczna ocena węzłów

●

Jakość funkcji oceny przy niepełnym minimaksie
ma niezwykle duże znaczenie

●

Powinna uwzględniać „siłę” pozycji gracza (np.
liczbę figur, ich ustawienie itp.)

●

W zaawansowanych programach wykorzystuje
się funkcje uczące się na podstawie

dotychczasowych rozgrywek