Algoritmus minimaxu
- hra dvou hráčů s úplnou informací
- bílý a černý se pravidelně střídají na tahu
- cíl algoritmu: pro aktuální pozici zvolit nejvýhodnější tah
- strom hry:
kořen = aktuální pozice
počet synů = počet možných tahů
liché hladiny – na tahu je bílý, sudé – na tahu je černý
list = konec hry, některý z hráčů vyhrál (příp. remíza)
„Malé“ hry (piškvorky na hodně omezené ploše, odebírání zápalek)
 lze postavit celý strom hry, listy ohodnotit podle výsledku hry
(1 = vyhrál bílý, -1 = vyhrál černý, příp. 0 = remíza).
Z hodnot listů se algoritmem minimaxu postupně zdola určí hodnota
všech ostatních uzlů, až se získá hodnota kořene (= nejlepší
výsledek, který si může začínající hráč vynutit).
(c) Pavel Töpfer, 2014
Programování I - 10
1
Algoritmus minimaxu:
- hodnota uzlu, kde je na tahu bílý = maximum z hodnot jeho synů
(bílý si vybere ten tah, který je pro něj nejlepší)
- hodnota uzlu, kde je na tahu černý = minimum z hodnot jeho synů
(také černý si vybere ten tah, který je zase pro něj nejlepší)
Strom hry se ohodnocuje zdola od listů po vrstvách, v jednotlivých
vrstvách stromu se počítají střídavě minima a maxima z hodnot synů,
dokud se nezíská hodnota kořene.
Pokud je v kořeni na tahu bílý a kořen bude mí hodnotu 1, může si bílý
vynutit vítězství. Pokud získá kořen hodnotu 0, může si začínající bílý
vynutit aspoň remízu. Bude-li mít kořen hodnotu –1, bílý si vítězství
vynutit nemůže (což neznamená, že nemůže vyhrát – ale jedině za
cenu chyby černého).
Zvolený tah: ten, který vede z kořene do toho uzlu, kde je ohodnocení
stejné jako v kořeni.
(c) Pavel Töpfer, 2014
Programování I - 10
2
1
0
1
1
1
0
-1
(c) Pavel Töpfer, 2014
-1
1
1
1
1
Programování I - 10
0
-1
0
3
Programová realizace
- strom hry je rozsáhlý, není vhodné (nebo ani nelze) vygenerovat ho
naráz celý, uložit do paměti a pak zdola procházet
- algoritmus je realizován prohledáváním (tzn. zároveň i vytvářením)
stromu hry do hloubky, vždy při návratu z podstromu se přepočítá
hodnota uzlu, do něhož se vracíme
Minimax – na jednotlivých hladinách stromu hry se hodnoty uzlu
počítají střídavě jako minimum a maximum z hodnot synů (musíme
vědět, kdo je na tahu).
Negamax (jiná realizace téhož algoritmu) – hodnota každého uzlu
se počítá jako maximum z hodnot synů, před předáním výsledné
hodnoty z uzlu nahoru se změní její znaménko.
min(a,b) = -max(-a,-b)
(c) Pavel Töpfer, 2014
Programování I - 10
4
„Velké“ hry (šachy)
 lze postavit jenom část stromu (zvolený počet hladin),
listy ohodnotit podle statické ohodnocovací funkce
(ocenit materiál každého hráče, příp. vhodné bonusy za pozici):
kladná hodnota = pozice výhodnější pro bílého
(čím vyšší hodnota, tím výhodnější pozice)
záporná hodnota = pozice výhodnější pro černého
(čím vyšší absolutní hodnota, tím výhodnější pozice)
příp. 0 = vyrovnaná pozice
Dále algoritmus minimaxu stejně jako v předchozím případě.
Vylepšení ohodnocení: pokud by se stala listem „živá“ pozice (tah do
ní vedoucí zásadně mění pozici na hracím plánu), rozvíjí se zde
lokálně strom hry dále do hloubky.
(c) Pavel Töpfer, 2014
Programování I - 10
5
Zrychlení výpočtu – ořezávání stromu hry
- ztrátové: po několika málo vrstvách provést statické ohodnocení
pozic a část nejhorších pozic odmítnout (tedy dále nerozvíjet),
podrobněji do větší hloubky analyzovat jen nadějnější pozice
 kaskádové vyhodnocování
