AI_6_1

Gry

Poka

emy, w jaki sposób agent mo

osi

ąć

zamierzony cel je

eli musi

kooperowa

lub konkurowa

albo nawet

walczy

z innymi agentami.

© F.A. Dul 2007

walczy

z innymi agentami.

6.1. Czym s

gry?

Istota gier: s

to zadania z wieloma agentami działaj

cymi

(konkuruj

cymi) w tym samym

rodowisku.

• Co robi

inni agencji i w jaki sposób wpływaj

na działania naszego agenta?

•

rodowiska wieloagentowe mog

kooperatywne

lub konkurencyjne;

• Konkurencyjne

rodowiska wieloagentowe prowadz

do zada

poszukiwania z przeciwnikiem, czyli gier.

© F.A. Dul 2007

do zada

poszukiwania z przeciwnikiem, czyli gier.

Jaki jest cel analizy gier?

• Zabawa, hazard;
• S

to zagadnienia interesuj

ce, ale cz

sto bardzo

trudne;

• S

łatwe do sformułowania; agenci mog

zwykle

wykonywa

niewiele działa

;

• Słu

y budowie robotów które maj

działa

rodowisku

nieprzyjaznym;

Relacja gier i poszukiwa

Poszukiwania – nie ma przeciwnika.

• Rozwi

zanie jest heurystyczn

metod

osi

gni

cia celu.

• Heurystyki i CSP mog

znale

źć

rozwi

zanie optymalne.

• Funkcja szacuj

ca - oszacowanie kosztu przej

cia

od startu do celu poprzez dany w

zeł.

• Przykłady: planowanie dróg, opracowywanie

harmonogramów.

6.1. Gry

© F.A. Dul 2007

Gry – s

przeciwnicy.

• Rozwi

zanie jest

strategi

gry

, czyli odpowiedzi

na ka

de działanie przeciwnika;

• Ograniczenia czasowe gry wymuszaj

znajdywanie

rozwi

przybli

onych.

• Funkcja szacuj

ca - oszacowanie „dobroci” sytuacji.

• Przykłady: szachy, warcaby, Trik-trak (backgammon),

kółko i krzy

yk (Tic-Tac-Toe), Othello, Go.

Klasyfikacja gier

6.1. Gry

Deterministyczne

Hazardowe

Informacja
pełna

Szachy,
Warcaby,
Go,
Othello,
Kółko i krzy

Trik-trak
(backgammon),
Monopoly

© F.A. Dul 2007

Kółko i krzy

Informacja
niepełna

Bryd

Poker,
Scrabble,
wojna atomowa

6.2. Definicja gry

W grze uczestnicz

dwaj gracze: MAX i MIN.

Gra jako poszukiwanie

• Stan pocz

tkowy: np. ustawienie szachów

na szachownicy;

• gr

rozpoczyna MAX;

• ruchy wykonuj

naprzemian a

do zako

czenia gry;

• zwyci

zca otrzymuje nagrod

, przegrany ponosi kar

© F.A. Dul 2007

na szachownicy;

• Funkcja nast

pnika: lista ruchów (stanów) spełniaj

cych

reguły gry;

• Test ko

ca - czy gra si

zako

czyła?

• Funkcja u

yteczno

ci - definiuje warto

ci stanów

cowych, np. zwyci

zca (+1), przegrany (-1)

oraz remis(0) w grze kółko i krzy

yk (tic-tac-toe).

Gracz MAX u

ywa algorytmu przeszukiwania drzewa

do wyznaczenia nast

pnego ruchu.

Strategie optymalne

Znale

źć

strategi

warunkow

dla gracza MAX przy zało

eniu,

e MIN jest przeciwnikiem nieomylnym.

Znaj

c drzewo gry strategi

optymaln

na wyznaczy

na podstawie warto

ci minimax dla ka

dego w

zła.

6.2. Definicja gry

Zało

enie - obaj gracze graj

optymalnie.

Nale

y wybra

ruch do w

zła który ma najwi

ksz

warto

ść

minimax:

© F.A. Dul 2007

Odpowiada to uzyskaniu najkorzystniejszego wyniku przy
najlepszej grze.

minimax:

MINIMAX-VALUE(n) =

UTILITY(n)

If n is a terminal

max

∈

successors(n)

MINIMAX-VALUE(s)

