Alfa-beta algoritem

Alfa-beta algoritem

Avtor: Katja Bizjak

Učni cilji: Preučiti, po kakšnem algoritmu igra računalnik z uporabnikom igra kot so: šah, štiri v vrsto, dama, križci-krožci,...

UVOD

IGRA

Za razumevanje algoritma alfa-beta moramo najprej poznati minmax algoritem, še prej pa moramo vedeti naslednje: igramo igro med dvema igralcema.

Obravnavamo igro s popolno informacijo, kar pomeni, da vsak igralec v vsakem trenutku natančno pozna vse poteze nasprotnega igralca.

Take igre so:

- šah,

- dama,

- križci-krožci,

- štiri v vrsto,

- itn.

Vsakemu stanju igre priredimo neko vrednost,ki je izračunana z ocenitveno funkcijo.

En igralec je poimenovan kot MAX igralec, drugi pa kot MIN igralec. To pa zato, ker hoče MAX igralec dvigniti vrednost ocenitvene funkcije, MIN pa jo znižati.

Torej algoritma alfa-beta in minmax sta potrebna zato, da igralec, bodisi je to računalnik ali pa človek, izračuna, kaj se mu v igri izplača odigrati.

(http://www2.nauk.si/files/691/šah.jpg)
IGRA ŠAH

Pridobljeno 25.1.2014 na spletni strani: šah

DREVO IGRE

Igro predstavimo z iskalnim oziroma pregledovalnim drevesom. V angleščini se uporablja izraz search tree. V drevesu pregledujemo najboljše možne poteze za posameznega igralca.

Tako drevo prikazuje potek igre in vse možne poteze.

Celotno drevo je pri nekaterih igrah preveliko,zato preiskujemo le del drevesa. To potrjujejo naslednji podatki:

Število možnih potez:

- križci in krožci: 103 (deska 3 × 3)

- štiri v vrsto: 1013 (deska 4 × 4)

- šah: 1047 (deska 8 × 8)

Glede na drevo igre ločimo dva tipa iger:

- Igre, pri katerih lahko narišemo celotno drevo.

Listi, torej končna vozlišča so v drevesu ovrednoteni z vrednostjo igre. Dober primer take igre je igra KRIŽCI-KROŽCI.

- Igre, kjer je celotno drevo ogromno, zato pregledujemo igro po delih. Primeri takih iger so: šah, štiri v vrsto, …

Taka drevesa iger pregledujemo samo do določene globine. Listi so ocenjeni z ocenitveno funkcijo.

(http://www2.nauk.si/files/691/štiri.jpg)

Pridobljeno 25.1.2014 na spletni strani: Štiri v vrsto

GRAFIČEN PRIKAZ DREVESA IGRE

(http://www2.nauk.si/files/691/drevopravo_0.png)
DREVO IGRE

- koren drevesa kaže trenutni položaj v igri;

- vozlišča (na sliki krogci) prikazujejo naslednje položaje, med seboj so povezana s povezavami;

- nivoji drevesa so položaji, v katerih je na potezi eden od igralcev;

- listi predstavljajo konec pregledovanja.

Ocenitvena funkcija predstavlja najpomembnejši del implementacije računalniškega igralca, saj z njeno pomočjo ovrednostimo vozliščca, kar pomeni, da položajem dodelimo vrednosti. Težavnost igre je odvisna od ocenitvene funkcije. Če je le-ta dobra, bo računalniški program težko premagati.

KAKO SESTAVIMO DREVO IGRE

V nadaljevanju si bomo ogledali, kako sestavimo drevo igre.

Imejmo primer igre KRIŽCI-KROŽCI.

Trenutno stanje v igri:

(http://www2.nauk.si/files/691/k1_2.jpg)

V nadaljevanju bom polja na igralni površini poimenovala z številkami in črkam.

Primer: polje v prvi vrsti na sredini - 1B.

Na vrsti je igralec, ki je na igralni površini označen z krožcem. On bo prvi na potezi, zato bo na nivoju, kjer je zapisan koren drevesa. Ta igralec je poimenovan kot igralec MAKS.

(http://www2.nauk.si/files/691/k2_0.jpg)

KAKO SESTAVIMO DREVO IGRE

Preglejmo njegove možne poteze v trenutnem stanju igre.

Igralec lahko nariše krožec na tri polja, torej ima tri možne poteze.

Te prikažemo z povezavami do vozlišča naslednjega nivoja.

(http://www2.nauk.si/files/691/k3_0.jpg)


Krožec lahko nariše na naslednja polja:

- 1A

- 2B

- 3B

Od njega bodo odvisne poteze nasprotnega igralca oziroma potek same igre. Ne glede na to, katero potezo bo izbral se igra v tem stanju ne more končati, saj krožec nima možnosti za zmago.

Sedaj je na vrsti igralec z križcem. Ta igralec je poimenovan kot igralec MIN.

KAKO SESTAVIMO DREVO IGRE

Ker bo igralec MAKS odigral eno potezo in s tem zapolnil en kvadratek na igralni površini, bo imel igralec MIN na izbiro dve potezi.

(http://www2.nauk.si/files/691/k4_0.jpg)

Ko igralec MIN odigra svojo potezo, na igralni površini ostane prazno še eno polje. To polje bo zapolnil igralec MAKS s svojo zadnjo potezo, če seveda v prejšnji potezi ne bo zmagal igralec MIN.

Poglejmo si možne strategije igre.

KAKO SESTAVIMO DREVO IGRE

Igralec MAKS nariše krožec na polje 1A.

(http://www2.nauk.si/files/691/a1_0.jpg)

Možne poteze igralca MIN:

- polje 2B

Igra se konča, saj MIN ni zmagal, MAKS pa v naslednji potezi tudi ne more zmagati. Torej je rezultat igre neodločeno.

- polje 3B

Igra se ne konča, saj MIN ni zmagal, lahko pa MAKS v naslednji potezi.

(http://www2.nauk.si/files/691/s1_0.jpg)

KAKO SESTAVIMO DREVO IGRE

Igralec MAKS nariše krožec na polje 2B.

(http://www2.nauk.si/files/691/a2_0.jpg)

Možne poteze igralca MIN:

- polje 1A

Igra se konča, saj MIN ni zmagal, MAKS pa v naslednji potezi tudi ne more zmagati. Torej je rezultat igre neodločeno.

- polje 3B

Igra se ne konča, saj MIN ni zmagal, lahko pa MAKS v naslednji potezi.

(http://www2.nauk.si/files/691/s2_0.jpg)

KAKO SESTAVIMO DREVO IGRE

Igralec MAKS nariše krožec na polje 3B.

(http://www2.nauk.si/files/691/a3_0.jpg)

Možne poteze igralca MIN:

- polje 1A

Igra se konča, saj MIN ni zmagal, MAKS pa v naslednji potezi tudi ne more zmagati. Torej je rezultat igre neodločeno.

- polje 2B

Zaključek je isti kot pri zgornjem primeru.

(http://www2.nauk.si/files/691/s3_0.jpg)

KAKO SESTAVIMO DREVO IGRE

Drevo igre dopolnimo še s potezami igralca MIN.

(http://www2.nauk.si/files/691/kon_0.jpg)

KAKO SESTAVIMO DREVO IGRE

Ker ima igra KRIŽCI-KROŽCI le tri možnosti za zaključek igre za posazmeznega igralca (zmaga,poraz,neodločen izdi), spada med igre, ki imajo enostavno ocenjevanje posameznih potez.

Ocenimo jih lahko:

- ZMAGA: 1

- PORAZ: -1

- NEODLOČEN IZID: 0

Drevo z ocenami:

(http://www2.nauk.si/files/691/kon1.jpg)

Za boljše razumevanje sem nad vozlišči zapisala izbrana polja na igralni površini za določeno potezo.

MINMAX ALGORITEM

MINIMAX algoritem je algoritem, ki pregleda celotno pregledovalno drevo igre, posledično tudi vse možne poteze v drevesu.

Algoritem deluje po naslednjem principu:

- na nivoju MAX izbere vozlišče z največjo vrednostjo;

- na nivoju MIN izbere vozlišče z najmanjšo vrednostjo.

(http://www2.nauk.si/files/691/minmax.png)
Drevo pregledani z MINMAX algoritmom

MINMAX ALGORITEM

Algoritem za vhodne parametre dobi:

- igralca na potezi: MIN ali MAX

- globino drevesa

- koren, ki predstavlja trenutni položaj v igri

Rezultat algoritma sta:

- ocena, ki predstavlja vrednost drevesa

- poteza, ki predstavlja najboljšo naslednjo potezo

PSEVDOKODA ALGORITMA MINMAX

function minimaks(koren,globina,igralec)
    if koren je zadnji koren or globina == 0 then
        return (hevristično vrednost koren,NIL)
    end if
    if igralec = MAX then
        ocena = -∞
    else
        ocena = ∞
    end if
    poteza = NIL
    poteze = možne poteze igralca igralec v položaju koren
    foreach poteza in poteze
        podkoren = izvedi potezo poteza v položaju koren
        (o,p) = minimaks(podkoren,-igralec,globina-1)
        if(igralec = MAX and o > ocena)or(igralec = MIN and o < ocena) then
            ocena = o
            poteza = p
        end if
    end foreach
  return(ocena,poteza)
end function

Pridobljeno 25.1.2014 na spletni strani: VERK Razdelek: DATOTEKE: VS_Verk_Marjan_1985.pdf (10,84 MB)

DREVO IGRE KRIŽCI-KROŽCI

Primer: igra križci-krožci

(http://www2.nauk.si/files/691/kržcikrožci_0.jpg)
Drevo pri igri KRIŽCI-KROŽCI

Pridobljeno 25.1.2014 na spletni strani: KRIŽCI-KROŽCI

GRAFIČNI PRIKAZ ALGORITMA MINMAX

S klikom na spodnji gumb si lahko ogledate film, v kateri je grafično predstavljen algoritem minmax na primerjalnem drevesu neke igre.

Algoritem se nahaja na naslednji spletni strani: berkeley

MINMAX algoritem

MINMAX algoritem

Zapri

ALFA-BETA ALGORITEM

ALFA-BETA algoritem ali alfa-beta rezanje je izboljšava algoritma minmax. Pri pregledovanju drevesa se izogne obravnavi nekaterih poddreves oziroma vozlišč, ne da bi to vplivalo na končni rezultat igre/poteze.

Izboljšava se najbolj pozna v časovni zahtevnosti algoritmov.

Je rekurzivni algoritem – od listov do korena.

V algortimu vodimo dve spremenljivki: α in β

α – najboljša vrednost doslej za igralca MAX; na začetku ima vrednost -∞;

β – najboljša vrednost doslej za igralca MIN; na začetku ima vrednost ∞;

Potek algoritma:

- iščemo vrednost korena – začetne pozicije;

- preiskujemo v globino;

- v vozliščih MAX zavržemo vrednosti manjše od α;

- v vozliščih MIN zavržemo vrednosti večje od β.

ALFA-BETA ALGORITEM

Algoritem za vhodne parametre dobi:

- igralca na potezi: MIN ali MAX

- globino drevesa

- koren, ki predstavlja trenutni položaj v igri

- α (spodnja meja ocene)

- β (zgornja meja ocene)

Rezultat algoritma sta:

- ocena, ki predstavlja vrednost drevesa

- poteza, ki predstavlja najboljšo naslednjo potezo

PSEVDOKODA ALGORITMA ALFA-BETA

function alfabeta(koren,globina,α,β,igralec)
    if globina= 0 or koren je zadnji koren then
        return (hevristično vrednost koren,NIL)
    end if
    if igralec = MAX then
        ocena = -∞
    else
        ocena = ∞
    end if
    poteza = NIL
    poteze = možne poteze igralca igralec v položaju koren
    foreach pot in poteze
        podkoren = izvedi potezo pot v položaju koren
        (o,m) = alfabeta(podkoren,globina-1,α,β,-igralec)
        if(igralec = MAX and o > ocena) then
            ocena = o
            poteza = pot
            if ocena > α then
                α = ocena
            end if
        else if(igralec = MIN and o < ocena) then
            ocena = o
            poteza = pot
            if ocena < β then
                β = ocena
            end if
        end if
    end if
    if α >= β then
        return (ocena,poteza)
    end if

  end foreach
  return(ocena,poteza)
end function

Pridobljeno 25.1.2014 na spletni strani: VERK Razdelek: DATOTEKE: VS_Verk_Marjan_1985.pdf (10,84 MB)

GRAFIČNI PRIKAZ ALGORITMA ALFA-BETA

S klikom na spodnji gumb si lahko ogledat film, v kateri je grafično predstavljen alfa-beta algoritem na primerjalnem drevesu neke igre.

Algoritem se nahaja na naslednji spletni strani: berkeley

Alfa-beta algoritem

Alfa-beta algoritem

Zapri

ČASOVNA ZAHTEVNOST

ČASOVNA ZAHTEVNOST

- primerjava minimax in alfa-beta;

- odvisna od vrstnega reda vozlišč v drevesu;

- če ne posameznih vejah drevesa ne moremo odrezati, alfa-beta ni hitrejši kot minimax;

- v nasprotnem primeru je mnogo bolj hitrejši;

- ovrednotimo listov

Globina d je oddaljenost vozlišča od začetnega vozlišča, merjena v številu povezav med njima.

- Vejitveni faktor b je število povezav, ki vodijo iz nekega vozlišča, in je enako številu njegovih naslednikov.

KVIZ 1. vprašanje

Katera dva algoritma smo spoznali v prosojnicah? Izberi vse pravilne trditve!

Preveri

Pravilno!

Naprej

Poskusi še enkrat!

Ponovi

KVIZ 2.vprašanje

Poveži algoritma na desni strani s trditvami na levi strani!

Pregleda celotno drevo.
Pregleda le del drevesa.
Potrebuje spremenljivki alfa in beta.
Je osnovni algoritem za pregledovanje drevesa igre.
minmax algoritem
alfa-beta algoritem
alfa-beta algoritem
minmax algoritem

Preveri

Odlično,rešitev je pravilna!

Naprej

Oglej si prosojnice še enkrat!

Naprej

KVIZ 3.vprašanje

Ta algoritem lahko uporabimo pri igranju vseh iger.
Algoritma uporabljamo pri igrah s popolno informacijo.
Drevo igre je iskalno dvojiško drevo.
Alfabeta algoritem je izboljšava algoritma minmax.
Napačno.
Pravilno.
Napačno.
Pravilno.

Preveri

Vse vezave so pravilne!

Naprej

Nekaj ni v redu! Poskusi še enkrat.

Ponovi

KVIZ 4.vprašanje

Kateri algoritem je hitrejši?

minmax algoritem
alfa-beta algoritem

Pravilno!

Naprej

Narobe!

Ponovi

VIRI IN LITERATURA

- Viri, ki so navedeni na prosojnicah

- berkeley

- Tramte

- diplome:

- PROGRAM ZA IGRANJE IGRE ARIMAA,Marjan Verk, 2011

- NADGRADNJA IGRE OTHELLO Z ALGORITMI UMETNE INTELIGENCE, Edo Osmič, 2010

0%
0%