- bezztrátové: alfa-beta-prořezávání
5
5
3
neprohledává se
3
(c) Pavel Töpfer, 2014
Programování I - 10
6
-analogické prořezávání se provádí při jednom průchodu stromem
hry ve všech vrstvách stromu, pro bílého i pro černého
- pokud hráč v každé pozici zkouší přednostně ty tahy, které jsou
pro něj výhodnější, alfa-beta-prořezávání je výrazně účinnější
(prořeže se více větví, prochází se mnohem menší část stromu)
 uspořádat možné pokračovací tahy v každé pozici podle statické
ohodnocovací funkce nebo podle nějaké heuristiky
(c) Pavel Töpfer, 2014
Programování I - 10
7
5
5
8
3
5
4
9
3
4
NEPROHLEDÁVÁ SE
(c) Pavel Töpfer, 2014
Programování I - 10
8
Nepřímá rekurze
volání
nebo např.
ABA
ABCDA
Pořadí deklarací pro případ A  B  C  D  A :
procedure A (PA:
forward;
procedure D (PD:
begin …; A(X);
procedure C (PC:
begin …; D(X);
procedure B (PB:
begin …; C(X);
procedure A (PA:
begin …; B(X);
(c) Pavel Töpfer, 2014
real);
real);
… end;
real);
… end;
real);
… end;
real);
… end;
Programování I - 10
9
Jiné řešení pro případ A  B  C  D  A :
procedure A (PA: real); forward;
procedure B (PB: real); forward;
procedure C (PC: real); forward;
procedure D (PD: real); forward;
{zbytečně mnoho forward, ale je to pohodlné a
spolehlivé, následují deklarace všech procedur v
libovolném pořadí:}
procedure A (PA: real);
begin …; B(X); … end;
procedure B (PB: real);
begin …; C(X); … end;
procedure C (PC: real);
begin …; D(X); … end;
procedure D (PD: real);
begin …; A(X); … end;
(c) Pavel Töpfer, 2014
Programování I - 10
10
Příklad: vyhodnocení aritmetického výrazu
Zjednodušující předpoklady:
- výraz se vejde do proměnné typu string (má max. 254 znaků)
- obsahuje pouze celočíselné konstanty, binární operátory +, -, *, /
(ve významu div) a kulaté závorky
- neobsahuje žádné oddělovací mezery
- výraz je syntakticky správný
Postup vyhodnocování vychází z rekurzivní definice syntaxe
aritmetického výrazu:
Výraz = Člen [  Člen  Člen … ]
Člen = Faktor [ */ Faktor */ Faktor … ]
Faktor = Číslo | ( Výraz )
Tato definice v sobě již zahrnuje i priority operátorů při
vyhodnocování výrazu.
(c) Pavel Töpfer, 2014
Programování I - 10
11
Řešení:
tři procedury ve vztahu nepřímé rekurze podle definice výrazu
program AritmetVyraz;
var S: string;
function Vyraz (var S: string): integer;
forward;
function Faktor (var S: string): integer;
…
function Clen (var S: string): integer;
…
function Vyraz (var S: string): integer;
…
begin
write(‘Vyhodnocovaný výraz:’);
readln(S); S:=S+’$’; {kvůli ukončení}
writeln(‘Hodnota výrazu:’, Vyraz(S))
end.
(c) Pavel Töpfer, 2014
Programování I - 10
12
Halda (heap)
- datová struktura pro uložení datových záznamů podle svých klíčů
- binární strom
- zcela zaplněné hladiny až do předposlední, poslední hladina
zaplněná souvisle zleva
- uspořádání hodnot (klíčů) ve všech uzlech: otec < syn
(důsledek: v kořeni uložena nejmenší hodnota)
Použití
pokud s uloženými záznamy potřebujeme provádět operace:
- určení minima (záznamu s nejmenším klíčem)
- přidání nového prvku (datového záznamu)
- odebrání minima (záznamu s nejmenším klíčem)
 haldové operace