If n is a max node

min

∈

successors(n)

MINIMAX-VALUE(s)

If n is a min node

Algorytm MINIMAX

6.2. Definicja gry

Wybór minimax

Zasada algorytmu minimax dla dwóch graczy MAX i MIN

© F.A. Dul 2007

Algorytm minimax maksymalizuje wi

c najgorszy wynik gracza

MAX.

…za

MAX – posuni

cia odpowiadaj

ce warto

ciom

najwi

kszym.

Algorytm MINIMAX

6.2. Definicja gry

function MINIMAX-DECISION(state) returns an action

inputs: state, current state in game
v

←

MAX-VALUE(state)

return the action in SUCCESSORS(state) with value v

function MAX-VALUE(state) returns a utility value

if TERMINAL-TEST(state) then return UTILITY(state)
v

←

∞

© F.A. Dul 2007

function MIN-VALUE(state) returns a utility value

if TERMINAL-TEST(state) then return UTILITY(state)
v

← ∞

for a,s in SUCCESSORS(state) do

←

MIN(v,MAX-VALUE(s))

return v

←

∞

for a,s in SUCCESSORS(state) do

←

MAX(v,MIN-VALUE(s))

return v

Własno

ci algorytmu MINIMAX

6.2. Definicja gry

• Zupełno

ść

Tak, je

eli drzewo jest sko

czone.

• Czas

O(b

)

• Pami

ęć

O(bm) (poszukiwanie w gł

• Optymalno

ść

Tak (przeciwko graj

cemu optymalnie

przeciwnikowi)

Dla typowej partii szachów: b ~ 35, m ~ 100 co oznacza,

© F.A. Dul 2007

Dla typowej partii szachów: b ~ 35, m ~ 100 co oznacza,

e rozwi

zanie

cisłe jest zupełnie nieosi

galne.

Najwi

ksz

wad

algorytmu MINIMAX jest wykładniczy wzrost

czasu wyznaczania rozwi

zania ze wzrostem liczby ruchów.

Rozwi

zaniem problemu jest zastosowanie algorytmów

obcinania gał

zi drzewa poszukiwa

Idea: odrzcanie (przycinanie) tych gał

zi drzewa poszukiwa

które s

nieperspektywiczne.

∞

]

Zakres mo

liwych warto

6.3. Algorytm przycinania

αααα

–

ββββ

© F.A. Dul 2007

∞

, +

∞

]

Idea: odrzcanie (przycinanie) tych gał

zi drzewa poszukiwa

które s

nieperspektywiczne.

[3,+

∞

]

Ten w

zeł jest

gorszy dla MAX

6.3. Algorytm przycinania

αααα

–

ββββ

© F.A. Dul 2007

∞

,2]

[3,3]

Idea: odrzcanie (przycinanie) tych gał

zi drzewa poszukiwa

które s

nieperspektywiczne.

∞

,14]

∞

,2]

[3,14]

[3,3]

≥≥≥≥

≤≤≤≤

6.3. Algorytm przycinania

αααα

–

ββββ

© F.A. Dul 2007

∞

,14]

∞

,2]

[3,3]

≤≤≤≤

Idea: odrzcanie (przycinanie) tych gał

zi drzewa poszukiwa

które s

nieperspektywiczne.

∞

,5]

∞

,2]

[3,5]

[3,3]

≥≥≥≥

≤≤≤≤

6.3. Algorytm przycinania

αααα

–

ββββ

© F.A. Dul 2007

∞

,5]

∞

,2]

[3,3]

≤≤≤≤

Idea: odrzcanie (przycinanie) tych gał

zi drzewa poszukiwa

które s

nieperspektywiczne.

[2,2]

∞

,2]

[3,3]

6.3. Algorytm przycinania

αααα

–

ββββ

© F.A. Dul 2007

[2,2]

∞

,2]

[3,3]

Idea: odrzcanie (przycinanie) tych gał

zi drzewa poszukiwa

które s

nieperspektywiczne.

[2,2]

∞

,2]

[3,3]

6.3. Algorytm przycinania

αααα

–

ββββ

© F.A. Dul 2007

[2,2]

∞

,2]

[3,3]

Zasada ogólna przycinania

αααα

ββββ

• Rozwa

my w

zeł v le

Ŝą

gdzie

na drzewie.

