Sztuczna Inteligencja 520
zajęcia X - 11 grudnia 2003
wprowadzenie do teorii gier
Teoria gier jest dziedziną wiedzy zajmującą się teoretycznym opisem sytuacji, w których występuje konflikt interesów. Wbrew temu, co może sugerować nazwa, tradycyjne gry towarzyskie (planszowe, karciane itp.) stanowią tylko część bardzo szerokiej problematyki teorii gier. Teorię gier cechuje interdyscyplinarność, przede wszystkim wiąże się ją z naukami ekonomicznymi, a także z psychologią, biologią, matematyką.
proste gry macierzowe
Elementarz teorii gier stanowią tzw. gry macierzowe. Gra macierzowa to gra dwuosobowa o sumie zerowej i o skończonej liczbie strategii dla każdego z graczy. Gra o sumie zerowej to taka gra, w której wygrana zwycięzcy jest równa stracie przegranego.
Możliwe wyniki gry macierzowej przedstawia się zwykle w postaci tabeli (macierzy) wypłat. Poniżej podano przykład prostej gry macierzowej.
| Pani Kolumna | |||
|---|---|---|---|
| A | B | ||
| Pan Wiersz | A | 2 | -3 |
| B | 0 | 2 | |
| C | -5 | 10 | |
W powyższej grze bierze udział dwóch graczy: Pan Wiersz i Pani Kolumna. Pan Wiersz ma do wyboru trzy strategie: A, B lub C, zaś Pani Kolumna dwie - A lub B. Zakłada się, że oboje gracze równocześnie podejmują decyzje o wyborze strategii. Wypłaty (wygrane) Pana Wiersza można odczytać na przecięciu odpowiedniego wiersza i kolumny. Ponieważ jest to gra o sumie zerowej, nie trzeba wypisywać wypłat Pani Kolumny (są to po prostu przeciwieństwa wypłat Pana Wiersza). Wypłaty można traktować jako nagrody pieniężne. Jeśli np. Pan Wiersz wybierze strategię C, natomiast Pani Kolumna strategię A, Pani Kolumna wygra 5 (powiedzmy dolarów) i tyle straci Pan Wiersz.
Ćwiczenie Podać macierz wypłat dla gry "kamień, nożyce, papier".
Ćwiczenie Podać strategie optymalne dla poniższych gier macierzowych. Podać wartość gry. (Wartość gry to wypłata gracza przy wybraniu przez obu graczy strategii optymalnych.)
| A | B | C | |
| A | -1 | 5 | 0 |
| B | -1 | 2 | 1 |
| C | 0 | 5 | 2 |
| A | B | C | |
| A | -1 | 0 | 5 |
| B | 6 | 3 | 4 |
| A | B | C | |
| A | -2 | 0 | 4 |
| B | 2 | 1 | 3 |
| C | 3 | -1 | -2 |
| A | B | C | D | |
| A | 4 | 2 | 5 | 2 |
| B | 2 | 1 | -1 | -20 |
| C | 3 | 2 | 4 | 2 |
| D | -16 | 0 | 16 | 1 |
| A | B | C | D | |
| A | 3 | -6 | 2 | -4 |
| B | 2 | 1 | 0 | 1 |
| C | -4 | 3 | -5 | 4 |
| A | B | |
| A | 2 | -3 |
| B | 0 | 3 |
(W ostatnim przykładzie strategią optymalną będzie pewna strategia mieszana. Ze strategią mieszaną mamy do czynienia wtedy, gdy właściwe strategie wybierane są z pewnym prawdopodobieństwem.)
Zadanie X.1 Podać strategie optymalne obu graczy dla podanych poniżej gier macierzowych. Podać wartość gry.
| A | B | C | |
| A | -2 | 5 | -4 |
| B | -1 | -3 | 1 |
| C | 0 | 5 | 2 |
| A | B | C | |
| A | -50 | 100 | 0 |
| B | 15 | 10 | 5 |
| A | B | C | D | |
| A | 4 | 3 | 2 | 5 |
| B | -10 | 2 | 0 | -1 |
| C | 7 | 5 | 2 | 3 |
| D | 0 | 8 | -4 | -5 |
[110 pkt; do 2003-12-31 23:59].
gry o sumie niezerowej
W grze o sumie zerowej interesy graczy są dokładnie przeciwstawne (wygrana jednego gracza jest równa stracie drugiego). W przypadku gier o sumie niezerowej interesy graczy mogą być częściowo zbieżne. Gry takie są zwykle trudniejsze do rozwiązania niż gry macierzowe o sumie zerowej.
gra w "cykora"
Dwa samochody jadą naprzeciw siebie z dużą prędkością. Możliwe są dwie strategie: A - stchórzyć i skręcić w prawo (i uniknąć w ten sposób zderzenia, ale stracić honor), B - być twardzielem i jechać naprzód. Poniżej podano wypłaty w takiej grze, pierwsza liczba to wypłata Pana Wiersza, druga - Pani Kolumny.
| A | B | |
| A | 0/0 | -2/1 |
| B | 1/-2 | -8/-8 |
inne przykłady gier o sumie niezerowej
| A | B | |
| A | 2/3 | 3/2 |
| B | 1/0 | 0/1 |
| A | B | |
| A | 2/4 | 1/0 |
| B | 3/1 | 0/4 |
| A | B | |
| A | 1/1 | 2/5 |
| B | 5/2 | -1/-1 |
dylemat więźnia
Dylemat więźnia jest najsłynniejszą grą o sumie niezerowej. W pojedynczej rozgrywce uczestniczy dwóch graczy. Każdy z nich może "współpracować" (decyzja W) lub "zdradzić" (decyzja Z). Decyzję obaj gracze podejmują równocześnie. Jeśli obydwu zechce współpracować, każdy z nich otrzymuje po $5 ("zgoda buduje"). Jeśli któryś z nich zdradzi, a drugi chce współpracować, to zdrajca otrzymuje $6, a jego przeciwnik nic nie wygrywa ("oszust trafił na frajera"). Natomiast jeśli obaj oszukują, każdy z nich otrzymuje tylko po $2 ("trafiła kosa na kamień"). Oto macierz wypłat dla takiej gry:
| W | Z | |
| W | 5/5 | 0/6 |
| Z | 6/0 | 2/2 |
Ogólnie dylemat więźnia przedstawia się następująco:
| W | Z | |
| W | R/R | S/T |
| Z | T/S | UU |
gdzie R - nagroda za współpracę, S - wypłata frajera, T - wypłata za jednostronną zdradę, U - wypłata w przypadku obopólnej zdrady, przy czym spełnione muszą być następujące warunki: T > R > U > S i R >= (S+T)/2.
Zadanie X.2 Wyjaśnić, dlaczego powyższe dwa warunki muszą być spełnione, by można było mówić o dylemacie więźnia [80 pkt; do 2003-12-23 22:00].
W dylemat więźnia można zagrać z komputerem w Internecie.
Zwykle rozpatrywany jest iterowany dylemat więźnia, w którym gra jest wielokrotnie powtarzana i gracze znają wyniki wcześniejszych rozgrywek.
Turniej
Zadanie X.3 Wystawić gracza do Turnieju [525 pkt; do 2004-01-07 22:00].
8 stycznia 2004 r. zostanie rozegrany turniej programów grających w proste gry macierzowe o sumie niezerowej.
Rozegranych zostanie 5000 rund. W każdej rundzie każdy gracz zmierzy się z każdym innym. Dla każdej rundy zostanie wylosowana pewna gra o sumie niezerowej. W każdej z tych gier obaj gracze będą mieli dwie strategie A i B do wyboru. Gry są symetryczne (żaden gracz nie jest poszkodowany) i macierz wypłat wygląda (dla każdego z graczy) następująco:
| A | B | |
| A | X | Y |
| B | Z | V |
Parametry X, Y, Z, V są losowane dla każdej rundy osobno. Są to liczby całkowite z zakresu od 0 do 9, przy czym zawsze X > V.
(Warto zauważyć, że często może być losowany dylemat więźnia, np. dla X = 5, Y = 0, Z = 6, V = 2.)
przykład
Załóżmy, że w danej rundzie wylosowano następujące parametry: X = 4, Y = 2, Z = 9, V = 0. Otrzymamy następującą macierz wypłat:
| A | B | |
| A | 4 | 2 |
| B | 9 | 0 |
Zauważmy, że gra ta przypomina grę w cykora, strategia A to strategia mięczaka, B - twardziela. Czy wybrać strategię B i zyskać aż 9 pkt (ale ryzykować brak wygranej, jeśli przeciwnik też będzie twardzielem), czy pozostać przy "bezpiecznej" strategii A (gwarantującej przynajmniej 2 pkt)? Można np. badać zachowanie przeciwnika w podobnych grach w poprzednich rundach i sprawdzić, czy przeciwnik jest twardzielem (ryzykantem), czy nie.
jak zaprogramować gracza?
Wszystkie pliki potrzebne do rozegrania turnieju zawarte są w archiwum turniej.tar.gz. (Aby rozpakować archiwum, należy skopiować je do własnego katalogu i wydać polecenie tar zvxf turniej.tar.gz.) Aby skompilować "środowisko" turnieju (razem z graczami), należy wydać polecenie make. Wpierw trzeba jednak wygenerować plik Makefile używając skryptu genmake.pl w następujący sposób:
perl genmake.pl N < listagraczygdzie N to liczba rund, natomiast listagraczy to plik tekstowy zawierający spis graczy (opis każdego gracza w jednym wierszu, najpierw identyfikator gracza, a następnie po spacji dowolny opis gracza).
Każdy student musi dostarczyć pojedynczy plik zawierający definicję funkcji w języku C opisującej gracza. Nazwa pliku to graczN.c, gdzie N to numer indeksu studenta. Funkcja opisująca sposób działania gracza ma mieć nazwę graczN, gdzie N - numer indeksu.
Uwaga: za brak zgłoszenia gracza do Turnieju student otrzymuje -100 pkt.
Funkcja graczN ma pięć argumentów, pierwszy to numer
rundy (nr_rundy), cztery następne to parametry gry w
danej rundzie, czyli wyplataAA (X) - wypłata, kiedy
ja gram A i przeciwnik też gra A, wyplataAB (Y) -
wypłata, kiedy ja gram A, a przeciwnik gra B, wyplataBA
(Z) - wypłata, kiedy ja gram B, a przeciwnik gra A,
wyplataBB (V) - wypłata, kiedy ja gram B i
przeciwnik też gra B.
Funkcja graczN musi wyliczyć, którą strategię wybierze
gracz w konkretnym pojedynku z konkretnym przeciwnikiem w danej
rundzie. Jeśli wybrano strategię A, należy zwrócić znak
'A', jeśli wybrano strategię B - znak 'B'.
Każda inna odpowiedź z funkcji graczN będzie traktowana
jak wybór strategii A.
Przy wybieraniu strategii można odwołać się do informacji o
wynikach (i parametrach) poprzednich pojedynków z danym przeciwnikiem.
Służą do tego funkcje: podaj_moja_decyzje,
podaj_decyzje_przeciwnika,
podaj_moja_wyplate,
podaj_wyplate_przeciwnika, podaj_wyplateAA,
podaj_wyplateAB, podaj_wyplateBA,
podaj_wyplateBB. Uwaga: przy danym
wywołaniu funkcji graczN wolno korzystać tylko z
informacji dotyczących rozgrywek z przeciwnikiem, z którym pojedynkuje
się w danej chwili gracz. Nie można uzyskać informacji o wynikach
pojedynków, w których nie brało się udziału, ani o pojedynkach z
przeciwnikiem, którego nie dotyczy dane wywołanie funkcji
graczN.
Graczowi nie wolno zapamiętywać niczego między
kolejnymi wywołaniami funkcji graczN - dlatego
nie wolno stosować zmiennych globalnych ani zmiennych
statycznych. Można jedynie "przypominać" sobie dane o poprzednich
pojedynkach z konkretnym przeciwnikiem za pomocą funkcji
podaj....
W funkcji graczN można tylko dokonywać obliczeń.
Zabronione jest użycie funkcji wejścia-wyjścia. Ponadto nie wolno
używać funkcji do przydzielania i zwalniania pamięci
(malloc, free itp.).
Każde wywołanie funkcji graczN musi zakończyć się w
rozsądnym czasie. Sumaryczny czas, w jakim gracz podejmie wszystkie
swoje decyzje (5000 x 11), nie może przekroczyć 10 minut. Uczestnik
turnieju może zostać poproszony o przyspieszenie działania swojego
gracza, jeśli okaże się, że jego wykonanie zajmuje zbyt dużo
czasu.
Każde przesłane rozwiązanie (plik graczN.c) musi zaczynać się komentarzem, w którym powinny znaleźć się następujące informacje:
- numer indeksu, imie i nazwisko studenta,
- kilkuzdaniowy opis sposobu działania gracza.
Oto przykład gracza dla hipotetycznego studenta o indeksie numer 99999:
/*
99999, Xawery Iksinski
Wybieram zawsze strategię A, chyba że wypłata BA jest 2 razy
większa od wypłaty AA.
*/
char gracz99999(int nr_rundy,
int wyplataAA,
int wyplataAB,
int wyplataBA,
int wyplataBB)
{
if(wyplataBA >= 2*wyplataAA)
return 'B';
else
return 'A';
}
w archiwum turniej.tar.gz można znaleźć kilku innych przykładowych graczy, a także wszystkich graczy wystawionych przez studentów w zeszłym roku!
Poniżej podano przelicznik miejsce w turnieju/liczba punktów.
| 1 | 500 |
| 2 | 300 |
| 3 | 100 |
| 4 | 80 |
| 5 | 40 |
| 6 | 30 |
| 7 | 10 |
| 8 | 5 |
| 9 | 0 |
| 10-przedostatnie | -10 |
| ostatnie | -50 |
| brak zgłoszonego gracza | -100 |
(Punktacja od 18 grudnia 2003 uległa zmianie.)
W przypadku równej ilości punktów o kolejności decydować będzie data zgłoszenia gracza (im szybciej, tym lepiej).
Dodatkowo każdy uczestnik może dostać do 35 pkt - za dobry opis, czytelne zaprogramowanie, oryginalny pomysł itp.