Efektivita operací
- určení minima: konstantní časová složitost
- přidání a odebrání prvku: logaritmická časová složitost O(log N)
počet kroků = výška stromu
(c) Pavel Töpfer, 2014
Programování I - 10
13
Operace
Přidání prvku:
- nový uzel přidat do haldy na poslední hladinu co nejvíce vlevo
- do nového uzlu vložit přidávanou hodnotu
- novou hodnotu postupně zaměňovat vždy s hodnotou uloženou v
jejím otci, dokud je třeba (tzn. dokud je otec větší)
Odebrání minima:
- odebrat minimum z kořenu haldy
- do kořenu vložit hodnotu z posledního uzlu haldy (uzel v poslední
hladině co nejvíce vpravo), tento uzel zrušit
- přesunutou hodnotu postupně zaměňovat vždy s hodnotou
uloženou v jejím synovi, dokud je třeba (tzn. dokud je syn menší,
mají-li menší hodnotu oba synové, tak zaměnit s menším z obou
synů)
(c) Pavel Töpfer, 2014
Programování I - 10
14
Realizace haldy v poli
- jednorozměrné pole ukládaných záznamů, indexované od 1
- obsah haldy je v poli uložen po vrstvách vždy zleva doprava
(tedy kořen haldy má index 1)
- uzel s indexem i má syny uložené v poli na indexech 2i, 2i+1
(tedy uzel s indexem i má otce uloženého v poli na indexu i div 2)
type Halda = record
Data: array[1..Max] of integer;
{pro jednoduchost halda čísel}
Pocet: 0..Max
end;
(c) Pavel Töpfer, 2014
Programování I - 10
15
procedure Pridej (var H: Halda; X: integer);
{Přidání hodnoty X do haldy H}
var j,p,d: integer;
Pokracovat: boolean;
begin
with H do
if Pocet = Max then
Error
else
begin
Pocet := Pocet+1;
Data[Pocet] := X;
j := Pocet;
Pokracovat := j > 1;
(c) Pavel Töpfer, 2014
Programování I - 10
16
while Pokracovat do
begin
p := j div 2;
if Data[j] < Data[p] then
begin
d := Data[j];
Data[j] := Data[p];
Data[p] := d;
j := p;
Pokracovat := j > 1
end
else
Pokracovat := false
end
end
end; {Pridej}
(c) Pavel Töpfer, 2014
Programování I - 10
17
procedure ZrusMin (var H: Halda);
{Vypuštění minimální hodnoty z haldy H}
var j,n,d: integer;
Pokracovat: boolean;
begin
with H do
if Pocet = 0 then
Error
else
begin
Data[1] := Data[Pocet];
Pocet := Pocet-1;
j := 1;
Pokracovat := 2 <= Pocet;
(c) Pavel Töpfer, 2014
Programování I - 10
18
while Pokracovat do
begin
n := 2*j;
if n < Pocet then
if Data[n+1] < Data[n] then n:=n+1;
if Data[j] > Data[n] then
begin
d := Data[j];
Data[j] := Data[n];
Data[n] := d;
j := n;
Pokracovat := 2*j <= Pocet
end
else
Pokracovat := false
end
end
end; {ZrusMin}
(c) Pavel Töpfer, 2014
Programování I - 10
19
Konstrukce haldy v lineárním čase
- výchozí rozložení dat představuje úplný binární strom hloubky d
(bez uspořádání hodnot do haldy)
- nejprve postavíme „haldy“ z podstromů, jejichž kořeny mají
hloubku d-1, potom pro d-2, … atd., až do kořene celé haldy
- stavění hald se provádí záměnami hodnot od kořene k listům
(výměna s menším z obou synů)
Časová složitost
hloubka
0
1
…
j
…
d-1
(c) Pavel Töpfer, 2014
počet uzlů
20
21
…
2j
…
2d-1
Programování I - 10
max. počet výměn
pro každý z nich
d
d-1
…
d-j
…
1
20
Pozorování: Při tomto postupu konstrukce haldy má hodně uzlů
malý maximální počet výměn a jen málo z nich může absolvovat
výměn hodně  celková časová složitost O(N).
Celkem se provede výměn (viz tabulka):
d 1
d 1
d 1
j


2
d

j

d
2

j
.
2


 
j
j 0
j 0

j 0
 d  2.2
 d. 2 1 
d
j
d

   ON 
2  O 2
d
… viz dva důkazy matematickou indukcí dále
(c) Pavel Töpfer, 2014
Programování I - 10
21
d 1
j
d
2

2
1

Důkaz matematickou indukcí č.1:
j 0
1. pro d=1 zjevně platí
2. nechť platí pro všechna d < D, dokazujeme platnost pro D > 1 :
D 1
D2
j 0
j 0