• Je

eli gracz MAX mo

dokona

lepszego wyboru

w w

ęź

le rodzica lub

gdziekolwiek wy

ej (

αααα

)

zeł v nigdy nie bi

dzie

6.3. Algorytm przycinania

αααα

–

ββββ

© F.A. Dul 2007

zeł v nigdy nie bi

dzie

osi

gni

ty.

• Gał

ąź

z w

złem v mo

przyci

ta.

Dlaczego algorytm nosi nazw

„przycinanie

αααα

ββββ

” ?

• Niech

αααα

dzie najlepsz

(najwi

ksz

) warto

gał

zi gracza MAX.

• Je

eli v jest gorsze ni

αααα

gracz MAX ominie gał

ąź

na której znajduje si

– Mo

na przyci

ąć

gał

ąź

6.3. Algorytm przycinania

αααα

–

ββββ

© F.A. Dul 2007

– Mo

na przyci

ąć

gał

ąź

•

ββββ

definiuje si

podobnie

dla gracza MIN.

Algorytm przycinania

αααα

ββββ

function ALPHA-BETA-SEARCH(state) returns an action

inputs: state, current state in game
v

←

MAX-VALUE(state, -

∞

, +

∞

)

return the action in SUCCESSORS(state) with value v

function MAX-VALUE(state,

) returns a utility value

if TERMINAL-TEST(state) then return UTILITY(state)
v

←

∞

for a,s in SUCCESSORS(state) do

←

MAX( v, MIN-VALUE(s,

) )

≥

6.3. Algorytm przycinania

αααα

–

ββββ

© F.A. Dul 2007

←

MAX( v, MIN-VALUE(s,

) )

if v

≥

then return v

←

MAX(

,v)

return v

function MIN-VALUE(state,

) returns a utility value

if TERMINAL-TEST(state) then return UTILITY(state)
v

←

∞

for a,s in SUCCESSORS(state) do

←

MIN( v, MAX-VALUE(s,

) )

if v

≤

then return v

←

MIN(

,v)

return v

Własno

ci algorytmu przycinania

αααα

ββββ

• Przycinanie nie wpływa na ko

cowy wynik gry.

• Przycina

na całe gał

zie (poddrzewa).

• Wła

ciwe uporz

dkowanie (kolejno

ść

) ruchów

zwi

ksza efektywno

ść

przycinania.

• Czas oblicze

przy idealnym uporz

dkowaniu ruchów

~O(b

m/2

). Pozwala to podwoi

gł

boko

ść

poszukiwa

6.3. Algorytm przycinania

αααα

–

ββββ

© F.A. Dul 2007

6.4. Gry z niepełn

informacj

Algorytmy MINMAX i przycinania

wymagaj

zbyt wielu

oszacowa

warto

ci na gał

ziach, co zaj

łoby za du

o czasu

w grach rzeczywistych.

Poprawa efektywno

ci algorytmów gier (Shannon, 1950)

• Wprowadzenie ustalonej gł

boko

ci poszukiwa

tak, aby

nie przekroczy

limitu czasu ustalonego w danej grze;

• Zast

pienie TERMINAL-TEST przez CUTOFF-TEST;

© F.A. Dul 2007

• Zast

pienie TERMINAL-TEST przez CUTOFF-TEST;

• Zastosowanie heurystycznej funkcji EVAL zamiast funkcji

yteczno

ci w przycinaniu

if TERMINAL-TEST(state) then return UTILITY(state

)

if CUTOFF-TEST(state,depth) then return EVAL(state)

Funkcja heurystyczna EVAL

Idea: oszacowanie przewidywanego wyniku gry pocz

wszy

od aktualnego stanu.

Efektywno

ść

gry zale

y od jako

ci funkcji EVAL:

• funkcja EVAL powinna porz

dkowa

zły ko

ce gr

w taki sam sposób jak funkcja UTILITY,

• obliczenia nie mog

trwa

zbyt długo,

• dla stanów nieko

cowych funkcja EVAL powinna by

6.4. Gry z niepełn

informacj

© F.A. Dul 2007

• dla stanów nieko

cowych funkcja EVAL powinna by

silnie skorelowana z aktualn

szans

wygranej.

W szachach EVAL jest zazwyczaj

liniow

sum

starsze

stwa

figur