j
j
D 1
D 1
D 1
D 1
D
2

2

2

2

1

2

2
.
2

1

2
1
 

podle indukčního předpokladu
(c) Pavel Töpfer, 2014
Programování I - 10
qed
22
Důkaz matematickou indukcí č.2:
d 1

j . 2 j  d  2 . 2d  2
j 0
1. pro d=1 zjevně platí
2. nechť platí pro všechna d < D, dokazujeme platnost pro D > 1 :
D 1
D2


j
D 1
D 1
D 1






j
.
2

j
.
2

D

1
.
2

D

3
.
2

2

D

1
.
2



j 0
j
j 0

podle indukčního předpokladu
 D . 2D1  3. 2D1  D . 2D1  2D1  2  2 . D . 2D1  4 . 2D1  2 
 D . 2D  2 . 2D  2  D  2. 2 D  2
(c) Pavel Töpfer, 2014
Programování I - 10
qed
23
HeapSort (třídění haldou, haldové třídění)
- z prvků postavit haldu (N x přidání prvku do haldy)
 časová složitost O(N.log N)
nebo zdola v lineárním čase O(N)
- haldu postupně rozebrat (N x odebrat minimum z haldy)
 časová složitost O(N.log N)
 tedy celková časová složitost O(N.log N) i v nejhorším případě
- třídí „na místě“ (tzn. nepotřebuje další datovou strukturu velikosti N):
prvky uložené v poli postupně řadí do haldy, přičemž haldu staví v
levé části téhož pole
pak rozebírá postupně haldu a vyřazované prvky ukládá postupně do
pravé části téhož pole, kde se uvolňuje místo po zkracující se haldě
(c) Pavel Töpfer, 2014
Programování I - 10
24
Příkaz CASE
- výběr z více variant podle hodnoty výrazu
case Výraz of
Hodnota1: Příkaz1;
Hodnota2: Příkaz2;
…
HodnotaN: PříkazN
end
Výraz uvedený za case může být libovolného celočíselného typu,
hodnoty musí být konstanty téhož typu.
Sémantika:
if Výraz = Hodnota1 then Příkaz1
else if Výraz = Hodnota2 then Příkaz2
…
else if Výraz = HodnotaN then PříkazN
Pokud se tedy Výraz nerovná žádné z uvedených hodnot, nevykoná
se žádný z příkazů.
(c) Pavel Töpfer, 2014
Programování I - 10
25
Rozšíření příkazu case
Možnost doplnit implicitní variantu  pokud se Výraz nerovná
žádné z uvedených hodnot, vykoná se Příkaz z větve else.
case Výraz of
Hodnota1: Příkaz1;
Hodnota2: Příkaz2;
…
HodnotaN: PříkazN;
else Příkaz
end
Přípustné tvary hodnot uváděných u variant:
- konstanta
20:
- několik konstant oddělených čárkami
20, 22, 24:
- interval hodnot
30..40:
- kombinace výše uvedených možností
1, 3..7, 9..15, 40:
Hodnoty u variant nemusí být navzájem disjunktní  vykoná se
příkaz z první větve, u které dojde ke shodě hodnoty s výrazem.
(c) Pavel Töpfer, 2014
Programování I - 10
26
Příklad: case N of
{N je proměnná typu integer}
1: writeln(N);
{jedna akce}
2: begin inc(A); dec(B) end; {více akcí – složený příkaz}
0..9:
{jiné jednociferné číslo – nedělej nic}
else writeln(‘CHYBA’)
{víceciferné číslo je chyba}
end.
Příklad praktického použití:
Program potřebuje reagovat podle toho, jaká klávesa byla stisknuta na
klávesnici – rozhoduje se podle hodnoty proměnné obsahující hodnotu
stisknuté klávesy (každá klávesa má nějaký celočíselný kód), je
mnoho možností, pro některé klávesy bude stejná reakce.
case StisknutaKlavesa of
SipkaNahoru:
SipkaDolu:
SipkaVlevo, SipkaVpravo:
Cifra0..Cifra9:
else
end
(c) Pavel Töpfer, 2014
akce pro šipku nahoru;
akce pro šipku dolů;
akce pro jinou šipku
akce pro dekadickou číslici;
akce pro všechny ostatní klávesy
Programování I - 10
27
Download

null