Eval(s) = w

(s) + w

(s) + … + w

(s)

Np. w

= 9 dla

(s) = (liczba białych królowych) – (liczba czarnych królowych)

Addytywno

ść

funkcji EVAL zakłada niezale

ść

sytuacji

szachowych.

Efekt wyj

cia poza horyzont

Poszukiwania o ustalonej
gł

boko

ci nie zauwa

Ŝą

liwej

zmiany pionka na królow

6.4. Gry z niepełn

informacj

Funkcja EVAL w postaci kombinacji liniowej sytuacji jest
jednak u

yteczna tylko dla stanów zmieniaj

cych si

umiarkowanie.

© F.A. Dul 2007

Jak to działa w praktyce?

Załó

my,

e na jeden ruch mamy 100 sekund, a mo

emy

sprawdza

złów/s.

emy zatem sprawdza

złów na jeden ruch.

= 10

, b=35

m = 4 posuni

cia naprzód

Analiza mniej ni

czterech posuni

ęć

naprzód cechuje gracza

beznadziejnego!

6.4. Gry z niepełn

informacj

© F.A. Dul 2007

beznadziejnego!

• 4 ruchy - nowicjusz,
• 8 ruchów - mistrz, komputer PC,
• 12 ruchów - arcymistrz Kasparow, komputer Deep Blue.

6.5. Gry z losowo

W wielu grach wyst

puj

elementy losowe, odzwierciedlaj

nieprzewidywalno

ść

rzeczywisto

ci.

Gra Trik-Trak (Backgammon) zawiera losowo

ść

w postaci

rzutów kostk

0 1 2 3 4 5 6 7 8 9 10 11 12

© F.A. Dul 2007

liwe ruchy: (5-10,5-11), (5-11,19-24),(5-10,10-16)

oraz (5-11,11-16)

25 24 23 22 21 20 19 18 17 16 15 14 13

6.5. Gry z losowo

Do analizy gier losowych nie wystarcza drzewo dla ruchów
MAX – MIN.
Nale

y je uzupełni

złami losowymi

(chance nodes).

W w

złach losowych wyboru gał

zi dokonuje si

podstawie prawdopodobie

stw poszczególnych mo

liwo

ci.

6.5. Gry z losowo

Algorytmy M

INMAX

dla gier losowych wykorzystuje warto

ść

oczekiwan

obliczan

wzgl

dem wszystkich mo

liwych

zdarze

XPECTIMINIMAX(n) =

TILITY(n)

If n is a terminal

Uogólnienie algorytmu M

INMAX

dla gier losowych w postaci

algorytmu E

XPECTIMINMAX

TILITY(n)

If n is a terminal

max

∈

successors(n)

XPECTIMINIMAX(s)

If n is a MAX node

min

∈

successors(n)

XPECTIMINIMAX(s)

If n is a MIN node

∑

∈

successors(n)

(s)

XPECTIMINIMAX(s) If n is a CHANCE node

6.5. Gry z losowo

Przykład działania algorytmu E

XPECTIMINMAX

dla gry Trik-Trak.

0 1 2 3 4 5 6 7 8 9 10 11 12

liwe ruchy: (5-10,5-11), (5-11,19-24),(5-10,10-16)

oraz (5-11,11-16)

25 24 23 22 21 20 19 18 17 16 15 14 13

Prawdopodobie

stwa par [1,1] , ... , [6,6] wynosz

1/36.

Prawdopodobie

stwa pozostałych rzutów – 1/18.

6.5. Gry z losowo

Przykład działania algorytmu E

XPECTIMINMAX

dla gry Trik-Trak.

0 1 2 3 4 5 6 7 8 9 10 11 12

liwe ruchy: (5-10,5-11), (5-11,19-24),(5-10,10-16)

oraz (5-11,11-16)

25 24 23 22 21 20 19 18 17 16 15 14 13

Prawdopodobie

stwa par [1,1] , ... , [6,6] wynosz

1/36.

Prawdopodobie

stwa pozostałych rzutów – 1/18.

Obliczenie warto

ci oczekiwanej pozwala wybra

gał

ąź

poszukiwa

Karty − gry losowe z niepełn

informacj

Gry w karty s

interesuj

ce, gdy

wyst

puj

w nich zarówno

losowo

ść

jak i niepewno

ci informacji:

• pocz

tkowy rozkład kart jest losowy,

• gracze nie znaj

rozkładu kart przeciwników.

6.5. Gry z losowo

Losowo

ść

wyst

puje tylko na pocz

tku gry.

Poniewa

brak jest pełnej informacji o rozkładzie kart,

to mo

na wykorzystywa

tylko t

informacj

, która jest

dost

pna w danej chwili.

to mo

na wykorzystywa

tylko t

informacj

, która jest

dost

pna w danej chwili.

Do analizy gier w karty mo

na u

algorytmu MINIMAX.

Idea

: obliczy

warto

ci MINIMAX dla ka

dego ruchu

w ka

dym rozdaniu i wybra

ruchy z najwi

kszymi

warto

ciami oczekiwanymi.

Program GIB do gry w bryd

a działa nast

puj

co:

• generuje sto rozda

zgodnych z licytacj

• wybiera te ruchy, które wygraj

cej lew.

•

Szachy

W roku 1997 komputer Deep Blue pokonał arcymistrza

wiata Garego Kasparowa w sze

ciu partiach.

6.6. Osi

gni

cia programów AI dla gier

DeepBlue analizował sze

ść

milionów pozycji w ci

sekundy u

ywaj

c bardzo wyszukanego szacowania oraz

pewnych metod nieujawnionych, co umo

liwiło przedłu

anie

cie

ek poszukiwa

nawet do 40 ruchów do przodu.

•

Warcaby

W roku 1994 program Chinook zako

czył czterdziestoletnie

panowanie geniusza warcabów, wielokrotnego mistrza

wiata, dr Mariona Tinsleya.

6.6. Osi

gni

cia programów AI dla gier

Chinook u

ywał w tym celu bazy danych zawieraj

cej

wst

pnie obliczone ko

cówki gry opisuj

ce 444,000,000,000

pozycje dla o

miu lub mniejszej liczby pionków.

•

Othello (Reversi)

Mistrzowie odrzucaj

z komputerami, gdy

one zbyt

dobre. Program Logistello wygrał mistrzostwa

wiata w roku

1997 wynikiem 6:0.

•

Mistrzowie odrzucaj

z komputerami, gdy

one

za słabe. W tej grze b > 361 wi

c wi

kszo

ść

programów

ywa baz wiedzy które sugeruj

liwe ruchy.

Najlepsze programy: Goemate i Go4++, osi

gaj

zaledwie

6.6. Osi

gni

cia programów AI dla gier

Najlepsze programy: Goemate i Go4++, osi

gaj

zaledwie

poziom słabych amatorów.

•

Bryd

Program Bridge Baron™ wygrał po raz pierwszy mistrzostwa

wiata w roku 1997, a ogółem - pi

ciokrotnie.

Program GIB wygrał mistrzostwa

wiata w roku 2000.

•

Trik-Trak (Backgammon)

Program TD-G

AMMON

uwa

any jest za jednego z trzech

najlepszych graczy na

wiecie.

Podsumowanie

• Gry s

przyjemne (ale czasami niebezpieczne...)

• W grach dwóch graczy o sumie zerowej z pełn

informacj

algorytm M

INIMAX

pozwala wyznaczy

ruchy optymalne.

• Niemo

ść

analizy całego drzewa zmusza do u

ycia

funkcji szacuj

cych u

yteczno

ci stanów w grze.

• Gry ilustruj

wiele wa

nych kwestii dotycz

cych AI:

• gra perfekcyjna jest nieosi

galna, konieczna jest

• gra perfekcyjna jest nieosi

galna, konieczna jest

aproksymacja;

• niepewno

ść

wymaga u

ycia metod statystycznych.

• Gry dorównuj

mistrzom w wielu przypadkach:

szachach, warcabach, Othello, Trik-Traku i innych.

• Uwa

a si

e gry s

tym dla sztucznej inteligencji,

czym wy

cigi Grand Prix Formuły I s

dla rozwoju

automobilizmu.

Podsumowanie

tpliwo

ść

Wprawdzie programy AI s

w stanie pokona

nawet

arcymistrzów, ale musz

one korzysta

z heurystyk

wymy

lonych przez człowieka.

Czy zatem mo

na uwa

e s

to rzeczywi

cie byty

cechuj

ce si

sztuczn

inteligencj